How to Efficiently Combine Sparse Matrices Vertically

Question

My goal is to combine many sparse matrices together to form one large sparse matrix. The only two ideas I've been able to think of are (1) create a large sparse matrix and overwrite certain blocks, (2) create the blocks individually use vertcat to form my final sparse matrix. However,I've read that overwriting sparse matrices is quite inefficient, and I've also read that vertcat isn't exactly computationally efficient. (I didn't both to consider using a for loop because of how inefficient they are).

What other alternatives do I have then?

Edit: By combine I mean "gluing" matrices together (vertically), the elements don't interact.

Answer 1

According to the matlab help, you can "disassemble" a sparse matrix with

[i,j,s] = find(S);

This means that if you have two matrices S and T, and you want to (effectively) vertcat them, you can do

[is, js, ss] = find(S);
[it, jt, st] = find(T);
ST = sparse([is; it + size(S,1)], [js; jt], [ss; st]);

Not sure if this is very efficient... but I'm guessing it's not too bad.

EDIT: using a 2000x1000 sparse matrix with a density of 1%, and combining it with another that has density of 2%, the above code ran in 0.016 seconds on my machine. Just doing [S;T] was 10x faster. What makes you think vertical concatenation is slow?

EDIT2: assuming you need to do this with "many" sparse matrices, the following works (this assumes you want them all "in the same place"):

m = 1000; n = 2000; density = 0.01;
N = 100;
Q = cell(1, N);
is = Q;
js = Q;
ss = Q;
numrows = 0; % keep track of dimensions so far

for ii = 1:N
    Q{ii} = sprandn(m+ii, n-jj, density); % so each matrix has different size
    [a b c] = find(Q{ii});
    sz = size(Q{ii}); 
    is{ii} = a' + numrows; js{ii}=b'; ss{ii}=c'; % append "on the corner"
    numrows = numrows + sz(1); % keep track of the size
end

tic
ST = sparse([is{:}], [js{:}], [ss{:}]);
fprintf(1, 'using find takes %.2f sec\n', toc);

Output:

using find takes 0.63 sec

The big advantage of this method is that you don't need to have the same number of columns in your individual sparse arrays... it will all get sorted out by the sparse command which will simply consider the missing columns to be all zeros.