Computing multiple roots of inexact polynomials

Author:
Zhonggang Zeng

Journal:
Math. Comp. **74** (2005), 869-903

MSC (2000):
Primary 12Y05, 65H05; Secondary 65F20, 65F22, 65F35

Published electronically:
July 22, 2004

MathSciNet review:
2114653

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We present a combination of two algorithms that accurately calculate multiple roots of general polynomials.

Algorithm I transforms the singular root-finding into a regular nonlinear least squares problem on a pejorative manifold, and it calculates multiple roots simultaneously from a given multiplicity structure and initial root approximations. To fulfill the input requirement of Algorithm I, we develop a numerical GCD-finder containing a successive singular value updating and an iterative GCD refinement as the main engine of Algorithm II that calculates the multiplicity structure and the initial root approximation. While limitations exist in certain situations, the combined method calculates multiple roots with high accuracy and consistency in practice without using multiprecision arithmetic, even if the coefficients are inexact. This is perhaps the first blackbox-type root-finder with such capabilities.

To measure the sensitivity of the multiple roots, a structure-preserving condition number is proposed and error bounds are established. According to our computational experiments and error analysis, a polynomial being ill-conditioned in the conventional sense can be well conditioned with the multiplicity structure being preserved, and its multiple roots can be computed with high accuracy.

**1.**D. H. Bailey,*A Fortran-90 based multiprecision system*, ACM Trans. Math. Software, 21 (1995), pp. 379-387.**2.**D. Bini and G. Fiorentino,*Numerical computation of polynomial roots using MPSolve - version 2.0*. manuscript, Software and paper available at`ftp://ftp.dm.unipi.it/pub/mpsolve/`, 1999.**3.**L. Brugnanao and D. Trigiante,*Polynomial roots: the ultimate answer?*, Linear Alg. and Its Appl., 225 (1995), pp. 207-219. MR**96b:65050****4.**L. Brugnano,*Numerical implementation of a new algorithm for polynomials with multiple roots*, J. Difference Eq. and Appl., 1 (1995), pp. 187-207.MR**96m:12001a****5.**P. Chin, R. M. Corless, and G. F. Corless,*Optimization strategies for the approximate GCD problem*, Proceedings of 1998 International Symposium on Symbolic and Algebraic Computation (ISSAC '98), New York, 1998, ACM Press, pp. 228-235.MR**2001m:68004****6.**R. M. Corless, P. M. Gianni, B. M. Trager, and S. M. Watt,*The singular value decomposition for polynomial systems*, Proceedings of 1995 nternational Symposium on Symbolic and Algebraic Computation (ISSAC '95), ACM Press, New York, 1995, pp. 195-207.**7.**J.-P. Dedieu and M. Shub,*Newton's method for over-determined system of equations*, Math. Comp., 69 (1999), pp. 1099-1115.MR**2000j:65133****8.**J. W. Demmel,*On condition numbers and the distance to the nearest ill-posed problem*, Numer. Math., 51 (1987), pp. 251-289.MR**88i:15014****9.**J. W. Demmel and B. Kagström,*The generalized Schur decomposition of an arbitrary pencil**: robust software with error bounds and applications. Part I & Part II*, ACM Trans. Math. Software, 19 (1993), pp. 161-201.MR**96d:65060a**; MR**96d:65060b****10.**J. E. Dennis and R. B. Schnabel,*Numerical Methods for Unconstrained Optimization and Nonlinear Equations*, Prentice-Hall Series in Computational Mathematics, Prentice-Hall, Englewood Cliffs, New Jersey, 1983. MR**85j:65001****11.**A. Edelman, E. Elmroth, and B. Kagström,*A geometric approach to perturbation theory of matrices and and matrix pencils. Part I: Versal deformations*, SIAM J. Matrix Anal. Appl., 18 (1997), pp. 693-705. MR**99e:58021****12.**A. Edelman, E. Elmroth, and B. Kagström,*A geometric approach to perturbation theory of matrices and and matrix pencils. Part II: a stratification-enhanced staircase algorithm*, SIAM J. Matrix Anal. Appl., 20 (1999), pp. 667-699.MR**2000c:65032****13.**I. Z. Emiris, A. Galligo, and H. Lombardi,*Certified approximate univariate GCDs*, J. Pure Appl. Algebra, 117/118 (1997), pp. 229-251. MR**98f:65135****14.**M. R. Farmer and G. Loizou,*An algorithm for the total, or partial, factorization of a polynomial*, Math. Proc. Camb. Phil. Soc., 82 (1977), pp. 427-437.MR**57:14402****15.**M. R. Farmer and G. Loizou,*Locating multiple zeros interactively*, Comp. Math. Appl., 11 (1985), pp. 595-603.MR**86h:65067****16.**S. Fortune,*An iterated eigenvalue algorithm for approximating roots of univariate polynomials*, J. Symbolic Comput., 33 (2002), pp. 627-646. MR**2003e:13039****17.**W. Gautschi,*Questions of numerical condition related to polynomials*, in MAA Studies in Mathematics, Vol. 24, Studies in Numerical Analysis, G. H. Golub, ed., USA, 1984, The Mathematical Association of America, pp. 140-177.MR**88i:65007****18.**V. Hribernig and H. J. Stetter,*Detection and validation of clusters of polynomial zeros*, J. Symb. Comput., 24 (1997), pp. 667-681. MR**2000b:68275****19.**M. Igarashi and T. Ypma,*Relationships between order and efficiency of a class of methods for multiple zeros of polynomials*, J. Comput. Appl. Math., 60 (1995), pp. 101-113.MR**96f:65059****20.**M. A. Jenkins and J. F. Traub,*Principles for testing polynomial zerofinding programs*, ACM Trans. Math. Software, 1 (1975), pp. 26-34. MR**53:2009****21.**W. Kahan,*Conserving confluence curbs ill-condition*. Technical Report 6, Computer Science, University of California, Berkeley, 1972.**22.**N. K. Karmarkar and Y. N. Lakshman,*On approximate polynomial greatest common divisors*, J. Symb. Comput., 26 (1998), pp. 653-666. MR**99j:68059****23.**P. Kravanja and M. Van Barel,*Computing Zeros of Analytic Functions, Lecture Notes in Mathematics, 1727*, Springer-Verlag, 2000. MR**2001c:65004****24.**R. A. Lippert and A. Edelman,*The computation and sensitivity of double eigenvalues*, in Advances in computational mathematics, Lecture Notes in Pure and Appl. Math. 202, New York, 1999, Dekker, pp. 353-393. MR**2000e:65043****25.**T. Miyakoda,*Iterative methods for multiple zeros of a polynomial by clustering*, J. Comput. Appl. Math., 28 (1989), pp. 315-326. MR**91k:65086****26.**V. Y. Pan,*Numerical computation of a polynomial gcd and extensions*. Research Report 2996, Institut National de Recherche en Informatique et en Automatique (INRIA), Sophia-Antipolis, France, 1996.**27.**V. Y. Pan,*Solving polynomial equations: some history and recent progress*, SIAM Review, 39 (1997), pp. 187-220.MR**99b:65066****28.**D. Rupprecht,*An algorithm for computing certified approximate GCD of n univariate polynomials*, J. Pure and Appl. Alg., 139 (1999), pp. 255-284.MR**2000d:65255****29.**H. J. Stetter,*Condition analysis of overdetermined algebraic problems*, in Computer Algebra in Scientific Computing-CASC 2000, e. a. V.G. Ganzha, ed., Springer, 2000, pp. 345-365.MR**2002e:65088****30.**J. A. Stolan,*An improved Siljak's algorithm for solving polynomial equations converges quadratically to multiple zeros*, J. Comput. Appl. Math., 64 (1995), pp. 247-268.MR**96h:65074****31.**F. Uhlig,*General polynomial roots and their multiplicities in**memory and**time*, Linear and Multilinear Algebra, 46 (1999), pp. 327-359.MR**2000i:12010****32.**S. Van Huffel,*Iterative algorithms for computing the singular subspace of a matrix associated with its smallest singular values*, Linear Alg. Appl., 154-156 (1991), pp. 675-709.MR**92d:65065****33.**J. H. Wilkinson,*Rounding Errors in Algebraic Processes*, Prentice-Hall, Englewood Cliffs, N.J., 1963.MR**28:4661****34.**J. R. Winkler,*Condition numbers of a nearly singular simple root of a polynomial*, Appl. Numer. Math., (2001), pp. 275-285.**35.**T. J. Ypma,*Finding a multiple zero by transformations and Newton-like methods*, SIAM Review, 25 (1983), pp. 365-378. MR**85a:65078****36.**D. Y. Y. Yun,*On square-free decomposition algorithms*, in Proceedings of 1976 ACM Symposium of Symbolic and Algebraic Computation (ISSAC'76), ACM Press, Yorktown Heights, New York, 1976, pp. 26-35.**37.**Z. Zeng,*A method computing multiple roots of inexact polynomials*, Proceedings of 2003 International Symposium of Symbolic and Algebraic Computation (ISSAC '03), ACM Press, New York, 2003, pp. 266-272.**38.**Z. Zeng,*Algorithm**Multroot - a Matlab package computing polynomial roots and multiplicities*, ACM Trans. Math. Software, 30 (2004), pp. 218-235.**39.**Z. Zeng,*On ill-conditioned eigenvalues, multiple roots of polynomials, and their accurate computation*. MSRI Preprint No. 1998-048, (1998).

Retrieve articles in *Mathematics of Computation*
with MSC (2000):
12Y05,
65H05,
65F20,
65F22,
65F35

Retrieve articles in all journals with MSC (2000): 12Y05, 65H05, 65F20, 65F22, 65F35

Additional Information

**Zhonggang Zeng**

Affiliation:
Department of Mathematics, Northeastern Illinois University, Chicago, Illinois 60625

Email:
zzeng@neiu.edu

DOI:
https://doi.org/10.1090/S0025-5718-04-01692-8

Keywords:
Polynomial,
root,
multiplicity

Received by editor(s):
January 13, 2003

Received by editor(s) in revised form:
September 17, 2003

Published electronically:
July 22, 2004

Article copyright:
© Copyright 2004
American Mathematical Society