Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

SVDS-- what is the point of using it and is it ever faster than SVD??

Asked by Clare on 22 Jul 2013

My program finds the eigenvalues of a bunch of matrices and adds them together. But the matrices can get really big and sparse, and this adds to my computation time. I'm using the function SVD to get the eigenvalues, so I tried using the sparse version, SVDS, since I only need the biggest eigenvalues anyway. This wasn't any faster. In fact, I think it's SLOWER! If this is the case, I don't see why SVDS exists. I need to find a sparse matrix operation that will reduce my computation time. Thanks!

8 Comments

dpb on 22 Jul 2013

If it were more sparse or if there was a different regularity in the existing sparsity either could make a difference, yes. All in all, it'd probably be more likely to make a difference if there were some recognizable/usable pattern in the sparsity over just numbers. What, if any, analysis SVDS does internally on that I don't know.

Clare on 22 Jul 2013

When you say usable pattern, do you mean usable to do other operations? I'm wondering if there is a workaround to use instead of SVDS.

Jan Simon on 23 Jul 2013

@Clare: When the programmer knows, that a matrix is a block-sparse matrix with all non-zero elements in square blocks of a growing size at the main diagonal, the SVD can be calculated much faster. It is like the application of a Gauss decomposition for an upper triangle matrix. Then you do not have to search for pivot elements under the main diagonal.

An algorithm can be much faster when a known pattern can be exploited, but the programming and testing of an individually adjusted solver will take much time. So it is worth to check, if you need 2 weeks for programming only to save 4 seconds of run time.

Clare

Tags

Products

No products are associated with this question.

2 Answers

Answer by Matt J on 22 Jul 2013
Edited by Matt J on 22 Jul 2013
Accepted answer

Really big means millions by millions. I use the sparse type for the matrix, but still it doesn't seem to speed things up.

I assume the comparison between SVD and SVDS that you're performing is on a scaled down version of this matrix. There is no way a "millions by millions" matrix can be stored in anything but sparse type and there is no way you can be running SVD on a sparse type matrix (it would return an error).

If your tests are based on small scale versions of your actual matrix, we need to ask how small. Definitely the gains in SVDS over SVD won't be seen if your examples are too small, e.g.,

>> N=100; As=speye(N);A=eye(N); tic; svd(A); toc ; tic; svds(A); toc
Elapsed time is 0.001177 seconds.
Elapsed time is 0.006077 seconds.

but there are clearly also examples where svds is better, e.g.,

>> N=5000; As=speye(N);A=eye(N); tic; svd(A); toc ; tic; svds(A); toc
Elapsed time is 47.876229 seconds.
Elapsed time is 0.324260 seconds.

1 Comment

Clare on 22 Jul 2013

Yes, I meant that they will eventually be millions by millions, thanks. Good to see that SVDS is clearly faster with the identity matrix.

Matt J
Answer by Jan Simon on 22 Jul 2013
Edited by Jan Simon on 22 Jul 2013

"Millions" means something >= 2e6. Then the array has 32 TB when it is full. Do you have enough memory for this?

I tried this under Matlab 2009a/64/Win7/4 GB:

x = rand(1e4);
x(rand(size(x))<0.9) = 0;
tic; S = svd(x); toc
% 1313.510373 sec
x = sparse(x);
tic; S = svds(x); toc
% 54.953447 sec

This looks like a good argument for SVDS. Now tell us please something about the sparsity of your array and the number of eigenvalues you need. And please explain, which timings you expect for [2e6 x 2e6] matrices.

5 Comments

Jan Simon on 23 Jul 2013

A good question. The sparse matrix stores the data and the indices in three different blocks, while the full matrix requires one large contiguous block of free memory. Therefore full matrices cause Out-Of-Memory errors earlier.

If the indices of sparse arrays are stored as UINT32, less memory is consumed. But I do not know the type of the indices.

Cedric Wannaz on 23 Jul 2013

A very good question indeed. A sparsity of 0.3 is almost not sparse (you can find a document that describes the internals here).. and in R2012b and earlier versions at least, we cannot use UINT32 as indices.

Matt J on 23 Jul 2013

But here is my question-- if I use S = sparse(i,j,s) to construct my sparse matrix, and the sparsity is around 0.3 (meaning 30% nonzero elements, 70% zeros), will I save any memory?

@Clare - even if your sparsity is zero, it is still possible to waste memory as the following example shows,

 >> Asparse=spalloc(1,1e6,1); 
 >> Afull=full(Asparse);
 >> whos Asparse Afull
Name         Size                   Bytes  Class     Attributes
Afull        1x1000000            8000000  double              
Asparse      1x1000000            8000024  double    sparse  
Jan Simon

Contact us