On approximate irreducibility of polynomials in several variables

ABSTRACT

We study the problem of bounding a polynomial away from polynomials which are absolutely irreducible. Such separation bounds are useful for testing whether a numerical polynomial is absolutely irreducible, given a certain tolerance on its coefficients. Using an absolute irreducibility criterion due to Ruppert, we are able to find useful separation bounds, in several norms, for bivariate polynomials. We also use Ruppert's criterion to derive new, more effective Noether forms for polynomials of arbitrarily many variables. These forms lead to small separation bounds for polynomials of arbitrarily many variables.

REFERENCES

• 1: Campbell, S. L., and Meyer, Jr., C. D. Generalized Inverses of Linear Transformations. Pitman Publ. Ltd., London, 1979.
• 2: Chu, M. T., Funderlic, R. E., and Plemmons, R. J. Structured low rank approximation. Paper submitted, 10 pages, 2002.
• 3: 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]
• 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: Eckart, C., and Young, G. The approximation of one matrix by another of lower rank. Psychometrika 1, 3 (Sept. 1936), 211--218.
• 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 , 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]
• 8: 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]
• 9: Gao, S., and Rodrigues, V. M. Irreducibility of polynomials modulo p via Newton polytopes. Preprint, 13 pages. Available from http://www.math.clemson.edu/ sgao/pub.html. To appear J. Number Theory, 2003.
• 10: Markus A. Hitz , Erich Kaltofen, Efficient algorithms for computing the nearest polynomial with constrained roots, Proceedings of the 1998 international symposium on Symbolic and algebraic computation, p.236-243, August 13-15, 1998, Rostock, Germany [doi>10.1145/281508.281624]
• 11: 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]
• 12: 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]
• 13: Kahan, W. Numerical linear algebra. Canadian Math. Bull. 9 (1966), 757--801.
• 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, Polynomial Factorization 1987-1991, Proceedings of the 1st Latin American Symposium on Theoretical Informatics, p.294-313, April 06-10, 1992
• 16: Erich Kaltofen, Effective Noether irreducibility forms and applications, Journal of Computer and System Sciences, v.50 n.2, p.274-295, April 1995
• 17: 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]
• 18: Mora, T., Ed. ISSAC 2002 Proc. 2002 Internat. Symp. Symbolic Algebraic Comput. (New York, N. Y., 2002), ACM Press.
• 19: Mourrain, B., Ed. ISSAC 2001 Proc. 2001 Internat. Symp. Symbolic Algebraic Comput. (New York, N. Y., 2001), ACM Press.
• 20: 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]
• 21: Ruppert, W. M. Reduzibilität ebener Kurven. J. reine angew. Math. 369 (1986), 167--191.
• 22: Ruppert, W. M. Reducibility of polynomials f(x,y) modulo p. J. Number Theory 77 (1999), 62--70.
• 23: 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]
• 24: 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.
• 25: Sasaki, T., Suzuki, M., Kolár, 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.
• 26: Hans J. Stetter, The nearest polynomial with a given zero, and similar problems, ACM SIGSAM Bulletin, v.33 n.4, p.2-4, 12/01/1999 [doi>10.1145/500457.500458]
• 27: Stewart, G. W. Introduction to Matrix Computations. Academic Press, Inc., New York, 1973.

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

Keywords:
absolute irreducibility, approximate factorization, effective Noether irreducibility forms, multivariate polynomial factorization, radius of irreducibility, symbolic/numeric hybrid method