rank and null of sparse matrix not allowed without using full

Consider the following, where A has the sparse matrix attribute.

>> rank(A)
Error using svd
Use svds for sparse singular values and vectors.
Error in rank (line 14)
s = svd(A); 
>> null(A);
Error using svd
Use svds for sparse singular values and vectors.
Error in null (line 66)
   [~,S,V] = svd(A,0);

Is there a way, without writing your own, to get an SVD-based null without doing null(full(A)), and SVD-based rank without doing rank(full(A))?

Note that qr and eig are allowed on a sparse matrix, but svd is not. Is there a reason for this? Yes, I can get rank and nullspace basis using qr on a sparse matrix, bit why not be allowed to use SVD-based commands without taking full of the matrix?

svds is based on eigs, which is very unreliable, so I have no interest in relying on svds in the middle of something like a nonlinear optimization. I'd for sure go with qr over svds. I'm willing to pay a computation time penalty for use of SVD instead of qr, but the "natural" penalty is jacked way up due to having to take full of the matrix.

Yhanks.

[Matt J]

Note that qr and eig are allowed on a sparse matrix

I believe eig just calls full() internally. In what way is eigs "unreliable"?

[Mark Stone]

See for instance, http://www.mathworks.com/matlabcentral/answers/23182-number-of-eigenvalues-when-using-eigs and http://www.mathworks.com/matlabcentral/answers/159727-eigs-function-incorrect-eigenvectors and some other posts listed under http://www.mathworks.com/matlabcentral/answers/?term=answered_by_id%3A18110 .

Answer 1

[John D'Errico]

A svd will generally result in completely filled in matrices. There will be no non-zero elements in general.

So asking for a svd that does not first make the matrix a full one is a waste of time. It would be considerably slower on a sparse matrix than a full one. Immensely so in fact.

I've attached a code I wrote some years ago, rowspaces. It returns a basis for the rows of an array, as well as the null space of the rows of that matrix. It uses QR, and it does work for sparse matrices, and since it uses the pivoted QR, it will be moderately stable, I hope.

A = sprand(10,5,.1)
A =
   (4,2)          0.7572
   (3,3)         0.91719
  (10,3)         0.75373
   (3,4)         0.28584
   (2,5)         0.54972

[rowsp,nullsp] = rowspaces(A)
rowsp =
   (2,2)        1
   (3,3)        1
   (4,4)        1
   (1,5)        1

nullsp =
   (1,1)        1

As you can see both inputs and outputs are sparse. It allows you to provide the expected rank of the matrix, in which case it will check against the rank that it found. I make no claims about the speed of this code, since my use of it was generally for low dimensional problems.

A quick test though...

A = sprand(1000,500,.001);

tic,[rowsp,nullsp] = rowspaces(A);toc
Elapsed time is 0.092103 seconds.

tic,sp = null(full(A));toc
Elapsed time is 0.302519 seconds.

So it seems reasonably fast. Note that the nullspace here will be the transpose of what null returns, but the results should be equivalent otherwise.

[Mark Stone]

Thanks. Yes, my alternative to null(A) for m by n A, m < n, is to use the last n-m columns of q from qr(A') as a spanning set, but not necessarily linearly independent basis, for the null space of A; however, rank could be less than n-m.

The question still remains though why rank and null are so unfriendly as to produce an error message, rather than using full and at most providing a warning that it is/has done so. I have been using null(full(A)) on sparse A, and now that I am trying to improve the speed of linear algebra for large A, was about to switch over to qr as indicated above, but wanted to find out whether there is a faster SVD-based calculation than null(full(A)).

[John D'Errico]

No. As I said, to do an svd efficiently on a sparse matrix simply won't work. So if you want the svd produced null, you need to either accept svds, or use the full matrix.

[Mark Stone]

My point is that in my opinion, svd and rank should use full rather than rejecting the command.