More Web Proxy on the site http://driver.im/

Article

Solving sparse rational linear systems

Authors:

Mark Giesbrecht,

Arne Storjohann,

Gilles VillardAuthors Info & Claims

ISSAC '06: Proceedings of the 2006 international symposium on Symbolic and algebraic computation

Pages 63 - 70

https://doi.org/10.1145/1145768.1145785

Published: 09 July 2006 Publication History

Abstract

We propose a new algorithm to find a rational solution to a sparse system of linear equations over the integers. This algorithm is based on a p-adic lifting technique combined with the use of block matrices with structured blocks. It achieves a sub-cubic complexity in terms of machine operations subject to a conjecture on the effectiveness of certain sparse projections. A LinBox-based implementation of this algorithm is demonstrated, and emphasizes the practical benefits of this new method over the previous state of the art.

References

[1]

B. Beckermann and G. Labahn. A uniform approach for the fast, reliable computation of matrix-type padé approximants. SIAM J. Matrix Anal. Appl., 15:804--823, 1994.

Digital Library

[2]

D. Cantor and E. Kaltofen. Fast multiplication of polynomials over arbitrary algebras. Acta Informatica, 28:693--701, 1991.

Digital Library

[3]

L. Chen, W. Eberly, E. Kaltofen, B. D. Saunders, W. J. Turner, and G. Villard. Efficient matrix preconditioners for black box linear algebra. Linear Algebra and its Applications, 343--344:119--146, 2002.

[4]

Z. Chen and A. Storjohann. A BLAS based C library for exact linear algebra on integer matrices. In ISSAC'05: Proceedings of the 2005 international symposium on Symbolic and algebraic computation, pages 92--99, New York, NY, USA, 2005. ACM Press.

Digital Library

[5]

D. Coppersmith. Solving homogeneous linear equations over GF{2} via block Wiedemann algorithm. Mathematics of Computation, 62(205):333--350, Jan. 1994.

Digital Library

[6]

J. D. Dixon. Exact solution of linear equations using p-adic expansions. Numerische Mathematik, 40:137--141, 1982.

Digital Library

[7]

J.-G. Dumas, T. Gautier, M. Giesbrecht, P. Giorgi, B. Hovinen, E. Kaltofen, B. D. Saunders, W. J. Turner, and G. Villard. LinBox: A generic library for exact linear algebra. In A. M. Cohen, X.-S. Gao, and N. Takayama, editors, Proceedings of the 2002 International Congress of Mathematical Software, Beijing, China, pages 40--50. World Scientific, Aug. 2002.

[8]

J.-G. Dumas, P. Giorgi, and C. Pernet. FFPACK: Finite field linear algebra package. In Gutierrez {14}, pages 63--74.

Digital Library

[9]

W. Eberly, M. Giesbrecht, and G. Villard. On computing the determinant and Smith form of an integer matrix. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science, page 675. IEEE Computer Society, 2000.

Digital Library

[10]

W. Eberly and E. Kaltofen. On randomized Lanczos algorithms. In W. Küchlin, editor, Proc. 1997 Internat. Symp. Symbolic Algebraic Comput. (ISSAC'97), pages 176--183, New York, N. Y., 1997. ACM Press.

Digital Library

[11]

J. von zur Gathen and J. Gerhard. Modern Computer Algebra. Cambridge University Press, New York, USA, 1999.

Digital Library

[12]

M. Giesbrecht. Efficient parallel solution of sparse systems of linear diophantine equations. In Parallel Symbolic Computation (PASCO'97), pages 1--10, Maui, Hawaii, July 1997.

Digital Library

[13]

P. Giorgi, C.-P. Jeannerod, and G. Villard. On the complexity of polynomial matrix computations. In R. Sendra, editor, Proceedings of the 2003 International Symposium on Symbolic and Algebraic Computation, Philadelphia, Pennsylvania, USA, pages 135--142. ACM Press, New York, Aug. 2003.

Digital Library

[14]

J. Gutierrez, editor. ISSAC'2004. Proceedings of the 2004 International Symposium on Symbolic and Algebraic Computation, Santander, Spain. ACM Press, New York, July 2004.

[15]

G. H. Hardy and E. M. Wright. An Introduction to the Theory of Numbers. Oxford University Press, fifth edition, 1979.

[16]

E. Kaltofen. Analysis of Coppersmith's block Wiedemann algorithm for the parallel solution of sparse linear systems. Mathematics of Computation, 64(210):777--806, Apr. 1995.

Digital Library

[17]

E. Kaltofen and B. D. Saunders. On Wiedemann's method of solving sparse linear systems. In Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (AAECC '91), volume 539 of LNCS, pages 29--38, Oct. 1991.

Digital Library

[18]

G. Labahn, D. K. Chio, and S. Cabay. The inverses of block hankel and block toeplitz matrices. SIAM J. Comput., 19(1):98--123, 1990.

Digital Library

[19]

R. T. Moenck and J. H. Carter. Approximate algorithms to derive exact solutions to systems of linear equations. In Proc. EUROSAM'79, volume 72 of Lecture Notes in Computer Science, pages 65--72, Berlin-Heidelberg-New York, 1979. Springer-Verlag.

Digital Library

[20]

T. Mulders and A. Storjohann. Diophantine linear system solving. In International Symposium on Symbolic and Algebraic Computation (ISSAC 99), pages 181--188, Vancouver, BC, Canada, July 1999.

Digital Library

[21]

T. Mulders and A. Storjohann. Certified dense linear system solving. Journal of Symbolic Computation, 37(4):485--510, 2004.

[22]

B. D. Saunders and Z. Wan. Smith normal form of dense integer matrices, fast algorithms into practice. In Gutierrez {14}.

Digital Library

[23]

A. Storjohann. The shifted number system for fast linear algebra on integer matrices. Journal of Complexity, 21(4):609--650, 2005.

Digital Library

[24]

W. J. Turner. Black Box Linear Algebra with Linbox Library. PhD thesis, North Carolina State University, May 2002.

Digital Library

[25]

G. Villard. A study of Coppersmith's block Wiedemann algorithm using matrix polynomials. Technical Report 975-IM, LMC/IMAG, Apr. 1997.

[26]

P. S. Wang. A p-adic algorithm for univariate partial fractions. In Proceedings of the fourth ACM symposium on Symbolic and algebraic computation, pages 212--217. ACM Press, 1981.

Digital Library

[27]

D. H. Wiedemann. Solving sparse linear equations over finite fields. IEEE Transactions on Information Theory, 32(1):54--62, Jan. 1986.

Digital Library

Cited By

Ghadiri M(2023)On Symmetric Factorizations of Hankel Matrices2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00127(2081-2092)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00127
Ghadiri MPeng RVempala S(2023)The Bit Complexity of Efficient Continuous Optimization2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00125(2059-2070)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00125
Zoubritzky LCoudert F(2022)CrystalNets.jl: Identification of Crystal TopologiesSciPost Chemistry10.21468/SciPostChem.1.2.0051:2Online publication date: 17-Jun-2022
https://doi.org/10.21468/SciPostChem.1.2.005
Show More Cited By

Index Terms

Solving sparse rational linear systems
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
      1. Algebraic algorithms
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Solving Very Sparse Rational Systems of Equations

Efficient methods for solving linear-programming problems in exact precision rely on the solution of sparse systems of linear equations over the rational numbers. We consider a test set of instances arising from exact-precision linear programming and ...
Faster inversion and other black box matrix computations using efficient block projections
ISSAC '07: Proceedings of the 2007 international symposium on Symbolic and algebraic computation

Efficient block projections of non-singular matrices have recently been used by the authors in [10] to obtain an efficient algorithm to find rational solutions for sparse systems of linear equations. In particular a bound ofO^~(n^2.5) machine operations ...
The shifted number system for fast linear algebra on integer matrices
Festschrift for the 70th birthday of Arnold Schönhage

The shifted number system is presented: a method for detecting and avoiding error producing carries during approximate computations with truncated expansions of rational numbers. Using the shifted number system the high-order lifting and integrality ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISSAC '06: Proceedings of the 2006 international symposium on Symbolic and algebraic computation

July 2006

374 pages

ISBN:1595932763

DOI:10.1145/1145768

General Chair:
Barry Trager
IBM T.J. Watson Research Center, USA

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 July 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ISSAC06

Sponsor:

ISSAC06: International Symposium on Symbolic and Algebraic Computation

July 9 - 12, 2006

Genoa, Italy

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

26
Total Citations
View Citations
337
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)3

Reflects downloads up to 31 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ghadiri M(2023)On Symmetric Factorizations of Hankel Matrices2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00127(2081-2092)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00127
Ghadiri MPeng RVempala S(2023)The Bit Complexity of Efficient Continuous Optimization2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00125(2059-2070)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00125
Zoubritzky LCoudert F(2022)CrystalNets.jl: Identification of Crystal TopologiesSciPost Chemistry10.21468/SciPostChem.1.2.0051:2Online publication date: 17-Jun-2022
https://doi.org/10.21468/SciPostChem.1.2.005
Nie ZLeonardi SGupta A(2022)Matrix anti-concentration inequalities with applicationsProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520060(568-581)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3520060
Peng RVempala SMarx D(2021)Solving sparse linear systems faster than matrix multiplicationProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458095(504-521)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458095
Kumaraswamy DVivek S(2021)Cryptanalysis of the Privacy-Preserving Ride-Hailing Service TRACEProgress in Cryptology – INDOCRYPT 202110.1007/978-3-030-92518-5_21(462-484)Online publication date: 9-Dec-2021
https://doi.org/10.1007/978-3-030-92518-5_21
Roychowdhury AParthasarathy S(2017)Adaptive Bayesian sampling with Monte Carlo EMProceedings of the 31st International Conference on Neural Information Processing Systems10.5555/3294771.3294891(1256-1266)Online publication date: 4-Dec-2017
https://dl.acm.org/doi/10.5555/3294771.3294891
Gaubert SQu Z(2017)Checking strict positivity of Kraus maps is NP-hardInformation Processing Letters10.1016/j.ipl.2016.09.008118:C(35-43)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1016/j.ipl.2016.09.008
Brill MConitzer VFreeman RShah NJonker CMarsella SThangarajah JTuyls K(2016)False-Name-Proof Recommendations in Social NetworksProceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems10.5555/2936924.2936974(332-340)Online publication date: 9-May-2016
https://dl.acm.org/doi/10.5555/2936924.2936974
Harrison GJohnson JSaunders B(2016)Probabilistic analysis of Wiedemann's algorithm for minimal polynomial computationJournal of Symbolic Computation10.1016/j.jsc.2015.06.00574:C(55-69)Online publication date: 1-May-2016
https://dl.acm.org/doi/10.1016/j.jsc.2015.06.005
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents