The approximate GCD of inexact polynomials

ABSTRACT

This paper presents an algorithm and its implementation for computing the approximate GCD (greatest common divisor) of multivariate polynomials whose coefficients may be inexact. The method and the companion software appear to be the first practical package with such capabilities. The most significant features of the algorithm are its robustness and accuracy as demonstrated in computational experiments. In addition, two variations of a squarefree factorization method for multivariate polynomials are proposed as an application of the GCD algorithm.

REFERENCES

• 1: W. S. Brown, On Euclid's Algorithm and the Computation of Polynomial Greatest Common Divisors, Journal of the ACM (JACM), v.18 n.4, p.478-504, Oct. 1971 [doi>10.1145/321662.321664]
• 2: 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]
• 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: I. Z. Emiris, A. Galligo, and H. Lombardi. Certified approximate univariate GCDs. J. Pure Appl. Algebra, 117/118:229--251, 1997.
• 5: 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]
• 6: V. Hribernig , H. J. Stetter, Detection and validation of clusters of polynomial zeros, Journal of Symbolic Computation, v.24 n.6, p.667-681, Dec. 1997 [doi>10.1006/jsco.1997.0160]
• 7: 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]
• 8: N. Karmarkar , Y. N. Lakshman, Approximate polynomial greatest common divisors and nearest singular polynomials, Proceedings of the 1996 international symposium on Symbolic and algebraic computation, p.35-39, July 24-26, 1996, Zurich, Switzerland [doi>10.1145/236869.236892]
• 9: T. Y. Li , Zhonggang Zeng, A Rank-Revealing Method with Updating, Downdating, and Applications, SIAM Journal on Matrix Analysis and Applications, v.26 n.4, p.918-946, 2005 [doi>10.1137/S0895479803435282]
• 10: Hsin-Chao Liao , Richard J. Fateman, Evaluation of the heuristic polynomial GCD, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.240-247, July 10-12, 1995, Montreal, Quebec, Canada [doi>10.1145/220346.220376]
• 11: Masa-aki Ochi , Matu-tarow Noda , Tateaki Sasaki, Approximate greatest common divisor of multivariate polynomials and its application to ill-conditioned systems of algebraic equations, Journal of Information Processing, v.14 n.3, p.292-300, 1991
• 12: S. Pillai and B. Liang. Blind image deconvolution using GCD approach. IEEE Trans. Image Processing, 8:202--219, 1999.
• 13: D. Rupprecht. An algorithm for computing certified approximate GCD of n univariate polynomials. J. Pure and Appl. Alg., 139:255--284, 1999.
• 14: Tateaki Sasaki , Mutsuko Sasaki, Polynomial remainder sequence and approximate GCD, ACM SIGSAM Bulletin, v.31 n.3, p.4-10, Sept. 1997 [doi>10.1145/271130.271131]
• 15: Hans J. Stetter, Numerical Polynomial Algebra, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2004
• 16: F. Sroubek and J. Flusser. Multichannel blind iterative image restoration. IEEE Trans. Image Processing, 9:1094--1106, 2003.
• 17: David Y.Y. Yun, On square-free decomposition algorithms, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.26-35, August 10-12, 1976, Yorktown Heights, New York, United States [doi>10.1145/800205.806320]
• 18: Z. Zeng. The approximate GCD of inexact polynomials. Part I: a univariate algorithm. Preprint, 2004.
• 19: 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]
• 20: Zhonggang Zeng, Algorithm 835: MultRoot---a Matlab package for computing polynomial roots and multiplicities, ACM Transactions on Mathematical Software (TOMS), v.30 n.2, p.218-236, June 2004 [doi>10.1145/992200.992209]
• 21: L. Zhi, K. Li, and M.-T. Noda. Approximate GCD of multivariate polynomials using Hensel lifting. MM Research Preprint 241--248, MMRC, AMSS, Academia, Sinica, Beijing, China, No. 21, 2001, 2001.
• 22: L. Zhi and M.-T. Noda. Approximate GCD of multivariate polynomials. Proc. ASCM 2000, World Scientific Press, pages 9--18, 2000.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
          Subjects: Iterative methods

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Performance measures

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms

Keywords:
factorization, greatest common divisor, polynomial, squarefree