quick numerical calculation without for loop

Hello, there is a sequence x(i) (about 1 million number points), how to optimize the algorithm and calculate the equation below in about one second? if two or more for loop are employed, the calculation will last for one or more hours. Thank you!

[Adam]

Do you have code for it at al? Usually you just implement something and then work on speeding it up so it would be easier to make suggestions if you show the code you currently have for it.

Is it a realistic expectation to go from 'one or more hours' to 'below or about one second'? Do you have some reference that says this is even feasible?

Answer 1

[Florian]

What are the numbers for m and N?

The double sum is nasty. One strategy would be as follows: You can at least get rid of the innermost loop by using indexing. Then, use a parallel loop to calculate the outer loop.

clear; %clc;
N = 1000000;
m = 1000;
rng(0);
x = rand(N,1);
tic
s2 = zeros(N-3*m+1,1);
parfor j = 1:N-3*m+1 
  i = j:j+m-1;
  idx = [ i+2*m; i+m; i ];
  s1 = x(idx);
  s1(2,:) = -2*s1(2,:);
  s1 = sum(s1(:));
  s2(j) = s1^2;
end
T = sqrt( (1/(6*m^2*(N-3*m+1))) * sum(s2) );
toc

Takes 31 seconds on my machine without the parfor, and 11 seconds with parfor.

Hope this gets you somewhere, Florian