Zhonggang Zeng
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.
Supplemental Material
Available for Download
Software for "MultRoot---a Matlab package for computing polynomial roots and multiplicities"
- 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/.Google Scholar
- Bini, D. A. and Mourrain, B. 1996. Polynomial test suite. http://www-sop.inria.fr/saga/POL.Google Scholar
- Brugnanao, L. and Trigiante, D. 1995. Polynomial roots: the ultimate answer? Linear Alg. and Its Appl. 225, 207--219.Google Scholar
- Dvorčuk, J. 1969. Factorization of a polynomial into quadratic factors by Newton method. Apl. Mat. 14, 54--80.Google Scholar
- 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.Google Scholar
- Goedecker, S. 1994. Remarks on algorithms to find roots of polynomials. SIAM J. Sci. Comput 15, 1059--1063. Google Scholar
- Igarashi, M. and Ypma, T. 1984. Relationships between order and efficiency of a class of methods for multiple zeros of polynomials. J. Comput. Appl. Math. 60, 101--113. Google Scholar
- Iliev, A. I. 2000. A generalization of Obreshkoff-Ehrlich method for multiple roots of algebraic, trigonometric and exponential equations. Math. Balkanica 14, 17--18.Google Scholar
- Jenkins, M. A. and Traub, J. F. 1975. Principles for testing polynomial zerofinding programs. ACM Trans. Math. Soft. 1, 1, 26--34. Google Scholar
- Kahan, W. 1972. Conserving confluence curbs ill-condition. Tech. Rep. 6, Computer Science, University of California, Berkeley.Google Scholar
- Li, T. Y. and Zeng, Z. 2003. A rank-revealing method and its applications. SIAM J. Matrix Annal. Appli., to appear.Google Scholar
- Loizou, G. 1983. Higher-order iteration functions for simultaneously approximating polynomial zeros. Intern. J. Comput. Math. 14, 45--58.Google Scholar
- McNamee, J. 1993. A bibliography on roots of polynomials. J. Comput. Appl. Math. 47, 391--394. Google Scholar
- Miyakoda, T. 1989. Iterative methods for multiple zeros of a polynomial by clustering. J. Comput. Appl. Math. 28, 315--326. Google Scholar
- Pan, V. Y. 1997. Solving polynomial equations: some history and recent progress. SIAM Review 39, 187--220. Google Scholar
- Petković, M. 1989. Iterative Methods for Simultaneous Inclusion of Polynomial zeros, Lecture Notes in Mathematics, 1387. Springer-Verlag.Google Scholar
- Stolan, J. A. 1995. An improved Šiljak's algorithm for solving polynomial equations converges quadratically to multiple zeros. J. Comput. Appl. Math. 64, 247--268. Google Scholar
- Toh, K. C. and Trefethen, L. N. 1994. Pseudozeros of polynomials and pseudospectra of companion matrices. Numer. Math. 68, 403--425.Google Scholar
- Uhlig, F. 1999. General polynomial roots and their multiplicities in O(n) memory and O(n2) time. Linear and Multilinear Algebra 46, 327--359.Google Scholar
- Zeng, Z. 2003. Computing multiple roots of inexact polynomials. Math. Comp., to appear.Google Scholar
- Zhang, H. 2001. Numerical condition of polynomials in different forms. Elec. Trans. Numer. Anal. 12, 66--87.Google Scholar
Index Terms
- Algorithm 835: MultRoot---a Matlab package for computing polynomial roots and multiplicities
Recommendations
An effective description of the roots of bivariates mod pk and the related Igusa’s local zeta function
ISSAC '23: Proceedings of the 2023 International Symposium on Symbolic and Algebraic ComputationFinding roots of a bivariate polynomial f(x1, x2), over a prime field , is a fundamental question with a long history and several practical algorithms are now known. Effective algorithms for describing the roots modulo pk, k ≥ 2, for any general ...
A one parameter family of locally quartically convergent zero-finding methods
A one parameter family of iteration functions for finding simple and multiple zeros of analytic functions is derived. The family includes, as a special case, Traub's quartic square root method and, as limiting cases, the Kiss method of order 4, the ...
Exact polynomial factorization by approximate high degree algebraic numbers
SNC '09: Proceedings of the 2009 conference on Symbolic numeric computationFor factoring polynomials in two variables with rational coefficients, an algorithm using transcendental evaluation was presented by Hulst and Lenstra. In their algorithm, transcendence measure was computed. However, a constant c is necessary to compute ...
Comments