Adding sparse matrices efficiently?
23 visualizaciones (últimos 30 días)
Mostrar comentarios más antiguos
Mohammod Minhajur Rahman
el 17 de Nov. de 2018
Editada: James Tursa
el 16 de Jul. de 2020
Hi, I have a cell array which consists of many sparse matrices. For example:
N.B. In my original problem each sparse matrix is about 4000*4000 in size and has many zero entries
A{1}=sparse(magic(150));
A{2}=sparse(magic(150));
A{3}=sparse(magic(150));
A{4}=sparse(magic(150));
....
% I want something like:
KK = A{1}+A{2}+A{3}+....
% KK should be a sparse matrix of 150*150
% Adding them in a loop is very time consuming
% I tried the following but did not work:
KK = sum(cat(2,KC{:}),3); % or 1,2 as the sum dimension
% also
KK = sum([KC{:}]); % gives a vector
2 comentarios
David Goodmanson
el 17 de Nov. de 2018
Hi Mohammod,
It's not going to be a good idea to use sparse(magic(N)) as a benchmark for timing. This matrix is stored in the sparse convention but is absolutely not sparse, since it has no nonzero elements at all. Sparse has to do a lot of work in that case.
sparse(magic(N)) + sparse(magic(N)) takes more time than the addition of the full matrices, magic(N) + magic(N).
Respuesta aceptada
James Tursa
el 17 de Nov. de 2018
In general, everytime you add two sparse matrices together a bunch of sparse index sorting etc has to take place first and then the result of the additions gets put into new memory. Doing this at each iteration is what is slowing you down.
If your matrices are only 4000x4000, then maybe adding the individual matrices into a full matrix would be faster since there wouldn't be any need to sort the combined indexes or to put the result into new memory. You could try two different options with this approach.
1) Start with a full 0's matrix and add your sparse matrices into it. A good underlying algorithm will simply add the sparse stuff into the full matrix at the appropriate spots without any index sorting needed. So:
result = zeros(4000,4000);
for k=1:whatever
result = result + A{k};
end
result = sparse(result);
2) Do the equivalent of the above inside a mex routine. That way you could ensure that no large extraneous data copying was taking place, but everything was simply added directly into the result. This mex routine would not be too difficult to write. If you opt for this method let me know and I can help.
3 comentarios
Jin Yang
el 16 de Jul. de 2020
James, thank you for this answering! Is there anything we need to take care to write a c mex file with cell data?
James Tursa
el 16 de Jul. de 2020
Editada: James Tursa
el 16 de Jul. de 2020
Nothing special needed. Just pass in the cell array, create the full array inside the mex routine, and write a loop that does the adding. You could sparse the end result either inside or outside the mex routine.
Más respuestas (1)
Bruno Luong
el 17 de Nov. de 2018
Editada: Bruno Luong
el 17 de Nov. de 2018
The fatest way to add sparse matrices is to build the sum from scratch.
It takes 4 second for 1000 random matrices of 4000x4000 with density 1e-3.
I = [];
J = [];
V = [];
n = 0;
for k = 1:length(A)
[i,j,v] = find(A{k});
p = n + numel(i);
m = numel(I);
if p > m
m = max(p,2*m);
I(m) = 0;
J(m) = 0;
V(m) = 0;
end
idx = (n+1:p);
I(idx) = i;
J(idx) = j;
V(idx) = v;
n = p;
end
idx = (n+1:numel(I));
I(idx) = [];
J(idx) = [];
V(idx) = [];
[m,n] = size(A{1});
SUM = sparse(I,J,V,m,n)
Ver también
Categorías
Más información sobre Sparse Matrices en Help Center y File Exchange.
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!