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.     

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.     

Characterizations of inverse M-matrices with special zero patterns

In this paper, we provide some characterizations of inverse M-matrices with special zero patterns. In particular, we give necessary and sufficient conditions for k-diagonal matrices and symmetric k-diagonal matrices to be inverse M-matrices. In addition, results for triadic matrices, tridiagonal matrices and symmetric 5-diagonal matrices are presented as corollaries.     

Eigenvalues of Ax = λBx for real symmetric matrices A and B computed by reduction to a pseudosymmetric form and the HR process

The paper presents a method for solving the eigenvalue problem Ax = λBx, where A and B are real symmetric but not necessarily positive definite matrices, and B is nonsingular. The method reduces the general case into a form Cz = λz where C is a pseudosymmetric matrix. A further reduction of C produces a tridiagonal pseudosymmetric form to which the iterative HR process is applied. The tridiagonal pseudosymmetric form is invariant under the HR transformations. The amount of computation is significantly less than in treating the problem by a general method.     

A property of eigenvalue bounds for a class of symmetric tridiagonal interval matrices

The eigenvalue bounds of interval matrices are often required in some mechanical and engineering fields. In this paper, we consider an interval eigenvalue problem with symmetric tridiagonal matrices. A theoretical result is obtained that under certain assumptions the upper and lower bounds of interval eigenvalues of the problem must be achieved just at some vertex matrices of the interval matrix. Then a sufficient condition is provided to guarantee the assumption to be satisfied. The conclusion is illustrated also by a numerical example. Copyright © 2010 John Wiley & Sons, Ltd.     

Extremal inverse eigenvalue problem for symmetric doubly arrow matrices

In this paper, we consider the following inverse eigenvalue problem: to construct a real symmetric doubly arrow matrix A from the minimal and maximal eigenvalues of all its leading principal submatrices. The necessary and sufficient condition for the solvability of the problem is derived. We also give a necessary and sufficient condition in order that the constructed matrices can be nonnegative. Our results are constructive and they generate algorithmic procedures to construct such matrices.     

A method of congruent type for linear systems with conjugate-normal coefficient matrices

Minimal residual methods, such as MINRES and GMRES, are well-known iterative versions of direct procedures for reducing a matrix to special condensed forms. The method of reduction used in these procedures is a sequence of unitary similarity transformations, while the condensed form is a tridiagonal matrix (MINRES) or a Hessenberg matrix (GMRES). The algorithm CSYM proposed in the 1990s for solving systems with complex symmetric matrices was based on the tridiagonal reduction performed via unitary congruences rather than similarities. In this paper, we construct an extension of this algorithm to the entire class of conjugate-normal matrices. (Complex symmetric matrices are a part of this class.) Numerical results are presented. They show that, on many occasions, the proposed algorithm has a superior convergence rate compared to GMRES.     

Tridiagonal and upper triangular inverse M-matrices

In this paper we characterize the nonnegative nonsingular tridiagonal matrices belonging to the class of inverse M-matrices. We give a geometric equivalence for a nonnegative nonsingular upper triangular matrix to be in this class. This equivalence is extended to include some reducible matrices.     

Extremal eigenvalue intervals of symmetric tridiagonal interval matrices

Computing the extremal eigenvalue bounds of interval matrices is non‐deterministic polynomial‐time (NP)‐hard. We investigate bounds on real eigenvalues of real symmetric tridiagonal interval matrices and prove that for a given real symmetric tridiagonal interval matrices, we can achieve its exact range of the smallest and largest eigenvalues just by computing extremal eigenvalues of four symmetric tridiagonal matrices.     

The {\cal {D Q R}} algorithm, basic theory, convergence, and conditional stability

Summary. We describe a fast matrix eigenvalue algorithm that uses a matrix factorization and reverse order multiply technique involving three factors and that is based on the symmetric matrix factorization as well as on –orthogonal reduction techniques where is computed from the given matrix . It operates on a similarity reduction of a real matrix to general tridiagonal form and computes all of 's eigenvalues in operations, where the part of the operations is possibly performed over , instead of the 7–8 real flops required by the eigenvalue algorithm. Potential breakdo wn of the algorithm can occur in the reduction to tridiagonal form and in the –orthogonal reductions. Both, however, can be monitored during the computations. The former occurs rather rarely for dimensions and can essentially be bypassed, while the latter is extremely rare and can be bypassed as well in our conditionally stable implementation of the steps. We prove an implicit theorem which allows implicit shifts, give a convergence proof for the algorithm and show that is conditionally stable for general balanced tridiagonal matrices . Received April 25, 1995 / Revised version received February 9, 1996     

A note on “Methods for constructing distance matrices and the inverse eigenvalue problem”

In this paper, a symmetric nonnegative matrix with zero diagonal and given spectrum, where exactly one of the eigenvalues is positive, is constructed. This solves the symmetric nonnegative eigenvalue problem (SNIEP) for such a spectrum. The construction is based on the idea from the paper Hayden, Reams, Wells, “Methods for constructing distance matrices and the inverse eigenvalue problem”. Some results of this paper are enhanced. The construction is applied for the solution of the inverse eigenvalue problem for Euclidean distance matrices, under some assumptions on the eigenvalues.     

关于周期对称三对角矩阵的广义特征值反问题

在给定部分特征值、部分特征向量及附加条件下提出了一类反问题,并给出了此问题解存在性的证明及求解的算法.     

A Wilkinson-like multishift QR algorithm for symmetric eigenvalue problems and its global convergence

In 1989, Bai and Demmel proposed the multishift QR algorithm for eigenvalue problems. Although the global convergence property of the algorithm (i.e., the convergence from any initial matrix) still remains an open question for general nonsymmetric matrices, in 1992 Jiang focused on symmetric tridiagonal case and gave a global convergence proof for the generalized Rayleigh quotient shifts. In this paper, we propose Wilkinson-like shifts, which reduce to the standard Wilkinson shift in the single shift case, and show a global convergence theorem.     

A new updating method for the damped mass-spring systems

In this paper, we concern the inverse problem of constructing a monic quadratic pencil which possesses the prescribed partial eigendata, and the damping matrix and stiffness matrix are symmetric tridiagonal. Furthermore, the stiffness matrix is positive semi-definite and weakly diagonally dominant, which has positive diagonal elements and negative off-diagonal elements. Based on the solution of the inverse eigenvalue problem, we apply the alternating direction method with multiplier to solve the finite element model updating problem for the serially linked mass-spring system. The positive semi-definiteness of stiffness matrix, nonnegativity of stiffness and the physical connectivity of the original model are preserved. Numerical results show that our proposed method works well.     

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.     

Eigenvalue distributions of large Hermitian matrices; Wigner's semi-circle law and a theorem of Kac,Murdock, and Szegö

Wigner's semi-circle law describes the eigenvalue distribution of certain large random Hermitian matrices. A new proof is given for the case of Gaussian matrices, that involves reducing a random matrix to tridiagonal form by a method that is well known as a technique for numerical computation of eigenvalues. The result is a generalized Toeplitz matrix whose eigenvalue distribution can be found using a theorem of Kac, Murdock, and Szegö. A new and more elementary proof of the latter is also given. The arguments use only direct L² estimates, rather than the transform methods or moment calculations employed previously.     

Finding the Maximal Eigenpair for a Large,Dense,Symmetric Matrix based on Mufa Chen's Algorithm

A hybrid method is presented for determining maximal eigenvalue and its eigenvector(called eigenpair)of a large,dense,symmetric matrix.Many problems require finding only a small part of the eigenpairs,and some require only the maximal one.In a series of papers,efficient algorithms have been developed by Mufa Chen for computing the maximal eigenpairs of tridiagonal matrices with positive off-diagonal elements.The key idea is to explicitly construet effective initial guess of the maximal eigenpair and then to employ a self-closed iterative algorithm.In this paper we will extend Mufa Chen's algorithm to find maximal eigenpair for a large scale,dense,symmetric matrix.Our strategy is to first convert the underlying matrix into the tridiagonal form by using similarity transformations.We then handle the cases that prevent us from applying Chen's algorithm directly,e.g.,the cases with zero or negative super-or sub-diagonal elements.Serval numerical experiments are carried out to demonstrate the efficiency of the proposed hybrid method.     

Isospectral flow method for nonnegative inverse eigenvalue problem with prescribed structure

The nonnegative inverse eigenvalue problem is that given a family of complex numbers λ={λ₁,…,λ_n}, find a nonnegative matrix of order n with spectrum λ. This problem is difficult and remains unsolved partially. In this paper, we focus on its generalization that the reconstructed nonnegative matrices should have some prescribed entries. It is easy to see that this new problem will come back to the common nonnegative inverse eigenvalue problem if there is no constraint of the locations of entries. A numerical isospectral flow method which is developed by hybridizing the optimization theory and steepest descent method is used to study the reconstruction. Moreover, an error estimate of the numerical iteration for ordinary differential equations on the matrix manifold is presented. After that, a numerical method for the nonnegative symmetric inverse eigenvalue problem with prescribed entries and its error estimate are considered. Finally, the approaches are verified by the numerical test results.     

Characterization of symmetric M-matrices as resistive inverses

We aim here at characterizing those nonnegative matrices whose inverse is an irreducible Stieltjes matrix. Specifically, we prove that any irreducible Stieltjes matrix is a resistive inverse. To do this we consider the network defined by the off-diagonal entries of the matrix and we identify the matrix with a positive definite Schrödinger operator whose ground state is determined by the lowest eigenvalue of the matrix and the corresponding positive eigenvector. We also analyze the case in which the operator is positive semidefinite which corresponds to the study of singular irreducible symmetric M-matrices.     

On inverse eigenvalue problems for block Toeplitz matrices with Toeplitz blocks

We propose an algorithm for solving the inverse eigenvalue problem for real symmetric block Toeplitz matrices with symmetric Toeplitz blocks. It is based upon an algorithm which has been used before by others to solve the inverse eigenvalue problem for general real symmetric matrices and also for Toeplitz matrices. First we expose the structure of the eigenvectors of the so-called generalized centrosymmetric matrices. Then we explore the properties of the eigenvectors to derive an efficient algorithm that is able to deliver a matrix with the required structure and spectrum. We have implemented our ideas in a Matlab code. Numerical results produced with this code are included.