A global harmonic Arnoldi method for large non-Hermitian eigenproblems with an application to multiple eigenvalue problems

The global Arnoldi method can be used to compute exterior eigenpairs of a large non-Hermitian matrix A, but it does not work well for interior eigenvalue problems. Based on the global Arnoldi process that generates an F-orthonormal basis of a matrix Krylov subspace, we propose a global harmonic Arnoldi method for computing certain harmonic F-Ritz pairs that are used to approximate some interior eigenpairs. We propose computing the F-Rayleigh quotients of the large non-Hermitian matrix with respect to harmonic F-Ritz vectors and taking them as new approximate eigenvalues. They are better and more reliable than the harmonic F-Ritz values. The global harmonic Arnoldi method inherits convergence properties of the harmonic Arnoldi method applied to a larger matrix whose distinct eigenvalues are the same as those of the original given matrix. Some properties of the harmonic F-Ritz vectors are presented. As an application, assuming that A is diagonalizable, we show that the global harmonic Arnoldi method is able to solve multiple eigenvalue problems both in theory and in practice. To be practical, we develop an implicitly restarted global harmonic Arnoldi algorithm with certain harmonic F-shifts suggested. In particular, this algorithm can be adaptively used to solve multiple eigenvalue problems. Numerical experiments show that the algorithm is efficient for the eigenproblem and is reliable for quite ill-conditioned multiple eigenproblems.     

A canonical form for nonderogatory matrices under unitary similarity

A square matrix is nonderogatory if its Jordan blocks have distinct eigenvalues. We give canonical forms for

•

nonderogatory complex matrices up to unitary similarity, and

•

pairs of complex matrices up to similarity, in which one matrix has distinct eigenvalues.

The types of these canonical forms are given by undirected and, respectively, directed graphs with no undirected cycles.     

On the eigenvalues of specially low-rank perturbed matrices

We study the eigenvalues of a matrix A perturbed by a few special low-rank matrices. The perturbation is constructed from certain basis vectors of an invariant subspace of A, such as eigenvectors, Jordan vectors, or Schur vectors. We show that most of the eigenvalues of the low-rank perturbed matrix stayed unchanged from the eigenvalues of A; the perturbation can only change the eigenvalues of A that are related to the invariant subspace. Existing results mostly studied using eigenvectors with full column rank for perturbations, we generalize the results to more general settings. Applications of our results to a few interesting problems including the Google’s second eigenvalue problem are presented.     

Generalized block Lanczos methods for large unsymmetric eigenproblems

Generalized block Lanczos methods for large unsymmetric eigenproblems are presented, which contain the block Arnoldi method, and the block Arnoldi algorithms are developed. The convergence of this class of methods is analyzed when the matrix A is diagonalizable. Upper bounds for the distances between normalized eigenvectors and a block Krylov subspace are derived, and a priori theoretical error bounds for Ritz elements are established. Compared with generalized Lanczos methods, which contain Arnoldi's method, the convergence analysis shows that the block versions have two advantages: First, they may be efficient for computing clustered eigenvalues; second, they are able to solve multiple eigenproblems. However, a deep analysis exposes that the approximate eigenvectors or Ritz vectors obtained by general orthogonal projection methods including generalized block methods may fail to converge theoretically for a general unsymmetric matrix A even if corresponding approximate eigenvalues or Ritz values do, since the convergence of Ritz vectors needs more sufficient conditions, which may be impossible to satisfy theoretically, than that of Ritz values does. The issues of how to restart and to solve multiple eigenproblems are addressed, and some numerical examples are reported to confirm the theoretical analysis. Received July 7, 1994 / Revised version received March 1, 1997     

An explicit expression for the Fisher information matrix of a multiple time series process

The principal result in this paper is concerned with the derivative of a vector with respect to a block vector or matrix. This is applied to the asymptotic Fisher information matrix (FIM) of a stationary vector autoregressive and moving average time series process (VARMA). Representations which can be used for computing the components of the FIM are then obtained. In a related paper [A. Klein, A generalization of Whittle’s formula for the information matrix of vector mixed time series, Linear Algebra Appl. 321 (2000) 197-208], the derivative is taken with respect to a vector. This is obtained by vectorizing the appropriate matrix products whereas in this paper the corresponding matrix products are left unchanged.     

Extracting partial canonical structure for large scale eigenvalue problems

We present methods for computing a nearby partial Jordan-Schur form of a given matrix and a nearby partial Weierstrass-Schur form of a matrix pencil. The focus is on the use and the interplay of the algorithmic building blocks – the implicitly restarted Arnoldi method with prescribed restarts for computing an invariant subspace associated with the dominant eigenvalue, the clustering method for grouping computed eigenvalues into numerically multiple eigenvalues and the staircase algorithm for computing the structure revealing form of the projected problem. For matrix pencils, we present generalizations of these methods. We introduce a new and more accurate clustering heuristic for both matrices and matrix pencils. Particular emphasis is placed on reliability of the partial Jordan-Schur and Weierstrass-Schur methods with respect to the choice of deflation parameters connecting the steps of the algorithm such that the errors are controlled. Finally, successful results from computational experiments conducted on problems with known canonical structure and varying ill-conditioning are presented. This revised version was published online in June 2006 with corrections to the Cover Date.     

Matrices with prescribed Ritz values

On the way to establishing a commutative analog to the Gelfand-Kirillov theorem in Lie theory, Kostant and Wallach produced a decomposition of M(n) which we will describe in the language of linear algebra. The “Ritz values” of a matrix are the eigenvalues of its leading principal submatrices of order m=1,2,…,n. There is a unique unit upper Hessenberg matrix H with those eigenvalues. For real symmetric matrices with interlacing Ritz values, we extend their analysis to allow eigenvalues at successive levels to be equal. We also decide whether given Ritz values can come from a tridiagonal matrix.     

用奇异值分解方法计算具有重特征值矩阵的特征矢量

若当(Jordan)形是矩阵在相似条件下的一个标准形,在代数理论及其工程应用中都具有十分重要的意义．针对具有重特征值的矩阵,提出了一种运用奇异值分解方法计算它的特征矢量及若当形的算法．大量数值例子的计算结果表明,该算法在求解具有重特征值的矩阵的特征矢量及若当形上效果良好,优于商用软件MATLAB和MATHEMATICA．     

A note on upper bounds on the cp-rank

Hanna and Laffey gave an upper bound on the cp-rank of a completely positive matrix, in terms of its rank and the number of zeros in a full rank principal submatrix. This bound, for the case that the matrix is positive, was improved by Barioli and Berman. In this paper a new straightforward proof of both results is given, and the same approach is used to improve Hanna and Laffey’s bound in the case that the matrix has a zero entry.     

Determinant of a matrix that commutes with a Jordan matrix

Given a Jordan matrix J, we obtain an explicit formula for the determinant of any matrix T that commutes with it.     

Green’s matrices

Our goal is to identify and understand matrices A that share essential properties of the unitary Hessenberg matrices M that are fundamental for Szegö’s orthogonal polynomials. Those properties include: (i) Recurrence relations connect characteristic polynomials {r_k(x)} of principal minors of A. (ii) A is determined by generators (parameters generalizing reflection coefficients of unitary Hessenberg theory). (iii) Polynomials {r_k(x)} correspond not only to A but also to a certain “CMV-like” five-diagonal matrix. (iv) The five-diagonal matrix factors into a product BC of block diagonal matrices with 2 × 2 blocks. (v) Submatrices above and below the main diagonal of A have rank 1. (vi) A is a multiplication operator in the appropriate basis of Laurent polynomials. (vii) Eigenvectors of A can be expressed in terms of those polynomials.Conditions (v) connects our analysis to the study of quasi-separable matrices. But the factorization requirement (iv) narrows it to the subclass of “Green’s matrices” that share Properties (i)-(vii).The key tool is “twist transformations” that provide 2ⁿ matrices all sharing characteristic polynomials of principal minors with A. One such twist transformation connects unitary Hessenberg to CMV. Another twist transformation explains findings of Fiedler who noticed that companion matrices give examples outside the unitary Hessenberg framework. We mention briefly the further example of a Daubechies wavelet matrix. Infinite matrices are included.     

Application of a block modified Chebyshev algorithm to the iterative solution of symmetric linear systems with multiple right hand side vectors

Summary. An adaptive Richardson iteration method is described for the solution of large sparse symmetric positive definite linear systems of equations with multiple right-hand side vectors. This scheme ``learns' about the linear system to be solved by computing inner products of residual matrices during the iterations. These inner products are interpreted as block modified moments. A block version of the modified Chebyshev algorithm is presented which yields a block tridiagonal matrix from the block modified moments and the recursion coefficients of the residual polynomials. The eigenvalues of this block tridiagonal matrix define an interval, which determines the choice of relaxation parameters for Richardson iteration. Only minor modifications are necessary in order to obtain a scheme for the solution of symmetric indefinite linear systems with multiple right-hand side vectors. We outline the changes required. Received April 22, 1993     

Interlacing properties of the eigenvalues of some matrix classes

We establish the eigenvalue interlacing property (i.e. the smallest real eigenvalue of a matrix is less than the smallest real eigenvalue of any of its principal submatrices) for the class of matrices introduced by Kotelyansky (all principal and almost principal minors of these matrices are positive). We show that certain generalizations of Kotelyansky and totally positive matrices possess this property. We also prove some interlacing inequalities for the other eigenvalues of Kotelyansky matrices.     

Sum rules for hitting times of Markov chains

Using matrix algebra we obtain a general equation for the sum, normalized with suitable constants, of all the expected hitting times in an ergodic Markov chain. This equation yields as corollaries, among others, Broder and Karlin’s formula, Foster’s nth formula and an expression of the Kirchhoff index in terms of the eigenvalues of the Laplacian.     

A Jacobi matrix inverse eigenvalue problem with mixed data

In this paper, the inverse eigenvalue problem of reconstructing a Jacobi matrix from part of its eigenvalues and its leading principal submatrix is considered. The necessary and sufficient conditions for the existence and uniqueness of the solution are derived. Furthermore, a numerical algorithm and some numerical examples are given.     

On close eigenvalues of tridiagonal matrices

Summary. A symmetric tridiagonal matrix with a multiple eigenvalue must have a zero subdiagonal element and must be a direct sum of two complementary blocks, both of which have the eigenvalue. Yet it is well known that a small spectral gap does not necessarily imply that some is small, as is demonstrated by the Wilkinson matrix. In this note, it is shown that a pair of close eigenvalues can only arise from two complementary blocks on the diagonal, in spite of the fact that the coupling the two blocks may not be small. In particular, some explanatory bounds are derived and a connection to the Lanczos algorithm is observed. The nonsymmetric problem is also included. Received April 8, 1992 / Revised version received September 21, 1994     

Eigenvalue computation for unitary rank structured matrices

In this paper we describe how to compute the eigenvalues of a unitary rank structured matrix in two steps. First we perform a reduction of the given matrix into Hessenberg form, next we compute the eigenvalues of this resulting Hessenberg matrix via an implicit QR-algorithm. Along the way, we explain how the knowledge of a certain ‘shift’ correction term to the structure can be used to speed up the QR-algorithm for unitary Hessenberg matrices, and how this observation was implicitly used in a paper due to William B. Gragg. We also treat an analogue of this observation in the Hermitian tridiagonal case.     

On computing PageRank via lumping the Google matrix

Computing Google’s PageRank via lumping the Google matrix was recently analyzed in [I.C.F. Ipsen, T.M. Selee, PageRank computation, with special attention to dangling nodes, SIAM J. Matrix Anal. Appl. 29 (2007) 1281–1296]. It was shown that all of the dangling nodes can be lumped into a single node and the PageRank could be obtained by applying the power method to the reduced matrix. Furthermore, the stochastic reduced matrix had the same nonzero eigenvalues as the full Google matrix and the power method applied to the reduced matrix had the same convergence rate as that of the power method applied to the full matrix. Therefore, a large amount of operations could be saved for computing the full PageRank vector.     

Unitarily achievable zero patterns and traces of words in A and A

Our primary objective is to identify a natural and substantial problem about unitary similarity on arbitrary complex matrices: which 0-patterns may be achieved for any given n-by-n complex matrix via some unitary similarity of it. To this end, certain restrictions on “achievable” 0-patterns are mentioned, both positional and, more important, on the maximum number of achievable 0’s. Prior results fitting this general question are mentioned, as well as the “first” unresolved pattern (for 3-by-3 matrices!). In the process a recent question is answered.A closely related additional objective is to mention the best known bound for the maximum length of words necessary for the application of Specht’s theorem about which pairs of complex matrices are unitarily similar, which seems not widely known to matrix theorists. In the process, we mention the number of words necessary for small size matrices.     

An asymmetric Kadison’s inequality

Some inequalities for positive linear maps on matrix algebras are given, especially asymmetric extensions of Kadison’s inequality and several operator versions of Chebyshev’s inequality. We also discuss well-known results around the matrix geometric mean and connect it with complex interpolation.