scalanlp/breeze — pull request #240 by vrilleup (2014-05-04 20:22:27+00:00)
Title: modify sparse svd implementation to support any matrix type

Hi David and Matthew,

I made the changes to the sparse svd implementation. As David suggested in the email, it takes anything that can be multiplied by a DenseVector[Double]. In many cases, from a sparse matrix M the multiplication M*M^t is non-sparse. So in the reverse communication of arpack, two multiplications was made separately, i.e. first z=M^t*x, then y=M*z. This could avoid the OOM when allocating memory for M*M^t in large scale scenarios. In the mul function, there is a parameter to indicate whether the DenseVector is multiplied with the matrix or its transpose. Some explanations to the changes:

1. I added some argument checks in the implementation. arpack requires nev < ncv <= n, so k should be strictly less than min(cols, rows).

2. Exposed tolerance as parameter in the general implementation. I think this is useful to the caller since the tolerance controls the number of iterations.

3. For svds on CSCMatrix[Double], the signature is the same as before. I just changed it to call the general implementation. I created a helper class to cache the transpose of input matrix so that the transpose does not need to be recreated in each iteration. When rows > cols, it uses the transposed matrix when calling the general implementation. This would save some arpack working memory since the working memory is propositional to rows.
Changed default tolerance for CSCMatrix[Double] from 0.001 to 1e-6, otherwise the test will fail on singular vectors when asserting with 1e-5 Double tolerance.
It seems that the implicit def doesn't automatically apply to CSCMatrixWithTranspose. So I explicitly use svd.Svd_Sparse_Impl[CSCMatrixWithTranspose] to make it work. Is there any way to let it work implicitly?

4. Improved the test to check singular vectors, as well as singular values.