# Ways to speed up Lanczos algorithm when we have a very dense cluster of many eigenvalues?

Lanczos algorithm can be used to find the largest/smallest eigenvalues of matrices. I am trying to find a good library in C/C++/Rust for finding the smallest singular value (or eigenvalue). I have attempted several open-source implementations of the Lanczos algorithms. I benchmarked them against the svds function in MATLAB.

I find that several open-source implementations are much faster than svds function in MATLAB when computing the biggest singular value of a random uniform[0,1] matrix $$A$$. (The biggest singular values are not clustered, so no issues here.) On the other hand, however, these open-source implementations are extremely slow, much slower than MATLAB when trying to find the smallest singular value of $$A.$$ That's possibly because the smaller singular values are very clustered together, and there are many similar values. Similarly, if I construct a matrix with clustered largest singular values, then finding the largest singular value will also be slow.

What algorithm can be used to make sure that the clustered case will not be too slow (at least within a factor of $$5$$ of the non-clustered case)? Does anybody know a good library?

• I'm confused. Are you trying to find the eigenvalues or the singular values of the matrix? Feb 18 at 13:53
• @BillGreene Does not matter for a symmetric positive-definite matrix. Do not worry too much about this. If you can solve one you can probably easily solve the other. Feb 18 at 13:59
• @lightxbulb dgesvd is not helpful, because it finds ALL singular values, which is a waste of time if I only want the smallest. On the other hand, I could not figure out how to use ARPACK properly. Feb 18 at 14:15
• It very much DOES matter as far as the numerical algorithm used! If you want the matlab equivalent of the algorithm in the wiki article you reference, you should be using eigs, not svds. Feb 18 at 14:22
• You should also pay close attention to the value of the "SubspaceDimension" option to eigs. For many closely-spaced eigenvalues, this variable should be around 2X the number of eigenvalues you expect in the cluster. Feb 18 at 14:31