Exact eigensystems for some matrices arising from discretizations

It is known, for example, that the eigenvalues of the N×N matrix A, arising in the discretization of the wave equation, whose only nonzero entries are A_kk+1=A_k+1k=-1,k=1,…,N-1, and A_kk=2,k=1,…,N, are 2{1-cos[pπ/(N+1)]} with corresponding eigenvectors v^(p) given by . We show by considering a simple finite difference approximation to the second derivative and using the summation formulae for sines and cosines that these and other similar formulae arise in a simple and unified way.     

New symmetry preserving method for optimal correction of damping and stiffness matrices using measured modes

Measured and analytical data are unlikely to be equal due to measured noise, model inadequacies, structural damage, etc. It is necessary to update the physical parameters of analytical models for proper simulation and design studies. Starting from simulated measured modal data such as natural frequencies and their corresponding mode shapes, a new computationally efficient and symmetry preserving method and associated theories are presented in this paper to update the physical parameters of damping and stiffness matrices simultaneously for analytical modeling. A conjecture which is proposed in [Y.X. Yuan, H. Dai, A generalized inverse eigenvalue problem in structural dynamic model updating, J. Comput. Appl. Math. 226 (2009) 42-49] is solved. Two numerical examples are presented to show the efficiency and reliability of the proposed method. It is more important that, some numerical stability analysis on the model updating problem is given combining with numerical experiments.     

A generalized inverse eigenvalue problem in structural dynamic model updating

This paper is concerned with the problem of the best approximation for a given matrix pencil under a given spectral constraint and a submatrix pencil constraint. Such a problem arises in structural dynamic model updating. By using the Moore–Penrose generalized inverse and the singular value decomposition (SVD) matrices, the solvability condition and the expression for the solution of the problem are presented. A numerical algorithm for solving the problem is developed.     

Pseudospectra for matrix pencils and stability of equilibria

The concept of ε-pseudospectra for matrices, introduced by Trefethen and his coworkers, has been studied extensively since 1990. In this paper, ε-pseudospectra for matrix pencils, which are relevant in connection with generalized eigenvalue problems, are considered. Some properties as well as the practical computation of ε-pseudospectra for matrix pencils will be discussed. As an application, we demonstrate how this concept can be used for investigating the asymptotic stability of stationary solutions to time-dependent ordinary or partial differential equations; two cases, based on Burgers' equation, will be shown. This research has been supported by the Netherlands Organization for Scientific Research (N.W.O.)     

Fast and stable QR eigenvalue algorithms for generalized companion matrices and secular equations

Summary We introduce a class of n×n structured matrices which includes three well-known classes of generalized companion matrices: tridiagonal plus rank-one matrices (comrade matrices), diagonal plus rank-one matrices and arrowhead matrices. Relying on the structure properties of , we show that if A then A=RQ , where A=QR is the QR decomposition of A. This allows one to implement the QR iteration for computing the eigenvalues and the eigenvectors of any A with O(n) arithmetic operations per iteration and with O(n) memory storage. This iteration, applied to generalized companion matrices, provides new O(n²) flops algorithms for computing polynomial zeros and for solving the associated (rational) secular equations. Numerical experiments confirm the effectiveness and the robustness of our approach.The results of this paper were presented at the Workshop on Nonlinear Approximations in Numerical Analysis, June 22 – 25, 2003, Moscow, Russia, at the Workshop on Operator Theory and Applications (IWOTA), June 24 – 27, 2003, Cagliari, Italy, at the Workshop on Numerical Linear Algebra at Universidad Carlos III in Leganes, June 16 – 17, 2003, Leganes, Spain, at the SIAM Conference on Applied Linear Algebra, July 15 – 19, 2003, Williamsburg, VA and in the Technical Report [8]. This work was partially supported by MIUR, grant number 2002014121, and by GNCS-INDAM. This work was supported by NSF Grant CCR 9732206 and PSC CUNY Awards 66406-0033 and 65393-0034.     

A fast implicit QR eigenvalue algorithm for companion matrices

An implicit version of the shifted QR eigenvalue algorithm given in Bini et al. [D.A. Bini, Y. Eidelman, I. Gohberg, L. Gemignani, SIAM J. Matrix Anal. Appl. 29(2) (2007) 566-585] is presented for computing the eigenvalues of an n×n companion matrix using O(n²) flops and O(n) memory storage. Numerical experiments and comparisons confirm the effectiveness and the stability of the proposed method.     

A Hamiltonian Krylov-Schur-type method based on the symplectic Lanczos process

We discuss a Krylov-Schur like restarting technique applied within the symplectic Lanczos algorithm for the Hamiltonian eigenvalue problem. This allows us to easily implement a purging and locking strategy in order to improve the convergence properties of the symplectic Lanczos algorithm. The Krylov-Schur-like restarting is based on the SR algorithm. Some ingredients of the latter need to be adapted to the structure of the symplectic Lanczos recursion. We demonstrate the efficiency of the new method for several Hamiltonian eigenproblems.     

Current inverse iteration software can fail

Inverse iteration is widley used to compute the eigenvectors of a matrix once accurate eigenvalues are known. We discuss various issues involved in any implementation of inverse iteration for real, symmetric matrices. Current implementations resort to reorthogonalization when eigenvalues agree to more than three digits relative to the norm. Such reorthogonalization can have unexpected consequences. Indeed, as we show in this paper, the implementations in EISPACK and LAPACK may fail. We illustrate with both theoretical and empirical failures. This research was supported, while the author was at the University of California, Berkeley, in part by DARPA Contract No. DAAL03-91-C-0047 through a subcontract with the University of Tennessee, DOE Contract No. DOE-W-31-109-Eng-38 through a subcontract with Argonne National Laboratory, by DOE Grant No. DE-FG03-94ER25219, NSF Grant Nos. ASC-9313958 and CDA-9401156, and DOE Contract DE-AC06-76RLO 1830 through the Environmental Molecular Sciences construction project at Pacific Northwest National Laboraotry (PNNL).     

On the local convergence of inexact Newton-type methods under residual control-type conditions

A local convergence analysis of inexact Newton-type methods using a new type of residual control was recently presented by C. Li and W. Shen. Here, we introduce the center-Hölder condition on the operator involved, and use it in combination with the Hölder condition to provide a new local convergence analysis with the following advantages: larger radius of convergence, and tighter error bounds on the distances involved. These results are obtained under the same hypotheses and computational cost. Numerical examples further validating the theoretical results are also provided in this study.     

On convergence of the inexact Rayleigh quotient iteration with MINRES

For the Hermitian inexact Rayleigh quotient iteration (RQI), we present a new general theory, independent of iterative solvers for shifted inner linear systems. The theory shows that the method converges at least quadratically under a new condition, called the uniform positiveness condition, that may allow the residual norm _ξk≥1${\xi }_k\ge 1$ of the inner linear system at outer iteration k+1$k+1$ and can be considerably weaker than the condition _ξk≤ξ<1${\xi }_k\le \xi <1$ with ξ$\xi$ a constant not near one commonly used in the literature. We consider the convergence of the inexact RQI with the unpreconditioned and tuned preconditioned MINRES methods for the linear systems. Some attractive properties are derived for the residuals obtained by MINRES. Based on them and the new general theory, we make a refined analysis and establish a number of new convergence results. Let ‖_rk‖$\Vert r_k\Vert$ be the residual norm of approximating eigenpair at outer iteration k$k$. Then all the available cubic and quadratic convergence results require _ξk=O(‖_rk‖)${\xi }_k=O\left(\Vert r_k\Vert \right)$ and _ξk≤ξ${\xi }_k\le \xi$ with a fixed ξ$\xi$ not near one, respectively. Fundamentally different from these, we prove that the inexact RQI with MINRES generally converges cubically, quadratically and linearly provided that _ξk≤ξ${\xi }_k\le \xi$ with a constant ξ<1$\xi <1$ not near one, _ξk=1−O(‖_rk‖)${\xi }_k=1-O\left(\Vert r_k\Vert \right)$ and _ξk=1−O(‖_rk‖²)${\xi }_k=1-O\left({\Vert r_k\Vert }^2\right)$, respectively. The new convergence conditions are much more relaxed than ever before. The theory can be used to design practical stopping criteria to implement the method more effectively. Numerical experiments confirm our results.     

Direct and inverse spectral problems for a class of non-self-adjoint periodic tridiagonal matrices

The spectral properties of a class of tridiagonal matrices are investigated. The reconstruction of matrices of this special class from given spectral data is also studied. Necessary and sufficient conditions for that reconstruction are found. The obtained results extend some results on the direct and inverse spectral problems for periodic Jacobi matrices and for some non-self-adjoint tridiagonal matrices.     

Krylov type subspace methods for matrix polynomials

We consider solving eigenvalue problems or model reduction problems for a quadratic matrix polynomial Iλ² − Aλ − B with large and sparse A and B. We propose new Arnoldi and Lanczos type processes which operate on the same space as A and B live and construct projections of A and B to produce a quadratic matrix polynomial with the coefficient matrices of much smaller size, which is used to approximate the original problem. We shall apply the new processes to solve eigenvalue problems and model reductions of a second order linear input-output system and discuss convergence properties. Our new processes are also extendable to cover a general matrix polynomial of any degree.     

Deflating quadratic matrix polynomials with structure preserving transformations

Given a pair of distinct eigenvalues (λ₁,λ₂) of an n×n quadratic matrix polynomial Q(λ) with nonsingular leading coefficient and their corresponding eigenvectors, we show how to transform Q(λ) into a quadratic of the form having the same eigenvalue s as Q(λ), with Q_d(λ) an (n-1)×(n-1) quadratic matrix polynomial and q(λ) a scalar quadratic polynomial with roots λ₁ and λ₂. This block diagonalization cannot be achieved by a similarity transformation applied directly to Q(λ) unless the eigenvectors corresponding to λ₁ and λ₂ are parallel. We identify conditions under which we can construct a family of 2n×2n elementary similarity transformations that (a) are rank-two modifications of the identity matrix, (b) act on linearizations of Q(λ), (c) preserve the block structure of a large class of block symmetric linearizations of Q(λ), thereby defining new quadratic matrix polynomials Q₁(λ) that have the same eigenvalue s as Q(λ), (d) yield quadratics Q₁(λ) with the property that their eigenvectors associated with λ₁ and λ₂ are parallel and hence can subsequently be deflated by a similarity applied directly to Q₁(λ). This is the first attempt at building elementary transformations that preserve the block structure of widely used linearizations and which have a specific action.     

A Jacobi–Davidson type method for the product eigenvalue problem

We propose a Jacobi–Davidson type method to compute selected eigenpairs of the product eigenvalue problem _Am?_A1x=λx,$A_m?A_{1}x=\lambda x,$ where the matrices may be large and sparse. To avoid difficulties caused by a high condition number of the product matrix, we split up the action of the product matrix and work with several search spaces. We generalize the Jacobi–Davidson correction equation and the harmonic and refined extraction for the product eigenvalue problem. Numerical experiments indicate that the method can be used to compute eigenvalues of product matrices with extremely high condition numbers.     

Fixing multiple eigenvalues by a minimal perturbation

Suppose we are given an n×n matrix, M, and a set of values, (m?n), and we wish to find the smallest perturbation in the 2-norm (i.e., spectral norm), ΔM, such that M-ΔM has the given eigenvalues λ_i. Some interesting results have been obtained for variants of this problem for fixing two distinct eigenvalues, fixing one double eigenvalue, and fixing a triple eigenvalue. This paper provides a geometric motivation for these results and also motivates their generalization. We also present numerical examples (both “successes” and “failures”) of fixing more than two eigenvalues by these generalizations.     

A backward error for the inverse singular value problem

A backward error for inverse singular value problems with respect to an approximate solution is defined, and an explicit expression for the backward error is derived by extending the approach described in [J.G. Sun, Backward errors for the inverse eigenvalue problem, Numer. Math. 82 (1999) 339-349]. The expression may be useful for testing the stability of practical algorithms.     

Note on structured indefinite perturbations to Hermitian matrices

In a recent paper, Overton and Van Dooren have considered structured indefinite perturbations to a given Hermitian matrix. We extend their results to skew-Hermitian, Hamiltonian and skew-Hamiltonian matrices. As an application, we give a formula for computation of the smallest perturbation with a special structure, which makes a given Hamiltonian matrix own a purely imaginary eigenvalue.     

A framework for analyzing nonlinear eigenproblems and parametrized linear systems

Associated with an n×n matrix polynomial of degree , are the eigenvalue problem P(λ)x=0 and the linear system problem P(ω)x=b, where in the latter case x is to be computed for many values of the parameter ω. Both problems can be solved by conversion to an equivalent problem L(λ)z=0 or L(ω)z=c that is linear in the parameter λ or ω. This linearization process has received much attention in recent years for the eigenvalue problem, but it is less well understood for the linear system problem. We develop a framework in which more general versions of both problems can be analyzed, based on one-sided factorizations connecting a general nonlinear matrix function N(λ) to a simpler function M(λ), typically a polynomial of degree 1 or 2. Our analysis relates the solutions of the original and lower degree problems and in the linear system case indicates how to choose the right-hand side c and recover the solution x from z. For the eigenvalue problem this framework includes many special cases studied in the literature, including the vector spaces of pencils L₁(P) and L₂(P) recently introduced by Mackey, Mackey, Mehl, and Mehrmann and a class of rational problems. We use the framework to investigate the conditioning and stability of the parametrized linear system P(ω)x=b and thereby study the effect of scaling, both of the original polynomial and of the pencil L. Our results identify situations in which scaling can potentially greatly improve the conditioning and stability and our numerical results show that dramatic improvements can be achieved in practice.     

Computation of eigenpair partial derivatives by Rayleigh–Ritz procedure

Based on Rayleigh–Ritz procedure, a new method is proposed for a few eigenpair partial derivatives of large matrices. This method simultaneously computes the approximate eigenpairs and their partial derivatives. The linear systems of equations that are solved for eigenvector partial derivatives are greatly reduced from the original matrix size. And the left eigenvectors are not required. Moreover, errors of the computed eigenpairs and their partial derivatives are investigated. Hausdorff distance and containment gap are used to measure the accuracy of approximate eigenpair partial derivatives. Error bounds on the computed eigenpairs and their partial derivatives are derived. Finally numerical experiments are reported to show the efficiency of the proposed method.