A block-symmetric linearization of odd degree matrix polynomials with optimal eigenvalue condition number and backward error

Abstract

The standard way of solving numerically a polynomial eigenvalue problem (PEP) is to use a linearization and solve the corresponding generalized eigenvalue problem (GEP). In addition, if the PEP possesses one of the structures arising very often in applications, then the use of a linearization that preserves such structure combined with a structured algorithm for the GEP presents considerable numerical advantages. Block-symmetric linearizations have proven to be very useful for constructing structured linearizations of structured matrix polynomials. In this scenario, we analyze the eigenvalue condition numbers and backward errors of approximated eigenpairs of a block symmetric linearization that was introduced by Fiedler (Linear Algebra Appl 372:325-331, 2003) for scalar polynomials and generalized to matrix polynomials by Antoniou and Vologiannidis (Electron J Linear Algebra 11:78-87, 2004). This analysis reveals that such linearization has much better numerical properties than any other block-symmetric linearization analyzed so far in the literature, including those in the well known vector space of block-symmetric linearizations. The main drawback of the analyzed linearization is that it can be constructed only for matrix polynomials of odd degree, but we believe that it will be possible to extend its use to even degree polynomials via some strategies in the near future.