Matlab matrix operations without loops

Hello. I have an issue with a code performing some array operations. It is getting to slow, because I am using loops. I am trying for some time to optimize this code and to re-write it with less or without loops. Until now unsuccessful. Can you please help me solve this:

YVal = 1:1:100000;
M_MAX = 1000;
N_MAX = 2000;
clear YTemp
tic
for M=1:1:M_MAX 
    for N = 1:1:N_MAX 
       YTemp(M,N) = sum(YVal (N+1:N+M)  ) - sum(YVal   (1:M)  );  
    end
end

For large N_MAX and M_MAX the execution time of these two loops is very high. How can I optimize this?

Thank you,

Florin

Answer 1

[Azzi Abdelmalek]

Try his code, 200 faster

YVal = 1:1:100000;
M_MAX = 1000;
N_MAX = 2000;
tic
som1=zeros(1,M_MAX+N_MAX);
YTemp=zeros(M_MAX,N_MAX);
for k=1:M_MAX+N_MAX
  som1(k)=sum(YVal(1:k));
end
for M=1:1:M_MAX % Number of accumulated periods
  som2=som1(M+1)-YVal(1);
  for N = 1:1:N_MAX % statistic
    YTemp(M,N) = som2- som1(M);  
    som2=som2+YVal(N+M+1)-YVal(N+1);
  end 
end
toc

[Florin]

:) Thank you for the input! It is fast, indeed.

[Jan]

MLint moans, that som1 should be pre-allocated.

[Azzi Abdelmalek]

Ok, I will do it

Answer 2

[Teja Muppirala]

Your entire script is equivalent to this:

M_MAX = 1000;
N_MAX = 2000;

YTemp  = (1:M_MAX)'*(1:N_MAX);

[Azzi Abdelmalek]

Look at Thorsten's answer (the same) and the comment of OP

[Teja Muppirala]

Ah, I see, I should have read that. This works quickly, but it's not very readable.

YVal = rand(1,1e6);
M_MAX = 1000;
N_MAX = 2000;
YS = cumsum(YVal);
YTemp = bsxfun(@minus, YS( bsxfun(@plus,(1:N_MAX),(1:M_MAX)') ) , YS(1:N_MAX));
YTemp = bsxfun(@minus, YTemp, YS(1:M_MAX)');

[Florin]

This is what I was looking for (regarding code optimization without using loops)! Thank you.

Answer 3

[Thorsten]

 Ytemp = [1:M_MAX]'*[1:N_MAX];

[Florin]

Hello!

Thank you for the fast answer. This works perfectly in case if

 YVal = 1:1:100000;

Though, if I change this to

YVal = 1:2:100000 or rand(1, 100000)

this will not work any more

I Tried:

Ytemp = [YVal(1:M_MAX)]'*[YVal(1:N_MAX)];

Answer 4

[Azzi Abdelmalek]

You can begin by pre-allocating

YTemp=zeros(M_MAX,N_MAX);
YVal = 1:1:100000;
M_MAX = 1000;
N_MAX = 2000;
YTemp=zeros(M_MAX,N_MAX);
for k=1:M_MAX
  som1(k)=sum(YVal(1:k));
end
tic
for M=1:1:M_MAX % Number of accumulated periods
  for N = 1:1:N_MAX % statistic
     YTemp(M,N) = sum(YVal(N+1:N+M)) - som1(M);  
  end
end
toc

This code is three times faster

[Florin]

Thanks for the input!

Answer 5

[Jan]

No, the code is not slow due to the loops, but due to a missing pre-allocation and repeated work. Please measure the speed of this:

YVal  = 1:100000;
M_MAX = 1000;
N_MAX = 2000;
YTemp = zeros(M_MAX, N_MAX);
tic
a = 0;
for M = 1:M_MAX % Number of accumulated periods
    a = a + YVal(M);                 % sum(YVal(1:M))
    b = a;
    for N = 1:N_MAX                  % statistic
       b = b - YVal(N) + YVal(N+M);  % sum(YVal(N+1:N+M))
       YTemp(M, N) = b - a;
    end
end
toc

[EDITED] In fact, the code can be simplified:

YVal  = 1:100000;
M_MAX = 1000;
N_MAX = 2000;
YTemp = zeros(M_MAX, N_MAX);
for M = 1:M_MAX % Number of accumulated periods
    b = 0;
    for N = 1:N_MAX                  % statistic
       b = b - YVal(N) + YVal(N+M);  % sum(YVal(N+1:N+M))
       YTemp(M, N) = b;
    end
end

[Florin]

Hmmm... At some point I tried to to some pre-allocation, but not so deep.

Your code, on my machine, is ~18 times faster. Thank you! Next time I will remember this lesson.

[Jan]

Here only the ZEROS call pre-allocates. Avoiding the repeated summation helps also according to the simple rule, that all repeated work wastes time - as in the real life also.

Answer 6

[Florin]

Both answers from Azzi Abdelmaleka and Jan Simon are very helpful, regarding the matter of runtime optimization. Though, I am still curious if you can do this without loops.

Thank you guys and have a nice day!

[Jan]

Does my answer reply the correct result? I do not have access to Matlab currently, but if it is correct, there is no dependency to "a" in the inner loop: At first "b" is initialized to "a", than "a" is subtracted in each iteration. Therefore I could imagine, that 2 CUMSUMs could be sufficient, but I cannot try this at the moment.