×

A refined harmonic Lanczos bidiagonalization method and an implicitly restarted algorithm for computing the smallest singular triplets of large matrices. (English) Zbl 1215.65072

The refined harmonic Lanczos bidiagonalization (RHLB) of this paper is the same as proposed by J. Baglama and L. Reichel [SIAM J. Sci. Comput. 27, No. 1, 19–42 (2005; Zbl 1087.65039)] but it is derived here in a different way. The approximate singular values are obtained as Rayleigh quotients of harmonic Ritz vectors and the eigenvectors are obtained form the subspaces based on residual minimization.
A convergence analysis is given and convergence is proved once the subspaces are ‘good enough’. An implicit restart of the method (IRRHLB) is however needed in practice. Refined harmonic shifts are suggested that are in theory better than the shifts proposed in the unrefined version (IRHLB) proposed by the authors [SIAM J. Matrix Anal. Appl. 25, No. 1, 246–265 (2003; Zbl 1063.65030)].
The numerical procedure to compute these shifts is described and the whole algorithm is extensively tested on practical large scale problems. A numerical comparison with five other state-of-the-art algorithms shows a compatible, if not better performance. It is also illustrated that the method works for the largest singular triplets as well, but it is definitely better for the smallest ones.

MSC:

65F20 Numerical solutions to overdetermined systems, pseudoinverses
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
PDFBibTeX XMLCite
Full Text: DOI arXiv