MATLAB Answers

Ming
0

Large Sparse Matrix Summation

Asked by Ming
on 22 Apr 2013

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

  1 Comment

James Tursa
on 22 Apr 2013

What are the actual sizes you are working with?

2 Answers

Answer by Teja Muppirala
on 22 Apr 2013
 Accepted answer

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

  2 Comments

Teja Muppirala
on 22 Apr 2013

I guess that last line would be simpler as this:

Asum = sparse(rnew,c,val,N,N);
Ming
on 22 Apr 2013

Thank a lot !


Answer by Cedric Wannaz
on 22 Apr 2013
Edited by Cedric Wannaz
on 22 Apr 2013

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

  3 Comments

Cedric Wannaz
on 22 Apr 2013

Well, Teja was faster ;-)

Ming
on 22 Apr 2013

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

James Tursa
on 23 Apr 2013

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


Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi test

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

MATLAB Academy

New to MATLAB?

Learn MATLAB today!