Generalized companion forms for scalar and matrix polynomials

Abstract

Matrix polynomials arise frequently associated with Polynomial Eigenvalue Problems (PEPs). The standard way to solve PEPs is by means of (strong) linearizations, which are matrix pencils (namely, matrix polynomials of grade 1), that allow to recover the relevant spectral information of the PEP in a relatively simple way, using appropiate algorithms. Any matrix polynomial has infinitely many linearizations. One way to construct such linearizations is by means of symbolic constructions (involving no arithmetic operations) consisting of block-partitioned pencils whose blocks contain the coeficients of the matrix polynomial. (Generalized) companion forms are exactly particular cases of such constructions. In particular, the central notion in this thesis is the notion of (generalized) companion forms (of grade ℓ) of matrix polynomials. To abbreviate, we refer to “(generalized) companion forms" when ℓ = 1 (that is, when they are matrix pencils). One of the properties of (generalized) companion forms (of grade ℓ), we are especially interested in is the sparsity. Sparse (generalized) companion forms (of grade ℓ) are those having the smallest possible number of nonzero entries. This notion is interesting from the point of view of the simplicity in the construction, and it may have some relevance from the numerical point of view. We are also interested in structured (generalized) companion forms (of grade ℓ), that is, companion forms that preserve some of the structures that matrix polynomials frequently present in applications. The most relevant structures are the (skew-)symmetric, (skew)-Hermitian, (anti-)palindromic and alternating structures. These structures correspond to certain symmetries in the entries of the coefficients of the matrix polynomial, and in turn imply some symmetries in their spectral information. To compute this spectral information is the main goal of the PEPs. Therefore, to preserve the symmetries in the block entries of the matrix polynomial is key in the whole process, in order to avoid that, due to numerical errors, the symmetries in the spectrum are lost, which would lead to meaningless results. This is the motivation behind searching for structured (generalized) companion forms, even though we do not deal with numerical issues in this part of the thesis. This dissertation consists of three parts. The first one is devoted to introduce a wide family of quasi-sparse companion forms (which have a small number of nonzero entries, although not necessarily the smallest one) for arbitrary square matrix polynomials, expressed in the monomial basis, which includes all the quasi-sparse companion forms known so far (the Fiedler-like families and the recent block-Kronecker linearizations), and which extends the class of “companion matrix patterns" introduced in [58] for monic scalar polynomials. In addition, a thorough study of the sparsity of companion forms in this new family is carried out. This first part also includes a theoretical analysis of generalized companion forms. In particular, we introduce a new notion of generalized companion forms for matrix polynomials expressed in the monomial basis. This definition is quite general and extends the notions of companion form in [41], generalized companion matrix in [68], and Ma-Zhan companion matrix in [100], as well as the previous class of quasisparse companion forms. Then, we analyze some algebraic properties of generalized companion pencils as well as the sparsity of these constructions (by imposing some natural conditions on their entries). The second part of this thesis is related to structured (generalized) companion forms of matrix polynomials, expressed in the monomial basis. It is well known that is not possible to construct companion forms that preserve any of the structures mentioned before for matrix polynomials of even degree. This motivates the search for more general companion forms, in particular (generalized) companion forms of grade ℓ (for ℓ > 1). These constructions are strong ℓ-ifications and, like (generalized) companion forms, they are constructed in a symbolic way containing the coeficients of the polynomial. The term “structured" here means that these companion forms preserve the structure of the polynomial (that is, the matrix polynomial and its ℓ-ification have the same structure). Then, we present, for the first time, a family of structured (generalized) companion forms of grade ℓ, that preserve any of the structures mentioned before, for matrix polynomials of grade k = sℓ, with s being an odd number, extending recent works (such as [55, 56]), and we give a procedure to obtain sparse ℓ-ifications within this family. Finally, we prove that there are no structured companion quadratifications for quartic matrix polynomials. The third part of this thesis focuses on matrix polynomials expressed in a Lagrange(-like) basis. Matrix polynomials expressed in non-monomial bases are more natural for certain applications than those expressed in the monomial basis and, when we aim to solve the PEP, it is important to avoid reformulating the matrix polynomial into the monomial basis (because this may introduce numerical errors in the computation). Then, this part is focused on new contributions regarding polynomials in non-monomial bases, specifically for the Lagrange basis. In this part, we develop both a numerical and a theoretical analysis. First, regarding the numerical analysis, we perform a first-order backward error analysis of the PEP solved by applying a certain linearization of a matrix polynomial (expressed in the Lagrange basis). More precisely, we obtain that, if the matrix polynomial is suitably scaled, then we get a good backward stability (to first order) from the polynomial point of view when the linearization is combined with a backward stable method for computing the spectral information of the matrix polynomial. Regarding the theoretical analysis, this third part is also devoted to present a family of structured strong linearizations for matrix polynomials of odd grade k, expressed in a Lagrange(-like) basis, which enables the preservation of the spectral symmetries for the matrix polynomial.