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)
The numerical simulation of the band structure of three-dimensional dispersive metallic photonic crystals with face-centered cubic lattices leads to large-scale nonlinear eigenvalue problems, which are very challenging due to a high dimensional subspace associated with the eigenvalue zero and the fact that the desired eigenvalues (with smallest real part) cluster near the zero eigenvalues. For
the solution of the eigenvalue problem, a Newton-type iterative method is proposed and the nullspace-free method is applied to exclude the zero eigenvalues from the associated generalized eigenvalue problem. To find the successive eigenvalue/eigenvector pairs, we propose a new non-equivalence deflation method to transform converged eigenvalues to infinity, while all other eigenvalues remain unchanged. The deflated problem is then solved by the same Newton-type method, which uses a hybrid method that combines the Jacobi-Davidson, the shift-invert residual Arnoldi and nonlinear Arnoldi methods to compute the clustered eigenvalues. Numerical results illustrate that the method is robust even for the case of computing many eigenvalues in very large problems.
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.
For regular matrix pencils the distance in norm to the nearest singular pencil
under low rank perturbation is studied. Characterizations of this distance are derived via the Weyl function of the perturbation. Special attention is paid to the Hermitian pencil case.
Estimates for the distance of a given pencil to the set of singular pencils are obtained.
When simulating isolated resonators, the application of transparent boundary conditions causes the approximated spectrum to be polluted with spurious solutions. Distinguishing these artificial solutions from solutions with a physical meaning is often difficult and requires a priori knowledge of the spectrum or the expected field distribution of resonant states. We present an implementation of the pole condition that distinguishes between incoming and outgoing waves by the location of the poles of their Laplace transform as transparent boundary condition. This implementation depends on one tuning parameter. We will use the sensitivity of the computed solutions to perturbations of this parameter as a means to identify spurious solutions. To obtain global statements, we will combine this technique with a convergence monitor for the boundary condition.
New perturbation results for the behavior of eigenvalues and Jordan forms of real and complex matrices
under generic rank one perturbations are discussed. Several results that are available in the complex
case are proved as well for the real case and the assumptions on the genericity are weakened.
Rank one perturbations that lead to maximal algebraic multiplicities of the ``new" eigenvalues are also
discussed.
We discuss the numerical solution of large scale nonlinear eigenvalue problems and frequency
response problems that arise in the analysis, simulation and optimization of acoustic fields.
We report about the cooperation with the company SFE in Berlin. We present the challenges
in the current industrial problems and the state-of-the-art of current methods. The difficulties
that arise with current off-the-shelf methods are discussed and several industrial examples are presented. It is documented that industrial cooperation is by no means a one-way street
of transfer from academia to industry but the challenges arising in industrial practice also lead to new mathematical questions which actually change the mathematical theory and methods.
We discuss the perturbation analysis for
eigenvalues and eigenvectors of structured homogeneous matrix polynomials with
Hermitian, skew-Hermitian, H-even and H-odd structure.
We construct minimal structured perturbations (structured backward errors) such that an
approximate eigenpair is an exact eigenpair of an appropriate perturbed structured matrix
polynomial. We present various comparisons with unstructured backward
errors and previous error bounds derived for the non-homogeneous case
and show that our bounds present a significant improvement.
Many applications give rise to matrix polynomials whose coefficients have
a kind of reversal symmetry, a structure we call palindromic.
Several properties of scalar palindromic polynomials are derived,
and together with properties of compound matrices, used to
establish the Smith form of regular and singular T-palindromic matrix polynomials,
over arbitrary fields.
The invariant polynomials are shown to
inherit palindromicity,
and their structure is described in detail.
Jordan structures of palindromic matrix polynomials are characterized,
and necessary conditions for the
existence of structured linearizations established.
In the odd degree case, a constructive procedure for building
palindromic linearizations shows that the necessary conditions are sufficient as well.
The Smith form for *-palindromic polynomials is also analyzed. Finally, results for palindromic matrix polynomials over fields of
characteristic two are presented.
In this work we propose a general framework for the structured perturbation
analysis of several classes of structured matrix polynomials in homogeneous
form, including complex symmetric, skew-symmetric, even and odd matrix polynomials. We introduce structured backward errors for approximate eigenvalues and eigenvectors and we construct minimal structured perturbations such that an approximate eigenpair is an exact eigenpair of an appropriately perturbed matrix polynomial. This work extends previous work for the non-homogeneous case (we include infinite eigenvalues) and we show that the structured backward errors improve the known unstructured backward errors.
A new implicitly-restarted Krylov subspace method
for real symmetric/skew-symmetric generalized eigenvalue problems
is presented. The new method improves and generalizes the SHIRA method
to the case where the skew symmetric matrix is singular.
It computes a few eigenvalues and eigenvectors of the matrix pencil
close to a given target point. Several applications from control theory are
presented and the properties of the new method are illustrated by benchmark
examples.
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.