## Publication: Generalized companion forms for scalar and matrix polynomials

Loading...

##### Identifiers

##### Publication date

2020-09

##### Defense date

2020-09-29

##### Authors

##### Advisors

##### Tutors

##### Journal Title

##### Journal ISSN

##### Volume Title

##### Publisher

##### 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.

##### Description

Mención Internacional en el título de doctor

##### Keywords

Companion matrix, Companion pencil, Linearization, Sparsity, Scalar polynomial, Matrix polynomial