Approximate factorization of multivariate polynomials via differential equations

ABSTRACT

The input to our algorithm is a multivariate polynomial, whose complex rational coefficients are considered imprecise with an unknown error that causes f to be irreducible over the complex numbers C. We seek to perturb the coefficients by a small quantitity such that the resulting polynomial factors over C. Ideally, one would like to minimize the perturbation in some selected distance measure, but no efficient algorithm for that is known. We give a numerical multivariate greatest common divisor algorithm and use it on a numerical variant of algorithms by W. M. Ruppert and S. Gao. Our numerical factorizer makes repeated use of singular value decompositions. We demonstrate on a significant body of experimental data that our algorithm is practical and can find factorizable polynomials within a distance that is about the same in relative magnitude as the input error, even when the relative error in the input is substantial (10^-3).

REFERENCES

• 1: Cheze, G., and Galligo, A. From an approximate to an exact absolute polynomial factorization. Paper submitted, 22 pages, 2003.
• 2: 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]
• 3: Robert M. Corless , Patrizia M. Gianni , Barry M. Trager , Stephen M. Watt, The singular value decomposition for polynomial systems, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.195-207, July 10-12, 1995, Montreal, Quebec, Canada [doi>10.1145/220346.220371]
• 4: 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]
• 5: Emiris, I. Z., Galligo, A., and Lombardi, H. Certified approximate univariate GCDs. J. Pure Applied Algebra 117 & 118 (May 1997), 229--251. Special Issue on Algorithms for Algebra.
• 6: 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]
• 7: 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]
• 8: Gelfond, A. O. Transcendental and algebraic numbers. Translated from the 1st Russian ed. by Leo F. Boron. Dover, New York, 1960.
• 9: Patrizia Gianni , Mika Seppälä , Robert Silhol , Barry Trager, Riemann surfaces, plane algebraic curves and their period matrices, Journal of Symbolic Computation, v.26 n.6, p.789-803, Dec. 1998 [doi>10.1006/jsco.1998.0240]
• 10: Giesbrecht, M., Labahn, G., and Lee, W.-s. Symbolic-numeric sparse interpolation of multivariate polynomials (extended abstract). In Proc. Ninth Rhine Workshop on Computer Algebra (RWCA'04), University of Nijmegen, the Netherlands (2004), pp. 127--139. Full paper under preparation.
• 11: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 12: 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]
• 13: 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]
• 14: 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]
• 15: 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]
• 16: Kaltofen, E. The art of symbolic computation, Mar. 2002. Colloquium at the University of Waterloo. Transparencies at http://www.math.ncsu.edu/~kaltofen/bibliography/02/waterloo.pdf.
• 17: 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]
• 18: Erich Kaltofen , Barry M. Trager, Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators, Journal of Symbolic Computation, v.9 n.3, p.301-320, March 1990 [doi>10.1016/S0747-7171(08)80015-6]
• 19: Li, T. Y., and Zeng, Z. A rank-revealing method and its application. Manuscript available at http://www.neiu.edu/~zzeng/papers.htm, 2003.
• 20: Mora, T., Ed. ISSAC 2002 Proc. 2002 Internat. Symp. Symbolic Algebraic Comput. (New York, N. Y., 2002), ACM Press.
• 21: Mourrain, B., Ed. ISSAC 2001 Proc. 2001 Internat. Symp. Symbolic Algebraic Comput. (New York, N. Y., 2001), ACM Press.
• 22: Kosaku Nagasaka, Towards certified irreducibility testing of bivariate approximate polynomials, Proceedings of the 2002 international symposium on Symbolic and algebraic computation, p.192-199, July 07-10, 2002, Lille, France [doi>10.1145/780506.780531]
• 23: Nagasaka, K., June 2003. Private email commun.
• 24: Ruppert, W. M. Reducibility of polynomials f(x,y) modulo p. J. Number Theory 77 (1999), 62--70.
• 25: Rupprecht, D. Semi-numerical absolute factorization of polynomials with integer coefficients. J. Symbolic Comput. 37, 5 (2004), 557--574.
• 26: 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]
• 27: Sasaki, T., Saito, T., and Hilano, T. Analysis of approximate factorization algorithm I. Japan J. of Industrial and Applied Mathem. 9, 3 (Oct. 1992), 351--368.
• 28: Sasaki, T., Suzuki, M., Kolaur, M., and Sasaki, M. Approximate factorization of multivariate polynomials and absolute irreducibility testing. Japan J. of Industrial and Applied Mathem. 8, 3 (Oct. 1991), 357--375.
• 29: Sendra, J. R., Ed. ISSAC 2003 Proc. 2003 Internat. Symp. Symbolic Algebraic Comput. (New York, N. Y., 2003), ACM Press.
• 30: 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]
• 31: Stewart, G. W. Error and perturbation bounds for subspaces associated with certain eigenvalue problems. SIAM Review 15, 4 (Oct. 1973), 727--764.
• 32: Zhonggang Zeng, A method computing multiple roots of inexact polynomials, Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.266-272, August 03-06, 2003, Philadelphia, PA, USA [doi>10.1145/860854.860907]
• 33: 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]
• 34: Zhi, L. Displacement structure in computing approximate GCD of univariate polynomials. In Proc. Sixth Asian Symposium on Computer Mathematics (ASCM 2003) (Singapore, 2003), Z. Li and W. Sit, Eds., vol. 10 of Lecture Notes Series on Computing, World Scientific, pp. 288--298.

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.2 Approximation

General Terms:
Algorithms, Experimentation

Keywords:
approximate factorization, approximate gcd, multivariate gcd, multivariate polynomial factorization, singular value decomposition, symbolic numeric hybrid method