Eigenvalue perturbation theory of symplectic,orthogonal, and unitary matrices under generic structured rank one perturbations

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.     

Eigenvalue perturbation theory of classes of structured matrices under generic structured rank one perturbations

udy the perturbation theory of structured matrices under structured rank one perturbations, and then focus on several classes of complex matrices. Generic Jordan structures of perturbed matrices are identified. It is shown that the perturbation behavior of the Jordan structures in the case of singular J-Hamiltonian matrices is substantially different from the corresponding theory for unstructured generic rank one perturbation as it has been studied in [18, 28, 30, 31]. Thus a generic structured perturbation would not be generic if considered as an unstructured perturbation. In other settings of structured matrices, the generic perturbation behavior of the Jordan structures, within the confines imposed by the structure, follows the pattern of that of unstructured perturbations.     

A note on structured pseudospectra

In this note, we study the notion of structured pseudospectra. We prove that for Toeplitz, circulant, Hankel and symmetric structures, the structured pseudospectrum equals the unstructured pseudospectrum. We show that this is false for Hermitian and skew-Hermitian structures. We generalize the result to pseudospectra of matrix polynomials. Indeed, we prove that the structured pseudospectrum equals the unstructured pseudospectrum for matrix polynomials with Toeplitz, circulant, Hankel and symmetric structures. We conclude by giving a formula for structured pseudospectra of real matrix polynomials. The particular type of perturbations used for these pseudospectra arise in control theory.     

Computation of Pseudospectra by Spectral Dichotomy Methods in a Parallel Environment

The standard methods for computing pseudospectra of matrices are based on the computation of the smallest singular value on each point of the domain of interest, which must be discretized beforehand. A different approach consists of determining the different regions that constitute the pseudospectrum and computing the spectral projector associated with each region. The determination of these regions and the computation of the corresponding projectors use the spectral dichotomy methods. We briefly recall these methods and propose a parallel version with performance results obtained on CRAY T3E parallel machine.     

When is a matrix unitary or Hermitian plus low rank?

Hermitian and unitary matrices are two representatives of the class of normal matrices whose full eigenvalue decomposition can be stably computed in quadratic computing complexity once the matrix has been reduced, for instance, to tridiagonal or Hessenberg form. Recently, fast and reliable eigensolvers dealing with low‐rank perturbations of unitary and Hermitian matrices have been proposed. These structured eigenvalue problems appear naturally when computing roots, via confederate linearizations, of polynomials expressed in, for example, the monomial or Chebyshev basis. Often, however, it is not known beforehand whether or not a matrix can be written as the sum of a Hermitian or unitary matrix plus a low‐rank perturbation. In this paper, we give necessary and sufficient conditions characterizing the class of Hermitian or unitary plus low‐rank matrices. The number of singular values deviating from 1 determines the rank of a perturbation to bring a matrix to unitary form. A similar condition holds for Hermitian matrices; the eigenvalues of the skew‐Hermitian part differing from 0 dictate the rank of the perturbation. We prove that these relations are linked via the Cayley transform. Then, based on these conditions, we identify the closest Hermitian or unitary plus rank k matrix to a given matrix A, in Frobenius and spectral norm, and give a formula for their distance from A. Finally, we present a practical iteration to detect the low‐rank perturbation. Numerical tests prove that this straightforward algorithm is effective.     

Eigenvalue perturbation theory of structured real matrices and their sign characteristics under generic structured rank-one perturbations

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 behaviour 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.     

Spectra,pseudospectra, and localization for random bidiagonal matrices

There has been much recent interest, initiated by work of the physicists Hatano and Nelson, in the eigenvalues of certain random, non‐Hermitian, periodic tridiagonal matrices and their bidiagonal limits. These eigenvalues cluster along a “bubble with wings” in the complex plane, and the corresponding eigenvectors are localized in the wings, delocalized in the bubble. Here, in addition to eigenvalues, pseudospectra are analyzed, making it possible to treat the nonperiodic analogues of these random matrix problems. Inside the bubble, the resolvent norm grows exponentially with the dimension. Outside, it grows subexponentially in a bounded region that is the spectrum of the infinite‐dimensional operator. Localization and delocalization correspond to resolvent matrices whose entries exponentially decrease or increase, respectively, with distance from the diagonal. This article presents theorems that characterize the spectra, pseudospectra, and numerical range for the four cases of finite bidiagonal matrices, infinite bidiagonal matrices (“stochastic Toeplitz operators”), finite periodic matrices, and doubly infinite bidiagonal matrices (“stochastic Laurent operators”). © 2001 John Wiley & Sons, Inc.     

Eigenvector sensitivity under general and structured perturbations of tridiagonal Toeplitz‐type matrices

The sensitivity of eigenvalues of structured matrices under general or structured perturbations of the matrix entries has been thoroughly studied in the literature. Error bounds are available, and the pseudospectrum can be computed to gain insight. Few investigations have focused on analyzing the sensitivity of eigenvectors under general or structured perturbations. This paper discusses this sensitivity for tridiagonal Toeplitz and Toeplitz‐type matrices.     

Computing the field of values and pseudospectra using the Lanczos method with continuation

The field of values and pseudospectra are useful tools for understanding the behaviour of various matrix processes. To compute these subsets of the complex plane it is necessary to estimate one or two eigenvalues of a large number of parametrized Hermitian matrices; these computations are prohibitively expensive for large, possibly sparse, matrices, if done by use of the QR algorithm. We describe an approach based on the Lanczos method with selective reorthogonalization and Chebyshev acceleration that, when combined with continuation and a shift and invert technique, enables efficient and reliable computation of the field of values and pseudospectra for large matrices. The idea of using the Lanczos method with continuation to compute pseudospectra is not new, but in experiments reported here our algorithm is faster and more accurate than existing algorithms of this type.This work was supported by Engineering and Physical Sciences Research Council grants GR/H/52139 and GR/H/94528.     

Pseudospectra and delay differential equations

In this paper, we present a new method for computing the pseudospectra of delay differential equations (DDEs) with fixed finite delay. This provides information on the sensitivity of eigenvalues under arbitrary perturbations of a given size, and hence insight into how stability may change under variation of parameters. We also investigate how differently weighted perturbations applied to the individual matrices of the delayed eigenvalue problem affect the pseudospectra. Furthermore, we compute pseudospectra of the infinitesimal generator of the DDE, from which a lower bound on the maximum transient growth can be inferred. To illustrate our method, we consider a DDE modelling a semiconductor laser subject to external feedback.     

Spectral conditioning and pseudospectral growth

Using the language of pseudospectra, we study the behavior of matrix eigenvalues under two scales of matrix perturbation. First, we relate Lidskii’s analysis of small perturbations to a recent result of Karow on the growth rate of pseudospectra. Then, considering larger perturbations, we follow recent work of Alam and Bora in characterizing the distance from a given matrix to the set of matrices with multiple eigenvalues in terms of the number of connected components of pseudospectra. J. V. Burke’s research was supported in part by National Science Foundation Grant DMS-0505712. A. S. Lewis’s research was supported in part by National Science Foundation Grant DMS-0504032. M. L. Overton’s research was supported in part by National Science Foundation Grant DMS-0412049.     

Towards an optimal condition number of certain augmented Lagrangian‐type saddle‐point matrices

We present an analysis for minimizing the condition number of nonsingular parameter‐dependent 2 × 2 block‐structured saddle‐point matrices with a maximally rank‐deficient (1,1) block. The matrices arise from an augmented Lagrangian approach. Using quasidirect sums, we show that a decomposition akin to simultaneous diagonalization leads to an optimization based on the extremal nonzero eigenvalues and singular values of the associated block matrices. Bounds on the condition number of the parameter‐dependent matrix are obtained, and we demonstrate their tightness on some numerical examples. Copyright © 2016 John Wiley & Sons, Ltd.     

The structured total least‐squares approach for non‐linearly structured matrices

In this paper, an extension of the structured total least‐squares (STLS) approach for non‐linearly structured matrices is presented in the so‐called ‘Riemannian singular value decomposition’ (RiSVD) framework. It is shown that this type of STLS problem can be solved by solving a set of Riemannian SVD equations. For small perturbations the problem can be reformulated into finding the smallest singular value and the corresponding right singular vector of this Riemannian SVD. A heuristic algorithm is proposed. Some examples of Vandermonde‐type matrices are used to demonstrate the improved accuracy of the obtained parameter estimator when compared to other methods such as least squares (LS) or total least squares (TLS). Copyright © 2002 John Wiley & Sons, Ltd.     

Schur complement‐based domain decomposition preconditioners with low‐rank corrections

This paper introduces a robust preconditioner for general sparse matrices based on low‐rank approximations of the Schur complement in a Domain Decomposition framework. In this ‘Schur Low Rank’ preconditioning approach, the coefficient matrix is first decoupled by a graph partitioner, and then a low‐rank correction is exploited to compute an approximate inverse of the Schur complement associated with the interface unknowns. The method avoids explicit formation of the Schur complement. We show the feasibility of this strategy for a model problem and conduct a detailed spectral analysis for the relation between the low‐rank correction and the quality of the preconditioner. We first introduce the SLR preconditioner for symmetric positive definite matrices and symmetric indefinite matrices if the interface matrices are symmetric positive definite. Extensions to general symmetric indefinite matrices as well as to nonsymmetric matrices are also discussed. Numerical experiments on general matrices illustrate the robustness and efficiency of the proposed approach. Copyright © 2016 John Wiley & Sons, Ltd.     

Structured pseudospectra for nonlinear eigenvalue problems

In this paper we introduce structured pseudospectra for nonlinear eigenvalue problems and derive computable formulae. The results are applied to the sensitivity analysis of the eigenvalues of a second-order system arising from structural dynamics and of a time-delay system arising from laser physics. In the former case, a comparison is made with the results obtained in the framework of random eigenvalue problems.     

Identification of heat transfer dynamics for non-modal analysis of thermoacoustic stability

A systematic approach for non-modal stability analysis of thermoacoustic systems with a localized heat source is proposed. The response of the heat source to flow perturbations is obtained from unsteady computational fluid dynamics combined with correlation-based linear system identification. A model for the complete thermoacoustic system is formulated with a Galerkin expansion technique, where the heat source is included as an acoustically compact element. The eigenvalues of the resulting system are obtained from discretization of the solution operator, the maximum growth factor is estimated from the pseudospectra using Kreiss’ theorem.The approach is illustrated with a simple Rijke tube configuration. Results obtained with a simple “baseline” model for the heat source dynamics based on King’s law - widely used in hot wire anemometry - are compared against the more advanced treatment developed here. Analysis of pseudospectra diagrams shows that the choice of the heat source model does influence the sensitivity of eigenvalues to perturbations and hence the non-normal behavior. The maximum growth factor for the system with the heat source model based on King’s law is more sensitive to changes in the heat source location than the CFD-based heat source model.     

Block‐row Hankel weighted low rank approximation

This paper extends the weighted low rank approximation (WLRA) approach to linearly structured matrices. In the case of Hankel matrices with a special block structure, an equivalent unconstrained optimization problem is derived and an algorithm for solving it is proposed. Copyright © 2005 John Wiley & Sons, Ltd.     

New fast divide‐and‐conquer algorithms for the symmetric tridiagonal eigenvalue problem

In this paper, two accelerated divide‐and‐conquer (ADC) algorithms are proposed for the symmetric tridiagonal eigenvalue problem, which cost O(N²r) flops in the worst case, where N is the dimension of the matrix and r is a modest number depending on the distribution of eigenvalues. Both of these algorithms use hierarchically semiseparable (HSS) matrices to approximate some intermediate eigenvector matrices, which are Cauchy‐like matrices and are off‐diagonally low‐rank. The difference of these two versions lies in using different HSS construction algorithms, one (denoted by ADC1) uses a structured low‐rank approximation method and the other (ADC2) uses a randomized HSS construction algorithm. For the ADC2 algorithm, a method is proposed to estimate the off‐diagonal rank. Numerous experiments have been carried out to show their stability and efficiency. These algorithms are implemented in parallel in a shared memory environment, and some parallel implementation details are included. Comparing the ADCs with highly optimized multithreaded libraries such as Intel MKL, we find that ADCs could be more than six times faster for some large matrices with few deflations. Copyright © 2016 John Wiley & Sons, Ltd.     

Pseudospectra of rectangular matrices

Pseudospectra of rectangular matrices vary continuously withthe matrix entries, a feature that eigenvalues of these matricesdo not have. Some properties of eigenvalues and pseudospectraof rectangular matrices are explored, and an efficient algorithmfor the computation of pseudospectra is proposed. Applicationsare given in (square) eigenvalue computation (Lanczos iteration),square pseudospectra approximation (Arnoldi iteration), controltheory (nearest uncontrollable system) and game theory.     

On backward errors of structured polynomial eigenproblems solved by structure preserving linearizations

We derive explicit computable expressions of structured backward errors of approximate eigenelements of structured matrix polynomials including symmetric, skew-symmetric, Hermitian, skew-Hermitian, even and odd polynomials. We determine minimal structured perturbations for which approximate eigenelements are exact eigenelements of the perturbed polynomials. We also analyze structured pseudospectra of a structured matrix polynomial and establish a partial equality between unstructured and structured pseudospectra. Finally, we analyze the effect of structure preserving linearizations of structured matrix polynomials on the structured backward errors of approximate eigenelements and show that structure preserving linearizations which minimize structured condition numbers of eigenvalues also minimize the structured backward errors of approximate eigenelements.