SparseMatrix mat = matw * mathc * matq;

Matrix bar = mat.ToDense();

SVD svdtable = new SVD(bar);

Are there plans to make a sparsematrix SVD function?  Thanks!

Jeffrey Baron
jbaron@mediamark.com

Currently NML does not have a direct method for computing the Singular Value Decomposition of a SparseMatrix object. In your code you attempt to convert a SparseMatrix to a dense matrix, but a dense matrix requires more memory and that causes the out of memory error.

A dense matrix of that size would require 26000 X 26000 X 8 = 5,408,000,000 bytes, about 5Gb or RAM. The SVD method uses internally a work area which is 6-8 times larger than the size of the original matrix, this means you would need about 40Gb.  

Even if you had and could use that large amount of memory, it would take ages to compute the singular value decomposition of a matrix because the SVD computation is an O(n^3) process, meaning that when the matrix size is doubled the operation count is multiplied by a factor of 8.

It is possible that there is an alternative way to solve the problem. Do you need to compute all the singular values and vectors or just a few of them? 

Trifon Triantafillidis

Lead Developer

Thanks!

Jeffrey Baron
jbaron@mediamark.com

Can you send me the matrix data?

Here you can find how to save a matrix in a file : http://www.bluebit.gr/forum/Topic63-3-1.aspx

Trifon Triantafillidis

Lead Developer

What are these alternatives that you have mentioned?

Are they destinated to generate just a few singular values and vector instead of all the three matrices?

For example:

From a matrix

26.000 X 40.000

And generate:

26.000 X 150 ,   150 X 150  & 40.000 X 150

Instead of all

See the uploaded document in this post. An algorithm that would converge to the dominant singular vectors would be as follows:

Let A be a m x n matrix. Define u(0) as an m-sized non zero vector and v(0) as an n-sized non zero vector.

Start iterating:

Loop until convergence ( e.g  ( u(t) - u(t-1) )^2 < epsilon )

u(t) = A * v(t-1) /  Sqrt( v(t-1) * v(t-1) )

v(t) = u(t) * A /  Sqrt( u(t-1) * u(t-1) )

Repeat

Then u(t) t->oo will converge to the dominant left singular vector, v(t) to the dominant right singular vector and  the normalization factor Sqrt( v(t)*v(t)  will converge to the larger singular value.

After finding u1, s1, v1 then we may subtract their product from matrix A and get A(2). Repeating the process we find u2, s2, v2 and so on.

Trifon Triantafillidis

Lead Developer

	Post Attachments
	Dax.pdf (37 views, 554.11 KB)

I will check it.

I am working on some sparse SVD routines now, do you want to mail me your matrix (in sparse format) so that I will run some tests with it?

Trifon Triantafillidis

Lead Developer

But I´m afraid that it is not posible for me at this moment to send it in sparse format. I work with BML 2.5. I will pursache later a version with sparse matrices but before, I have to organize all.

If you want, I can send you by ftp or something like that, the dense matrix in a binay format.

Do you want me to send it?

G