Forward stable eigenvalue decomposition of rank-one modifications of diagonal matrices. (English) Zbl 1325.65053
Summary: We present a new algorithm for solving an eigenvalue problem for a real symmetric matrix which is a rank-one modification of a diagonal matrix. The algorithm computes each eigenvalue and all components of the corresponding eigenvector with high relative accuracy in \(O(n)\) operations. The algorithm is based on a shift-and-invert approach. Only a single element of the inverse of the shifted matrix eventually needs to be computed with double the working precision. Each eigenvalue and the corresponding eigenvector can be computed separately, which makes the algorithm adaptable for parallel computing. Our results extend to the complex Hermitian case. The algorithm is similar to the algorithm for solving the eigenvalue problem for real symmetric arrowhead matrices from N. Jakovčević Stor et al. [Linear Algebra Appl. 464, 62–89 (2015; Zbl 1302.65087)].
MSC:
| 65F15 | Numerical computation of eigenvalues and eigenvectors of matrices |
| 65G50 | Roundoff error |
| 15-04 | Software, source code, etc. for problems pertaining to linear algebra |
| 15B99 | Special matrices |
Keywords:
eigenvalue decomposition; diagonal-plus-rank-one matrix; real symmetric matrix; arrowhead matrix; high relative accuracy; forward stabilityCitations:
Zbl 1302.65087References:
| [1] | Anderson, E., LAPACK Users’ Guide (1999), SIAM: SIAM Philadelphia · Zbl 0755.65028 |
| [2] | Barlow, J. L., Error analysis of update methods for the symmetric eigenvalue problem, SIAM J. Matrix Anal. Appl., 14, 598-618 (1993) · Zbl 0774.65014 |
| [3] | Bernstein, D. S., Matrix Mathematics: Theory, Facts and Formulas (2009), Princeton Univ. Press: Princeton Univ. Press New Jersey · Zbl 1183.15001 |
| [4] | Borges, C. F.; Gragg, W. B., A parallel divide-and-conquer method for the generalized real symmetric definite tridiagonal eigenproblem, (Reichel, L.; Ruttan, A.; Varga, R. S., Numerical Linear Algebra and Scientific Computing (1993), de Gruyter: de Gruyter Berlin), 11-29 · Zbl 0799.65043 |
| [5] | Bunch, J. R.; Nielsen, C. P., Rank-one modification of the symmetric eigenproblem, Numer. Math., 31, 31-48 (1978) · Zbl 0369.65007 |
| [6] | Cuppen, J. J.M., A divide and conquer method for the symmetric tridiagonal eigenproblem, Numer. Math., 36, 177-195 (1981) · Zbl 0431.65022 |
| [7] | Dekker, T. J., A floating-point technique for extending the available precision, Numer. Math., 18, 224-242 (1971) · Zbl 0226.65034 |
| [8] | Delvaux, S.; Van Barel, M., Structures preserved by matrix inversion, SIAM J. Matrix Anal. Appl., 28, 213-228 (2006) · Zbl 1111.15005 |
| [9] | Dongarra, J.; Sorensen, D., A fully parallel algorithm for the symmetric eigenvalue problem, SIAM J. Sci. Statist. Comput., 8, 139-154 (1987) · Zbl 0627.65033 |
| [10] | Elsner, L.; Rozsa, P., On eigenvectors and adjoints of modified matrices, Linear Multilinear Algebra, 10, 235-247 (1981) · Zbl 0465.15005 |
| [11] | Golub, G. H.; Van Loan, C. F., Matrix Computations (2013), The John Hopkins University Press: The John Hopkins University Press Baltimore · Zbl 1268.65037 |
| [12] | Gu, M.; Eisenstat, S. C., A stable and efficient algorithm for the rank-one modification of the symmetric eigenproblem, SIAM J. Matrix Anal. Appl., 15, 1266-1276 (1994) · Zbl 0807.65029 |
| [13] | Gu, M.; Eisenstat, S. C., A divide-and-conquer algorithm for the symmetric tridiagonal eigenproblem, SIAM J. Matrix Anal. Appl., 16, 79-92 (1995) · Zbl 0821.65019 |
| [14] | Higham, N., Accuracy and Stability of Numerical Algorithms (2002), SIAM: SIAM Philadelphia · Zbl 1011.65010 |
| [15] | Intel Fortran Compiler |
| [16] | Jakovčević Stor, N.; Slapničar, I.; Barlow, J. L., Accurate eigenvalue decomposition of real symmetric arrowhead matrices and applications, Linear Algebra Appl., 464, 62-89 (2015) · Zbl 1302.65087 |
| [17] | The Julia Language |
| [18] | Julia Package Listing |
| [19] | Li, R. C., Solving secular equations stably and efficiently (1994), Computer Science Division, University of California: Computer Science Division, University of California Berkeley, CA, also: LAPACK Working Note 89 |
| [20] | Livne, O.; Brandt, A., \(N\) Roots of the secular equation in \(O(N)\) operations, SIAM J. Matrix Anal. Appl., 24, 439-453 (2002) · Zbl 1017.65035 |
| [21] | MATLAB, The MathWorks, Inc., Natick, MA, USA |
| [22] | Melman, A., Numerical solution of a secular equation, Numer. Math., 69, 483-493 (1995) · Zbl 0821.65020 |
| [23] | O’Leary, D. P.; Stewart, G. W., Computing the eigenvalues and eigenvectors of symmetric arrowhead matrices, J. Comput. Phys., 90, 2, 497-505 (1990) · Zbl 0716.65033 |
| [24] | Parlett, B. N., The Symmetric Eigenvalue Problem (1980), Prentice Hall: Prentice Hall Englewood Cliffs · Zbl 0431.65017 |
| [25] | Stewart, G. W., Matrix Algorithms, vol. II (2001), SIAM: SIAM Philadelphia · Zbl 0984.65031 |
| [26] | Vandebril, R.; Van Barel, M.; Mastronardi, N., Matrix Computations and Semiseparable Matrices, vol. II (2008), The John Hopkins University Press: The John Hopkins University Press Baltimore · Zbl 1141.65019 |
| [27] | Wilkinson, J. H., The Algebraic Eigenvalue Problem (1965), Clarendon Press: Clarendon Press Oxford · Zbl 0258.65037 |
| [28] | Wolfram Mathematica, Documentation Center |
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.
