Approximate bivariate factorization: a geometric viewpoint

ABSTRACT

We briefly present and analyze, from a geometric viewpoint, strategies for designing algorithms to factor bivariate approximate polynomials in C[x; y].

Given a composite polynomial, stably square-free, satisfying a genericity hypothesis, we describe the effect of a perturbation on the roots of its discriminant with respect to one variable, and the perturbation of the corresponding monodromy action on a smooth fiber.

A novel geometric approach is presented, based on guided projection in the parameter space and continuation method above randomly chosen loops, to reconstruct from a perturbed polynomial a nearby composite polynomial and its irreducible factors. An algorithm and its ingredients are described.

REFERENCES

• 1: Chanderjit Bajaj , John Canny , Thomas Garrity , Joe Warren, Factoring rational polynomials over the complex numbers, SIAM Journal on Computing, v.22 n.2, p.318-331, April 1993 [doi>10.1137/0222024]
• 2: G. Chèze and A. Galligo. Four lectures on polynomial absolute factorization. In Solving polynomial equations, volume 14 of Algorithms Comput. Math., pages 339--392. Springer, Berlin, 2005.
• 3: G. Chèze and A. Galligo. From an approximate to an exact absolute polynomial factorization. J. Symbolic Comput., 41(6):682--696, 2006.
• 4: G. Chèze and G. Lecerf. Lifting and recombination techniques for absolute factorization. Accepted for publication in Journal of Complexity, 2006.
• 5: 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]
• 6: Robert M. Corless , André Galligo , Ilias S. Kotsireas , Stephen M. Watt, A geometric-numeric algorithm for absolute factorization of multivariate polynomials, Proceedings of the 2002 international symposium on Symbolic and algebraic computation, p.37-45, July 07-10, 2002, Lille, France [doi>10.1145/780506.780512]
• 7: R. M. Corless, P. M. Gianni, B. M. Trager, and S. M. Watt. The Singular Value Decomposition for polynomial systems. pages 195--207, Montréal, Canada, 1995. ACM.
• 8: B. Deconinck and M. van Hoeij. Computing riemann matrices of algebraic curves. PhysicaD, 152:28--46, 2001.
• 9: P. Diaconis and A. Galligo. A probabilistic approach to compute the orbits of a monodromy group of a plane curve. In preparation, 2007.
• 10: A. Dimca. Singularities and topology of hypersurfaces. Universitext. Springer-Verlag, New York, 1992.
• 11: I. Z. Emiris, A. Galligo, and H. Lombardi. Numerical univariate polynomial GCD. volume 32, pages 323--344, 1996.
• 12: I. Z. Emiris, A. Galligo, and H. Lombardi. Certified approximate univariate gcds. J. Pure Applied Algebra, 117-118:229--251, 1997.
• 13: A. Galligo. Real factorization of multivariate polynomials with integer coefficients. Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI), 258(Teor. Predst. Din. Sist. Komb. i Algoritm. Metody. 4):60--70, 355, 1999.
• 14: A. Galligo and M. van Hoeij. Implementation: http://www.math.fsu.edu/~hoeij/files/approxfact.
• 15: A. Galligo and S. M. Watt. A numerical absolute primality test for bivariate polynomials. pages 217--224, Maui, USA, 1997. ACM.
• 16: Shuhong Gao, Factoring multivariate polynomials via partial differential equations, Mathematics of Computation, v.72 n.242, p.801-822, 1 April 2003 [doi>10.1090/S0025-5718-02-01428-X]
• 17: Shuhong Gao , Erich Kaltofen , John May , Zhengfeng Yang , Lihong Zhi, Approximate factorization of multivariate polynomials via differential equations, Proceedings of the 2004 international symposium on Symbolic and algebraic computation, p.167-174, July 04-07, 2004, Santander, Spain [doi>10.1145/1005285.1005311]
• 18: Mark Giesbrecht , George Labahn , Wen-shin Lee, Symbolic-numeric sparse interpolation of multivariate polynomials, Proceedings of the 2006 international symposium on Symbolic and algebraic computation, July 09-12, 2006, Genoa, Italy [doi>10.1145/1145768.1145792]
• 19: M. Giusti , G. Lecerf , B. Salvy , J.-C. Yakoubsohn, On Location and Approximation of Clusters of Zeros: Case of Embedding Dimension One, Foundations of Computational Mathematics, v.7 n.1, p.1-58, February 2007 [doi>10.1007/s10208-004-0159-5]
• 20: Markus A. Hitz , Erich Kaltofen , Y. N. Lakshman, Efficient algorithms for computing the nearest polynomial with a real root and related problems, Proceedings of the 1999 international symposium on Symbolic and algebraic computation, p.205-212, July 28-31, 1999, Vancouver, British Columbia, Canada [doi>10.1145/309831.309937]
• 21: Yuzhen Huang , Wenda Wu , Hans J. Stetter , Lihong Zhi, Pseudofactors of multivariate polynomials, Proceedings of the 2000 international symposium on Symbolic and algebraic computation, p.161-168, July 2000, St. Andrews, Scotland [doi>10.1145/345542.345616]
• 22: E. Kaltofen. Polynomial factorization 1982--1986. In Computers in mathematics (Stanford, CA, 1986), volume 125 of Lecture Notes in Pure and Appl. Math., pages 285--309. Dekker, New York, 1990.
• 23: Erich Kaltofen, Polynomial Factorization 1987-1991, Proceedings of the 1st Latin American Symposium on Theoretical Informatics, p.294-313, April 06-10, 1992
• 24: Erich Kaltofen , Robert M. Corless , David J. Jeffrey, Challenges of symbolic computation: my favorite open problems, Journal of Symbolic Computation, v.29 n.6, p.891-919, June 2000 [doi>10.1006/jsco.2000.0370]
• 25: Erich Kaltofen , John May, On approximate irreducibility of polynomials in several variables, Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.161-168, August 03-06, 2003, Philadelphia, PA, USA [doi>10.1145/860854.860893]
• 26: E. Kaltofen, J. May, Z. Yang, and L. Zhi. Approximate factorization of multivariate polynomials using singular value decomposition. 2006.
• 27: Anton Leykin , Jan Verschelde , Ailing Zhao, Newton's method with deflation for isolated singularities of polynomial systems, Theoretical Computer Science, v.359 n.1, p.111-122, 14 August 2006 [doi>10.1016/j.tcs.2006.02.018]
• 28: T. Ojika. Modified de ation algorithm for the solution of singular problems. I. A system of nonlinear algebraic equations. J. Math. Anal. Appl., 123:199--221, 1987.
• 29: D. Rupprecht. Elements de géométrie algébrique approchée: Etude du pgcd et de la factorisation. PhD thesis, Univ. Nice Sophia Antipolis, 2000.
• 30: 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]
• 31: T. Sasaki, T. Saito, and T. Hilano. Analysis of approximate factorization algorithm. I. Japan J. Indust. Appl. Math., 9(3):351--368, 1992.
• 32: T. Sasaki and M. Sasaki. A unified method for multivariate polynomial factorizations. Japan J. Indust. Appl. Math., 10(1):21--39, 1993.
• 33: T. Sasaki, M. Suzuki, M. Kolář, and M. Sasaki. Approximate factorization of multivariate polynomials and absolute irreducibility testing. Japan J. Indust. Appl. Math., 8(3):357--375, 1991.
• 34: A. Sommese, J. Verschelde, and C. Wampler. Using monodromy to decompose solution sets of polynomial systems into irreducible components. In Application of Algebraic Geometry to Coding Theory, Physics and Computation, pages 297--315. Kluwer Academic Publishers, 2001. Proceedings of a NATO Conference, February 25 - March 1, 2001, Eilat, Israel.
• 35: Andrew J. Sommese , Jan Verschelde , Charles W. Wampler, Symmetric Functions Applied to Decomposing Solution Sets of Polynomial Systems, SIAM Journal on Numerical Analysis, v.40 n.6, p.2026-2046, 2002 [doi>10.1137/S0036142901397101]
• 36: Andrew J. Sommese , Jan Verschelde , Charles W. Wampler, Numerical factorization of multivariate complex polynomials, Theoretical Computer Science, v.315 n.2-3, p.651-669, 6 May 2004 [doi>10.1016/j.tcs.2004.01.011]
• 37: Zhonggang Zeng , Barry H. Dayton, The approximate GCD of inexact polynomials, Proceedings of the 2004 international symposium on Symbolic and algebraic computation, p.320-327, July 04-07, 2004, Santander, Spain [doi>10.1145/1005285.1005331]

INDEX TERMS

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

General Terms:
Algorithms, Theory

Keywords:
algebraic geometry, algorithms, approximate factorization, maple code