Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It only takes a minute to sign up.
Sign up to join this community
I have been given the task of implementing SVD using the Lanczos method.
As I understand it only helps to find eigenvalues using a sequence of tridiagonal matrices, but i don't know how to apply this to actually computing the SVD.
Do I need to approximate the given matrix with tridiagonal and then compute SVD with different algorithm or something different?
In theory, you can "square up" $A$ as Jan illustrates in his answer, but you really don't want to do that when actually computing the SVD, as it comes at a significant cost of accuracy. A better approach that leverages standard Lanczos tridiagonalization is to perform the tridiagonalization of the matrix $\left[\begin{smallmatrix} 0 & A \\ A^T & 0 \end{smallmatrix}\right]$. This avoids the accuracy loss from squaring up, and you can extract both the singular values and their accompanying left and right vectors from the eigendecomposition of this larger matrix.
Ideally though what you're looking for is Lanczos bidiagonalization. Lanczos bidiagonlization is intimately related to the tridiagonalization of the cyclic matrix, but can also be derived on its own.
PROPACK is a good example of an existing software package that implements Lanczos bidiagonalization for SVD. It sounds like you're required to implement it yourself, but the page I'm linking to here provides a number of papers that provide an introduction to the algorithmic approach. You can likely ignore the "partial reorthogonalization" that is a key part of the PROPACK package and focus on the bidiagonalization.
Of course, if this isn't a homework assignment or educational exercise, then I would suggest considering using PROPACK or related packages instead of implementing it yourself! There's no need to reinvent the wheel. SLEPc also includes a Lanczos SVD implementation. The SLEPc documentation provides a good introduction to Lanczos bidiagonalization as well.
