Algorithms and theory for polynomial eigenproblems

In this thesis we develop new theoretical and numerical results for matrix polynomials and polynomial eigenproblems. This includes the cases of standard and generalized eigenproblems. Two chapters concern quadratic eigenproblems $(M\lambda^2+D\lambda+K)x=0$, where $M$, $D$ and $K$ enjoy special properties that are commonly encountered in modal analysis. We discuss this application in some detail, in particular the mathematics behind discrete dampers. We show how the physical intuition of a damper that gets stronger and stronger can be mathematically proved using matrix analysis. We then develop an algorithm for quadratic eigenvalue problems with low rank damping, which outperforms existing algorithm both in terms of speed and accuracy. The first part of our algorithm requires the solution of a generalized eigenproblem with semidefinite coefficient matrices. To solve this problem we develop a new algorithm based on an algorithm proposed by Wang and Zhao [SIAM J. Matrix Anal. Appl. 12-4 (1991), pp. 654--660]. The new algorithm computes all eigenvalues in a backward stable and symmetry preserving manner. The next two chapters are about equivalences of matrix polynomials. We show, for an algebraically closed field $\mathbb{F}$, that any matrix polynomial $P(\lambda)\in\mathbb{F}[\lambda]^{n\times m}$, $n\leq m$, can be reduced to triangular form, while preserving the degree and the finite and infinite elementary divisors. We then show that the same result holds for real matrix polynomials if we replace ``triangular'' with ``quasi-triangular,'' that is, block-triangular with diagonal blocks of size $1\times 1$ and $2 \times 2$. The proofs are constructive in the sense that we build up triangular and quasi-triangular matrix polynomials starting the Smith form. In this sense we are solving structured inverse problems. In particular, our results imply that the necessary constraints that make list of elementary divisors admissible for a real square matrix polynomial of degree $\ell$ are also sufficient conditions. For the case of matrix polynomials with invertible leading coefficients, we show how triangular/quasi-triangular forms, as well as diagonal and Hessenberg forms, can be computed numerically. Finally, we present a backward error analysis of the shift-and-invert Arnoldi algorithm for matrices. This algorithm is also of interest to polynomial eigenproblems with easily constructible monic linearizations. The analysis shows how errors from the linear system solves and orthonormalization process affect the Arnoldi recurrence. Residual bounds for linear systems and columnwise backward error bounds for QR factorizations come to play, so we discuss these in some detail. The main result is a set of backward error bounds that can be estimated cheaply. We also use our error analysis to define a sensible condition for ``breakdown,'' that is, a condition for when the Arnoldi iteration should be stopped