On theoretical and practical acceleration of randomized computation of the determinant of an integer matrix

V. Ya. Pan

Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part IX, Tome 316 (2004), pp. 163-187

Résumé

We reexamine the Wiedemann–Coppersmith–Kaltofen–Villard algorithm for randomized computation of the determinant of integer matrices and substantially simplify and accelerate its bottleneck stage of computing the minimum generating matrix polynomial, to make the algorithm practically promising while keeping it asymptotically fast.

Bibliographie

[1] J. Abbott, M. Bronstein, T. Mulders, “Fast Deterministic Computations of the Determinants of Dense Matrices”, Proceeding of International Symposium on Symbolic and Algebraic Computation (ISSAC'99), ACM Press, New York, 1999, 197–204 | MR

[2] M. Agrawal, N. Kayal, N. Saxena, http://www.cse.iitk.ac.in/news

[3] D. J. Bernstein, Fast Multiplication and Its Applications, Preprint, 2003 ; http://cr.yp.to/papers.html | MR

[4] R. R. Bitmead, B. D. O. Anderson, “Asymptotically Fast Solution of Toeplitz and Related Systems of Linear Equations”, Linear Algebra and Its Applications, 34 (1980), 103–116 | DOI | MR | Zbl

[5] H. Brönnimann, I. Z. Emiris, V. Y. Pan, S. Pion, “Sign Determination in Residue Number Systems”, Theoretical Computer Science, 210:1 (1999), 173–197 | DOI | MR | Zbl

[6] B. Beckermann, G. Labahn, “A Uniform Approach for Fast Computation of Matrix-Type Padé Approximants”, SIAM J. Matrix Anal. Appl., 15:3 (1994), 804–823 | DOI | MR | Zbl

[7] D. Bini, V. Y. Pan, Polynomial and Matrix Computations. V. 1. Fundamental Algorithms, Birkhäuser, Boston, 1994 | MR | Zbl

[8] K. L. Clarkson, “Safe and Efficilent Determinant Evaluation”, Proceedings 33rd Annual Symp. Foundations of Comp. Sci.(FOCS92), IEEE Computer Society Press, Los Alamitos, California, 1992, 387–395 | Zbl

[9] D. Coppersmith, “Solving Homogeneous Linear Equations over $GF(2)$ via block Wiedemann Algorithm”, Math. of Computation, 62:205 (1994), 333–350 | DOI | MR | Zbl

[10] D. Coppersmith, “Rectangular Matrix Multiplication Revisited”, J. Complexity, 13 (1997), 42–49 | DOI | MR | Zbl

[11] L. Chen, W. Eberly, E. Kaltofen, B. D. Saunders, W. J. Turner, G. Villard, “Efficient Matrix Preconditioners for Black Box Linear Algebra”, Linear Algebra and Its Applications, 343–344 (2002), 119–146 | DOI | MR | Zbl

[12] D. Coppersmith, S. Winograd, “Matrix Multplication via Arithmetic Progressions”, J. Symolic Comput., 9:3 (1990), 251–281 | DOI | MR

[13] J. D. Dixon, “Exact Solution of Linear Equations Using $p$-adic Expansions”, Numerische Math., 40 (1982), 137–141 | DOI | MR | Zbl

[14] R. A. DeMillo, R. J. Lipton, “A Probabilistic Remark on Algebraic Program Testing”, Information Process. Letters, 7:4 (1978), 193–195 | DOI | Zbl

[15] W. Eberly, M. Giesbrecht, G. Villard, “On Computing the Determinant and Smith Form of an Integer Matrix”, Proc. 41st Annual Symposium on Foundations of Computer Science (FOCS'2000), IEEE Computer Society Press, Los Alamitos, California, 2000, 675–685 | MR

[16] I. Z. Emiris, V. Y. Pan, Y. Yu, “Modular-Arithmetic for Linear Algebra Computations in the Real Field”, J. of Symblolic Computation, 26 (1998), 71–87 | DOI | MR | Zbl

[17] I. Z. Emiris, V. Y. Pan, “Improved Computation of Determinants and Resultants”, Proc. of the 6th Intern. Workshop on Computer Algebra in Scientific Computing (CACS'03), eds. E. W. Mayr, V. G. Ganzha, E. V. Vorozhtzov, Tech. Univ. München, Germany, 2003, 81–99; Report 2002-019, Ph.D. Program in Computer Science, The Graduate Center, CUNY, 2002

[18] I. Z. Emiris, V. Y. Pan, “Improved Algortihms for Computing Determinants and Resultants”, J. of Complexity, 2004, in press | MR

[19] M. Giesbrecht, “Fast Computation of the Smith Form of a Sparse Integer Matrix”, Computational Complexity, 10 (2001), 41–69 | DOI | MR | Zbl

[20] J. von zur Gathen, J. Gerhard, Modern Computer Algebra, 2nd edition, Cambridge University Press, Cambridge, 2003 | MR

[21] M. Giesbrecht, A. Storjohann, “Computing Rational Forms of Integer Matrices”, J. of Symbolic Computation, 34:3 (2002), 157–172 | DOI | MR | Zbl

[22] E. Kaltofen, “Analysis of Coppersmith's Block Wiedemann Algorithm for the Parallel Solution of Sparse Linear Systems”, Math. of Computation, 64:210 (1995), 777–806 | DOI | MR | Zbl

[23] I. Kaporin, “A Practical Algorithm for Faster Matrix Multiplication”, Numerical Linear Algebra with Applications, 6:8 (1999), 687–700 | 3.0.CO;2-I class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[24] E. Kaltofen, “An Output-sensitive Variant of the Baby Steps/Giant Steps Determinant Algorithm”, Proc. ACM Intern. Symp. on Symbolic and Algebraic Computation (ISSAC'02), ACM Press, New York, 2002, 138–144 | MR | Zbl

[25] E. Kaltofen, Private communication, 2002

[26] I. Kaporin, “The Aggregation and Cancellation Techniques as a Practical Tool for Faster Matrix Multiplication”, Theoretical Computer Science, 315:2–3 (2004), 469–510 | DOI | MR | Zbl

[27] E. Kaltofen, M. S. Krishnamoorthy, B. D. Saunders, “Parallel Algorithms for Matrix Normal Forms”, Linear Algebra and Applications, 136 (1990), 189–208 | DOI | MR | Zbl

[28] E. Kaltofen, V. Y. Pan, “Processor Efficient Parallel Solution of Linear Systems over an Abstract Field”, Proceedings of {\rm3}rd Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA'91), ACM Press, New York, 1991, 180–191

[29] E. Kaltofen, B. D. Saunders, “On Wiedemann's Method for Solving Sparse Linear Systems”, Proceedings of AAECC–5, Lecture Notes in Computer Science, 536, Springer, Berlin, 1991, 29–38 | MR

[30] E. Kaltofen, G. Villard, “On the Complexity of Computing Determinants”, Proc. Fifth Asian Symposium on Computer Mathematics (ASCM 2001), Lecture Notes Series on Computing, 9, eds. Shirayanagi, Kiyoshi and Yokoyama, Kazuhiro, World Scientific, Singapore, 2001, 13–27 | MR | Zbl

[31] E. Kaltofen, G. Villard, “Computing the Sign or the Value of the Determinant of an Integer Matrix, a Complexity Survey”, J. Computational Applied Math., 162:1 (2004), 133–146 | DOI | MR | Zbl

[32] M. Morf, Fast Algorithms for Multivariable Systems, Ph.D. Thesis, Department of Electrical Engineering, Stanford University, Stanford, California, 1974

[33] M. Morf, “Doubling Algorithms for Toeplitz and Related Equations”, Proceedings of IEEE International Conference on ASSP, IEEE Press, Piscataway, New Jersey, 1980, 954–959

[34] M. Monahan, “Maximal Quotient Rational Reconstruction: an Almost Optimal Algorithm for Rational Reconstruction”, Proc. International Symp. on Algebraic and Symbolic Computation (ISSAC'04), ACM Press, New York, 2004, 243–249 | MR

[35] R. T. Moenck, J. H. Carter, “Approximate Algorithms to Derive Exact Solutions to Systems of Linear Equations”, Proceedings of EUROSAM, Lecture Notes in Computer Science, 72, Springer, Berlin, 1979, 63–73 | MR

[36] M. Newman, Integral Matrices, Academic Press, New York, 1972 | MR | Zbl

[37] V. Y. Pan, “Complexity of Parallel Matrix Computations”, Theoretical Computer Science, 54 (1987), 65–85 | DOI | MR | Zbl

[38] V. Y. Pan, “Computing the Determinant and the Characteristic Polynomials of a Matrix via Solving Linear Systems of Equations”, Information Processing Letters, 28 (1988), 71–75 | DOI | MR

[39] V. Y. Pan, Can We Utilize the Cancelation of the Most Significant Digits?, Tech. Report TR-92-061, The International Computer Science Institute, Berkeley, California, 1992

[40] V. Y. Pan, “Univariate Polynomials: Nearly Optimal Algorithms for Numerical Factorization and Rootfinding”, J. of Symbolic Computation, 33:5 (2002), 701–733 ; Proc. International Symposium on Symbolic and Algebraic Computation (ISSAC'01), ACM Press, New York, 2001, 253–266 | DOI | MR | Zbl

[41] V. Y. Pan, Structured Matrices and Polynomials: Unified Superfast Algorithms, Birkhäuser/Springer, Boston–New York, 2001 | MR

[42] V. Y. Pan, “Randomized Acceleration of Fundamental Matrix Computations”, Proc. Symp. on Theoretical Aspects of Computer Science (STACS), Lect. Notes in Comput. Sci., 2285, Springer, Heldelberg, Germany, 2002, 215–226 | MR | Zbl

[43] V. Y. Pan, “Can We Optimize Toeplitz/Hankel Computations?”, Proc. of the 5th Intern. Workshop on Computer Algebra in Scientific Computing (CASC'03), eds. E. W. Mayr, V. G. Ganzha, E. V. Vorozhtzov, Tech. Univ. München, Germany, 2002, 253–264

[44] V. Y. Pan, Nearly Optimal Toeplitz/Hankel Computations. Technical Reports 2002-001 and 2202-017, Ph.D. Program in Computer Science, The Graduate Center, CUNY, New York, 2002 | MR

[45] V. Y. Pan, Superfast Algorithms for Singular Integer Toeplitz/Hankel-like Matrices, Technical Reports 2002-002 and 2003-004. Ph.D. Program in Computer Science, The Graduate Center, CUNY, New York, 2002–2003

[46] V. Y. Pan, Superfast Divide-and-Conquer Algorithms for Integer Toeplitz-like Matrices, Technical Report 2004-015. Ph.D. Program in Computer Science, The Graduate Center, CUNY, New York, 2004

[47] V. Y. Pan, B. Murphy, R. E. Rosholt, X. Wang, Toeplitz and Hankel Meet Hensel and Newton Nearly Optimal Algorithms and Their Practical Acceleration with Saturated Initialization, Technical Report 2004-013. Ph.D. Program in Computer Science, The Graduate Center, CUNY, New York, 2004

[48] V. Y. Pan, X. Wang, “Acceleration of Euclidean Algorithm and Extensions”, Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC'02), ed. Teo Mora, ACM Press, New York, 2002, 207–213 | MR | Zbl

[49] V. Y. Pan, X. Wang, “On Rational Number Reconstruction and Approximation”, SIAM J. on Computing, 33:2 (2004), 502–503 | DOI | MR | Zbl

[50] V. Y. Pan, Y. Yu, “Certification of Numerical Computation of the Sign of the Determinant of a Matrix”, Algorithmica, 30 (2001), 708–729 | DOI | MR

[51] A. Storjohann, “High Order Lifting and Integrality Certification”, J. of Symbolic Computation, 36:3–4 (2003), 613–648 ; Proc. of Intern. Symposium on Symbolic and Algebraic Computation, ACM Press, New York, 2002, 246–254 | DOI | MR | Zbl | MR | Zbl

[52] A. Storjohann, The Shifted Number System for Fast Linear Algebra on Integer Matrices, Technical Report TR CS-2004-18, School of Computer Science, University of Waterloo, Canada, April, 2004 | MR

[53] J. Schwartz, “Fast Probabilistic Algorithms for Verification of Polynomial Identities”, J. ACM, 27:4 (1980), 701–717 | DOI | MR | Zbl

[54] A. Storjohann, Computing the Frobenius Form of a Sparse Integer Matrix, Preprint

[55] E. Thomé, “Fast Computation of Linear Generators for Matrix Sequences and Application to the Block Wiedemann Algorithm”, Proc. 2001 Internat. Symp. Symbolic Algebraic Comput (ISSAC 2001), ACM Press, New York, 2001, 323–331 | MR

[56] D. Wiedemann, “Solving Sparse Linear Equations over Finite Fields”, IEEE Trans. Inf. Theory IT, 32 (1986), 54–62 | DOI | MR | Zbl

[57] X. Wang, V. Y. Pan, “Acceleration of Euclidean Algorithm and Rational Number Reconstruction”, SIAM J. on Computing, 32:2 (2003), 548–556 | DOI | MR | Zbl

[58] R. Zippel, “Probaliistic Algorithms for Sparse Polynomials”, Proc. EUROSAM'79, Lect. Notes Comp. Science, Springer, Berlin, 1979, 216–226 | MR