rank and null of sparse matrix not allowed without using full

조회 수: 6 (최근 30일)
Mark Stone
Mark Stone 2015년 6월 29일
댓글: Mark Stone 2015년 6월 30일
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.

채택된 답변

John D'Errico
John D'Errico 2015년 6월 29일
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.
  댓글 수: 3
John D'Errico
John D'Errico 2015년 6월 29일
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
Mark Stone 2015년 6월 30일
My point is that in my opinion, svd and rank should use full rather than rejecting the command.

댓글을 달려면 로그인하십시오.

추가 답변 (0개)

카테고리

Help CenterFile Exchange에서 Linear Algebra에 대해 자세히 알아보기

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by