next up previous contents index
Next: Golub-Kahan-Lanczos Bidiagonalization Procedure. Up: Iterative Algorithms   J. Previous: Which Singular Values and   Contents   Index


Golub-Kahan-Lanczos Method

We have seen that the Hermitian eigenvalue problem and the singular value decomposition are closely related. The singular values of a matrix $A$ are the square roots of the eigenvalues of Hermitian matrix $A^{\ast} A$. Consequently, we can calculate singular values by applying the Hermitian Lanczos method to $A^{\ast} A$. The matrix-vector product required by the algorithm can be computed in the form $A^{\ast} (A q)$.

In this section we consider applying the Lanczos method of §4.4 to $H(A)$. The special structure of $H(A)$ lets us choose a special starting vector that leads to a cheaper algorithm that produces two sequences of vectors, one intended to span the left singular vectors and one for the right singular vectors. In addition, it reduces $A$ to bidiagonal form $B$; i.e., $B$ is nonzero only on the main diagonal and first superdiagonal. We derive it from first principles and then show how it is related to Lanczos as described in §4.4.



Subsections
next up previous contents index
Next: Golub-Kahan-Lanczos Bidiagonalization Procedure. Up: Iterative Algorithms   J. Previous: Which Singular Values and   Contents   Index
Susan Blackford 2000-11-20