I'm interested in finding the quickest way of grouping the elements of a large matrix in sub-groups of NxM elements and them summing them together. To be completely clear, I'm actually not interested in the "regrouped" matrice, but only in the final results where the elements are summed.
"Standard matrix" case
I'll show you an example below:
Say I have the following matrix 9x8:
test = Array[Subscript[a, ##] &, {8, 9}]
I regroup it in sub-matrices NxM, in this example 3x2:
subtest = Partition[test, {2, 3}]
and then I sum them together (as suggested in the comment by @:
out = MapAt[Total[#, -1] &, subtest, {All, All}];
I could use other ways of summing the subgroups, as for example:
out = Total /@ Flatten /@ # & /@ subtest;
Or using two nested tables, or for loops, etc.
My question is what is the fastest method for doing this? I need to do it on a 48k x 48k matrix, so I'd really need something reasonably quick. Should I look into compiling nested for loops in C (not sure, I haven't ever tried)?
Something worth mentioning is that the entries of the matrix are all integers larger or equal to 0.
EDIT: as pointed out in the comments below, it's important to consider that most of the entries of the matrix (>99%) are zeroes. This might encourage a sparse array approach.
I'll add a (redundant) example with numeric values, thac can be however modified to larger matrices:
test = RandomInteger[1, {8, 9}];
{{0, 0, 1, 0, 1, 1, 0, 0, 0}, {1, 1, 0, 1, 0, 0, 1, 0, 0}, {0, 0, 1, 1, 1, 1, 0, 0, 0}, {0, 0, 1, 0, 0, 1, 1, 0, 1}, {0, 0, 1, 1, 0, 0, 1, 1, 1}, {1, 0, 0, 1, 0, 1, 1, 1, 1}, {1, 0, 1, 1, 1, 0, 1, 1, 0}, {0, 0, 1, 1, 1, 0, 1, 0, 1}}
m = 3
n = 2
out = MapAt[Total[#, -1] &, Partition[test, {n, m}], {All, All}]
{{3, 3, 1}, {2, 4, 2}, {2, 3, 6}, {3, 4, 4}}
Sparse array case
EDIT: In light of very useful discussion below, I'd like to add a "second question" (which is not really a different question). How to do the same procedure described above, but when the input matrix is instead a sparse array?
Here a sample code for testing with a small sparse array:
test = SparseArray[{{5, 5} -> 1, {2, 2} -> 2, {3, 3} -> 3, {5, 3} -> 4}, {8, 9}];
and a sample code for testing with a nxn matrix where 99% of the entries are 0:
n = 100;
entries = {{#[[1]], #[[2]]} -> #[[3]]} & /@ RandomInteger[{1, n},{Ceiling[n*0.01], 3}];
SparseArray[Flatten@entries, {n, n}] // MatrixForm
Total[]
:Total[Partition[test, {2, 3}], {3, 4}]
. $\endgroup$RandomInteger[1, {n, n}]
are packed which can be checked withDeveloper`PackedArrayQ[test]
. $\endgroup$BlockMap
, but after some superficial tests I have to conclude that it really isn't very fast... $\endgroup$