15A23 Factorization of matrices
Refine
Language
- English (4)
Keywords
- palindromic eigenvalue problem (3)
- canonical form (2)
- (even eigenvalue problem (1)
- Hessenberg matrix (1)
- QR algorithm (1)
- URV decomposition (1)
- bulge chasing (1)
- bulge exchange (1)
- congruence (1)
- convergence theory) (1)
Project
- C4 (4)
Application Area
- C (4)
In the spirit of the Hamiltonian QR algorithm and other bidirectional chasing algorithms, a structure-preserving variant of the implicit QR algorithm for palindromic eigenvalue problems is proposed.
This new palindromic QR algorithm is strongly backward stable and requires less operations than the standard QZ algorithm, but
is restricted to matrix classes where a preliminary reduction to structured Hessenberg form can be performed. By an extension of the
implicit Q theorem, the palindromic QR algorithm is shown to be equivalent to a previously developed explicit version.
Also, the classical convergence theory for the QR algorithm can be extended to prove local quadratic convergence.
We briefly demonstrate how even eigenvalue problems can be addressed by similar techniques.
In this paper we develop a QR-like algorithm for the palindromic eigenvalue problem $Ax=\lambda A^\adj x$.
We will discuss the two cases that $A^\adj$ denotes the transpose or the conjugate transpose of $A\in\C^{n,n}$.
It is shown that this so-called palindromic QR iteration is equivalent to applying the standard QR algorithm to $A^{-\adj}A$.
Also the concepts of deflation, shifting, and exploiting the invariance of a Hessenberg-type form are adapted.
Moreover, we analyze the problem of reducing a general square matrix to the mentioned Hessenberg-type form
and establish analogies to the Hamiltonian eigenvalue problem.
Finally, we present concrete Hessenberg-type reduction algorithms for special cases.
In this work numerical methods for the solution of two classes of structured generalized eigenvalue problems, $Ax=\lambda Bx$, are developed. Those classes are the palindromic ($B=A^T$) and the even ($A=A^T$, $B=-B^T$) eigenvalue problems.
The spectrum of these problems is not arbitrary, rather do eigenvalues occur in pairs.
We will construct methods for palindromic and even eigenvalue problems that are of cubic complexity and that are guaranteed to produce eigenvalues that are paired to working precision.
At the heart of both methods is a new URV-type matrix decomposition, that simultaneously transforms three matrices to skew triangular form, i.e., to a form that is triangular with respect to the Northeast-Southwest diagonal.
The algorithm to compute this URV decomposition uses several other methods to reduce a single square matrix to skew triangular form: the skew QR factorization and the skew QRQ$^T$ decomposition. Moreover, a method to compute the singular value decomposition of a complex, skew symmetric matrix is presented and used.
We consider real or complex palindromic pencils, i.e., pencils of the form $A-\lambda A^\star$,
where $A^{\star}$ denotes either the transpose $A^T$ or the conjugate transpose $A^*$.
Structured canonical forms for these pencils are derived that reveal complete spectral information.
Moreover, this canonical form is used to provide necessary and sufficient conditions for the existence of palindromic factorizations $B=A^{-\star}A$ of a given square matrix $B$.
In particular, we answer the questions when symplectic matrices allow palindromic factorization and when a matrix having a palindromic factorization is similar to a symplectic one.