How large can a sparse matrix be?

Hi,

I thought I could exploit the fact that a matrix is sparse to build a big matrix. I would like to build a sparse matrix of size 46 times 8153726976. The matrix itself is very big but only has approximately 60,000 non-zero entries. I have not succeeded even in creating a completely sparse matrix of the same size. Is there any solution to this problem?

Thanks,

Answer 1

[Steven Lord]

The larger the number of columns in a sparse matrix, the more memory it consumes. Try creating a tall but thin sparse matrix instead of a short and wide matrix.

 S = spalloc(8153726976, 46, 60000);

[Cedric]

As a reference: Sparce Matrices in MATLAB. Section 3.1.1 provides insights about Steven's point.

And to illustrate:

 >> a = sparse( [zeros(1, 1e6), 1] ) ;  % Row    -> 1e6+1 columns.
 >> b = a' ;                            % Column -> 1 column.
 >> whos
  Name            Size                   Bytes  Class     Attributes
  a               1x1000001            8000032  double    sparse    
  b         1000001x1                       32  double    sparse

[James Tursa]

And Section 2.1 gives the storage formula for the data, which I have expanded a bit:

Data storage requirements for M x N sparse double matrix with memory allocated for nzmax non-zero elements:

8 * nzmax + (4 or 8) * (nzmax + N + 1)  bytes of data storage

Which breaks out as follows:

8 * nzmax          --> For the double element storage
(4 or 8) * nzmax   --> For the row element indexes storage
(4 or 8) * (N + 1) --> For the column indexing data storage

The (4 or 8) depends on whether your MATLAB is using 32-bit or 64-bit integers for indexing. Also note that I have used nzmax rather than nnz in the formula above. Often they are the same, but they don't have to be. For a sparse logical matrix, replace the 8*nzmax with 1*nzmax ... the indexing requirements stay the same.

(The above ignores the variable header storage and memory alignment stuff, which could easily add another 60 - 120 bytes or so to the overall footprint)

[Patrick Mboma]

Dear all,

Thank you so much for the replies. Suppose I succeed in creating the transpose of the matrix that I want, wouldn't I have to transpose it in order to do some computations?

I would like to be able to compute A*B, where A is the large sparse matrix and B is another sparse matrix.

[James Tursa]

Regarding your transpose question, you need to be more specific about what you are doing. E.g.,

A = large sparse column vector
B = large sparse column vector
AT = A'; % <-- will consume much more memory because of the N effect
C = A'*B; <-- will likely be OK because A' is not explicitly formed

The mtimes operator * is often smart enough to not form transposes explicitly. Rather, this transpose information is passed on to the actual multiply routine internally, and then a different indexing scheme is used to do the multiply without forming the transpose explicitly in memory first.

Regarding your A*B question, just type A*B and MATLAB will recognize the sparse matrices and call the appropriate routines in the background for you.

[Patrick Mboma]

The transpose came into the picture because Mr. Lord suggested to construct "a tall but thin sparse matrix instead of a short and wide matrix". The tall-and-thin sparse matrix will be the transpose of the matrix I would like to use in my computations.

The operation I need to do is rather simple: C=A*B . In this operation however, A is short, wide and sparse, whereas B is conformably tall and potentially thin.

Any suggestions?

[Titus Edelhofer]

Hi Patrick,

then the result C should be relatively small. Did you try the obvious, namely

C = A' * B;

I'm not sure, but it guess that MATLAB identifies the pattern and computes the multiplication without "computing" the transpose before ...

Titus

[Patrick Mboma]

Titus, I have checked that what you suggested works. Matlab somehow avoids transposing the matrix before doing the multiplication. Wahoo! Now the only thing I have to make sure of is that matrix B is not too wide.

To all, Thank you so much