Algorithm 835: MultRoot---a Matlab package for computing polynomial roots and multiplicities

ABSTRACT

MultRoot is a collection of Matlab modules for accurate computation of polynomial roots, especially roots with non-trivial multiplicities. As a blackbox-type software, MultRoot requires the polynomial coefficients as the only input, and outputs the computed roots, multiplicities, backward error, estimated forward error, and the structure-preserving condition number. The most significant features of MultRoot are the multiplicity identification capability and high accuracy on multiple roots without using multiprecision arithmetic, even if the polynomial coefficients are inexact. A comprehensive test suite of polynomials that are collected from the literature is included for numerical experiments and performance comparison.

REFERENCES

• 1: Bini, D. A. and Fiorentino, G. 1999. Numerical computation of polynomial roots using mpsolve---version 2.0. Manuscript, available at ftp://ftp.dm.unipi.it/pub/mpsolve/.
• 2: Bini, D. A. and Mourrain, B. 1996. Polynomial test suite. http://www-sop.inria.fr/saga/POL.
• 3: Brugnanao, L. and Trigiante, D. 1995. Polynomial roots: the ultimate answer? Linear Alg. and Its Appl. 225, 207--219.
• 4: Dvorčuk, J. 1969. Factorization of a polynomial into quadratic factors by Newton method. Apl. Mat. 14, 54--80.
• 5: Farmer, M. R. and Loizou, G. 1975. A class of iteration functions for improving, simultaneously, approximation to the zeros of a polynomial. BIT 15, 250--258.
• 6: S. Goedecker, Remark on algorithms to find roots of polynomials, SIAM Journal on Scientific Computing, v.15 n.5, p.1059-1063, Sept. 1994 [doi>10.1137/0915064]
• 7: Masao Igarashi , Tjalling Ypma, Relationships between order and efficiency of a class of methods for multiple zeros of polynomials, Journal of Computational and Applied Mathematics, v.60 n.1-2, p.101-113, June 20, 1995
• 8: Iliev, A. I. 2000. A generalization of Obreshkoff-Ehrlich method for multiple roots of algebraic, trigonometric and exponential equations. Math. Balkanica 14, 17--18.
• 9: M. A. Jenkins , J. F. Traub, Principles for Testing Polynomial Zerofinding Programs, ACM Transactions on Mathematical Software (TOMS), v.1 n.1, p.26-34, March 1975 [doi>10.1145/355626.355632]
• 10: Kahan, W. 1972. Conserving confluence curbs ill-condition. Tech. Rep. 6, Computer Science, University of California, Berkeley.
• 11: Li, T. Y. and Zeng, Z. 2003. A rank-revealing method and its applications. SIAM J. Matrix Annal. Appli., to appear.
• 12: Loizou, G. 1983. Higher-order iteration functions for simultaneously approximating polynomial zeros. Intern. J. Comput. Math. 14, 45--58.
• 13: John Michael McNamee, A bibliography on roots of polynomials, Journal of Computational and Applied Mathematics, v.47 n.3, p.391-394, Sept. 30, 1993 [doi>10.1016/0377-0427(93)90064-I]
• 14: Tsyuyako Miyakoda, Iterative methods for multiple zeros of a polynomial by clustering, Journal of Computational and Applied Mathematics, v.28 n.1989, p.315-326, December 1989 [doi>10.1016/0377-0427(89)90343-9]
• 15: Victor Y. Pan, Solving a Polynomial Equation: Some History and Recent Progress, SIAM Review, v.39 n.2, p.187-220, June 1997 [doi>10.1137/S0036144595288554]
• 16: Petković, M. 1989. Iterative Methods for Simultaneous Inclusion of Polynomial zeros, Lecture Notes in Mathematics, 1387. Springer-Verlag.
• 17: J. A. Stolan, An improved Sˇiljak's algorithm for solving polynomial equations converges quadratically to multiple zeros, Journal of Computational and Applied Mathematics, v.64 n.3, p.247-268, Dec. 20, 1995 [doi>10.1016/0377-0427(94)00114-6]
• 18: Toh, K. C. and Trefethen, L. N. 1994. Pseudozeros of polynomials and pseudospectra of companion matrices. Numer. Math. 68, 403--425.
• 19: Uhlig, F. 1999. General polynomial roots and their multiplicities in O(n) memory and O(n2) time. Linear and Multilinear Algebra 46, 327--359.
• 20: Zeng, Z. 2003. Computing multiple roots of inexact polynomials. Math. Comp., to appear.
• 21: Zhang, H. 2001. Numerical condition of polynomials in different forms. Elec. Trans. Numer. Anal. 12, 66--87.

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Certification and testing; Algorithm design and analysis

General Terms:
Algorithms, Documentation, Experimentation

Keywords:
multiple root, multiple zero, multiplicity identification, polynomial, root-finding