Volume 55, pp. 401-423, 2022.

On a compensated Ehrlich-Aberth method for the accurate computation of all polynomial roots

Thomas R. Cameron and Stef Graillat

Abstract

In this article, we use the complex compensated Horner method to derive a compensated Ehrlich-Aberth method for the accurate computation of all roots, real or complex, of a polynomial. In particular, under suitable conditions, we prove that the limiting accuracy for the compensated Ehrlich-Aberth iterations is as accurate as if computed in twice the working precision and then rounded to the working precision. Moreover, we derive a running error bound for the complex compensated Horner method and use it to form robust stopping criteria for the compensated Ehrlich-Aberth iterations. Finally, extensive numerical experiments illustrate that the backward and forward errors of the root approximations computed via the compensated Ehrlich-Aberth method are similar to those obtained with a quadruple precision implementation of the Ehrlich-Aberth method with a significant speed-up in terms of computation time.

Full Text (PDF) [352 KB], BibTeX

Key words

polynomial evaluation, error-free transformations, polynomial roots, backward error, forward error, rounding error analysis

AMS subject classifications

65H04, 65Y20, 65-04

< Back