  We introduce a new class of structured matrix polynomials, namely, the class
of M_A-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 M_A-structured strong block
minimal bases pencils and of M_A-structured block Kronecker pencils,, and show
that any M_A-structured odd-degree matrix polynomial can be strongly linearized
via an M_A-structured block Kronecker pencil. Finally, for the classes of
(skew-)symmetric, (anti-)palindromic, and alternating odd-degree matrix
polynomials, the M_A-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 an M_A-structured
block Kronecker pencil a structurally backward stable algorithm that computes
its complete eigenstructure, like the palindromic-QR algorithm or the
structured versions of the staircase algorithm. This analysis allows us to
identify those M_A-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-antitridiagonal 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.
