On computing the eigenvectors of a class of structured matrices. (English) Zbl 1086.65035
Summary: A real symmetric matrix of order \(n\) has a full set of orthogonal eigenvectors. The most used approach to compute the spectrum of such matrices reduces first the dense symmetric matrix into a symmetric structured one, i.e., tridiagonal matrices or semiseparable matrices. This step is accomplished in \(O(n^{3})\) operations. Once the latter symmetric structured matrix is available, its spectrum is computed in an iterative fashion by means of the \(QR\) method in \(O(n^{2})\) operations.
In principle, the whole set of eigenvectors of the latter structured matrix can be computed by means of inverse iteration in \(O(n^{2})\) operations.
The blemish in this approach is that the computed eigenvectors may not be numerically orthogonal if clusters are present in the spectrum. To enforce orthogonality the Gram-Schmidt procedure is used, requiring \(O(n^{3})\) operations in the worst case.
In this paper a fast and stable method to compute the eigenvectors of tridiagonal and semiseparable matrices which does not suffer from the loss of orthogonality due to the presence of clusters in the spectrum is presented. The algorithm requires \(O(n^{2})\) floating point operations if clusters of small size are present in the spectrum.
In principle, the whole set of eigenvectors of the latter structured matrix can be computed by means of inverse iteration in \(O(n^{2})\) operations.
The blemish in this approach is that the computed eigenvectors may not be numerically orthogonal if clusters are present in the spectrum. To enforce orthogonality the Gram-Schmidt procedure is used, requiring \(O(n^{3})\) operations in the worst case.
In this paper a fast and stable method to compute the eigenvectors of tridiagonal and semiseparable matrices which does not suffer from the loss of orthogonality due to the presence of clusters in the spectrum is presented. The algorithm requires \(O(n^{2})\) floating point operations if clusters of small size are present in the spectrum.
MSC:
| 65F15 | Numerical computation of eigenvalues and eigenvectors of matrices |
Keywords:
symmetric matrix; tridiagonal matrix; semiseparable matrix; eigenvalues; eigenvectors; numerical examples; algorithm; inverse iteration; orthogonality; Gram-Schmidt procedureReferences:
| [1] | Dax, A., The orthogonal Rayleigh quotient iteration (ORQI) method, Linear Algebra Appl., 358, 1-3, 23-43 (2003) · Zbl 1016.65015 |
| [2] | I.S. Dhillon, A new \(\operatorname{O}( N^2)\); I.S. Dhillon, A new \(\operatorname{O}( N^2)\) |
| [3] | Dhillon, I. S., Current inverse iteration software can fail, BIT, 38, 4, 685-704 (1998) · Zbl 0918.65025 |
| [4] | Dhillon, I. S.; Malyshev, A. N., Inner deflation of symmetric, tridiagonal matrices, Linear Algebra Appl., 358, 1-3, 139-144 (2003) · Zbl 1012.65035 |
| [5] | Dhillon, I. S.; Parlett, B. N., Multiple representations to compute orthogonal eigenvectors of symmetric tridiagonal matrices, Linear Algebra Appl., 387, 1-28 (2004) · Zbl 1055.65048 |
| [6] | Dhillon, I. S.; Parlett, B. N., Orthogonal eigenvectors and relative gaps, SIAM J. Matrix Anal. Appl., 25, 3, 858-899 (2004) · Zbl 1068.65046 |
| [7] | Golub, G. H.; Van Loan, C. F., Matrix Computations (1989), The Johns Hopkins University Press: The Johns Hopkins University Press Baltimore, MD · Zbl 0733.65016 |
| [8] | Liesen, J.; Strakos, Z., Convergence of GMRES for tridiagonal toeplitz matrices, SIAM J. Matrix Anal. Appl., 26, 1, 233-251 (2004) · Zbl 1079.65031 |
| [9] | Parlett, B. N., The Symmetric Eigenvalue Problem (1998), SIAM: SIAM Philadelphia, PA · Zbl 0885.65039 |
| [10] | Parlett, B. N.; Dhillon, I. S., Fernando’s solution to Wilkinson’s problem: an application of double factorization, Linear Algebra Appl., 267, 247-279 (1997) · Zbl 0886.65033 |
| [11] | J. Rimas, On computing of arbitrary positive integer powers for one type of symmetric tridiagonal of even order-I, Appl. Math. Comput., in press.; J. Rimas, On computing of arbitrary positive integer powers for one type of symmetric tridiagonal of even order-I, Appl. Math. Comput., in press. · Zbl 1082.65523 |
| [12] | M. Van Barel, R. Vandebril, N. Mastronardi, The Lanczos-Ritz values appearing in an orthogonal similarity reduction of a matrix into semiseparable form, Report TW 360, Department of Computer Science, Katholieke Universiteit Leuven, Belgium, 2003, SIAM J. Matrix Anal. Appl., in press.; M. Van Barel, R. Vandebril, N. Mastronardi, The Lanczos-Ritz values appearing in an orthogonal similarity reduction of a matrix into semiseparable form, Report TW 360, Department of Computer Science, Katholieke Universiteit Leuven, Belgium, 2003, SIAM J. Matrix Anal. Appl., in press. · Zbl 1089.65032 |
| [13] | R. Vandebril, M. Van Barel, N. Mastronardi, An implicit QR algorithm for semiseparable matrices to compute the eigendecomposition of symmetric matrices, Report TW 367, Department of Computer Science, Katholieke Universiteit Leuven, Belgium, August 2003. Numer. Linear Algebr. on-line.; R. Vandebril, M. Van Barel, N. Mastronardi, An implicit QR algorithm for semiseparable matrices to compute the eigendecomposition of symmetric matrices, Report TW 367, Department of Computer Science, Katholieke Universiteit Leuven, Belgium, August 2003. Numer. Linear Algebr. on-line. · Zbl 1164.65368 |
| [14] | Wilkinson, J. H., The Algebraic Eigenvalue Problem (1965), Oxford University Press: Oxford University Press Oxford · Zbl 0258.65037 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
