Improved initialization of the accelerated and robust QR-like polynomial root-finding

Dario A. Bini, Luca Gemignani, and Victor Y. Pan

Abstract

We approximate polynomial roots numerically as the eigenvalues of a unitary diagonal plus rank-one matrix. We rely on our earlier adaptation of the $QR$ algorithm, which exploits the semiseparable matrix structure to approximate the eigenvalues in a fast and robust way, but we substantially improve the performance of the resulting algorithm at the initial stage, as confirmed by our numerical tests.

Full Text (PDF) [166 KB]

Key words

$QR$ iteration, eigenvalue computation, polynomial roots, semiseparable matrices, DFT, FFT, Moebius transformation.

65H17, 65F15.

Links to the cited ETNA articles

 [21] Vol. 12 (2001), pp. 66-87 Hong Zhang: Numerical condition of polynomials in different forms

< Back