na10
Numerical computation of polynomial zeros by means of Aberth’s method. n algorithm for computing polynomial zeros, based on Aberth’s method, is presented. The starting approximations are chosen by means of a suitable application of Rouché’s theorem. More precisely, an integerq ≥ 1 and a set of annuliA i,i=1,...,q, in the complex plane, are determined together with the numberk i of zeros of the polynomial contained in each annulusA i. As starting approximations we choosek i complex numbers lying on a suitable circle contained in the annulusA i, fori=1,...,q. The computation of Newton’s correction is performed in such a way that overflow situations are removed. A suitable stop condition, based on a rigorous backward rounding error analysis, guarantees that the computed approximations are the exact zeros of a “nearby” polynomial. This implies the backward stability of our algorithm. We provide a Fortran 77 implementation of the algorithm which is robust against overflow and allows us to deal with polynomials of any degree, not necessarily monic, whose zeros and coefficients are representable as floating point numbers. In all the tests performed with more than 1000 polynomials having degrees from 10 up to 25,600 and randomly generated coefficients, the Fortran 77 implementation of our algorithm computed approximations to all the zeros within the relative precision allowed by the classical conditioning theorems with 11.1 average iterations. In the worst case the number of iterations needed has been at most 17. Comparisons with available public domain software and with the algorithm PA16AD of Harwell are performed and show the effectiveness of our approach. A multiprecision implementation in MATHEMATICA ™ is presented together with the results of the numerical tests performed.
Keywords for this software
References in zbMATH (referenced in 37 articles , 1 standard article )
Showing results 1 to 20 of 37.
Sorted by year (- Nakatsukasa, Yuji; Noferini, Vanni: On the stability of computing polynomial roots via confederate linearizations (2016)
- Maity, Arunava; Gupta, U.C.: A comparative numerical study of the spectral theory approach of Nishimura and the roots method based on the analysis of BDMMAP/G/1 queue (2015)
- Bini, Dario A.; Robol, Leonardo: Solving secular and polynomial equations: a multiprecision algorithm (2014)
- De Terán, Fernando; Dopico, Froilán M.; Pérez, Javier: New bounds for roots of polynomials based on Fiedler companion matrices (2014)
- Melman, A.: Implementation of Pellet’s theorem (2014)
- Bini, Dario A.; Noferini, Vanni: Solving polynomial eigenvalue problems by means of the Ehrlich-Aberth method (2013)
- Bini, Dario A.; Noferini, Vanni; Sharify, Meisam: Locating the eigenvalues of matrix polynomials (2013)
- Melman, A.: Generalization and variations of Pellet’s theorem for matrix polynomials (2013)
- McNamee, J.M.; Pan, Victor Y.: Efficient polynomial root-refiners: a survey and new record efficiency estimates (2012)
- Strobach, Peter: A fitting algorithm for real coefficient polynomial rooting (2012)
- Gronchi, G.F.; Farnocchia, D.; Dimare, L.: Orbit determination with the two-body integrals. II (2011)
- Luo, Zhongxuan; Hu, Wenyu; Feng, Erbao: Computing curve intersection by homotopy methods (2011)
- Pan, Victor Y.; Zheng, Ai-Long: New progress in real and complex polynomial root-finding (2011)
- Pan, Victor Y.; Zheng, Ai-Long: Root-finding by expansion with independent constraints (2011)
- Farnocchia, Davide; Tommei, Giacomo; Milani, Andrea; Rossi, Alessandro: Innovative methods of correlation and orbit determination for space debris (2010)
- Gronchi, G.F.; Dimare, L.; Milani, A.: Orbit determination with the two-body integrals (2010)
- Bahi, Jacques Mohcine; Contassot-Vivier, Sylvain; Couturier, Raphaël: Parallel iterative algorithms. From sequential to grid computing. (2008)
- Emiris, Ioannis Z.; Mourrain, Bernard; Tsigaridas, Elias P.: Real algebraic numbers: Complexity analysis and experimentation (2008)
- Mourrain, Bernard; Pavone, Jean-Pascal; Trebuchet, Philippe; Tsigaridas, Elias P.; Wintz, Julien: SYNAPS: a library for dedicated applications in symbolic numeric computing (2008)
- Tsigaridas, Elias P.; Emiris, Ioannis Z.: On the complexity of real root isolation using continued fractions (2008)