Paper Info
Title
A Refined Harmonic Lanczos Bidiagonalization Method and an Implicitly Restarted Algorithm for Computing the Smallest Singular Triplets of Large Matrices
Abstract
The harmonic Lanczos bidiagonalization method can be used to compute the smallest singular triplets of a large matrix $A$. We prove that for good enough projection subspaces harmonic Ritz values converge if the columns of $A$ are strongly linearly independent. On the other hand, harmonic Ritz values may miss some desired singular values when the columns of $A$ are almost linearly dependent. Furthermore, harmonic Ritz vectors may converge irregularly and may even fail to converge. Based on the refined projection principle for large matrix eigenproblems due to the first author, we propose a refined harmonic Lanczos bidiagonalization method that takes the Rayleigh quotients of the harmonic Ritz vectors as approximate singular values and extracts the best approximate singular vectors, called the refined harmonic Ritz approximations, from the given subspaces in the sense of residual minimizations. The refined approximations are shown to converge to the desired singular vectors once the subspaces are sufficiently good and the Rayleigh quotients converge. An implicitly restarted refined harmonic Lanczos bidiagonalization algorithm (IRRHLB) is developed. We study how to select the best possible shifts, and suggest refined harmonic shifts that are theoretically better than the harmonic shifts used within the implicitly restarted harmonic Lanczos bidiagonalization algorithm (IRHLB). We propose a novel procedure that can numerically compute the refined harmonic shifts efficiently and accurately. Numerical experiments are reported that compare IRRHLB with five other algorithms based on the Lanczos bidiagonalization process. It appears that IRRHLB is at least competitive with them and can be considerably more efficient when computing the smallest singular triplets.
Year
DOI
Venue
2010
10.1137/080733383
SIAM J. Scientific Computing
Keywords
Field
DocType
svd,reflned harmonic shifts.,bidiagonalization algorithm,smallest singular triplets,implicitly restarted algorithm,lanczos bidiagonalization,large matrices,singular vectors,harmonic shift,reflned projec- tion,harmonic ritz,harmonic ritz value,refined harmonic lanczos,singular values,refined harmonic ritz approximation,refined harmonic lanczos bidiagonalization,harmonic ritz vector,smallest singular triplet,harmonic,implicit restart,harmonic shifts,harmonic lanczos,reflned harmonic,bidiagonalization method,numerical analysis,singular value
Singular value decomposition,Mathematical optimization,Linear independence,Lanczos resampling,Singular value,Matrix (mathematics),Mathematical analysis,Harmonic,Algorithm,Bidiagonalization,Numerical analysis,Mathematics
Journal
Volume
Issue
ISSN
32
2
SIAM Journal on Scientific Computing, 32 (2) (2010): 714-744
Citations 
PageRank 
References 
10
0.67
11
Authors
2
Name
Order
Citations
PageRank
Zhongxiao Jia112118.57
Datian Niu2262.90