Towards certified irreducibility testing of bivariate approximate polynomials

ABSTRACT

Let F(x, u) be a given bivariate polynomial and ε be a small positive number. We consider the approximate factorization of F: find polynomials G, H and ΔF such that F = GH + ΔF and ‖ΔF‖ / ‖F‖= ε, where ‖P‖ denotes 2-norm of polynomial P. At first, we introduce a relation between the irreducibility of F and the singular value of a certain matrix. By this relation and an upper bound of variations of the power-series roots of a bivariate polynomial, we give an algorithm for an absolute irreducibility test of a polynomial whose coefficients are perturbed within a given tolerance. In addition, we give a lower bound for a tolerance of the approximate factorization of a given bivariate polynomial. The lower bound is the necessary magnitude of perturbations which make a given polynomial reducible.

REFERENCES

• 1: 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]
• 2: 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]
• 3: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 4: 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]
• 5: Erich Kaltofen, Effective Noether irreducibility forms and applications, Journal of Computer and System Sciences, v.50 n.2, p.274-295, April 1995
• 6: Zou Mou-yan , Rolf Unbehauen, Approximate factorization of multivariable polynomials, Signal Processing, v.14 n.2, p.141-152, March 1988 [doi>10.1016/0165-1684(88)90002-3]
• 7: K. Nagasaka and T. Sasaki. Approximate multivariate factorization and its time complexity. Japan J. Indust. Appl. Math., accepted.
• 8: Y. Ozaki and T. Sasaki. Univariate factor separation and its application to multiple/close root problem. Sushikisyori, 6:30-46, 1998.
• 9: 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]
• 10: T. Sasaki, T. Saito, and T. Hilano. Analysis of approximate factorization algorithm i. Japan J. Indust. Appl. Math., 9:351-368, 1992.
• 11: T. Sasaki and M. Sasaki. A unified method for multivariate polynomial factorizations. Japan J. Indust. Appl. Math., 10:21-39, 1993.
• 12: T. Sasaki, M. Suzuki, M. Kolář, and M. Sasaki. Approximate factorization of multivariate polynomials and absolute irreducibility testing. Japan J. Indust. Appl. Math., 8:357-375, 1991.
• 13: A. Terui and T. Sasaki. "Approximate zero-points" of real univariate polynomial with large error terms. IPSJ J., 41:974-989, 2000.
• 14: 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]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

General Terms:
Algorithms, Experimentation