Seminar Details
2012-02-07 (14.00) : A centuries-old problem: how to compute the roots of a polynomial
At Euler building
Organized by Mathematical Engineering
Speaker :
Raf VANDEBRIL (K.U.Leuven)
Abstract :
Asking a pure mathematician how he would determine the eigenvalues of a matrix, odds are
fifty-fifty he'll just reply: ``retrieve them as roots from the characteristic
polynomial''. Confronting a computer scientist with the problem of computing roots of a
polynomial he'll likely answer: ``put the polynomial in a matrix and then compute the
eigenvalues of that matrix''. A confrontation could end in an absurd chicken-and-egg discussion.
Theoretically, the mathematician's idea is as valuable as
the computer scientist's. From a computational point of view, however, it is too time
consuming to compute the characteristic polynomial, and moreover, numerically it is no
good idea either.
Computing eigenvalues is done nowadays with one of the top 10 algorithms of the 20th
century: the QR-algorithm [B.A. Cipra, Siam News 33, 2000]. Root solving is done, in practice, by placing the polynomial
coefficients in a matrix, the so-called companion matrix. The roots are then retrieved by
simply applying the QR-algorithm on the companion matrix; all eigenvalues pop up one after
the other until eventually all eigenvalues/roots are found. Cleve Moler, pointed out,
however, in the Mathworks Newsletter in 1991 that this approach may not yet be optimal: `` it uses n^2
storage and order n^3 time. An algorithm designed specifically for polynomial roots might
use order n storage and n^2 time. ''
The goal of this talk is to elaborate on contemporary root solvers effectively using n
storage and achieving a computational complexity of n^2 operations. Roughly a
decade ago it emerged from exploiting rank structures in matrices, that the companion
matrix exhibited quite some useful, so far unexploited, properties. By splitting the
matrix in two parts a whole variety of algorithms was developed. About the same time that
the first successful fast solvers were developed, Fiedler proved that the companion matrix
is just an instance of a whole family of matrices, suitable for computing roots of a
polynomial. We will show that one can also, cheaply, and fastly compute eigenvalues based
on such Fiedler factorizations of companion matrices. The algorithm is simple in nature and numerical
evidence shows that this approach supersedes --in terms of speed-- the fastest currently
available root solvers.
This is joint work with
David Watkins and Jared Aurentz