Divide and conquer algorithms for computing the eigendecomposition of symmetric diagonal-plus-semiseparable matrices

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.

   Google Scholar 

3. J.R. Bunch, C.P. Nielsen and D.C. Sorensen, Rank-one modification of the symmetric eigenproblem, Numer. Math. 31 (1978) 31–48.

   Google Scholar 

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/~mgu/dc.ps.z.

5. S. Chandrasekaran and M. Gu, Fast and stable eigendecomposition of symmetric banded plus semi-separable matrices, Linear Algebra Appl. 313 (2000) 107–114.

   Google Scholar 

6. J.J.M. Cuppen, A divide and conquer method for the symmetric tridiagonal eigenproblem, Numer. Math. 36 (1981) 177–195.

   Google Scholar 

7. D. Fasino and L. Gemignani, Direct and inverse eigenvalue problems for diagonal-plus-semiseparable matrices, Preprint, url: fibonacci.dm.upipi.it/~gemignan.

8. I. Gohberg and V. Olshevsky, Fast algorithms with preprocessing for matrix–vector multiplication problems, J. Complexity 10 (1994) 411–427.

   Google Scholar 

9. G.H. Golub, Some modified matrix eigenvalue problems, SIAM Rev. 19 (1977) 46–89.

   Google Scholar 

10. G.H. Golub and C.F. Van Loan, Matrix Computations, 3rd ed. (John Hopkins Univ. Press, Baltimore, MD, 1996).

    Google Scholar 

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.

    Google Scholar 

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/~ran/intopfac2.ps.

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.

    Google Scholar 

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.

    Google Scholar 

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.

    Google Scholar 

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.

    Google Scholar 

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).

Download references