na10 swMATH ID: 11511 Software Authors: Bini, Dario Andrea Description: 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. Homepage: http://www.netlib.org/numeralgo/index.html Dependencies: Mathematica Keywords: Laguerre method; roots of a polynomial; Horner scheme; algorithm; Wilkinson polynomial Related Software: na20; mctoolbox; ISOLATE; Eigensolve; SYNAPS; Matlab; NAG; quadeig; MPSolve; MultRoot; FGb; CPOLY; MPC; MPFR; ANewDsc; MPFUN; Algorithm 610; PSIFN; rootsb; Chebfun Cited in: 53 Publications Standard Articles 1 Publication describing the Software, including 1 Publication in zbMATH Year Numerical computation of polynomial zeros by means of Aberth’s method. Zbl 0869.65034Bini, Dario Andrea 1996 all top 5 Cited by 66 Authors 8 Bini, Dario Andrea 8 Pan, Victor Yakovlevich 5 Mourrain, Bernard 4 Gemignani, Luca 4 Gronchi, Giovanni-Federico 4 Tsigaridas, Elias P. 3 Emiris, Ioannis Z. 3 Noferini, Vanni 2 Cameron, Thomas R. 2 Couturier, Raphaël 2 de Terán, Fernando 2 Dimare, Linda 2 Dopico, Froilán M. 2 Farnocchia, Davide 2 Fiorentino, Giuseppe 2 Herceg, Đorđe D. 2 Melman, Aaron 2 Milani, Andrea 2 Pérez, Javier J. 2 Petković, Ivan M. 2 Proinov, Petko D. 2 Sharify, Meisam 2 Zheng, Ailong 1 Akian, Marianne 1 Andreev, Fedor V. 1 Bahi, Jacques Mohcine 1 Canalda, Philippe 1 Chernov, Roman 1 Contassot-Vivier, Sylvain 1 Elkadi, Mohamed 1 Feng, Erbao 1 Gaubert, Stéphane 1 Graillat, Stef 1 Gupta, Umesh Chandra 1 Hu, Wenyu 1 Ivanovs, Jevgeņijs 1 Kalantari, Bahman 1 Keyser, John 1 Khomovsky, Dmitry I. 1 Lau, Chun 1 Luo, Zhongxuan 1 Maity, Arunava 1 Marco García, Ana 1 McNamee, John Michael 1 Nakatsukasa, Yuji 1 Ouchi, Koji 1 Pavlidis, Nicos G. 1 Pavone, Jean-Pascal 1 Petkova, Milena D. 1 Plestenjak, Bor 1 Robol, Leonardo 1 Rojas, J. Maurice 1 Rossi, Alessandro 1 Ruatta, Olivier 1 Rumiantsau, Dzmitry 1 Schleicher, Dierk 1 Schmitt, Simon 1 Shemyakov, Anton 1 Shemyakov, Sergey 1 Spies, François 1 Strobach, Peter 1 Tasoulis, Dimitris K. 1 Tommei, Giacomo 1 Trébuchet, Philippe 1 Vrahatis, Michael N. 1 Wintz, Julien all top 5 Cited in 20 Serials 7 Numerical Algorithms 5 Computers & Mathematics with Applications 5 Journal of Computational and Applied Mathematics 5 Linear Algebra and its Applications 4 Celestial Mechanics and Dynamical Astronomy 3 Theoretical Computer Science 3 SIAM Journal on Matrix Analysis and Applications 2 Mathematics of Computation 2 Calcolo 1 BIT 1 Journal of Symbolic Computation 1 Journal of Complexity 1 Queueing Systems 1 SIAM Review 1 SIAM Journal on Scientific Computing 1 Filomat 1 ETNA. Electronic Transactions on Numerical Analysis 1 Discrete and Continuous Dynamical Systems 1 Mediterranean Journal of Mathematics 1 International Journal of Stochastic Analysis all top 5 Cited in 15 Fields 41 Numerical analysis (65-XX) 11 Field theory and polynomials (12-XX) 11 Functions of a complex variable (30-XX) 9 Real functions (26-XX) 8 Linear and multilinear algebra; matrix theory (15-XX) 8 Computer science (68-XX) 5 Mechanics of particles and systems (70-XX) 2 Special functions (33-XX) 2 Probability theory and stochastic processes (60-XX) 1 History and biography (01-XX) 1 Commutative algebra (13-XX) 1 Algebraic geometry (14-XX) 1 Dynamical systems and ergodic theory (37-XX) 1 Operator theory (47-XX) 1 Operations research, mathematical programming (90-XX) Citations by Year