10 views (last 30 days)

What is the memory cost for multiplying sparse matrices? It seems to be much larger than the memory used by either of the matrices being multiplied:

>> A = sprand(5e9,2, 1e-7); B = sparse(eye(2));

whos

Name Size Bytes Class Attributes

A 5000000000x2 16024 double sparse

B 2x2 56 double sparse

>> A*B;

Error using *

Out of memory. Type HELP MEMORY for your options.

As you can see in the example above, the sparse matrices A and B are not taking up much memory, but computing A*B still results in an out of memory error. Why does this happen, and is there a way to avoid it?

Matt J
on 15 Sep 2020

Edited: Matt J
on 15 Sep 2020

I believe it is simply because Matlab sparse matrix routines don't handle very tall & thin matrix dimensions very well. It becomes much faster and less memory-consuming if you reshape A to have a few orders of magnitude fewer rows, and do the following equivalent computation:

A = sprand(5e9,2, 1e-7); B = speye(2);

%%Begin workaround

Ar=reshape(A,[],1000);

Br=kron(B, speye(500));

result= reshape(Ar*Br,size(A));

Matt J
on 16 Sep 2020

Bruno Luong
on 15 Sep 2020

Edited: Bruno Luong
on 15 Sep 2020

I guess MATLAB creates a temporary buffer of length equals to the number of rows of A when A*B is invoked. The exact detail only TMW employees who can acces to the source code can answer.

Here is what I suggest to multiply A*B for very long tall A

[iA, jA, a] = find(A);

m = size(A,1);

n = size(B,2);

p = numel(jA)*n; % Guess of size of I, J, S

% Preallocate

I = zeros(p,1,'uint32');

J = zeros(p,1,'uint32');

S = zeros(p,1);

p = 0;

for k=1:n

[jB, ~, b] = find(B(:,k));

[i, l] = ismember(jA,jB);

q = nnz(i);

idx = p+(1:q);

I(idx) = iA(i);

J(idx) = k;

S(idx) = a(i).*b(l(i));

p = p+q;

end

idx = 1:p;

AB = sparse(I(idx), J(idx), S(idx), m, n);

Bruno Luong
on 15 Sep 2020

A variant

[iA, jA, a] = find(A);

m = size(A,1);

n = size(B,2);

p = numel(jA)*n; % Guess of size of I, J, S

% Preallocate

I = zeros(p,1,'uint32');

J = zeros(p,1,'uint32');

S = zeros(p,1);

p = 0;

for k=1:n

Bk = B(:,k);

jB = find(Bk);

i = ismembc(jA,jB); % undocumented stock function, too bad it's doesn't return second argument of ISMEMBER

q = nnz(i);

idx = p+(1:q);

I(idx) = iA(i);

J(idx) = k;

S(idx) = a(i).*Bk(jA(i));

p = p+q;

end

idx = 1:p;

AB = sparse(I(idx), J(idx), S(idx), m, n);

It doesn't seem to be faster than the first method when I test with tic/toc, but the tests I conducted are far from cover all the cases.

Matt J
on 16 Sep 2020

Edited: Matt J
on 16 Sep 2020

Here's another customized multiplication routine for tall A. I do not know how it compares to Bruno's in terms of speed, but it is loop-free.

A = sprand(5e9,2, 1e-7); B = speye(2);

tic

m=size(A,1);

n=size(B,2);

Ia=find(any(A,2));

Jb=find(any(B,1));

C=A(Ia,:)*B(:,Jb);

[Ic,Jc,S]=find(C);

AB=sparse( Ia(Ic) , Jb(Jc) , S , m,n); %equal to A*B

toc%Elapsed time is 0.001254 seconds.

Opportunities for recent engineering grads.

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

Start Hunting!
## 8 Comments

## Direct link to this comment

https://fr.mathworks.com/matlabcentral/answers/593647-memory-cost-of-multiplying-sparse-matrices#comment_1009120

⋮## Direct link to this comment

https://fr.mathworks.com/matlabcentral/answers/593647-memory-cost-of-multiplying-sparse-matrices#comment_1009120

## Direct link to this comment

https://fr.mathworks.com/matlabcentral/answers/593647-memory-cost-of-multiplying-sparse-matrices#comment_1013647

⋮## Direct link to this comment

https://fr.mathworks.com/matlabcentral/answers/593647-memory-cost-of-multiplying-sparse-matrices#comment_1013647

## Direct link to this comment

https://fr.mathworks.com/matlabcentral/answers/593647-memory-cost-of-multiplying-sparse-matrices#comment_1013680

⋮## Direct link to this comment

https://fr.mathworks.com/matlabcentral/answers/593647-memory-cost-of-multiplying-sparse-matrices#comment_1013680

## Direct link to this comment

https://fr.mathworks.com/matlabcentral/answers/593647-memory-cost-of-multiplying-sparse-matrices#comment_1013701

⋮## Direct link to this comment

https://fr.mathworks.com/matlabcentral/answers/593647-memory-cost-of-multiplying-sparse-matrices#comment_1013701

## Direct link to this comment

https://fr.mathworks.com/matlabcentral/answers/593647-memory-cost-of-multiplying-sparse-matrices#comment_1013797

⋮## Direct link to this comment

https://fr.mathworks.com/matlabcentral/answers/593647-memory-cost-of-multiplying-sparse-matrices#comment_1013797

## Direct link to this comment

https://fr.mathworks.com/matlabcentral/answers/593647-memory-cost-of-multiplying-sparse-matrices#comment_1014295

⋮## Direct link to this comment

https://fr.mathworks.com/matlabcentral/answers/593647-memory-cost-of-multiplying-sparse-matrices#comment_1014295

## Direct link to this comment

https://fr.mathworks.com/matlabcentral/answers/593647-memory-cost-of-multiplying-sparse-matrices#comment_1014493

⋮## Direct link to this comment

https://fr.mathworks.com/matlabcentral/answers/593647-memory-cost-of-multiplying-sparse-matrices#comment_1014493

## Direct link to this comment

https://fr.mathworks.com/matlabcentral/answers/593647-memory-cost-of-multiplying-sparse-matrices#comment_1014505

⋮## Direct link to this comment

https://fr.mathworks.com/matlabcentral/answers/593647-memory-cost-of-multiplying-sparse-matrices#comment_1014505

Sign in to comment.