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:
Possible vectorization of for loop?

Subject: Possible vectorization of for loop?

From: James Morgan

Date: 21 Aug, 2010 10:53:05

Message: 1 of 7

Hi there, I hope someone might have a suggestion for this:

I'm looking for a way to vectorize the following (since it is a rather big bottleneck, 80%+):

    for t = 1:25
        Z(t)= sum(prod(bsxfun(@power, X,(n_1 + n_2(:,t)))));
    end

Basically it is a monte-carlo simulation, where I have the following definitions:

X = 25x40000 matrix
n_1 = 25x1 vector
n_2 = 25x25 identity matrix
Z = 1x25 vector

The idea is to e.g.:
1) Take the first column of X, raise that column to the power of a vector n_1, where a +1 is added to the first element of n (using the n_2 identity matrix for doing this)
2) Then the product of the elements of this column gives me an "observation". A similar thing is done for the remaining 40000 columns of X and the result is a vector, which is then summed and then makes up the first element of Z.
3) After this, the for loop does the same thing for the remaining 25 elements of Z, creating Z as a 1x25 vector.

Is there some way to do this without using the for loop? I don't know if the above is sufficient information, else please let me know.

Any suggestions are greatly appreciated! :)

Subject: Possible vectorization of for loop?

From: Roger Stafford

Date: 21 Aug, 2010 17:30:10

Message: 2 of 7

"James Morgan" <martinfalch@hotmail.com> wrote in message <i4ob6h$67g$1@fred.mathworks.com>...
> Hi there, I hope someone might have a suggestion for this:
>
> I'm looking for a way to vectorize the following (since it is a rather big bottleneck, 80%+):
>
> for t = 1:25
> Z(t)= sum(prod(bsxfun(@power, X,(n_1 + n_2(:,t)))));
> end
>
> Basically it is a monte-carlo simulation, where I have the following definitions:
>
> X = 25x40000 matrix
> n_1 = 25x1 vector
> n_2 = 25x25 identity matrix
> Z = 1x25 vector
>
> The idea is to e.g.:
> 1) Take the first column of X, raise that column to the power of a vector n_1, where a +1 is added to the first element of n (using the n_2 identity matrix for doing this)
> 2) Then the product of the elements of this column gives me an "observation". A similar thing is done for the remaining 40000 columns of X and the result is a vector, which is then summed and then makes up the first element of Z.
> 3) After this, the for loop does the same thing for the remaining 25 elements of Z, creating Z as a 1x25 vector.
>
> Is there some way to do this without using the for loop? I don't know if the above is sufficient information, else please let me know.
>
> Any suggestions are greatly appreciated! :)
- - - - - - - -
  If n_2 is an identity matrix, doesn't this do the same thing?

 Z = prod(bsxfun(@power,X,n_1))*X.';

Roger Stafford

Subject: Possible vectorization of for loop?

From: James Morgan

Date: 22 Aug, 2010 00:40:07

Message: 3 of 7

It did! And it cut off 80% of my computation time! :D Thank you so much for that suggestion!

Subject: Possible vectorization of for loop?

From: Roger Stafford

Date: 22 Aug, 2010 02:35:05

Message: 4 of 7

"James Morgan" <martinfalch@hotmail.com> wrote in message <i4prl7$idv$1@fred.mathworks.com>...
> It did! And it cut off 80% of my computation time! :D Thank you so much for that suggestion!
- - - - - - - - - -
  I suspect the savings in cpu time are due primarily to avoiding repetition in taking the powers of X values rather than to the vectorization. In the twenty-five trips through the previous for-loop the same power of each X element was being taken twenty-four times and only once with a different power. I think if you first computed prod(bsxfun(@power,X,n_1))) and then did a multiplication and summing of this with each separate row of X using a for-loop, you would still save time.

  I am saying this so you won't put too much reliance on vectorization for its own sake. For-loops, used properly, have an important rote to play in matlab coding, and they are sometimes the only way possible to carry out an algorithm.

Roger Stafford

Subject: Possible vectorization of for loop?

From: James Morgan

Date: 22 Aug, 2010 05:57:03

Message: 5 of 7

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <i4q2cp$ogf$1@fred.mathworks.com>...
> "James Morgan" <martinfalch@hotmail.com> wrote in message <i4prl7$idv$1@fred.mathworks.com>...
> > It did! And it cut off 80% of my computation time! :D Thank you so much for that suggestion!
> - - - - - - - - - -
> I suspect the savings in cpu time are due primarily to avoiding repetition in taking the powers of X values rather than to the vectorization. In the twenty-five trips through the previous for-loop the same power of each X element was being taken twenty-four times and only once with a different power. I think if you first computed prod(bsxfun(@power,X,n_1))) and then did a multiplication and summing of this with each separate row of X using a for-loop, you would still save time.
>
> I am saying this so you won't put too much reliance on vectorization for its own sake. For-loops, used properly, have an important rote to play in matlab coding, and they are sometimes the only way possible to carry out an algorithm.
>
> Roger Stafford

Hm yeah I see your point.. One thing I have a bit of hard time grasping is why the two operations actually do the same thing, I mean the original for loop and your suggestion - I don't know if it is possible to explain in a fairly simple manner?

Thanks!

Subject: Possible vectorization of for loop?

From: Matt J

Date: 22 Aug, 2010 13:25:21

Message: 6 of 7

"James Morgan" <martinfalch@hotmail.com> wrote in message <i4qe7f$o4k$1@fred.mathworks.com>...

>
> Hm yeah I see your point.. One thing I have a bit of hard time grasping is why the two operations actually do the same thing, I mean the original for loop and your suggestion - I don't know if it is possible to explain in a fairly simple manner?

It basically comes from factoring out the exponent

X(i,j)^(n_1+n_2(:,t)) = X(i,j)^n_1 * X(i,j)^n_2(:,t)

If you take the columnwise product (i.e. over i) you get, because n_2 is identity,

prod(X(:,j)^n_1)*X(t,j)

When you sum this over j, you get the exact formula for column t of the matrix multiplication Roger showed you.

Subject: Possible vectorization of for loop?

From: James Morgan

Date: 22 Aug, 2010 13:46:08

Message: 7 of 7

"Matt J " <mattjacREMOVE@THISieee.spam> wrote in message <i4r8g1$cml$1@fred.mathworks.com>...
> "James Morgan" <martinfalch@hotmail.com> wrote in message <i4qe7f$o4k$1@fred.mathworks.com>...
>
> >
> > Hm yeah I see your point.. One thing I have a bit of hard time grasping is why the two operations actually do the same thing, I mean the original for loop and your suggestion - I don't know if it is possible to explain in a fairly simple manner?
>
> It basically comes from factoring out the exponent
>
> X(i,j)^(n_1+n_2(:,t)) = X(i,j)^n_1 * X(i,j)^n_2(:,t)
>
> If you take the columnwise product (i.e. over i) you get, because n_2 is identity,
>
> prod(X(:,j)^n_1)*X(t,j)
>
> When you sum this over j, you get the exact formula for column t of the matrix multiplication Roger showed you.

Ahh ok, thanks alot :)

Tags for this Thread

No tags are associated with 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