Acceleration of Euclidean algorithm and extensions

ABSTRACT

We accelerate the extended Euclidean algorithm for integers, the rational number reconstruction, and consequently, the stage of the recovery of the solution of a nonsingular integer system of linear equations via Hensel's lifting. The acceleration is by the order of magnitude and yields nearly optimal randomized algorithms. In the highly important case of Toeplitz, Hankel, and Toeplitz/Hankel-like linear systems, the accleration is potentially practical.

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: R. P. Brent, F. G. Gustavson, D. Y. Y. Yun. Fast Solution of Toeplitz Systems of Equations and Computation of Padé Approximations. Journal of Algorithms, 1:259-295, 1980.
• 4: Dario Bini , Victor Y. Pan, Polynomial and matrix computations (vol. 1): fundamental algorithms, Birkhauser Verlag, Basel, Switzerland, 1994
• 5: G. Cooperman, S. Feisel, J. von zur Gathen, G. Havas. GCD of Many Integers. Computing and Combinatorics, Lecture Notes in Computer Science, 1627:310-317, Springer, Berlin, 1999.
• 6: David G. Cantor , Erich Kaltofen, On fast multiplication of polynomials over arbitrary algebras, Acta Informatica, v.28 n.7, p.693-701, Oct. 1991 [doi>10.1007/BF01178683]
• 7: J. D. Dixon. Exact Solution of Linear Equations Using p-adic Expansions. Numerische Math., 40:137-141, 1982.
• 8: 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
• 9: Joachim von zur Gathen , Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, NY, 1999
• 10: 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]
• 11: 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]
• 12: Robert T. Moenck , John H. Carter, Approximate algorithms to derive exact solutions to systems of linear equations, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.65-73, June 01, 1979
• 13: T. Mulders, A. Storjohann. Certified Dense Linear System Solving, preprint, 2001.
• 14: V. Pan, Complexity of parallel matrix computations, Theoretical Computer Science, v.54 n.1, p.65-85, 1987 [doi>10.1016/0304-3975(87)90019-3]
• 15: Victor Pan, Computing the determinant and the characteristic polynomial of a matrix via solving linear systems of equations, Information Processing Letters, v.28 n.2, p.71-75, June 24, 1988 [doi>10.1016/0020-0190(88)90166-4]
• 16: V. Y. Pan. Parametrization of Newton's Iteration for Computations with Structured Matrices and Applications. Computers & Mathematics (with Applications), 24(3):61-75, 1992.
• 17: Victor Y. Pan, Parallel Complexity of Computations with General and Toeplitz-Like Matrices Filled with Integers and Extensions, SIAM Journal on Computing, v.30 n.4, p.1080-1125, 2000 [doi>10.1137/S0097539797349959]
• 18: Victor Y. Pan, Structured matrices and polynomials: unified superfast algorithms, Springer-Verlag New York, Inc., New York, NY, 2001
• 19: Victor Y. Pan, Randomized Acceleration of Fundamental Matrix Computations, Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science, p.215-226, March 14-16, 2002
• 20: V. Y. Pan. Can We Optimize Computations with Structured Matrices? preprint, 2002.
• 21: A. Schönhage. Schnelle Berechnung von Kettenbruchentwicklungen. Acta Informatica, 1:139-144, 1971.
• 22: A. Schönhage, V. Strassen. Schnelle Multiplikation grosse Zahlen. Computing, 7:281-292, 1971.

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Linear systems (direct and iterative methods)
      G.1.7 Ordinary Differential Equations
          Subjects: Differential-algebraic equations

General Terms:
Algorithms, Documentation

Keywords:
p-adic lifting, Smith invariant factors, Toeplitz and Hankel matrices, bit operation complexity, extended euclidean algorithm, linear system of equations, randomized algorithms, rational number reconstruction