A geometric-numeric algorithm for absolute factorization of multivariate polynomials

ABSTRACT

In this paper, we propose a new semi-numerical algorithmic method for factoring multivariate polynomials absolutely. It is based on algebraic and geometric properties after reduction to the bivariate case in a generic system of coordinates. The method combines 4 tools: zero-sum relations at triplets of points, partial information on monodromy action, Newton interpolation on a structured grid, and a homotopy method. The algorithm relies on a probabilistic approach and uses numerical computations to propose a candidate factorization (with probability almost one) which is later validated.

REFERENCES

• 1: C. Bajaj , J. Canny , R. Garrity , J. Warren, Factoring rational polynomials over the complexes, Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation, p.81-90, July 17-19, 1989, Portland, Oregon, United States [doi>10.1145/74540.74551]
• 2: Chistov, A. L. and Gregoriev D. Y. Subexponential-time solving systems of algebraic equations preprint (1983).
• 3: Robert M. Corless , Mark W. Giesbrecht , Mark van Hoeij , Ilias S. Kotsireas , Stephen M. Watt, Towards factoring bivariate approximate polynomials, Proceedings of the 2001 international symposium on Symbolic and algebraic computation, p.85-92, July 2001, London, Ontario, Canada [doi>10.1145/384101.384114]
• 4: Dominique Duval, Absolute factorization of polynomials: a geometric approach, SIAM Journal on Computing, v.20 n.1, p.1-21, Feb. 1991 [doi>10.1137/0220001]
• 5: André Galligo , Stephen Watt, A numerical absolute primality test for bivariate polynomials, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.217-224, July 21-23, 1997, Kihei, Maui, Hawaii, United States [doi>10.1145/258726.258788]
• 6: André Galligo , David Rupprecht, Semi-numerical determination of irreducible branches of a reduced space curve, Proceedings of the 2001 international symposium on Symbolic and algebraic computation, p.137-142, July 2001, London, Ontario, Canada [doi>10.1145/384101.384121]
• 7: André Galligo , David Rupprecht, Irreducible decomposition of curves, Journal of Symbolic Computation, v.33 n.5, p.661-677, May 2002 [doi>10.1006/jsco.2002.0528]
• 8: Joos Heintz , Malte Sieveking, Absolute Primality of Polynomials is Decidable in Random Polynomial Time in the Number of Variables, Proceedings of the 8th Colloquium on Automata, Languages and Programming, p.16-28, July 13-17, 1981
• 9: Erich Kaltofen, Fast parallel absolute irreducibility testing, Journal of Symbolic Computation, v.1 n.1, p.57-68, March 1985 [doi>10.1016/S0747-7171(85)80029-8]
• 10: Erich Kaltofen, Polynomial Factorization 1987-1991, Proceedings of the 1st Latin American Symposium on Theoretical Informatics, p.294-313, April 06-10, 1992
• 11: Kaltofen E., Effective Hilbert Irreducibility Information and Control, 66, 123-137 (1985).
• 12: Mumford D. Introduction to Algebraic Geometry, Cambridge Mass., Harvard University, 1955.
• 13: PARI-GP http://www.parigp-home.de/
• 14: Ostrowski A. M. Solution of equations and systems of equations, New York, Academic Press, 1960.
• 15: Ragot, J. F. Sur la factorisation absolue des polynomes, PhD Thesis, Univ. Limoges, (1997).
• 16: Ruppecht, D. Semi-numerical absolute factorization of polynomials with integer coefficients To appear in Journal of Symb. Comp. (2001).
• 17: Ruppecht, D. Elements pour un calcul approche et certifie : etude du PGCD et de la factorisation PhD thesis, University of Nice, France, (2000), http://www-math.unice.fr/~rupprech
• 18: Sasaki T. Suzuki M. Kolar M. Sasaki M. Approximate factorization of multivariate polynomials and absolute irreducibility testing. Japan J. Indust. Appl. Math. 8 (1991), no. 3, pp. 357-375.
• 19: Tateaki Sasaki, Approximate multivariate polynomial factorization based on zero-sum relations, Proceedings of the 2001 international symposium on Symbolic and algebraic computation, p.284-291, July 2001, London, Ontario, Canada [doi>10.1145/384101.384139]
• 20: L. F. Shampine , Robert M. Corless, Initial value problems for ODEs in problem solving environments, Journal of Computational and Applied Mathematics, v.125 n.1-2, p.31-40, Dec. 2000 [doi>10.1016/S0377-0427(00)00456-8]
• 21: Sommese A. J. Verschelde J. and Wampler C. W. Using Monodromy to Decompose Solution Sets of Polynomial Systems into Irreducible Components Proc. of a NATO Conference in Eilat Israel, "Application of Algebraic Geometry to Coding Theory, Physics and Computation", pp. 297-315, Kluwer Academic Publishers, (2001).
• 22: Sommese A. J. Verschelde J. and Wampler C. W. Symmetric functions applied to decomposing solution sets of polynomial systems preprint, november 2001.
• 23: Sommese A. J., Verschelde J. and Wampler C. W. Functions Applied to Decomposing Solution Sets of Polynomial Systems, (2001), preprint available from http://www.math.uic.edu/~jan.
• 24: Andrew J. Sommese , Jan Verschelde , Charles W. Wampler, Numerical Decomposition of the Solution Sets of Polynomial Systems into Irreducible Components, SIAM Journal on Numerical Analysis, v.38 n.6, p.2022-2046, 2001 [doi>10.1137/S0036142900372549]
• 25: Joachim von zur Gathen , Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, NY, 1999
• 26: Walker R. J. Algebraic curves, Princeton University Press, 1950. Princeton mathematical series ; vol 13.
• 27: Zippel, R. E. Effective polynomial computation Boston, Kluwer Academic Publishers, Kluwer international series in engineering and computer science vol 241 (1993)

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Numerical 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 polynomials

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.6 Methodology and Techniques
          Subjects: Standards

General Terms:
Algorithms, Measurement