Venue
Sala Seminari (Dip. Matematica).
Abstract
The most common methods to compute roots of polynomials is to rephrase the problem in linear algebra terms: one constructs a companion matrix (or pencil) that has the roots of the polynomial as eigenvalues. However, even when the eigenvalue method used is backward stable, it’s non-trivial to map the backward error back on the polynomial. This problem has been studied extensively in the past and it has been shown that relying on the QR method does not provide a normwise backward-stable rootfinder. For this reason, one needs to rely on QZ + appropriate scaling. However, companion matrices are unitary plus rank 1, and we claim that relying on fast QR method that exploits this structure can lead to a backward-stable method. To this end, one needs to ensure that the errors on the unitary and rank 1 parts satisfy different bounds. We show how to perform this analysis of “mixed perturbation backward-error”, as well as a method that satisfies these constrains. Time permitting, we discuss some more details that one should consider. We show, for example, that normwise backward stable operations (i.e., unitary rotations in our case) do not necessarily imply backward stable operations on the unitary and low-rank factors, unless some particular identities involving sines and cosines are preserved. This is joint work with Jared Aurentz, Thomas Mach, Raf Vandebril, and David Watkins.