Divide and conquer algorithms for computing the eigendecomposition of symmetric diagonal-plus-semiseparable matrices. (English) Zbl 1105.65035
The authors propose, test and compare three fast and stable divide and conquer algorithms for computing all the eigenvalues and eigenvectors of real matrices of the form \(D+U+U^T\), where \(D\) is diagonal and \(U\) is the upper triangular part of a rank-one matrix.
Reviewer: Alan L. Andrew (Bundoora)
MSC:
| 65F15 | Numerical computation of eigenvalues and eigenvectors of matrices |
| 15B57 | Hermitian, skew-Hermitian, and related matrices |
References:
| [1] | C.F. Borges and W.B. Gragg, Divide and conquer for generalized real symmetric definite tridiagonal eigenproblems, in: Proc. of Shanghai Internat. Conf. on Numerical Linear Algebra and Applications, Shanghai (26-30 October 1992) pp. 70-76. |
| [2] | C.F. Borges and W.B. Gragg, A parallel divide and conquer algorithm for the generalized real symmetric definite tridiagonal eigenvalue problem, in: Numerical Linear Algebra, eds. L. Reichel, A. Ruttan and R.S. Varga (de Gruyter, Berlin, 1993) pp. 11-29. · Zbl 0799.65043 |
| [3] | J.R. Bunch, C.P. Nielsen and D.C. Sorensen, Rank-one modification of the symmetric eigenproblem, Numer. Math. 31 (1978) 31-48. · Zbl 0369.65007 · doi:10.1007/BF01396012 |
| [4] | S. Chandrasekaran and M. Gu, A divide-and-conquer algorithm for the eigendecomposition of symmetric block-diagonal plus semi-separable matrices, Preprint, url: ucla.edu/\(\sim\)mgu/dc.ps.z. · Zbl 1047.65023 |
| [5] | S. Chandrasekaran and M. Gu, Fast and stable eigendecomposition of symmetric banded plus semi-separable matrices, Linear Algebra Appl. 313 (2000) 107-114. · Zbl 0959.65057 · doi:10.1016/S0024-3795(00)00106-3 |
| [6] | J.J.M. Cuppen, A divide and conquer method for the symmetric tridiagonal eigenproblem, Numer. Math. 36 (1981) 177-195. · Zbl 0431.65022 · doi:10.1007/BF01396757 |
| [7] | D. Fasino and L. Gemignani, Direct and inverse eigenvalue problems for diagonal-plus-semiseparable matrices, Preprint, url: fibonacci.dm.upipi.it/\(\sim\)gemignan. · Zbl 1053.65025 |
| [8] | I. Gohberg and V. Olshevsky, Fast algorithms with preprocessing for matrix?vector multiplication problems, J. Complexity 10 (1994) 411-427. · Zbl 0820.68051 · doi:10.1006/jcom.1994.1021 |
| [9] | G.H. Golub, Some modified matrix eigenvalue problems, SIAM Rev. 19 (1977) 46-89. · Zbl 0356.65041 · doi:10.1137/1019005 |
| [10] | G.H. Golub and C.F. Van Loan, Matrix Computations, 3rd ed. (John Hopkins Univ. Press, Baltimore, MD, 1996). · Zbl 0865.65009 |
| [11] | W.B. Gragg, J.R. Thornton and D.D. Warner, Parallel divide and conquer algorithms for the symmetric tridiagonal eigenvalue problem and bidiagonal singular value problem, in: Modeling and Simulation, Part 1, Vol. 23, eds. W.G. Vogt and M.H. Mickle (Univ. Pittsburgh School of Engineering, Pittsburgh, 1992) pp. 49-56. |
| [12] | G.J. Groenewald, M.A. Petersen and A.C.M. Ran, Factorization of integral operators with semi-separable kernel and symmetries, Preprint, url: www.cs.vu.nl/\(\sim\)ran/intopfac2.ps. · Zbl 1080.47039 |
| [13] | M. Gu and S.C. Eisenstat, A stable and efficient algorithm for the rank-one modification of the symmetric eigenproblem, SIAM J. Matrix Anal. Appl. 15(4) (1994) 1266-1276. · Zbl 0807.65029 · doi:10.1137/S089547989223924X |
| [14] | M. Gu and S.C. Eisenstat, A divide-and-conquer algorithm for the symmetric tridiagonal eigenvalue problem, SIAM J. Matrix Anal. Appl. 16(1) (1995) 172-191. · Zbl 0815.65050 · doi:10.1137/S0895479892241287 |
| [15] | N. Mastronardi, S. Chandrasekaran and S. Van Huffel, Fast and stable algorithms for reducing diagonal plus semi-separable matrices to tridiagonal and bidiagonal form, BIT 41(1) (2001) 149-157. · Zbl 0984.65041 · doi:10.1023/A:1021973919347 |
| [16] | C. Paige, The computation of eigenvalues and eigenvectors of very large sparse matrices, Ph.D. thesis, University of London, UK (1971). |
| [17] | H.D. Simon, The Lanczos algorithm with partial reorthogonalization, Math. Comp. 42 (1984) 115-142. · Zbl 0546.65017 · doi:10.1090/S0025-5718-1984-0725988-X |
| [18] | H.P. Starr, Jr., On the numerical solution of one?dimensional integral and differential equations, Ph.D. thesis, Department of Computer Science, Yale University (May 1992). |
| [19] | M. Van Barel, R. Vandebril and 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). · Zbl 1089.65032 |
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.
