The classical approach to investigating polynomial eigenvalue problems is linearization, where the
polynomial is converted into a larger matrix pencil with the same eigenvalues. For any polynomial there are infinitely
many linearizations with widely varying properties, but in practice the companion forms are typically used. However,
these companion forms are not always entirely satisfactory, and linearizations with special properties may sometimes
be required.
In this paper we develop a systematic approach to generating large classes of linearizations for matrix polynomials.
Given a polynomial P, we show how to simply construct two vector spaces of pencils that generalize the companion
forms of P, and prove that almost all of these pencils are linearizations for P. Eigenvectors of these pencils are
shown to be closely related to those of P. A distinguished subspace is then isolated, and the special properties of
these pencils are investigated. These spaces of pencils provide a convenient arena in which to look for structured
linearizations of structured polynomials, as well as to try to optimize the conditioning of linearizations, issues to be
addressed in further work.
Palindromic polynomial eigenvalue problems and related classes of structured eigenvalue problems are
considered. These structures generalize the concepts of symplectic and Hamiltonian matrices to matrix polynomials.
We discuss several applications where these matrix polynomials arise, and show how linearizations can be derived that
re
ect the structure of all these structured matrix polynomials and therefore preserve symmetries in the spectrum.
Numerical methods for palindromic eigenvalue problems: Computing the anti-triangular Schur form
(2007)
We present structure-preserving numerical methods
for complex palindromic polynomial eigenvalue problems
via corresponding palindromic linearizations.
A key ingredient is the development of an appropriate condensed form ---
the anti-triangular Schur form.
Ill-conditioned problems which have eigenvalues near the unit circle,
in particular near +/-1, are discussed.
We show how a combination of unstructured methods
followed by a structured refinement can be used
to solve such problems very accurately.
The asymptotic convergence behavior of cyclic versions of the nonsymmetric Jacobi algorithm for the
computation of the Schur form of a general complex matrix is investigated.
Similar to the symmetric case, the nonsymmetric Jacobi algorithm proceeds by applying a
sequence of rotations that annihilate a pivot element in the strict lower triangular
part of the matrix until convergence to the Schur form of the matrix is
achieved.
In this paper, it is shown that the cyclic nonsymmetric Jacobi method converges
locally and asymptotically quadratically under mild hypotheses if special ordering
schemes are chosen, namely ordering schemes that lead to so-called northeast directed sweeps.
The theory is illustrated by the help of numerical experiments. In particular, it is shown that
there are ordering schemes that lead to asymptotic quadratic convergence for the cyclic symmetric
Jacobi method, but only to asymptotic linear convergence for the cyclic nonsymmetric
Jacobi method. Finally, a generalization of the nonsymmetric Jacobi method
to the computation of the Hamiltonian Schur form for Hamiltonian matrices is introduced
and investigated.
The classical singular value decomposition for a matrix $A\in\Cmn$ is a
canonical form for $A$ that also displays the eigenvalues
of the Hermitian matrices $AA^\ast$ and $A^\ast A$. In this paper, we develop
a corresponding decomposition for $A$ that provides the Jordan canonical forms
for the complex symmetric matrices $AA^T$ and $A^TA$. More generally, we consider
the matrix triple $(A,G_1,G_2)$, where $G_1\in\CC{m}, G_2\in\CC{n}$
are invertible and either complex symmetric and complex skew-symmetric, and we
provide a canonical form under transformations of the form
$(A,G_1,G_2)\mapsto(X^T A Y, X^T G_1X, Y^T G_2Y)$, where $X,Y$ are nonsingular.
We study the perturbation theory of structured matrices under structured
rank one perturbations, with emphasis on matrices that are unitary, orthogonal, or symplectic
with respect to an indefinite inner product. The rank one perturbations are not necessarily of
arbitrary small size (in the sense of norm).
In the case of sesquilinear forms, results on selfadjoint matrices can be applied to
unitary matrices by using the Cayley transformation, but
in the case of real or complex symmetric or skew-symmetric bilinear forms
additional considerations are necessary. For complex symplectic matrices, it turns out that
generically (with respect to the perturbations) the behavior of the Jordan form of the
perturbed matrix follows the pattern established earlier for unstructured matrices and their unstructured perturbations, provided the specific properties of the Jordan
form of complex symplectic matrices are accounted for. For instance,
the number of Jordan blocks of fixed odd size corresponding to the eigenvalue $1$ or $-1$ have to be even.
For complex orthogonal matrices, it is shown that the behavior of
the Jordan structures corresponding to the original eigenvalues that are not moved by
perturbations follows again the pattern established earlier for unstructured matrices,
taking into account the specifics of Jordan forms of complex orthogonal
matrices.
The proofs are based on general results developed in the paper concerning Jordan forms of
structured matrices (which include in particular the classes of orthogonal and symplectic matrices)
under structured rank one perturbations. These results are presented and proved in the framework of
real as well as of complex matrices.
Structured eigenvalue backward errors of matrix pencils and polynomials with palindromic structures
(2014)
We derive formulas for the backward error of an approximate eigenvalue of a *-palindromic
matrix polynomial with respect to *-palindromic perturbations. Such formulas are also obtained
for complex T-palindromic pencils and quadratic
polynomials. When the T-palindromic polynomial is real, then we derive the backward error
of a real number considered as an approximate eigenvalue of the matrix polynomial with
respect to real T-palindromic perturbations.
In all cases the corresponding minimal structure preserving perturbations are obtained as well.
The results are illustrated by numerical experiments. These show that there is
significant difference between the backward errors with respect to structure
preserving and arbitrary perturbations in many cases.
An eigenvalue perturbation theory under rank-one perturbations is developed for classes
of real matrices that are symmetric with respect to a non-degenerate bilinear form,
or Hamiltonian with respect to a non-degenerate skew-symmetric form.
In contrast to the case of complex matrices, the sign characteristic is a crucial feature
of matrices in these classes. The behavior of the sign characteristic under generic
rank-one perturbations is analyzed in each of these two classes of matrices.
Partial results are presented, but some questions remain open. Applications
include boundedness and robust boundedness for solutions of structured systems
of linear differential equations with respect to general perturbations as well
as with respect to structured rank perturbations of the coefficients.
We derive a formula for the backward error of a complex number $\lambda$ when considered as an approximate eigenvalue
of a Hermitian matrix pencil or polynomial with respect to Hermitian perturbations. The same are also obtained for approximate
eigenvalues of matrix pencils and polynomials with related structures like skew-Hermitian, $*$-even and $*$-odd.
Numerical experiments suggest that in many cases there is a significant difference between the backward
errors with respect to perturbations that preserve structure and those with respect to arbitrary perturbations.
This paper deals with the effect of generic but structured low rank perturbations on the Jordan structure and sign
characteristic of matrices that have structure in an indefinite inner product space.
The paper is a follow-up of earlier papers in which the effect of rank one perturbations
was considered. Several results that are in contrast to the case of unstructured low rank
perturbations of general matrices are presented here.