Large Sparse Matrix Summation

Hi, Everyone:

Suppose I have a very large M*N sparse matrix A, where M=K*N, I need to equally split it into K N*N matrices and sum it up, I can't use loop, so I tried to use:

sum(reshape(A',N,N,K),3);

However, this command can't reshape sparse matrix into a 3-D array, is there any other way to do it? (without loop or converge to dense matrix)

Many Thanks

[James Tursa]

What are the actual sizes you are working with?

Answer 1

[Teja Muppirala]

This seems to work well:

% Making some random data...
N = 1000;
K = 100;
A = sprand(N*K,N,0.0001);

[r,c,val] = find(A);
rnew = mod(r-1,N)+1; % Shift all the row values to [1-->N]
Asum = accumarray([rnew c],val,[N N],[],[],true); % The answer

[Teja Muppirala]

I guess that last line would be simpler as this:

Asum = sparse(rnew,c,val,N,N);

[Ming]

Thank a lot !

Answer 2

[Cedric]

Why can't you use a loop? Is K that large?

If you are looking for efficiency, I'd say that you could directly build A in a way that sums up these N*N blocks, by working on indices using a modulus for row indices. As SPARSE works like ACCUMARRAY when multiple indices are similar, you would have the summation. Example:

 N = 4 ;
 I = randi(3*N, 5*N, 1) ;
 J = randi(N, 5*N, 1) ;
 V = 50 + randi(10, 5*N, 1) ;

 % - First method: assumes that A already built.
 A = sparse(I, J, V, 3*N, N) ;
 full(A)
 [r,c,v] = find(A) ;
 r = 1 + mod(r-1, N) ;
 A_sum = sparse(r, c, v, N, N) ;

 % - Second method: build directly the sum from indices.
 I = 1 + mod(I-1, N) ;
 B = sparse(I, J, V, N, N) ;

 % - Check.
 full(A_sum)
 full(B)
 full(all(A_sum(:) == B(:)))

Running this, you get (RANDI will generate something else if you test it):

 ans =
     0    55     0     0
    60     0    51     0
     0    54     0   112
     0     0     0     0
    52     0     0   114
     0    59   115     0
    57    51     0     0
     0    56     0    56
     0    55     0     0
     0     0     0     0
    54     0    56     0
     0    51     0     0

 ans =
    52   110     0   114
    60    59   166     0
   111   105    56   112
     0   107     0    56

 ans =
    52   110     0   114
    60    59   166     0
   111   105    56   112
     0   107     0    56

 ans =
     1

[Cedric]

Well, Teja was faster ;-)

[Ming]

Thank a lot ! and Yes, K is a big number

[James Tursa]

How big? What are the actual sizes you are using?