CODEWITHSUNDEEP
matlabsparse-matrix
Kobs
Kobs

Reputation: 209

Fastest way to add multiple sparse matrices in a loop in MATLAB

I have a code that repeatedly calculates a sparse matrix in a loop (it performs this calculation 13472 times to be precise). Each of these sparse matrices is unique.

After each execution, it adds the newly calculated sparse matrix to what was originally a sparse zero matrix.

When all 13742 matrices have been added, the code exits the loop and the program terminates.

The code bottleneck occurs in adding the sparse matrices. I have made a dummy version of the code that exhibits the same behavior as my real code. It consists of a MATLAB function and a script given below.

(1) Function that generates the sparse matrix:

function out = test_evaluate_stiffness(n)
ind = randi([1 n*n],300,1);
val = rand(300,1);
[I,J] = ind2sub([n,n],ind);
out = sparse(I,J,val,n,n);
end

(2) Main script (program)

% Calculate the stiffness matrix
n=1000;
K=sparse([],[],[],n,n,n^2);
tic
for i=1:13472
    temp=rand(1)*test_evaluate_stiffness(n);
    K=K+temp;
end
fprintf('Stiffness Calculation Complete\nTime taken = %f s\n',toc)

I'm not very familiar with sparse matrix operations so I may be missing a critical point here that may allow my code to be sped up considerably.

Am I handling the updating of my stiffness matrix in a reasonable way in my code? Is there another way that I should be using sparse that will result in a faster solution?

A profiler report is also provided below: MATLAB Profiler Report

Upvotes: 0

Views: 502

Answers (2)

yacc
yacc

Reputation: 1

The biggest remaining computation, taking 11s, is the sparse operation on the final I,J,V vectors so I think we've taken it down to the bare bones.

Nearly... but one final trick: if you can create the vectors so that J is sorted ascending then you will greatly improve the speed of the sparse call, about a factor 4 in my experience.

(If it's easier to have I sorted, then create the transpose matrix sparse(J,I,V) and un-transpose it afterwards.)

Upvotes: 0

knedlsepp
knedlsepp

Reputation: 6084

If you only need the sum of those matrices, instead of building all of them individually and then summing them, simply concatenate the vectors I,J and vals and call sparse only once. If there are duplicate rows [i,j] in [I,J] the corresponding values S(i,j) will be summed automatically, so the code is absolutely equivalent. As calling sparse involves an internal call to a sorting algorithm, you save 13742-1 intermediate sorts and can get away with only one.

This involves changing the signature of test_evaluate_stiffness to output [I,J,val]:

function [I,J,val] = test_evaluate_stiffness(n)

and removing the line out = sparse(I,J,val,n,n);.

You will then change your other function to:

n = 1000;
[I,J,V] = deal([]);
tic;
for i = 1:13472
    [I_i, J_i, V_i] = test_evaluate_stiffness(n);
    nE = numel(I_i);
    I(end+(1:nE)) = I_i;
    J(end+(1:nE)) = J_i;
    V(end+(1:nE)) = rand(1)*V_i;
end
K = sparse(I,J,V,n,n);
fprintf('Stiffness Calculation Complete\nTime taken = %f s\n',toc);

If you know the lengths of the output of test_evaluate_stiffness ahead of time, you can possibly save some time by preallocating the arrays I,J and V with appropriately-sized zeros matrices and set them using something like:

I((i-1)*nE + (1:nE)) = ...
J((i-1)*nE + (1:nE)) = ...
V((i-1)*nE + (1:nE)) = ...

Upvotes: 3

Related Questions