Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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.

References [Enhancements On Off] (What's this?)

Similar Articles

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
MR Author ID: 214819
ORCID: 0000-0001-8879-8077

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