http://www.mathworks.com/matlabcentral/newsreader/view_thread/289843
MATLAB Central Newsreader  Possible vectorization of for loop?
Feed for thread: Possible vectorization of for loop?
enus
©19942015 by MathWorks, Inc.
webmaster@mathworks.com
MATLAB Central Newsreader
http://blogs.law.harvard.edu/tech/rss
60
MathWorks
http://www.mathworks.com/images/membrane_icon.gif

Sat, 21 Aug 2010 10:53:05 +0000
Possible vectorization of for loop?
http://www.mathworks.com/matlabcentral/newsreader/view_thread/289843#773330
James Morgan
Hi there, I hope someone might have a suggestion for this:<br>
<br>
I'm looking for a way to vectorize the following (since it is a rather big bottleneck, 80%+):<br>
<br>
for t = 1:25 <br>
Z(t)= sum(prod(bsxfun(@power, X,(n_1 + n_2(:,t)))));<br>
end<br>
<br>
Basically it is a montecarlo simulation, where I have the following definitions:<br>
<br>
X = 25x40000 matrix<br>
n_1 = 25x1 vector<br>
n_2 = 25x25 identity matrix<br>
Z = 1x25 vector<br>
<br>
The idea is to e.g.:<br>
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)<br>
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. <br>
3) After this, the for loop does the same thing for the remaining 25 elements of Z, creating Z as a 1x25 vector.<br>
<br>
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.<br>
<br>
Any suggestions are greatly appreciated! :)

Sat, 21 Aug 2010 17:30:10 +0000
Re: Possible vectorization of for loop?
http://www.mathworks.com/matlabcentral/newsreader/view_thread/289843#773375
Roger Stafford
"James Morgan" <martinfalch@hotmail.com> wrote in message <i4ob6h$67g$1@fred.mathworks.com>...<br>
> Hi there, I hope someone might have a suggestion for this:<br>
> <br>
> I'm looking for a way to vectorize the following (since it is a rather big bottleneck, 80%+):<br>
> <br>
> for t = 1:25 <br>
> Z(t)= sum(prod(bsxfun(@power, X,(n_1 + n_2(:,t)))));<br>
> end<br>
> <br>
> Basically it is a montecarlo simulation, where I have the following definitions:<br>
> <br>
> X = 25x40000 matrix<br>
> n_1 = 25x1 vector<br>
> n_2 = 25x25 identity matrix<br>
> Z = 1x25 vector<br>
> <br>
> The idea is to e.g.:<br>
> 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)<br>
> 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. <br>
> 3) After this, the for loop does the same thing for the remaining 25 elements of Z, creating Z as a 1x25 vector.<br>
> <br>
> 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.<br>
> <br>
> Any suggestions are greatly appreciated! :)<br>
       <br>
If n_2 is an identity matrix, doesn't this do the same thing?<br>
<br>
Z = prod(bsxfun(@power,X,n_1))*X.';<br>
<br>
Roger Stafford

Sun, 22 Aug 2010 00:40:07 +0000
Re: Possible vectorization of for loop?
http://www.mathworks.com/matlabcentral/newsreader/view_thread/289843#773411
James Morgan
It did! And it cut off 80% of my computation time! :D Thank you so much for that suggestion!

Sun, 22 Aug 2010 02:35:05 +0000
Re: Possible vectorization of for loop?
http://www.mathworks.com/matlabcentral/newsreader/view_thread/289843#773417
Roger Stafford
"James Morgan" <martinfalch@hotmail.com> wrote in message <i4prl7$idv$1@fred.mathworks.com>...<br>
> It did! And it cut off 80% of my computation time! :D Thank you so much for that suggestion!<br>
         <br>
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 twentyfive trips through the previous forloop the same power of each X element was being taken twentyfour 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 forloop, you would still save time.<br>
<br>
I am saying this so you won't put too much reliance on vectorization for its own sake. Forloops, used properly, have an important rote to play in matlab coding, and they are sometimes the only way possible to carry out an algorithm.<br>
<br>
Roger Stafford

Sun, 22 Aug 2010 05:57:03 +0000
Re: Possible vectorization of for loop?
http://www.mathworks.com/matlabcentral/newsreader/view_thread/289843#773427
James Morgan
"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <i4q2cp$ogf$1@fred.mathworks.com>...<br>
> "James Morgan" <martinfalch@hotmail.com> wrote in message <i4prl7$idv$1@fred.mathworks.com>...<br>
> > It did! And it cut off 80% of my computation time! :D Thank you so much for that suggestion!<br>
>          <br>
> 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 twentyfive trips through the previous forloop the same power of each X element was being taken twentyfour 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 forloop, you would still save time.<br>
> <br>
> I am saying this so you won't put too much reliance on vectorization for its own sake. Forloops, used properly, have an important rote to play in matlab coding, and they are sometimes the only way possible to carry out an algorithm.<br>
> <br>
> Roger Stafford<br>
<br>
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?<br>
<br>
Thanks!

Sun, 22 Aug 2010 13:25:21 +0000
Re: Possible vectorization of for loop?
http://www.mathworks.com/matlabcentral/newsreader/view_thread/289843#773450
Matt J
"James Morgan" <martinfalch@hotmail.com> wrote in message <i4qe7f$o4k$1@fred.mathworks.com>...<br>
<br>
> <br>
> 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?<br>
<br>
It basically comes from factoring out the exponent<br>
<br>
X(i,j)^(n_1+n_2(:,t)) = X(i,j)^n_1 * X(i,j)^n_2(:,t)<br>
<br>
If you take the columnwise product (i.e. over i) you get, because n_2 is identity,<br>
<br>
prod(X(:,j)^n_1)*X(t,j)<br>
<br>
When you sum this over j, you get the exact formula for column t of the matrix multiplication Roger showed you.

Sun, 22 Aug 2010 13:46:08 +0000
Re: Possible vectorization of for loop?
http://www.mathworks.com/matlabcentral/newsreader/view_thread/289843#773455
James Morgan
"Matt J " <mattjacREMOVE@THISieee.spam> wrote in message <i4r8g1$cml$1@fred.mathworks.com>...<br>
> "James Morgan" <martinfalch@hotmail.com> wrote in message <i4qe7f$o4k$1@fred.mathworks.com>...<br>
> <br>
> > <br>
> > 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?<br>
> <br>
> It basically comes from factoring out the exponent<br>
> <br>
> X(i,j)^(n_1+n_2(:,t)) = X(i,j)^n_1 * X(i,j)^n_2(:,t)<br>
> <br>
> If you take the columnwise product (i.e. over i) you get, because n_2 is identity,<br>
> <br>
> prod(X(:,j)^n_1)*X(t,j)<br>
> <br>
> When you sum this over j, you get the exact formula for column t of the matrix multiplication Roger showed you.<br>
<br>
Ahh ok, thanks alot :)