Efficient way to combine SparseArray objects?

Question

I have several SparseArray objects, say sa11, sa12, sa21, sa22, which I would like to combine into the equivalent of {{sa11, sa12}, {sa21, sa22}}. As an example, I have :

sa11 = SparseArray[Band[{1, 1}, {4, 4 3}] -> {{ConstantArray[1, 3]}}] 
sa12 = SparseArray[Join[Band[{1, #}, {4, 4 3}] -> 1 & /@ Range[1,  4 3, 4]]]
sa21 = SparseArray[Join[Band[{1, #}, {3, 4 3}] -> 1 & /@ Range[1, 4 3, 3]]] 
sa22 = SparseArray[Band[{1, 1}, {3, 4 3}] -> {{ConstantArray[1, 4]}}] 

I am able to generate the big SparseArray with :

sa = SparseArray[Join[{Band[{1, 1}, {4, 4 3}] -> {{ConstantArray[1, 3]}}}, Band[{1,     #},{4, 2 4 3}] -> 1 & /@ Range[4 3 + 1, 2  4 3, 4], Band[{4 + 1, #}, {4 + 3, 4 3}] -> 1 & /@ Range[1, 4 3, 3], {Band[{4 + 1, 4 3 + 1}, {4 + 3, 2 4 3}] -> {{ConstantArray[1, 4]}}}], {4 + 3, 2 4 3}]

Is there an efficient way to achieve this in general ?

Answer 1

ArrayFlatten[{{sa11, sa12}, {sa21, sa22}}] seems to be what you need. It automatically merges everything into one big SparseArray[].

Answer 2

How about ArrayFlatten (docs):

sa2 = ArrayFlatten[{{sa11, sa12}, {sa21, sa22}}]
sa==sa2
(*
True
*)

Answer 3

In addition to the answers given (ArrayFlatten), there may be cases when the SparseArray-s need to be accumulated one-by-one, and keeping them all in memory at the same time may be too expensive. I've written a generic function to gradually accumulate SparseArray-s. Here is the code:

This is the low-level API for SparseArray construction / deconstruction, explained in details here (where the code slightly differs):

ClearAll[spart, getIC, getJR, getSparseData, getDefaultElement, 
  makeSparseArray];
HoldPattern[spart[SparseArray[s___], p_]] := {s}[[p]];
getIC[s_SparseArray] := spart[s, 4][[2, 1]];
getJR[s_SparseArray] := spart[s, 4][[2, 2]];
getSparseData[s_SparseArray] := spart[s, 4][[3]];
getDefaultElement[s_SparseArray] := spart[s, 3];
makeSparseArray[dims_List, jc_List, ir_List, data_List, defElem_: 0] :=
     SparseArray @@ {Automatic, dims, defElem, {1, {jc, ir}, data}};

This is the function itself. It accepts the code which is supposed to generate the next piece, wrapped in Hold.

Clear[accumulateSparseArray];
accumulateSparseArray[Hold[getDataChunkCode_]] :=
  Module[{start, ic, jr, sparseData, dims, dataChunk},
   start = getDataChunkCode;
   ic = getIC[start];
   jr = getJR[start];
   sparseData = getSparseData[start];
   dims = Dimensions[start];
   While[True, 
     dataChunk = getDataChunkCode;
     If[dataChunk === {}, Break[]];
     ic = Join[ic, Rest@getIC[dataChunk] + Last@ic];
     jr = Join[jr, getJR[dataChunk]];
     sparseData = Join[sparseData, getSparseData[dataChunk]];
     dims[[1]] += First[Dimensions[dataChunk]];
  ];
  makeSparseArray[dims, ic, jr, sparseData]];

Based on this function, it is not difficult to write a function that will do what you need:

Clear[sparseArrayFlatten]
sparseArrayFlatten[m_?(MatrixQ[#, MatchQ[#, _SparseArray] &] &)] :=
 Module[{joinRow, code},
   joinRow[row_List] :=
     Module[{i = 1},
        With[{l = Append[row, {{}}]}, code := l[[i++]]];
        accumulateSparseArray[Hold[Transpose[code]]]
     ];
   joinRow[joinRow /@ m]]

Now:

In[109]:= 
sparseArrayFlatten[{{sa11,sa12},{sa21,sa22}}]==ArrayFlatten[{{sa11,sa12},{sa21,sa22}}]
Out[109]= True

Note that my solution will only pay off if you do have a situation with a huge number of SparseArray-s, which you would like to process lazily (or, which are created one by one). One of situations when this happens is during the data transfer, as explained in my post here. I was also able to significantly improve efficiency by using this technique for efficient initialization of a certain sparse array, in my answer to this question. I consider this to be a rather general technique.