13 views (last 30 days)

Hello, in the code below, I have to do matrix multiplication thousands of time. The time it takes on my PC is about 70 secs to run this code. I want to reduce the time of execution. In the code below two variables, PRODOTTO3 and COEFF are sparse matrices and sparse vector respectively. I have tried making them sparse matrix but the time of execution increase to more than 200 secs. Does anybody have better idea to reduce the execution time?

From the time profiler I know that the 99.8% of the execution time is spent on this line "COEFF_S(i,j) = sum(COEFF.*(PRODOTTO3(:,j,i)))"

I really want to reduce the execution time.

THIS IS THE CODE WITHOUT SPARSE MATRIX

NU =25; %No. of Uncertain input Parameter

p=2 ; %Keep it same,

npolinomi=factorial(NU+p)/(factorial(NU)*factorial(p)); % No. of PCE terms (Polynomials) Formula is (N+P)! / (N!P!)

PRODOTTO3 = (double((randn(round(npolinomi),round(npolinomi),round(npolinomi)))>0.7));

COEFF = zeros(round(npolinomi),1) ;

COEFF(1:3) = 1 ;

COEFF_S = zeros(size(COEFF,1),size(COEFF,1)) ;

tic ;

for l = 1:200 %freq.

for i = 1 : size(COEFF,1)

for j=1:size(COEFF,1)

COEFF_S(i,j) = sum(COEFF.*(PRODOTTO3(:,j,i))) ;

end

end

end%freq.

for i= 1 : 250 %freq

for j = 1 : K

COEFF_S = COEFF_S*COEFF_S ;

end

end

end %freq

toc

THIS IS CODE WITH SPARSE MATRIX

if true

NU =25; %No. of Uncertain input Parameter

p=2 ; %Keep it same,

npolinomi=factorial(NU+p)/(factorial(NU)*factorial(p)); % No. of PCE terms (Polynomials) Formula is (N+P)! / (N!P!)

PRODOTTO3 = ndSparse(double((randn(round(npolinomi),round(npolinomi),round(npolinomi)))>0.7));

COEFF = zeros(round(npolinomi),1) ;

COEFF(1:3) = 1 ;

COEFF=sparse(COEFF) ;

COEFF_S = zeros(size(COEFF,1),size(COEFF,1)) ;

tic ;

for l = 1:200 %freq.

for i = 1 : size(COEFF,1)

for j=1:size(COEFF,1)

*COEFF_S(i,j) = sum(COEFF.*(PRODOTTO3(:,j,i))) ;*

end

end

end%freq.

for i= 1 : 250 %freq

for j = 1 : K

COEFF_S = COEFF_S*COEFF_S ;

end

end

end %freq

toc

end

Matt J
on 23 Aug 2017

Edited: Matt J
on 23 Aug 2017

This double loop

for i = 1 : size(COEFF,1)

for j=1:size(COEFF,1)

COEFF_S(i,j) = sum(COEFF.*(PRODOTTO3(:,j,i))) ;

end

end

should be replaced by

COEFF_S=reshape( COEFF.'*PRODOTTO3(:,:) , size(COEFF,1), []).';

This loop

for j = 1 : K

COEFF_S = COEFF_S*COEFF_S ;

end

should be replaced by

COEFF_S=COEFF_S^K;

Matt J
on 24 Aug 2017

How sparse is PRODOTTO3? The command

double(351,351,351)>0.7

gives an error so I don't think it could be your true code. If you really meant

rand(351,351,351)>0.7

this will not be very sparse.

Other than that, you should avoid overhead in the ndSparse class. Do the reshaping of PRODOTTO3 prior to the loop, and convert it to a regular 2D matrix

PRODOTTO3 = ndSparse(rand(351,351,351)>0.7);

PD3=sparse(PRODOTTO3(:,:));

COEFF = zeros(351,1) ;

COEFF(1:3) = 1 ;

COEFF=sparse(COEFF) ;

COEFF_S = sparse(size(COEFF,1),size(COEFF,1)) ;

tic ;

for l = 1:200 %freq.

COEFF_S=reshape( COEFF.'*(PD3) , size(COEFF,1), []).';

end%freq.

toc

Jan
on 24 Aug 2017

Edited: Jan
on 24 Aug 2017

Why do you run the firt loop 200 times, although the loop body does not depend on the counter l? Simply omit the for loop to speed up the code by a factor 200. If the loop is required, the simplification for the forum was to heavy (or too light).

Instead of sparse matrix calculations, use logical indexing:

iter = 10; % This is 200 in your example

S = zeros(n, n);

tic ;

n = numel(COEFF);

for l = 1:iter %freq.

for i = 1 : n % Original code

for j = 1:n

S(i,j) = sum(COEFF .* PRODOTTO3(:,j,i));

end

end

end

toc

S2 = zeros(n, n);

tic ;

n = numel(COEFF);

for l = 1:iter %freq.

for i = 1 : n*n % Omit the inner loop

S2(i) = sum(COEFF .* PRODOTTO3(:,i));

end

end

S2 = S2.';

toc

S3 = zeros(n, n);

tic ;

n = numel(COEFF);

M = (COEFF == 1);

for l = 1:iter %freq.

for i = 1 : n*n % Logical indexing in a loop

S3(i) = sum(PRODOTTO3(M,i));

end

end

S3 = S3.';

toc

S4 = zeros(n, n);

tic;

for l = 1:iter % Matrix multiplication

S4 = reshape( COEFF.'*(PRODOTTO3(:,:)) , size(COEFF,1), []).';

end

toc

tic;

for l = 1:iter %freq. % Logical indexing and matrix operation

S5 = squeeze(sum(PRODOTTO3(COEFF == 1, :, :), 1)).';

end

toc

Elapsed time is 6.041851 seconds.

Elapsed time is 5.717790 seconds.

Elapsed time is 4.114472 seconds.

Elapsed time is 4.665910 seconds.

Elapsed time is 0.159271 seconds. % !!! Logical indexing

If COEFF has more non zero entries, move the conversion to a LOGICAL out of the loop:

CC = (COEFF == 1);

for l = 1:iter %freq.

S5 = reshape(sum(PRODOTTO3(CC, :, :), 1), n, n).';

end

Elapsed time is 0.14 seconds.

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
## 2 Comments

## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/353797-can-i-reduce-computation-time-for-the-matrix-computation-sparse-matrices#comment_479322

⋮## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/353797-can-i-reduce-computation-time-for-the-matrix-computation-sparse-matrices#comment_479322

## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/353797-can-i-reduce-computation-time-for-the-matrix-computation-sparse-matrices#comment_479327

⋮## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/353797-can-i-reduce-computation-time-for-the-matrix-computation-sparse-matrices#comment_479327

Sign in to comment.