Structured backward error analysis of linearized structured polynomial eigenvalue problems

Abstract. We start by introducing a new class of structured matrix polynomials, namely, the class of MA-structured matrix polynomials, to provide a common framework for many classes of structured matrix polynomials that are important in applications: the classes of (skew-)symmetric, (anti-) palindromic, and alternating matrix polynomials. Then, we introduce the families of MA-structured strong block minimal bases pencils and of MAstructured block Kronecker pencils, which are particular examples of block minimal bases pencils recently introduced by Dopico, Lawrence, P´erez and Van Dooren, and show that any MA-structured odd-degree matrix polynomial can be strongly linearized via an MA-structured block Kronecker pencil. Finally, for the classes of (skew-)symmetric, (anti-)palindromic, and alternating odd-degree matrix polynomials, the MA-structured framework allows us to perform a global and structured backward stability analysis of complete structured polynomial eigenproblems, regular or singular, solved by applying to a MA-structured block Kronecker pencil a structurally backward stable algorithm that computes its complete eigenstructure, like the palindromicQR algorithm or the structured versions of the staircase algorithm. This analysis allows us to identify those MA-structured block Kronecker pencils that yield a computed complete eigenstructure which is the exact one of a slightly perturbed structured matrix polynomial. These pencils include (modulo permutations) the well-known block-tridiagonal and block-anti-tridiagonal structure-preserving linearizations. Our analysis incorporates structure to the recent (unstructured) backward error analysis performed for block Kronecker linearizations by Dopico, Lawrence, P´erez and Van Dooren, and share with it its key features, namely, it is a rigorous analysis valid for finite perturbations, i.e., it is not a first order analysis, it provides precise bounds, and it is valid simultaneously for a large class of structure-preserving strong linearizations.