Can I reduce computation time for the matrix computation (sparse matrices)
6 views (last 30 days)
Show older comments
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
2 Comments
Accepted Answer
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;
6 Comments
Matt J
on 24 Aug 2017
After replacing with the suggested changes the main hurdle is this piece of code shown below
COEFF_S=mtimesx(COEFF_S,A);
More Answers (1)
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.
5 Comments
See Also
Categories
Find more on Loops and Conditional Statements in Help Center and File Exchange
Products
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!