Numerical Algorithms for the Polynomial Eigenvalue Problem

The polynomial eigenvalue problem (PEP) is to find the eigenvalues and eigenvectors of a square matrix whose elements are polynomials in a variable lambda, where an eigenvalue is a value of lambda for which the matrix is singular.Excellent numerical methods exist for the case where the polynomial degree is 1. Matrix polynomials of degree 2 or higher arise commonly in areas such as structural mechanics, acoustic systems and electrical circuit simulation. The trend to towards extreme designs (such as in micro-electromechanical (MEMS) devices and superjumbo jets) means that these eigenproblems are often poorly conditioned (hence difficult to solve accurately) while also having algebraic structure that should be exploited in a numerical method. As a specific example, in a project at TU Berlin modelling the sound and vibration levels in European high-speed trains it was found that standard finite element packages provided no correct figures in the computed solutions until linear algebra techniques of the type to be used in this proposal were brought into play in the underlying quadratic (degree 2) eigenvalue problem (see the cover article in SIAM News, Nov. 2004).The standard way of solving the PEP is by converting the problem to a degree 1 eigenvalue problem of larger dimension---the process of linearization. This is almost invariably done using a linearization having the well known companion matrix form, but this is just one of many possible linearizations. In very recent work three vector spaces of linearizations have been studied that generalize the companion form and which provide a systematic way of generating a wide class of linearizations. These spaces make it possible to identify linearizations having specific properties such as optimal conditioning, optimal backward error bounds and preservation of structure such as symmetry. Our recent work has already shown that these new linearizations can produce numerical solutions of significantly better quality than the companion form.This project aims to develop new algorithms for solving the PEP by linearization that have substantially better accuracy and stability properties than those currently used in practice, and which take full advantage of structural properties such as symmetry and definiteness. The work will involve the development of new theory, including backward error bounds for the new spaces of linearizations, the study of a new eigenvector recovery formula, and the study of hyperbolic polynomials and their definite linearizations. (The hyperbolic polynomials are a subset of those that are symmetric and have real eigenvalues, and they are common in engineering applications, including in overdamped mechanical sytems.) An important output of the work will be algorithms that can serve as the basis for library software, since at present there is no standard library software for solving the PEP.