High-order lifting

ABSTRACT

The well-known technique of adic-lifting for linear-system solution is studied. Some new methods are developed and applied to get algorithms for the following problems over the ring of univariate polynomials with coefficients from a field: rational system-solving, integrality certification and determinant/Smith-form computation. All algorithms are Las Vegas probabilistic.

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: J. D. Dixon. Exact solution of linear equations using p-adic expansions. Numer. Math., 40:137-141, 1982.
• 3: 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
• 4: E. Kaltofen, M. S. Krishnamoorthy, and B. D. Saunders. Parallel algorithms for matrix normal forms. Linear Algebra and its Applications, 136:189-208, 1990.
• 5: E. Kaltofen and G. Villard. Computing the sign or the value of the determinant of an integer matrix, a complexity survey. 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.
• 6: R. T. Moenck and J. H. Carter. Approximate algorithms to derive exact solutions to systems of linear equations., pages 65-72. Springer-Verlag, Berlin-Heidelberg-New York, 1979.
• 7: Thom Mulders , Arne Storjohann, Diophantine linear system solving, Proceedings of the 1999 international symposium on Symbolic and algebraic computation, p.181-188, July 28-31, 1999, Vancouver, British Columbia, Canada [doi>10.1145/309831.309905]
• 8: T. Mulders and A. Storjohann. Certified diophantine dense linear system solving. Technical Report 355, Departement Informatik, ETH Zürich, Dec. 2000.
• 9: T. Mulders and A. Storjohann. On lattice reduction for polynomial matrices. Technical Report 356, Departement Informatik, ETH Zürich, Dec. 2000.
• 10: Thom Mulders , Arne Storjohann, Rational solutions of singular linear systems, Proceedings of the 2000 international symposium on Symbolic and algebraic computation, p.242-249, July 2000, St. Andrews, Scotland [doi>10.1145/345542.345644]
• 11: 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]
• 12: A. Storjohann. Algorithms for Matrix Canonical Forms. PhD thesis, ETH -- Swiss Federal Institute of Technology, 2000.
• 13: Arne Storjohann , George Labahn, Preconditioning of rectangular polynomial matrices for efficient Hermite normal form computation, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.119-125, July 10-12, 1995, Montreal, Quebec, Canada [doi>10.1145/220346.220362]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Linear systems (direct and iterative methods)

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms
  I.3 COMPUTER GRAPHICS
      I.3.6 Methodology and Techniques
          Subjects: Standards

General Terms:
Algorithms, Documentation, Standardization