Multiple representations to compute orthogonal eigenvectors of symmetric tridiagonal matrices. (English) Zbl 1055.65048
The authors present and analyze a new O\((nk)\) algorithm, \({\mathtt MR}^3\), for computing \(k\) eigenvectors of a real \(n\times n\) symmetric tridiagonal matrix. Sufficient conditions are established for the computed eigenvectors to be orthogonal, to working accuracy, and for the residuals to be small. The algorithm combines the use of the authors’ earlier algorithm Getvec [SIAM J. Matrix Anal. Appl. 25, No. 3, 858–899 (2004)] with a shift strategy, using several different shifts described by a representation tree. The shifts enable it to cope with clusters of close eigenvalues.
Reviewer: Alan L. Andrew (Bundoora)
MSC:
| 65F15 | Numerical computation of eigenvalues and eigenvectors of matrices |
| 15A18 | Eigenvalues, singular values, and eigenvectors |
| 15A23 | Factorization of matrices |
Keywords:
symmetric tridiagonal matrix; eigenvectors; orthogonality; high relative accuracy; relatively robust representations; clustered eigenvaluesSoftware:
LAPACKReferences:
| [1] | Anderson, E.; Bai, Z.; Bischof, C.; Demmel, J.; Dongarra, J.; Du Croz, J.; Greenbaum, A.; Hammarling, S.; McKenney, A.; Ostrouchov, S.; Sorensen, D., LAPACK Users’ Guide (1995), SIAM: SIAM Philadelphia, 324 p · Zbl 0843.65018 |
| [2] | Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L., Introduction to Algorithms, MIT Electrical and Computer Science Series (1992), MIT Press, ISBN 0-262-03141-8 · Zbl 1158.68538 |
| [3] | Cuppen, J. J.M., A divide and conquer method for the symmetric tridiagonal eigenproblem, Numer. Math., 36, 177-195 (1981) · Zbl 0431.65022 |
| [4] | Demmel, J.; Kahan, W., Accurate singular values of bidiagonal matrices, SIAM J. Sci. Stat. Comput., 11, 5, 873-912 (1990) · Zbl 0705.65027 |
| [5] | I.S. Dhillon, A new \(O(n^2)\) algorithm for the symmetric tridiagonal eigenvalue/eigenvector problem, Ph.D. Thesis, Computer Science Division, University of California, Berkeley, California, May 1997. Available as UC Berkeley Technical Report No. UCB//CSD-97-971; I.S. Dhillon, A new \(O(n^2)\) algorithm for the symmetric tridiagonal eigenvalue/eigenvector problem, Ph.D. Thesis, Computer Science Division, University of California, Berkeley, California, May 1997. Available as UC Berkeley Technical Report No. UCB//CSD-97-971 |
| [6] | Dhillon, I. S.; Parlett, B. N., Orthogonal eigenvectors and relative gaps, SIAM J. Matrix Anal. Appl., 25, 4 (2004), Also LAPACK Working Note 154 (ut-cs-02-474) · Zbl 1068.65046 |
| [7] | Eisenstat, S.; Ipsen, I., Relative perturbation techniques for singular value problems, SIAM J. Numer. Anal., 32, 6 (1995) · Zbl 0837.65039 |
| [8] | Fernando, K.; Parlett, B., Accurate singular values and differential qd algorithms, Numer. Math., 67, 2, 191-229 (1994) · Zbl 0814.65036 |
| [9] | Golub, Gene H.; Van Loan, Charles F., Matrix Computations (1996), Johns Hopkins University Press · Zbl 0865.65009 |
| [10] | Gu, M.; Eisenstat, S. C., A divide-and-conquer algorithm for the symmetric tridiagonal eigenproblem, SIAM J. Matrix Anal. Appl., 16, 1, 172-191 (1995) · Zbl 0815.65050 |
| [11] | Parlett, B. N., The spectral diameter as a function of the diagonal entries, Numer. Linear Algebra Appl., 1, 1-7 (2003) · Zbl 1071.65539 |
| [12] | 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 |
| [13] | Parlett, B. N.; Dhillon, I. S., Relatively robust representations of symmetric tridiagonals, Linear Algebra Appl., 309, 121-151 (2000) · Zbl 0948.65026 |
| [14] | Rutishauser, H., Der quotienten-differenzen-algorithmus, Z. Angew. Math. Phys., 5, 223-251 (1954) · Zbl 0055.34702 |
| [15] | J. Rutter, A serial implementation of Cuppen’s divide and conquer algorithm for the symmetric eigenvalue problem, Mathematics Dept. Master’s Thesis, University of California, 1994; J. Rutter, A serial implementation of Cuppen’s divide and conquer algorithm for the symmetric eigenvalue problem, Mathematics Dept. Master’s Thesis, University of California, 1994 |
| [16] | 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.
