Got Questions? Get Answers.
Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Vectorization of nested for loops

Subject: Vectorization of nested for loops

From: Michael

Date: 16 Aug, 2013 18:38:20

Message: 1 of 11

Hi,
I have a function with three nested for-loops that is too slow for its intended use. I've already tried to speed up the code by vectorizing the loops, but my attempts constantly gave me "matrix dimensions must agree" errors that I was unable to resolve. So I'd greatly appreciate any help on speeding up/ vectorizing the loops...Thanks

The function takes a 2d matrix called "rM" as input and returns a 3d matrix called "ec":

  minRisk = 6
  maxRisk = 18
  stepRisk = 2
  
  rows = size(rM, 1);
  cols = size(rM, 2);
  riskLevels = maxRisk / minRisk;
  
  %preallocate.
  ec = zeros(rows+1, cols, riskLevels);
  ec(1, :, :) = 100;
  
  for risk = minRisk:stepRisk:maxRisk;
      for c = 1:cols,
          for r = 2:rows+1,
              ec(r, c, risk) = ec(r-1, c, risk) * (1 + risk * rM(r-1, c));
          end
      end
  end

Subject: Vectorization of nested for loops

From: Roger Stafford

Date: 16 Aug, 2013 19:10:13

Message: 2 of 11

"Michael " <ak-he@hotmail.com> wrote in message <kulris$p09$1@newscl01ah.mathworks.com>...
> I have a function with three nested for-loops that is too slow for its intended use. ....
- - - - - - - -
Try replacing the nested loops with this:

 risk = minRisk:stepRisk:maxRisk;
 p = bsxfun(@times,reshape(1+risk,1,1,[]),rM)
 for r = 1:rows
   ec(r+1,:,risk) = ec(r,:,risk).*p(r,:,:);
 end

Subject: Vectorization of nested for loops

From: Michael

Date: 16 Aug, 2013 19:58:07

Message: 3 of 11

"Roger Stafford" wrote in message <kultel$j1k$1@newscl01ah.mathworks.com>...

> Try replacing the nested loops with this:
>
> risk = minRisk:stepRisk:maxRisk;
> p = bsxfun(@times,reshape(1+risk,1,1,[]),rM)
> for r = 1:rows
> ec(r+1,:,risk) = ec(r,:,risk).*p(r,:,:);
> end

Roger, thanks very much for your help - I just ran your code but it seems to give slightly different results than my original version (isequal returned '0'). Any idea?

Subject: Vectorization of nested for loops

From: Roger Stafford

Date: 16 Aug, 2013 23:27:30

Message: 4 of 11

"Michael " <ak-he@hotmail.com> wrote in message <kum08f$m55$1@newscl01ah.mathworks.com>...
> Roger, thanks very much for your help - I just ran your code but it seems to give slightly different results than my original version (isequal returned '0'). Any idea?
- - - - - - -
  What is important here is how large the differences in the two procedures are. As perhaps you may be aware, by altering the order of arithmetic operations, one can easily obtain results which differ in their least bits due to differing roundoffs, and 'isequal' would return a false result. Simple example (running contrary to the associative law of addition):

 3/14+(3/14+15/14) ~= (3/14+3/14)+15/14

  In your algorithm in which there is a sequence of values which are the result of an iteration through a 'rows' number of successive steps where each value depends on the previous one, such differences can accumulate to considerably more than least bit differences, depending on how may steps there are. Therefore you need to test absolute differences for what ideally would be exact equalities and see how large these get, rather than merely using 'isequal'. The latter doesn't constitute a good test.

Roger Stafford

Subject: Vectorization of nested for loops

From: Michael

Date: 17 Aug, 2013 08:11:07

Message: 5 of 11

"Roger Stafford" wrote in message <kumch2$eda$1@newscl01ah.mathworks.com>...
> "Michael " <ak-he@hotmail.com> wrote in message <kum08f$m55$1@newscl01ah.mathworks.com>...
> > Roger, thanks very much for your help - I just ran your code but it seems to give slightly different results than my original version (isequal returned '0'). Any idea?
> - - - - - - -
> What is important here is how large the differences in the two procedures are...

At first I thought the differences were only subtle, but after further investigation I found out that the opposite is the case. I just ran both algorithms (with the same inputs of course) on a very small dataset in order to be able to post it here . My code returned this:
[10, 10, 10;
10.5, 10.3, 9.9;
10.3, 10.4, 10.1]

Your code returned this:
[10, 10, 10;
100, 60, -20;
-260, 120, -80]

Obviously, these are major differences. I've tried to understand what your suggested code does and why it produces these differences in results, but I'm afraid the code is too advanced for me to comprehend...

Subject: Vectorization of nested for loops

From: Michael

Date: 17 Aug, 2013 09:03:07

Message: 6 of 11

"Michael " <ak-he@hotmail.com> wrote in message <kunb6r$r30$1@newscl01ah.mathworks.com>...
> "Roger Stafford" wrote in message <kumch2$eda$1@newscl01ah.mathworks.com>...
> > "Michael " <ak-he@hotmail.com> wrote in message <kum08f$m55$1@newscl01ah.mathworks.com>...
> > > Roger, thanks very much for your help - I just ran your code but it seems to give slightly different results than my original version (isequal returned '0'). Any idea?
> > - - - - - - -
> > What is important here is how large the differences in the two procedures are...
>
> At first I thought the differences were only subtle, but after further investigation I found out that the opposite is the case. I just ran both algorithms (with the same inputs of course) on a very small dataset in order to be able to post it here . My code returned this:
> [10, 10, 10;
> 10.5, 10.3, 9.9;
> 10.3, 10.4, 10.1]
>
> Your code returned this:
> [10, 10, 10;
> 100, 60, -20;
> -260, 120, -80]
>
> Obviously, these are major differences.


Ok, I found what makes the difference. Now both the algorithms give the exact same results. Here's the updated version:

risk = minRisk:stepRisk:maxRisk;
p = bsxfun(@times,reshape(risk,1,1,[]),rMultiples);
for r = 1:rows
   ec(r+1,:,risk) = ec(r,:,risk).*(1+p(r,:,:));
end

Subject: Vectorization of nested for loops

From: Roger Stafford

Date: 17 Aug, 2013 11:09:24

Message: 7 of 11

"Michael " <ak-he@hotmail.com> wrote in message <kune8b$j89$1@newscl01ah.mathworks.com>...
> Ok, I found what makes the difference. Now both the algorithms give the exact same results. Here's the updated version:
>
> risk = minRisk:stepRisk:maxRisk;
> p = bsxfun(@times,reshape(risk,1,1,[]),rMultiples);
> for r = 1:rows
> ec(r+1,:,risk) = ec(r,:,risk).*(1+p(r,:,:));
> end
- - - - - - - - -
  Yes, I was mistaken there. My apologies. The '1' should have been added AFTER multiplication by rM:

 risk = minRisk:stepRisk:maxRisk;
 p = 1+bsxfun(@times,reshape(risk,1,1,[]),rM);
 for r = 1:rows
   ec(r+1,:,risk) = ec(r,:,risk).*p(r,:,:);
 end

  I am puzzled by your two earlier lines:

 ec = zeros(rows+1, cols, riskLevels);
 ec(1, :, :) = 100;

where riskLevels = 3. If this is what you really do, you ought to get error messages stating that ec(r-1,c,risk) on the right side is undefined on the first trip through the three nested for-loops with risk = 6. In any case this would certainly make your execution very slow. The 'ec' array needs to be pre-defined up to risk = 18 in the third dimension of your allocation if the nested loops are going to extend it that far.

Roger Stafford

Subject: Vectorization of nested for loops

From: Michael

Date: 17 Aug, 2013 12:23:16

Message: 8 of 11

 > I am puzzled by your two earlier lines:
>
> ec = zeros(rows+1, cols, riskLevels);
> ec(1, :, :) = 100;
>
> where riskLevels = 3. If this is what you really do, you ought to get error messages stating that ec(r-1,c,risk) on the right side is undefined on the first trip through the three nested for-loops with risk = 6. In any case this would certainly make your execution very slow. The 'ec' array needs to be pre-defined up to risk = 18 in the third dimension of your allocation if the nested loops are going to extend it that far.
>
> Roger Stafford

You're right there...the risk level values I posted are not really the values I'm working with.

Over the last hour I've done some testing with your vectorized version of the code and I noticed that the vectorized version (for whatever reason) seems to be slower than the original version - and the differences in speed become worse the larger the input data are.

Subject: Vectorization of nested for loops

From: someone

Date: 20 Aug, 2013 14:20:23

Message: 9 of 11

"Michael " <ak-he@hotmail.com> wrote in message <kunpvk$94k$1@newscl01ah.mathworks.com>...
> > I am puzzled by your two earlier lines:
> >
> > ec = zeros(rows+1, cols, riskLevels);
> > ec(1, :, :) = 100;
> >
> > where riskLevels = 3. If this is what you really do, you ought to get error messages stating that ec(r-1,c,risk) on the right side is undefined on the first trip through the three nested for-loops with risk = 6. In any case this would certainly make your execution very slow. The 'ec' array needs to be pre-defined up to risk = 18 in the third dimension of your allocation if the nested loops are going to extend it that far.
> >
> > Roger Stafford
>
> You're right there...the risk level values I posted are not really the values I'm working with.
>
> Over the last hour I've done some testing with your vectorized version of the code and I noticed that the vectorized version (for whatever reason) seems to be slower than the original version - and the differences in speed become worse the larger the input data are.

When Mathworks introduced the Just In Time (JIT) interpreter
(some time ago - 5 years?) for loops became a lot faster
(as long as you preallocated variables).

For loops can indeed be faster than vectorized code in some circumstances.
It depends on many factors such as available (contiguous) memory,
size of arrays, etc .

Subject: Vectorization of nested for loops

From: Michael

Date: 20 Aug, 2013 14:20:30

Message: 10 of 11

I've finally managed to remove all(!) of the nested loops - the code is now completely vectorized:
-----
function ec = someFunction(rM, sE, minRisk, maxRisk, stepRisk)

dim1 = size(rM, 1);
dim2 = size(rM, 2);
dim3 = maxRisk / minRisk;
risk = minRisk:stepRisk:maxRisk;

ec = zeros(dim1+1, dim2, dim3);
ec(1, :, :) = sE;

i = 1:dim1;
ec(i+1, :, :) = 1 + bsxfun(@times, rM, reshape(risk,[1 1 dim3]));
ec = cumprod(ec);
-----
This version is now finally faster (about 20%) than the one with the for loops. However, it's still not fast enough. If anybody has some additional ideas on how to improve the speed, I'd be glad to hear about them..

Subject: Vectorization of nested for loops

From: Michael

Date: 20 Aug, 2013 14:20:30

Message: 11 of 11

I've finally managed to remove all(!) of the for loops - the code is completely vectorized now:
-----
function ec = someFunction(rM, sE, minRisk, maxRisk, stepRisk)

dim1 = size(rM, 1);
dim2 = size(rM, 2);
dim3 = maxRisk / minRisk;
risk = minRisk:stepRisk:maxRisk;

ec = zeros(dim1+1, dim2, dim3);
ec(1, :, :) = sE;

i = 1:dim1;
ec(i+1, :, :) = 1 + bsxfun(@times,rM,reshape(risk,[1 1 dim3]));
ec = cumprod(ec);
------
This version is is now also faster (about 20%) than the for loops. However, it's still not fast enough. If anybody has some additional ideas on how to improve the speed, I'd be glad to hear about them...

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us