An output-sensitive variant of the baby steps/giant steps determinant algorithm

ABSTRACT

In the first half of 2000, two new algorithms were discovered for the efficient computation of the determinant of a (dense) matrix with integer entries. Suppose that the dimension of the matrix is n x n and that the maximum bit length of all entries is b. The algorithm by [10] requires (n^3.5b^2.5)¹+o⁽¹⁾ fixed precision, that is, bit operations. Here and in the following we use the exponent "+o(1)" to capture missing polylogarithmic factors O((log n)^C1(log b)^C2), where C1, C2 are constants ("soft-O"). As it has turned out an algorithm in [15], which in turn is based on one by [31] and which uses the baby steps/giant steps algorithm design technique, can be adapted to the dense integer matrix determinant problem and then has bit complexity (n^3.5b)^1+o(1) [20, Section 2]. Both algorithms use randomization and the algorithm in [10] is Monte Carlo--always fast and probably correct--and the one in [20] is Las Vegas--always correct and probably fast. Both algorithms can be speeded by asymptotically fast subcubic matrix multiplication algorithms à la Strassen [8, 7, 14]. By blocking [6, 16, 29, 30] the baby steps/giant steps algorithm can be further improved, which yields the currently fastest known algorithms [20, Section 3] of bit complexity (n^3+1/3b)^1+o(1), that without subcubic matrix multiplication and without the FFT-based polynomial "half" GCD procedures à la Knuth [23; 2, Chapter 8], and of bit complexity n^2.698b^1+o(1) with subcubic matrix multiplication and FFT-based polynomial GCD procedures.

REFERENCES

• 1: John Abbott , Manuel Bronstein , Thom Mulders, Fast deterministic computation of determinants of dense matrices, Proceedings of the 1999 international symposium on Symbolic and algebraic computation, p.197-204, July 28-31, 1999, Vancouver, British Columbia, Canada [doi>10.1145/309831.309934]
• 2: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 3: BRENT, R. P., GUSTAVSON, F. G., AND YUN, D. Y. Y. Fast solution of Toeplitz systems of equations and computation of Padé approximants. J. Algorithms 1 (1980), 259-295.
• 4: Hervé Brönnimann , Ioannis Z. Emiris , Victor Y. Pan , Sylvain Pion, Sign determination in residue number systems, Theoretical Computer Science, v.210 n.1, p.173-197, Jan. 6, 1999 [doi>10.1016/S0304-3975(98)00101-7]
• 5: CHEN, L., EBERLY, W., KALTOFEN, E., SAUNDERS, B. D., TURNER, W. J., AND VILLARD, G. Efficient matrix preconditioners for black box linear algebra. Linear Algebra and Applications 343-344 (2002), 119-146. Special issue on Structured and Infinite Systems of Linear Equations, edited by P. Dewilde, V. Olshevsky and A. H. Sayed.
• 6: Don Coppersmith, Solving homogeneous linear equations over GF(2) via block Wiedemann algorithm, Mathematics of Computation, v.62 n.205, p.333-350, Jan. 1994 [doi>10.2307/2153413]
• 7: Don Coppersmith, Rectangular matrix multiplication revisited, Journal of Complexity, v.13 n.1, p.42-49, March 1997 [doi>10.1006/jcom.1997.0438]
• 8: Don Coppersmith , Shmuel Winograd, Matrix multiplication via arithmetic progressions, Journal of Symbolic Computation, v.9 n.3, p.251-280, March 1990 [doi>10.1016/S0747-7171(08)80013-2]
• 9: CRANDALL, R., AND KLIVINGTON, J. Fast matrix algebra on Apple G4. http://developer.apple.com/hardware/ve/pdf/g4matrix.pdf, Mar. 2000.
• 10: W. Eberly , M. Giesbrecht , G. Villard, On computing the determinant and Smith form of an integer matrix, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.675, November 12-14, 2000
• 11: EMIRIS, I. Z. A complete implementation for computing general dimensional convex hulls. Int. J. Comput. Geom. Appl. 8, 2 (1998), 223-254.
• 12: Timothy S. Freeman , Gregory M. Imirzian , Erich Kaltofen , Lakshman Yagati, Dagwood: a system for manipulating polynomials given by straight-line programs, ACM Transactions on Mathematical Software (TOMS), v.14 n.3, p.218-240, Sept. 1988 [doi>10.1145/44128.214376]
• 13: HEINDEL, L. E., AND HOROWITZ, E. On decreasing the computing time for modular arithmetic. In Conference Record, IEEE 12th Annual Symp. on Switching and Automata Theory (1971), pp. 126-128.
• 14: Xiaohan Huang , Victor Y. Pan, Fast rectangular matrix multiplications and improving parallel matrix computations, Proceedings of the second international symposium on Parallel symbolic computation, p.11-23, July 20-22, 1997, Maui, Hawaii, United States [doi>10.1145/266670.266679]
• 15: Erich Kaltofen, On computing determinants of matrices without divisions, Papers from the international symposium on Symbolic and algebraic computation, p.342-349, July 27-29, 1992, Berkeley, California, United States [doi>10.1145/143242.143350]
• 16: Erich Kaltofen, Analysis of Coppersmith's block Wiedemann algorithm for the parallel solution of sparse linear systems, Mathematics of Computation, v.64 n.210, p.777-806, April 1995 [doi>10.2307/2153451]
• 17: Erich Kaltofen , Wen-shin Lee , Austin A. Lobo, Early termination in Ben-Or/Tiwari sparse interpolation and a hybrid of Zippel's algorithm, Proceedings of the 2000 international symposium on Symbolic and algebraic computation, p.192-201, July 2000, St. Andrews, Scotland [doi>10.1145/345542.345629]
• 18: Erich Kaltofen , Victor Pan, Processor efficient parallel solution of linear systems over an abstract field, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.180-191, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113396]
• 19: Erich Kaltofen , Barry M. Trager, Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators, Journal of Symbolic Computation, v.9 n.3, p.301-320, March 1990 [doi>10.1016/S0747-7171(08)80015-6]
• 20: KALTOFEN, E., AND VILLARD, G. On the complexity of computing determinants. In Proc. Fifth Asian Symposium on Computer Mathematics (ASCM 2001) (Singapore, 2001), K. Shirayanagi and K. Yokoyama, Eds., vol. 9 of Lecture Notes Series on Computing, World Scientific, pp. 13-27. Invited contribution; extended abstract.
• 21: KALTOFEN, E., AND VILLARD, G. Computing the sign or the value of the determinant of an integer matrix, a complexity survey. J. Computational Applied Math. (2002). Submitted to the special issue on Congrès International Algèbre Linéaire et Arithmétique: Calcul Numérique, Symbolique et Parallèle, held in Rabat, Morocco, May 2001, 17 pages.
• 22: Wen-Shin Lee , Erich Kaltofen, Early termination strategies in sparse interpolation algorithms, 2001
• 23: R. T. Moenck, Fast computation of GCDs, Proceedings of the fifth annual ACM symposium on Theory of computing, p.142-151, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804045]
• 24: PATERSON, M. S., AND STOCKMEYER, L. J. On the number of nonscalar multiplications necessary to evaluate polynomials. SIAM J. Comp. 2 (1973), 60-66.
• 25: ROSSER, J. B., AND SCHOENFELD, L. Approximate formulas of some functions of prime numbers. Illinois J. Math. 6 (1962), 64-94.
• 26: Arne Storjohann, High-order lifting, Proceedings of the 2002 international symposium on Symbolic and algebraic computation, p.246-254, July 07-10, 2002, Lille, France [doi>10.1145/780506.780538]
• 27: Emmanuel Thomé, Fast computation of linear generators for matrix sequences and application to the block Wiedemann algorithm, Proceedings of the 2001 international symposium on Symbolic and algebraic computation, p.323-331, July 2001, London, Ontario, Canada [doi>10.1145/384101.384145]
• 28: TURNER, W. J. A note on determinantal divisors and matrix preconditioners. Paper to be submitted, Oct. 2001.
• 29: G. Villard, Further analysis of Coppersmith's block Wiedemann algorithm for the solution of sparse linear systems (extended abstract), Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.32-39, July 21-23, 1997, Kihei, Maui, Hawaii, United States [doi>10.1145/258726.258742]
• 30: VILLARD, G. A study of Coppersmith's block Wiedemann algorithm using matrix polynomials. Rapport de Recherche 975 IM, Institut d'Informatique et de Mathématiques Appliquées de Grenoble, www.imag.fr, Apr. 1997.
• 31: D H Wiedemann, Solving sparse linear equations over finite fields, IEEE Transactions on Information Theory, v.32 n.1, p.54-62, Jan. 1986 [doi>10.1109/TIT.1986.1057137]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.8 Partial Differential Equations
          Subjects: Iterative solution techniques

General Terms:
Algorithms, Experimentation, Standardization