ILAS2016 — 11–15 July 2016 — KU Leuven, Belgium

20th Conference of the International Linear Algebra Society (ILAS)

20th ILAS Conference

In minisymposium: Matrix Structures and Univariate Polynomial Rootfinding

Fri 12:00–12:30, Room AV 91.12
Global backward error analyses for polynomial eigenvalue problems solved via linearizations
Froilán Dopico (Universidad Carlos III de Madrid)
Joint work with Piers Lawrence (KU Leuven); Javier Pérez (The University of Manchester); Paul Van Dooren (UC Louvain)

Backward error analyses of algorithms for solving polynomial eigenvalue problems, as well as scalar polynomial root-finding problems, can be "local" or "global". The goal of "local" analyses is to prove that any computed eigenvalue is the exact eigenvalue of a nearby matrix polynomial, which may be different for each eigenvalue. In contrast, the aim of "global" analyses is to prove that the whole set of computed eigenvalues is the whole set of exact eigenvalues of a nearby matrix polynomial. Clearly, "global" analyses are much harder than "local" ones, since a "global" backward error result implies a local one, but the opposite is not true. This, among other reasons, has motivated considerable activity on "local" analyses in the last years, while the number of results on "global" analyses is very low. In this talk, we present a new approach to global backward error analyses for polynomial eigenvalue problems solved via linearizations, which is based on the concept of dual minimal bases and the solution of certain matrix equations. This approach allows us to prove global backward error results for a huge class of linearizations that include, among many others, all Fiedler linearizations, to include in the analysis the minimal indices in addition to the eigenvalues, and to provide more precise bounds than the ones previously available in the literature.