Linearizations for Interpolatory Bases - a Comparison: New Families of Linearizations

One strategy to solve a nonlinear eigenvalue problem $T(\lambda)x=0$ is to solve a polynomial eigenvalue problem (PEP) $P(\lambda)x=0$ that approximates the original problem through interpolation. Then, this PEP is usually solved by linearization. Because of the polynomial approximation techniques, in this context, $P(\lambda)$ is expressed in a non-monomial basis. The bases used with most frequency are the Chebyshev basis, the Newton basis and the Lagrange basis. Although, there exist already a number of linearizations available in the literature for matrix polynomials expressed in these bases, new families of linearizations are introduced because they present the following advantages: 1) they are easy to construct from the matrix coefficients of $P(\lambda)$ when this polynomial is expressed in any of those three bases; 2) their block-structure is given explicitly; 3) it is possible to provide equivalent formulations for all three bases which allows a natural framework for comparison. Also, recovery formulas of eigenvectors (when $P(\lambda)$ is regular) and recovery formulas of minimal bases and minimal indices (when $P(\lambda)$ is singular) are provided. The ultimate goal is to use these families to compare the numerical behavior of the linearizations associated to the same basis (to select the best one) and with the linearizations associated to the other two bases, to provide recommendations on what basis to use in each context. This comparison will appear in a subsequent paper.