Computing eigenspaces with specified eigenvalues of a regular matrix pair (A,B) and condition estimation: theory,algorithms and software

Theory, algorithms and LAPACK-style software for computing a pair of deflating subspaces with specified eigenvalues of a regular matrix pair (A, B) and error bounds for computed quantities (eigenvalues and eigenspaces) are presented. Thereordering of specified eigenvalues is performed with a direct orthogonal transformation method with guaranteed numerical stability. Each swap of two adjacent diagonal blocks in the real generalized Schur form, where at least one of them corresponds to a complex conjugate pair of eigenvalues, involves solving a generalized Sylvester equation and the construction of two orthogonal transformation matrices from certain eigenspaces associated with the diagonal blocks. The swapping of two 1×1 blocks is performed using orthogonal (unitary) Givens rotations. Theerror bounds are based on estimates of condition numbers for eigenvalues and eigenspaces. The software computes reciprocal values of a condition number for an individual eigenvalue (or a cluster of eigenvalues), a condition number for an eigenvector (or eigenspace), and spectral projectors onto a selected cluster. By computing reciprocal values we avoid overflow. Changes in eigenvectors and eigenspaces are measured by their change in angle. The condition numbers yield bothasymptotic andglobal error bounds. The asymptotic bounds are only accurate for small perturbations (E, F) of (A, B), while the global bounds work for all (E, F.) up to a certain bound, whose size is determined by the conditioning of the problem. It is also shown how these upper bounds can be estimated. Fortran 77software that implements our algorithms for reordering eigenvalues, computing (left and right) deflating subspaces with specified eigenvalues and condition number estimation are presented. Computational experiments that illustrate the accuracy, efficiency and reliability of our software are also described.     

Stabilité magnétohydrodynamique des modes ballooning dans un Tokamak

We implanted in the ERATO spectral code [1] the stability criterion for ballooning modes (toroidal wave numbern) [2]. The study of ballooning waves located around a given magnetic surface reduces itself to the investigation of the sign of the potential energy on this surface; this method avoids the determination of eigenvalues which is expensive in computing time. The stability criterion obtained by this way has been applied to a high-beta equilibria family proposed for JET. The stability limit found is more constraining than the limit for low-n internal modes.     

Presentation geometrique des methodes de calcul des valeurs propres

Summary We present a survey of recent work on the convergence of methods for computing eigenvalues and eigenvectors of matrices. We try to maintain a geometric point of view and give pride of place to the R algorithm.

---

---

Cet article a été ecrit pendant le sejour de l'auteur en laboratoire d'Analyse Numérique de l'Université de Paris 6     

Schrödinger Operators on Lattices. The Efimov Effect and Discrete Spectrum Asymptotics

The Hamiltonian of a system of three quantum mechanical particles moving on the three-dimensional lattice and interacting via zero-range attractive potentials is considered. For the two-particle energy operator h(k), with the two-particle quasi-momentum, the existence of a unique positive eigenvalue below the bottom of the continuous spectrum of h(k) for k 0 is proven, provided that h(0) has a zero energy resonance. The location of the essential and discrete spectra of the three-particle discrete Schrödinger operator H(K), being the three-particle quasi-momentum, is studied. The existence of infinitely many eigenvalues of H(0) is proven. It is found that for the number N(0, z) of eigenvalues of H(0) lying below the following limit exists with Moreover, for all sufficiently small nonzero values of the three-particle quasi-momentum K the finiteness of the number of eigenvalues of H(K) below the essential spectrum is established and the asymptotics for the number N(K, 0) of eigenvalues lying below zero is given. Communicated by Gian Michele GrafSubmitted 19/11/03, accepted 08/03/04     

The Inverse Resonance Problem for Hermite Operators

In this paper the inverse resonance problem for the Hermite operator is investigated. The Hermite operator with the creation operator , the annihilation operator , and a finitely supported multiplication operator b, is an unbounded operator on ℓ ²(ℕ₀) having finitely many eigenvalues and infinitely many resonances (except for b=0, when there are no eigenvalues or resonances). It is shown that knowing the location of eigenvalues and resonances determines the potential b uniquely.      

A multishift QR iteration without computation of the shifts

Each iteration of the multishift QR algorithm of Bai and Demmel requires the computation of a shift vector defined bym shifts of the origin of the spectrum that control the convergence of the process. A common choice of shifts consists of the eigenvalues of the trailing principal submatrix of orderm, and current practice includes the computation of these eigenvalues in the determination of the shift vector. In this paper, we describe an algorithm based on the evaluation of the characteristic polynomial of a Hessenberg matrix, which directly produces the shift vector without computing eigenvalues. This algorithm is stable, more accurate, faster, and simpler than the current alternative. It also allows for a consistent shift strategy with dynamic adjustment of the number of shifts.The work of this author was in part supported by the National Science Foundation, grant number ESC-9003107, and the Army Research Office, grant number DAAL-03-91-G-0038.     

Variational Principles for Eigenvalues of Self-adjoint Operator Functions

Variational principles for eigenvalues of certain functions whose values are possibly unbounded self-adjoint operators T() are proved. A generalised Rayleigh functional is used that assigns to a vector x a zero of the function T()x, x), where it is assumed that there exists at most one zero. Since there need not exist a zero for all x, an index shift may occur. Using this variational principle, eigenvalues of linear and quadratic polynomials and eigenvalues of block operator matrices in a gap of the essential spectrum are characterised. Moreover, applications are given to an elliptic eigenvalue problem with degenerate weight, Dirac operators, strings in a medium with a viscous friction, and a Sturm-Liouville problem that is rational in the eigenvalue parameter.     

An Arnoldi Method for Nonlinear Eigenvalue Problems

For the nonlinear eigenvalue problem T()x=0 we propose an iterative projection method for computing a few eigenvalues close to a given parameter. The current search space is expanded by a generalization of the shift-and-invert Arnoldi method. The resulting projected eigenproblems of small dimension are solved by inverse iteration. The method is applied to a rational eigenvalue problem governing damped vibrations of a structure.     

Simultaneous estimation of eigenvalues

The problem of simultaneous estimation of eigenvalues of covariance matrix is considered for one and two sample problems under a sum of squared error loss. New classes of estimators are obtained which dominate the best multiple of the sample eigenvalues in terms of risk. These estimators shrink or expand the sample eigenvalues towards their geometric mean. Similar results are obtained for the estimation of eigenvalues of the precision matrix and the residual matrix when the original covariance matrix is partitioned into two groups. As a consequence, a new estimator of trace of the covariance matrix is obtained.The results are extended to two sample problem where two Wishart distributions are independently observed, say, S _i W _p ( _i , k _i ), i=1, 2, and eigenvalues of _{1 2} ^-1 are estimated simultaneously. Finally, some numerical calculations are done to obtain the amount of risk improvement.     

A Low-Complexity Divide-and-Conquer Method for Computing Eigenvalues and Eigenvectors of Symmetric Band Matrices

A framework for an efficient low-complexity divide-and-conquer algorithm for computing eigenvalues and eigenvectors of an n × n symmetric band matrix with semibandwidth b n is proposed and its arithmetic complexity analyzed. The distinctive feature of the algorithm—after subdivision of the original problem into p subproblems and their solution—is a separation of the eigenvalue and eigenvector computations in the central synthesis problem. The eigenvalues are computed recursively by representing the corresponding symmetric rank b(p–1) modification of a diagonal matrix as a series of rank-one modifications. Each rank-one modifications problem can be solved using techniques developed for the tridiagonal divide-and-conquer algorithm. Once the eigenvalues are known, the corresponding eigenvectors can be computed efficiently using modified QR factorizations with restricted column pivoting. It is shown that the complexity of the resulting divide-and-conquer algorithm is O (n ² b ²) (in exact arithmetic).This revised version was published online in October 2005 with corrections to the Cover Date.     

Robust stability and a criss-cross algorithm for pseudospectra

A dynamical system = Ax is robustly stablewhen all eigenvalues of complex matrices within a given distanceof the square matrix A lie in the left half-plane. The ‘pseudospectralabscissa’, which is the largest real part of such an eigenvalue,measures the robust stability of A. We present an algorithmfor computing the pseudospectral abscissa, prove global andlocal quadratic convergence, and discuss numerical implementation.As with analogous methods for calculating H norms, our algorithmdepends on computing the eigenvalues of associated Hamiltonianmatrices.     

A new bound on the Morse index of constant mean curvature tori of revolution in {{\mathbb{S}}^{3}}

In this work we give a new lower bound on the Morse index for constant mean curvature tori of revolution immersed in the three-sphere ${{\mathbb{S}}^{3}}$ , by computing some explicit negative eigenvalues for an operator associated to the Jacobi’s one.     

On the efficiency of selection criteria in spline regression

This paper concerns the cubic smoothing spline approach to nonparametric regression. After first deriving sharp asymptotic formulas for the eigenvalues of the smoothing matrix, the paper uses these formulas to investigate the efficiency of different selection criteria for choosing the smoothing parameter. Special attention is paid to the generalized maximum likelihood (GML), C _p and extended exponential (EE) criteria and their marginal Bayesian interpretation. It is shown that (a) when the Bayesian model that motivates GML is true, using C _p to estimate the smoothing parameter would result in a loss of efficiency with a factor of 10/3, proving and strengthening a conjecture proposed in Stein (1990); (b) when the data indeed come from the C _p density, using GML would result in a loss of efficiency of ; (c) the loss of efficiency of the EE criterion is at most 1.543 when the data are sampled from its consistent density family. The paper not only studies equally spaced observations (the setting of Stein, 1990), but also investigates general sampling scheme of the design points, and shows that the efficiency results remain the same in both cases.This work is supported in part by NSF grant DMS-0204674 and Harvard University Clark-Cooke Fund. Mathematics Subject Classification (2000):Primary: 62G08; Secondary: 62G20     

Bound states of discrete Schrödinger operators with super-critical inverse square potentials

We consider discrete one-dimensional Schrödinger operators whose potentials decay asymptotically like an inverse square. In the super-critical case, where there are infinitely many discrete eigenvalues, we compute precise asymptotics of the number of eigenvalues below a given energy as this energy tends to the bottom of the essential spectrum.

     

The preconditioned inverse iteration for hierarchical matrices

The preconditioned inverse iteration is an efficient method to compute the smallest eigenpair of a symmetric positive definite matrix M. Here we use this method to find the smallest eigenvalues of a hierarchical matrix. The storage complexity of the data‐sparse ‐matrices is almost linear. We use ‐arithmetic to precondition with an approximate inverse of M or an approximate Cholesky decomposition of M. In general, ‐arithmetic is of linear‐polylogarithmic complexity, so the computation of one eigenvalue is cheap. We extend the ideas to the computation of inner eigenvalues by computing an invariant subspace S of (M ? μI)² by subspace preconditioned inverse iteration. The eigenvalues of the generalized matrix Rayleigh quotient μ_M(S) are the desired inner eigenvalues of M. The idea of using (M ? μI)² instead of M is known as the folded spectrum method. As we rely on the positive definiteness of the shifted matrix, we cannot simply apply shifted inverse iteration therefor. Numerical results substantiate the convergence properties and show that the computation of the eigenvalues is superior to existing algorithms for non‐sparse matrices.Copyright © 2012 John Wiley & Sons, Ltd.     

Limit points of eigenvalues of (di)graphs

The study on limit points of eigenvalues of undirected graphs was initiated by A. J. Hoffman in 1972. Now we extend the study to digraphs. We prove 1. Every real number is a limit point of eigenvalues of graphs. Every complex number is a limit point of eigenvalues of digraphs. 2. For a digraph D, the set of limit points of eigenvalues of iterated subdivision digraphs of D is the unit circle in the complex plane if and only if D has a directed cycle. 3. Every limit point of eigenvalues of a set D of digraphs (graphs) is a limit point of eigenvalues of a set of bipartite digraphs (graphs), where consists of the double covers of the members in D. 4. Every limit point of eigenvalues of a set D of digraphs is a limit point of eigenvalues of line digraphs of the digraphs in D. 5. If M is a limit point of the largest eigenvalues of graphs, then −M is a limit point of the smallest eigenvalues of graphs.     

A numerical method for computing the Hamiltonian Schur form

We derive a new numerical method for computing the Hamiltonian Schur form of a Hamiltonian matrix that has no purely imaginary eigenvalues. We demonstrate the properties of the new method by showing its performance for the benchmark collection of continuous-time algebraic Riccati equations. Despite the fact that no complete error analysis for the method is yet available, the numerical results indicate that if no eigenvalues of are close to the imaginary axis then the method computes the exact Hamiltonian Schur form of a nearby Hamiltonian matrix and thus is numerically strongly backward stable. The new method is of complexity and hence it solves a long-standing open problem in numerical analysis. Volker Mehrmann was supported by Deutsche Forschungsgemeinschaft, Research Grant Me 790/11-3.     

The number of bound states of a one-particle Hamiltonian on a three-dimensional lattice

We consider the Hamiltonian , describing the motion of one quantum particle on a three-dimensional lattice in an external field. We investigate the number of eigenvalues and their arrangement depending on the value of the interaction energy for μ ≥ 0 and λ ≥ 0. __________ Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 158, No. 3, pp. 425–443, March, 2009.     

Virtual Eigenvalues of the High Order Schrödinger Operator II

We consider the Schr?dinger operator H_γ = ( − Δ)^l + γ V(x)· acting in the space where 2l ≥ d, V (x) ≥ 0, V (x) is continuous and is not identically zero, and We study the asymptotic behavior as of the non-bottom negative eigenvalues of H_γ, which are born at the moment γ = 0 from the lower bound λ = 0 of the spectrum σ(H₀) of the unperturbed operator H₀ = ( − Δ)^l (virtual eigenvalues). To this end we use the Puiseux-Newton diagram for a power expansion of eigenvalues of some class of polynomial matrix functions. For the groups of virtual eigenvalues, having the same rate of decay, we obtain asymptotic estimates of Lieb-Thirring type.     

Computing Derivatives of Eigensystems by the Vector {varepsilon}-Algorithm

Rudisill & Chu proposed a (slowly converging) iterativemethod for computing partial derivatives of eigenvalues andeigenvectors of parameter-dependent matrices. It is shown that,with exact computation, application of the vector -algorithmto this method produces the exact solution in a small numberof steps. Numerical results demonstrate the viability of thismethod. A refinement process is suggested which makes the methodespecially effective for subdominant eigenvalues.