Analysis of the binary complexity of asymptotically fast algorithms for linear system solving

ABSTRACT

Two significant developments can be distinguished in the theory of algebraic algorithm design. One is that of fast algorithms in terms of counting the arithmetic operations, such as the asymptotically fast matrix multiplication procedures and related linear algebra algorithms or the asymptotically fast polynomial multiplication procedures and related polynomial manipulation algorithms. The other is to observe the actual bit complexity when such algorithms are performed for concrete fields, in particular the rational numbers. It was discovered in the mid-1960s that for rational polynomial GCD operations the classical algorithm can lead to exponential coefficient size growth. The beautiful theory of subresultants by Collins [7] and Brown & Traub [5] explains, however, that the size growth is not inherent but a consequence of over-simplified rational arithmetic. Similar phenomena were observed for the Gaussian elimination procedure [2], [9].

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Bareiss, E. H., "Sylvester's identity and multistep integers preserving Gaussian elimination," <i>Math. Comp.</i>, vol. 22, pp. 565--578, 1968.
• 3: Brent, R. P., Gustavson, F. G., and Yun, D. Y. Y., "Fast solution of Toeplitz systems of equations and computation of Pad&eacute; approximants," <i>J. Algorithms</i>, vol. 1, pp. 259--295, 1980.
• 4: W. S. Brown, On Euclid's Algorithm and the Computation of Polynomial Greatest Common Divisors, Journal of the ACM (JACM), v.18 n.4, p.478-504, Oct. 1971 [doi>10.1145/321662.321664]
• 5: W. S. Brown , J. F. Traub, On Euclid's Algorithm and the Theory of Subresultants, Journal of the ACM (JACM), v.18 n.4, p.505-514, Oct. 1971 [doi>10.1145/321662.321665]
• 6: Bunch, J. R. and Hopcroft, J. E., "Triangular factorization and inversion by fast matrix multiplication," <i>Math. Comp.</i>, vol. 28, pp. 231--236, 1974.
• 7: George E. Collins, Subresultants and Reduced Polynomial Remainder Sequences, Journal of the ACM (JACM), v.14 n.1, p.128-142, Jan. 1967 [doi>10.1145/321371.321381]
• 8: D. Coppersmith , S. Winograd, Matrix multiplication via arithmetic progressions, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.1-6, January 1987, New York, New York, United States [doi>10.1145/28395.28396]
• 9: Edmonds, J., "Systems of distinct representatives and linear algebra," <i>J. Research National Bureau Standards B</i>, vol. 71B, pp. 241--245, 1967.
• 10: Gantmacher, F. R., <i>The Theory of Matrices, Vol. 1</i>, Chelsea Publ. Co., New York, N. Y., 1960.
• 11: Leighton, F. T., "Gaussian elimination over the rationals," Unpublished Manuscript, Applied Math. Dept., MIT, 1980.
• 12: Michael T. McClellan, The Exact Solution of Systems of Linear Equations with Polynomial Coefficients, Journal of the ACM (JACM), v.20 n.4, p.563-588, Oct. 1973 [doi>10.1145/321784.321787]
• 13: 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]
• 14: A. Schönhage, Probabilistic computation of integer polynomial GCDs, Journal of Algorithms, v.9 n.3, p.365-371, September 1988 [doi>10.1016/0196-6774(88)90027-2]
• 15: Strassen, V., "Gaussian elimination is not optimal," <i>Numerische Mathematik</i>, vol. 13, pp. 354--356, 1969.
• 16: Waerden, B. L. van der, <i>Modern Algebra</i>, F. Ungar Publ. Co., New York, 1953.

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Matrix inversion

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

General Terms:
Algorithms, Design, Theory