Hermitizable,isospectral complex matrices or differential operators

The main purpose of the paper is looking for a larger class of matrices which have real spectrum. The first well-known class having this property is the symmetric one, then is the Hermite one. This paper introduces a new class, called Hermitizable matrices. The closely related isospectral problem, not only for matrices but also for differential operators is also studied. The paper provides a way to describe the discrete spectrum, at least for tridiagonal matrices or one-dimensional differential operators. Especially, an unexpected result in the paper says that each Hermitizable matrix is isospectral to a birth–death type matrix (having positive sub-diagonal elements, in the irreducible case for instance). Besides, new efficient algorithms are proposed for computing the maximal eigenpairs of these class of matrices.     

Development of powerful algorithm for maximal eigenpair

Based on a series of recent papers, a powerful algorithm is reformulated for computing the maximal eigenpair of self-adjoint complex tridiagonal matrices. In parallel, the same problem in a particular case for computing the sub-maximal eigenpair is also introduced. The key ideas for each critical improvement are explained. To illustrate the present algorithm and compare it with the related algorithms, more than 10 examples are included.     

The inverse eigenvalue problem for symmetric quasi anti-bidiagonal matrices

In this paper we construct the symmetric quasi anti-bidiagonal matrix that its eigenvalues are given, and show that the problem is also equivalent to the inverse eigenvalue problem for a certain symmetric tridiagonal matrix which has the same eigenvalues. Not only elements of the tridiagonal matrix come from quasi anti-bidiagonal matrix, but also the places of elements exchange based on some conditions.     

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.     

An implicit QR algorithm for symmetric semiseparable matrices

The QR algorithm is one of the classical methods to compute the eigendecomposition of a matrix. If it is applied on a dense n × n matrix, this algorithm requires O(n³) operations per iteration step. To reduce this complexity for a symmetric matrix to O(n), the original matrix is first reduced to tridiagonal form using orthogonal similarity transformations. In the report (Report TW360, May 2003) a reduction from a symmetric matrix into a similar semiseparable one is described. In this paper a QR algorithm to compute the eigenvalues of semiseparable matrices is designed where each iteration step requires O(n) operations. Hence, combined with the reduction to semiseparable form, the eigenvalues of symmetric matrices can be computed via intermediate semiseparable matrices, instead of tridiagonal ones. The eigenvectors of the intermediate semiseparable matrix will be computed by applying inverse iteration to this matrix. This will be achieved by using an O(n) system solver, for semiseparable matrices. A combination of the previous steps leads to an algorithm for computing the eigenvalue decompositions of semiseparable matrices. Combined with the reduction of a symmetric matrix towards semiseparable form, this algorithm can also be used to calculate the eigenvalue decomposition of symmetric matrices. The presented algorithm has the same order of complexity as the tridiagonal approach, but has larger lower order terms. Numerical experiments illustrate the complexity and the numerical accuracy of the proposed method. Copyright © 2005 John Wiley & Sons, Ltd.     

由两个右特征对构造三对角四元数矩阵

讨论由两个右特征对构造三对角四元数矩阵的数值求解问题,给出了该问题有解的充要条件,以及解的具体表达式.在已知两个特征对的条件下,进一步给出了三对角自共轭、三对角正定四元数矩阵的存在条件及计算方法.     

Homotopy algorithm for symmetric eigenvalue problems

Summary The homotopy method can be used to solve eigenvalue-eigenvector problems. The purpose of this paper is to report the numerical experience of the homotopy method of computing eigenpairs for real symmetric tridiagonal matrices together with a couple of new theoretical results. In practice, it is rerely of any interest to compute all the eigenvalues. The homotopy method, having the order preserving property, can provide any specific eigenvalue without calculating any other eigenvalues. Besides this advantage, we note that the homotopy algorithm is to a large degree a parallel algorithm. Numerical experimentation shows that the homotopy method can be very efficient especially for graded matrices.Research was supported in part by NSF under Grant DMS-8701349     

三对角矩阵求逆的快速算法和逆元素的表示式

本文给出了ｎ阶三对角矩阵求逆的快速算法，其四则运算的计算量只要ｎ＾２＋７ｎ－８。同时给出了逆元素的表示式，从而得到逆元素的准确估计，大大拓广和改进了［２］、［３］的结果。     

Computation of Gauss-Kronrod quadrature rules

Recently Laurie presented a new algorithm for the computation of -point Gauss-Kronrod quadrature rules with real nodes and positive weights. This algorithm first determines a symmetric tridiagonal matrix of order from certain mixed moments, and then computes a partial spectral factorization. We describe a new algorithm that does not require the entries of the tridiagonal matrix to be determined, and thereby avoids computations that can be sensitive to perturbations. Our algorithm uses the consolidation phase of a divide-and-conquer algorithm for the symmetric tridiagonal eigenproblem. We also discuss how the algorithm can be applied to compute Kronrod extensions of Gauss-Radau and Gauss-Lobatto quadrature rules. Throughout the paper we emphasize how the structure of the algorithm makes efficient implementation on parallel computers possible. Numerical examples illustrate the performance of the algorithm.

     

AN ESTIMATE OF EIGENVALUES IN THE SYMMETRIC QR ALGORITHM*

The estimate of the eigenvalues is given when the off-diagonal elements in symmetric tridiagonal matrix are replaced by zero. The result can be applied to QR or QL algorithm. It is a generalization of Jiang' s result in 1987. This estimate is sharper than Hager's result in 1982 and could not fail     

Computing top eigenpairs of Hermitizable matrix

The top eigenpairs at the title mean the maximal, the submaximal, or a few of the subsequent eigenpairs of an Hermitizable matrix. Restricting on top ones is to handle with the matrices having large scale, for which only little is known up to now. This is different from some mature algorithms, that are clearly limited only to medium-sized matrix for calculating full spectrum. It is hoped that a combination of this paper with the earlier works, to be seen soon, may provide some effective algorithms for computing the spectrum in practice, especially for matrix mechanics.     

On tridiagonal matrices unitarily equivalent to normal matrices

In this article the unitary equivalence transformation of normal matrices to tridiagonal form is studied.It is well-known that any matrix is unitarily equivalent to a tridiagonal matrix. In case of a normal matrix the resulting tridiagonal inherits a strong relation between its super- and subdiagonal elements. The corresponding elements of the super- and subdiagonal will have the same absolute value.In this article some basic facts about a unitary equivalence transformation of an arbitrary matrix to tridiagonal form are firstly studied. Both an iterative reduction based on Krylov sequences as a direct tridiagonalization procedure via Householder transformations are reconsidered. This equivalence transformation is then applied to the normal case and equality of the absolute value between the super- and subdiagonals is proved. Self-adjointness of the resulting tridiagonal matrix with regard to a specific scalar product is proved. Properties when applying the reduction on symmetric, skew-symmetric, Hermitian, skew-Hermitian and unitary matrices and their relations with, e.g., complex symmetric and pseudo-symmetric matrices are presented.It is shown that the reduction can then be used to compute the singular value decomposition of normal matrices making use of the Takagi factorization. Finally some extra properties of the reduction as well as an efficient method for computing a unitary complex symmetric decomposition of a normal matrix are given.     

广义Jacobi矩阵的逆特征问题

本文主要讨论广义Jacobi阵及多个特征对的广义Jacobi阵逆特征问题.通过相似变换将广义Jacobi阵变换为三对角对称矩阵,其特征不变、特征向量只作线性变换,再应用前人理论求得广义Jacobi阵元素ai,|bi|,|ci|有唯一解的充要条件及其具体表达式.     

Wilkinson's inertia‐revealing factorization and its application to sparse matrices

We propose a new inertia‐revealing factorization for sparse symmetric matrices. The factorization scheme and the method for extracting the inertia from it were proposed in the 1960s for dense, banded, or tridiagonal matrices, but they have been abandoned in favor of faster methods. We show that this scheme can be applied to any sparse symmetric matrix and that the fill in the factorization is bounded by the fill in the sparse QR factorization of the same matrix (but is usually much smaller). We describe our serial proof‐of‐concept implementation and present experimental results, studying the method's numerical stability and performance.     

Inverse eigenvalue problems for Jacobi matrices

It is proved that a real symmetric tridiagonal matrix with positive codiagonal elements is uniquely determined by its eigenvalues and the eigenvalues of the largest leading principal submatrix, and can be constructed from these data. The matrix depends continuously on the data, but because of rounding errors the investigated algorithm might in practice break down for large matrices.     

Analytical inversion of general periodic tridiagonal matrices

In this paper we present an analytical forms for the inversion of general periodic tridiagonal matrices, and provide some very simple analytical forms which immediately lead to closed formulae for some special cases such as symmetric or perturbed Toeplitz for both periodic and non-periodic tridiagonal matrices. An efficient computational algorithm for finding the inverse of any general periodic tridiagonal matrices from the analytical form is given, it is suited for implementation using Computer Algebra systems such as MAPLE, MATLAB, MACSYMA, and MATHEMATICA. An example is also given to illustrate the algorithm.     

Efficient initials for computing maximal eigenpair

This paper introduces some efficient initials for a well-known algorithm (an inverse iteration) for computing the maximal eigenpair of a class of real matrices. The initials not only avoid the collapse of the algorithm but are also unexpectedly efficient. The initials presented here are based on our analytic estimates of the maximal eigenvalue and a mimic of its eigenvector for many years of accumulation in the study of stochastic stability speed. In parallel, the same problem for computing the next to the maximal eigenpair is also studied.     

非奇异阵特征极值和条件数的近似计算

本文从共轭梯度法的公式推导出对称正定阵A与三对角阵B的相似关系,B的元素由共轭梯度法的迭代参数确定.因此,对称正定阵的条件数计算可以化成三对角阵条件数的计算,并且可以在共轭梯度法的计算中顺带完成.它只需增加O(s)次的计算量,s为迭代次数.这与共轭梯度法的计算量相比是可以忽略的.当A为非对称正定阵时,只要A非奇异,即可用共轭梯度法计算ATA的特征极值和条件数,从而得出A的条件数.对不同算例的计算表明,这是一种快速有效的简便方法.     

A homotopy algorithm for a symmetric generalized eigenproblem

In this paper, a homotopy algorithm for finding all eigenpairs of a real symmetric matrix pencil (A, B) is presented, whereA andB are realn×n symmetric matrices andB is a positive semidefinite matrix. In the algorithm, pencil (A, B) is first reduced to a pencil , where is a symmetric tridiagonal matrix and is a positive definite and diagonal matrix. Then, the Divide and Conquer strategy with homotopy continuation approach is used to find all eigenpairs of pencil . One can easily form the eigenpair (x,) of pencil (A, B) from the eigenpair (y, ) of pencil with a few computations. Numerical comparisons of our algorithm with the QZ algorithm in the widely used EISPACK library are presented. Numerical results show that our algorithm is strongly competitive in terms of speed, accuracy and orthogonality. The performance of the parallel version of our algorithm is also presented.Research supported in part by NSF under Grant CCR-9024840.     

On some structured inverse eigenvalue problems

This work deals with various finite algorithms that solve two special Structured Inverse Eigenvalue Problems (SIEP). The first problem we consider is the Jacobi Inverse Eigenvalue Problem (JIEP): given some constraints on two sets of reals, find a Jacobi matrix J (real, symmetric, tridiagonal, with positive off-diagonal entries) that admits as spectrum and principal subspectrum the two given sets. Two classes of finite algorithms are considered. The polynomial algorithm which is based on a special Euclid–Sturm algorithm (Householder's terminology) and has been rediscovered several times. The matrix algorithm which is a symmetric Lanczos algorithm with a special initial vector. Some characterization of the matrix ensures the equivalence of the two algorithms in exact arithmetic. The results of the symmetric situation are extended to the nonsymmetric case. This is the second SIEP to be considered: the Tridiagonal Inverse Eigenvalue Problem (TIEP). Possible breakdowns may occur in the polynomial algorithm as it may happen with the nonsymmetric Lanczos algorithm. The connection between the two algorithms exhibits a similarity transformation from the classical Frobenius companion matrix to the tridiagonal matrix. This result is used to illustrate the fact that, when computing the eigenvalues of a matrix, the nonsymmetric Lanczos algorithm may lead to a slow convergence, even for a symmetric matrix, since an outer eigenvalue of the tridiagonal matrix of order n − 1 can be arbitrarily far from the spectrum of the original matrix. This revised version was published online in August 2006 with corrections to the Cover Date.