Computing multiple roots of inexact polynomials

Zeng, Zhonggang

doi:10.1090/S0025-5718-04-01692-8

Computing multiple roots of inexact polynomials
HTML articles powered by AMS MathViewer

by Zhonggang Zeng PDF

Math. Comp. 74 (2005), 869-903 Request permission

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.

References

D. H. Bailey, A Fortran-90 based multiprecision system, ACM Trans. Math. Software, 21 (1995), pp. 379–387.
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.
L. Brugnano and D. Trigiante, Polynomial roots: the ultimate answer?, Linear Algebra Appl. 225 (1995), 207–219. MR 1341079, DOI 10.1016/0024-3795(93)00341-V
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, DOI 10.1080/10236199508808019
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.
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.
J. P. Dedieu and M. Shub, Newton’s method for overdetermined systems of equations, Math. Comp. 69 (2000), no. 231, 1099–1115. MR 1651750, DOI 10.1090/S0025-5718-99-01115-1
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, DOI 10.1007/BF01400115
James Demmel and Bo Kågström, The generalized Schur decomposition of an arbitrary pencil $A-\lambda B$: robust software with error bounds and applications. I. Theory and algorithms, ACM Trans. Math. Software 19 (1993), no. 2, 160–174. MR 1342589, DOI 10.1145/152613.152615
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
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, DOI 10.1137/S0895479895284634
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, DOI 10.1137/S0895479896310184
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, DOI 10.1016/S0022-4049(97)00013-3
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, DOI 10.1017/S0305004100054098
M. R. Farmer and G. Loizou, Locating multiple zeros interactively, Comput. Math. Appl. 11 (1985), no. 6, 595–603. MR 795497, DOI 10.1016/0898-1221(85)90042-2
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, DOI 10.1006/jsco.2002.0526
Gene H. Golub (ed.), Studies in numerical analysis, MAA Studies in Mathematics, vol. 24, Mathematical Association of America, Washington, DC, 1984. MR 925209
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, DOI 10.1006/jsco.1997.0160
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, DOI 10.1016/0377-0427(94)00086-G
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, DOI 10.1145/355626.355632
W. Kahan, Conserving confluence curbs ill-condition. Technical Report 6, Computer Science, University of California, Berkeley, 1972.
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, DOI 10.1006/jsco.1998.0232
Peter Kravanja and Marc Van Barel, Computing the zeros of analytic functions, Lecture Notes in Mathematics, vol. 1727, Springer-Verlag, Berlin, 2000. MR 1754959, DOI 10.1007/BFb0103927
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
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, DOI 10.1016/0377-0427(89)90343-9
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.
Victor Y. Pan, Solving a polynomial equation: some history and recent progress, SIAM Rev. 39 (1997), no. 2, 187–220. MR 1453318, DOI 10.1137/S0036144595288554
David Rupprecht, An algorithm for computing certified approximate GCD of $n$ univariate polynomials, J. Pure Appl. Algebra 139 (1999), no. 1-3, 255–284. Effective methods in algebraic geometry (Saint-Malo, 1998). MR 1700546, DOI 10.1016/S0022-4049(99)00014-6
Hans J. Stetter, Condition analysis of overdetermined algebraic problems, Computer algebra in scientific computing (Samarkand, 2000) Springer, Berlin, 2000, pp. 345–365. MR 1849762
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, DOI 10.1016/0377-0427(94)00114-6
Frank Uhlig, General polynomial roots and their multiplicities in $O(n)$ memory and $O(n^2)$ time, Linear and Multilinear Algebra 46 (1999), no. 4, 327–359. MR 1730074, DOI 10.1080/03081089908818625
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, DOI 10.1016/0024-3795(91)90399-H
J. H. Wilkinson, Rounding errors in algebraic processes, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1963. MR 0161456
J. R. Winkler, Condition numbers of a nearly singular simple root of a polynomial, Appl. Numer. Math., (2001), pp. 275–285.
T. J. Ypma, Finding a multiple zero by transformations and Newton-like methods, SIAM Rev. 25 (1983), no. 3, 365–378. MR 710467, DOI 10.1137/1025077
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.
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.
Z. Zeng, Algorithm $835:$ Multroot – a Matlab package computing polynomial roots and multiplicities, ACM Trans. Math. Software, 30 (2004), pp. 218-235.
Z. Zeng, On ill-conditioned eigenvalues, multiple roots of polynomials, and their accurate computation. MSRI Preprint No. 1998-048, (1998).