15A18 Eigenvalues, singular values, and eigenvectors
Refine
Language
- English (24)
Keywords
- eigenvalues (4)
- matrix polynomial (3)
- nonlinear eigenvalue problem (3)
- $\mu$-values (2)
- Hamiltonian matrix (2)
- Smith form (2)
- backward error (2)
- condition numbers (2)
- matrix pencil (2)
- palindromic eigenvalue problem (2)
Alternating matrix polynomials, that is, polynomials whose coefficients
alternate between symmetric and skew-symmetric matrices,
generalize the notions of even and odd scalar polynomials.
We investigate the Smith forms of alternating matrix polynomials,
showing that each invariant factor is an even or odd scalar polynomial.
Necessary and sufficient conditions
are derived for a given Smith form to be that of an alternating matrix polynomial.
These conditions allow a characterization of the possible Jordan structures
of alternating matrix polynomials,
and also lead to necessary and sufficient conditions
for the existence of structure-preserving strong linearizations.
Most of the results are applicable to singular as well
as regular matrix polynomials.
In this paper we study the shape and growth of structured pseudospectra
for small matrix perturbations of the form $A \leadsto
A_\Delta=A+B\Delta C$, $\Delta \in \DD$, $\|\Delta\|\leq \delta$.
It is shown that the properly scaled pseudospectra components converge
to non-trivial limit sets as $\delta$ tends to 0.
We discuss the relationship of these limit sets with $\mu$-values and
structured eigenvalue condition numbers for multiple eigenvalues.
In many applications such as data compression, imaging or
genomic data analysis,
it is important to approximate a given $m\times n$ matrix $A$
by a matrix $B$ of rank at most $k$ which is much smaller than $m$ and $n$.
The best rank $k$ approximation can be determined via
the singular value decomposition
which, however, has prohibitively
high computational complexity and storage requirements
for very large $m$ and $n$.
We present an optimal least squares algorithm for computing a rank $k$
approximation to an $m\times n$ matrix $A$ by reading
only a limited number of rows and columns of $A$.
The algorithm has complexity $\mathcal O(k^2\max(m,n))$ and
allows to iteratively improve given rank $k$
approximations by reading additional rows and
columns of $A$. We also show how this approach can be extended
to tensors and present numerical results.
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.
Let $\lambda$ be a nonderogatory eigenvalue of $A \in \C^{n \times
n}$. The sensitivity of $\lambda$ with respect to matrix
perturbations
$A \leadsto A+\Delta,\Delta \in \DD$, is measured by the structured
condition number $\kappa_\DD(A,\lambda)$. Here $\DD$ denotes the set
of admissible perturbations. However, if $\DD$ is not a vector space
over $\C$ then $\kappa_\DD(A,\lambda)$ provides only incomplete
information about the mobility of $\lambda$ under small
perturbations from $\DD$. The full
information is then given by a certain set $K_\DD(x,y)\subset \C$
which depends on $\DD$ and
a pair of normalized right and left eigenvectors $x,y$. In this paper
we study the sets $K_\DD(x,y)$ and obtain methods for computing
them.
In particular we show that $K_\DD(x,y)$ is an ellipse in some
important cases.
$\mu$-values and spectral value sets for linear perturbation classes defined by a scalar product
(2007)
We study the variation of the spectrum of matrices
under perturbations which are self- or skew-adjoint
with respect to a scalar product.
Computable formulae are given for the associated
$\mu$-values. The results can be used to calculate spectral value
sets for the perturbation classes under consideration.
We discuss the special case of
complex Hamiltonian perturbations of a Hamiltonian matrix in detail.
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.
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.
Structured eigenvalue conditioning and backward error of a class of polynomial eigenvalue problems
(2007)
Characterisations of simple eigenvalues of complex matrix polynomials with *-even/odd and *-palindromic/antipalindromic structures that have the same normwise condition number with respect to structure preserving and arbitrary perturbations are obtained. Here * denotes either the transpose T or the conjugate tranpose *. In the process we obtain formulae for the normwise structured condition number of simple eigenvalues of T-palindromic/antipalindromic and *-even/odd polynomials. Moreover, conditions under which the normwise structured backward error of approximate eigenvalues of such polynomials is equal to the unstructured error are also derived. These lead to complete characterisations of approximate eigenvalues that have the same structured and unstructured backward errors for the *-even/odd and T-even/odd polynomials.
In this paper we consider structure-preserving model reduction of
second-order systems using a~ba\-lan\-ced truncation approach.
Several sets of singular values are introduced for such systems,
which lead to different concepts of balancing and different
second-order balanced truncation methods. We compare the
properties of these methods on numerical examples.
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.
Being one of the key tools in conformation dynamics, the identification of
meta-stable states of Markov chains has been subject to extensive research in
recent years, especially when the Markov chains represent energy states of biomolecules. Some previous work on this topic involved the computation
of the eigenvalue cluster close to one, as well as the corresponding
eigenvectors and the stationary probability distribution of the associated stochastic
matrix. Later, since the eigenvalue cluster algorithm turned out to be non-robust, an optimisation approach was developed. As a possible less costly alternative, we present an SVD approach to identifying
meta-stable states of a stochastic matrix, where we only need
the second largest singular vector. We outline some theoretical background
and discuss the advantages of this strategy. Some simulated and real
numerical examples illustrate the effectiveness of the proposed algorithm.
We present a new extension of the well-known
Perron-Frobenius theorem to regular matrix pairs $(E,A)$.
The new extension is based on projector chains and is motivated from
the solution of positive differential-algebraic systems or descriptor
systems. We present several examples where the new condition holds, whereas conditions
in previous literature are not satisfied.
Perturbation of Purely Imaginary Eigenvalues of Hamiltonian Matrices under Structured Perturbations
(2007)
We discuss the perturbation theory for purely imaginary eigenvalues of Hamiltonian matrices under Hamiltonian and non-Hamiltonian perturbations. We
show that there is a substantial difference in the behavior under these perturbations. We also discuss the perturbation of real eigenvalues of real
skew-Hamiltonian matrices under structured perturbations and use these results to analyze the properties of the URV method of computing the
eigenvalues of Hamiltonian matrices.