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

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

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. Brugnano and D. Trigiante,*Polynomial roots: the ultimate answer?*, Linear Algebra Appl.**225**(1995), 207–219. MR**1341079**, https://doi.org/10.1016/0024-3795(93)00341-V**4.**Luigi Brugnano,*Numerical implementation of a new algorithm for polynomials with multiple roots*, J. Differ. Equations Appl.**1**(1995), no. 2, 187–207. MR**1350437**, https://doi.org/10.1080/10236199508808019**5.***Proceedings of the 1998 International Symposium on Symbolic and Algebraic Computation*, Association for Computing Machinery (ACM), New York, 1998. Held in Rostock, August 13–15, 1998.**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 overdetermined systems of equations*, Math. Comp.**69**(2000), no. 231, 1099–1115. MR**1651750**, https://doi.org/10.1090/S0025-5718-99-01115-1**8.**James Weldon Demmel,*On condition numbers and the distance to the nearest ill-posed problem*, Numer. Math.**51**(1987), no. 3, 251–289. MR**895087**, https://doi.org/10.1007/BF01400115**9.**James Demmel and Bo Kågström,*The generalized Schur decomposition of an arbitrary pencil 𝐴-𝜆𝐵: robust software with error bounds and applications. I. Theory and algorithms*, ACM Trans. Math. Software**19**(1993), no. 2, 160–174. MR**1342589**, https://doi.org/10.1145/152613.152615**10.**John E. Dennis Jr. and Robert B. Schnabel,*Numerical methods for unconstrained optimization and nonlinear equations*, Prentice Hall Series in Computational Mathematics, Prentice Hall, Inc., Englewood Cliffs, NJ, 1983. MR**702023****11.**Alan Edelman, Erik Elmroth, and Bo Kågström,*A geometric approach to perturbation theory of matrices and matrix pencils. I. Versal deformations*, SIAM J. Matrix Anal. Appl.**18**(1997), no. 3, 653–692. MR**1453545**, https://doi.org/10.1137/S0895479895284634**12.**Alan Edelman, Erik Elmroth, and Bo Kågström,*A geometric approach to perturbation theory of matrices and matrix pencils. II. A stratification-enhanced staircase algorithm*, SIAM J. Matrix Anal. Appl.**20**(1999), no. 3, 667–699. MR**1685048**, https://doi.org/10.1137/S0895479896310184**13.**Ioannis Z. Emiris, André Galligo, and Henri Lombardi,*Certified approximate univariate GCDs*, J. Pure Appl. Algebra**117/118**(1997), 229–251. Algorithms for algebra (Eindhoven, 1996). MR**1457841**, https://doi.org/10.1016/S0022-4049(97)00013-3**14.**M. R. Farmer and G. Loizou,*An algorithm for the total, or partial, factorization of a polynomial*, Math. Proc. Cambridge Philos. Soc.**82**(1977), no. 3, 427–437. MR**474769**, https://doi.org/10.1017/S0305004100054098**15.**M. R. Farmer and G. Loizou,*Locating multiple zeros interactively*, Comput. Math. Appl.**11**(1985), no. 6, 595–603. MR**795497**, https://doi.org/10.1016/0898-1221(85)90042-2**16.**Steven Fortune,*An iterated eigenvalue algorithm for approximating roots of univariate polynomials*, J. Symbolic Comput.**33**(2002), no. 5, 627–646. Computer algebra (London, ON, 2001). MR**1919907**, https://doi.org/10.1006/jsco.2002.0526**17.**Gene H. Golub (ed.),*Studies in numerical analysis*, MAA Studies in Mathematics, vol. 24, Mathematical Association of America, Washington, DC, 1984. MR**925209****18.**V. Hribernig and H. J. Stetter,*Detection and validation of clusters of polynomial zeros*, J. Symbolic Comput.**24**(1997), no. 6, 667–681. MR**1487793**, https://doi.org/10.1006/jsco.1997.0160**19.**Masao Igarashi and Tjalling Ypma,*Relationships between order and efficiency of a class of methods for multiple zeros of polynomials*, J. Comput. Appl. Math.**60**(1995), no. 1-2, 101–113. Linear/nonlinear iterative methods and verification of solution (Matsuyama, 1993). MR**1354650**, https://doi.org/10.1016/0377-0427(94)00086-G**20.**M. A. Jenkins and J. F. Traub,*Principles for testing polynomial zerofinding programs*, ACM Trans. Math. Software**1**(1975), no. 1, 26–34. MR**398154**, https://doi.org/10.1145/355626.355632**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 GCDs of univariate polynomials*, J. Symbolic Comput.**26**(1998), no. 6, 653–666. Symbolic numeric algebra for polynomials. MR**1662028**, https://doi.org/10.1006/jsco.1998.0232**23.**Peter Kravanja and Marc Van Barel,*Computing the zeros of analytic functions*, Lecture Notes in Mathematics, vol. 1727, Springer-Verlag, Berlin, 2000. MR**1754959****24.**Ross A. Lippert and Alan Edelman,*The computation and sensitivity of double eigenvalues*, Advances in computational mathematics (Guangzhou, 1997) Lecture Notes in Pure and Appl. Math., vol. 202, Dekker, New York, 1999, pp. 353–393. MR**1661545****25.**Tsuyako Miyakoda,*Iterative methods for multiple zeros of a polynomial by clustering*, Proceedings of the 3rd International Congress on Computational and Applied Mathematics (Leuven, 1988), 1989, pp. 315–326. MR**1038853**, https://doi.org/10.1016/0377-0427(89)90343-9**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.**Victor Y. Pan,*Solving a polynomial equation: some history and recent progress*, SIAM Rev.**39**(1997), no. 2, 187–220. MR**1453318**, https://doi.org/10.1137/S0036144595288554**28.**David Rupprecht,*An algorithm for computing certified approximate GCD of 𝑛 univariate polynomials*, J. Pure Appl. Algebra**139**(1999), no. 1-3, 255–284. Effective methods in algebraic geometry (Saint-Malo, 1998). MR**1700546**, https://doi.org/10.1016/S0022-4049(99)00014-6**29.**Hans J. Stetter,*Condition analysis of overdetermined algebraic problems*, Computer algebra in scientific computing (Samarkand, 2000) Springer, Berlin, 2000, pp. 345–365. MR**1849762****30.**J. A. Stolan,*An improved Šiljak’s algorithm for solving polynomial equations converges quadratically to multiple zeros*, J. Comput. Appl. Math.**64**(1995), no. 3, 247–268. MR**1365428**, https://doi.org/10.1016/0377-0427(94)00114-6**31.**Frank Uhlig,*General polynomial roots and their multiplicities in 𝑂(𝑛) memory and 𝑂(𝑛²) time*, Linear and Multilinear Algebra**46**(1999), no. 4, 327–359. MR**1730074**, https://doi.org/10.1080/03081089908818625**32.**Sabine Van Huffel,*Iterative algorithms for computing the singular subspace of a matrix associated with its smallest singular values*, Linear Algebra Appl.**154/156**(1991), 675–709. MR**1113165**, https://doi.org/10.1016/0024-3795(91)90399-H**33.**J. H. Wilkinson,*Rounding errors in algebraic processes*, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1963. MR**0161456****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 Rev.**25**(1983), no. 3, 365–378. MR**710467**, https://doi.org/10.1137/1025077**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