MATLAB: Memory cost of multiplying sparse matrices

arraybugMATLABmatrix manipulationsparse

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?

Best Answer

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));
Related Question