MATLAB Newsgroup

Dear all,

I am struggling a bit with a piece of my code. This actual piece seems to be the bottleneck in my code (according to profiler). This is mostly due to the for/if loops.

I was wondering if it is possible to vectorize some part (or completely) of it.

The code:

for i=1:ngrids-1

sumk = zeros(ngrids,1);

for k = 1:i

Vdif = Vhalf(i+1)-V(k);

if Vdif < Vhalf(2)

Vdif = Vhalf(2);

end

for j=2:length(Vhalf)

if Vdif <= Vhalf(j) && Vdif > Vhalf(j-1)

alpha=j;

end

end

int1 = zeros(ngrids,1);

for j = alpha:ngrids

int1(j)=f(j)/V(i)*(Vhalf(j+1)-Vhalf(j))*agglom((i*2),(k*2));

end

int2=f(alpha-1)/(Vhalf(alpha)+Vhalf(i+1)-V(k))*(Vhalf(alpha)-Vhalf(i+1)-V(k))*agglom((((2*alpha)-1)+((2*i)+1)-(k*2))/2);

sumk (k) = (sum(int1)+int2)*(Vhalf(k+1)-Vhalf(k))*f(k);

end

Fphalf (i) = sum(sumk);

end

If anyone of you could give me some pointers it would be much appreciated.

"Sven " <sven.molenaar.prive@gmail.com> wrote in message <ia3f8a$od2$1@fred.mathworks.com>...

> Dear all,

>

> I am struggling a bit with a piece of my code. This actual piece seems to be the bottleneck in my code (according to profiler). This is mostly due to the for/if loops.

> I was wondering if it is possible to vectorize some part (or completely) of it.

>

> The code:

>

> for i=1:ngrids-1

> sumk = zeros(ngrids,1);

> for k = 1:i

> Vdif = Vhalf(i+1)-V(k);

> if Vdif < Vhalf(2)

> Vdif = Vhalf(2);

> end

>

> for j=2:length(Vhalf)

> if Vdif <= Vhalf(j) && Vdif > Vhalf(j-1)

> alpha=j;

> end

> end

>

> int1 = zeros(ngrids,1);

> for j = alpha:ngrids

> int1(j)=f(j)/V(i)*(Vhalf(j+1)-Vhalf(j))*agglom((i*2),(k*2));

> end

>

> int2=f(alpha-1)/(Vhalf(alpha)+Vhalf(i+1)-V(k))*(Vhalf(alpha)-Vhalf(i+1)-V(k))*agglom((((2*alpha)-1)+((2*i)+1)-(k*2))/2);

> sumk (k) = (sum(int1)+int2)*(Vhalf(k+1)-Vhalf(k))*f(k);

> end

> Fphalf (i) = sum(sumk);

> end

>

> If anyone of you could give me some pointers it would be much appreciated.

- - - - - - - - - - -

The two innermost for-loops involving j are presumably crucial to the efficiency of your algorithm. I see a few ways these could be improved.

As for the first of these, the way it is written you are seeking the last index j for which the given inequalities hold. You should therefore be going backward with j starting from j = length(Vhalf) and moving downwards towards j = 2 and seeking the first j for which the inequalities hold and then doing a 'break'. You can economize further by seeking (while still moving backwards) the first j for which Vdif <= Vhalf(j) and breaking. Then continuing with that j, seek the first j for which Vdif > Vhalf(j-1) and again breaking. You will have arrived at alpha. This should cut down the expected length of array you have to cover and the number of inequalities that need calculating while doing so.

The second j-for-loop can be greatly improved. In the subsequent code you never use int1 for any other purpose than taking its sum. To avoid adding up the same quantities in this for-loop over and over again, you can establish a cumulative sum of the quantities f(j)*(Vhalf(j+1)-Vhalf(j)) but working backwards from ngrids. That is,

c = -cumsum(f(ngrids:-1:2).*diff(Vhalf(ngrids+1:-1:2));

can be computed just once before ever entering into any of the for-loops. Then instead of this second for-loop you would just write

sumint1 = c(ngrids+1-alpha)*agglom((i*2),(k*2))/V(i);

which you would use in place of the sum(int1) term in computing sumk(k). There would be no need to allocate space for an int1 array.

A third improvement might be to avoid the repeated sumk allocation. Just keep a running sum of sumk which you can place in Fphalf(i) when you exit from the "for k = 1:i" loop.

Your calculation of Vdif can be simplified to

Vdif = max(Vhalf(i+1)-V(k),Vhalf2);

though this may be only a saving in the number of lines of code.

Anyway this is a starter for you. Perhaps you will be inspired to find many other ways of improving this code. Note that it isn't necessarily the for-loops that are the source of the excessive computation time but what you do within these loops. Vectorization per se does not necessarily save computation time. It is the algorithm that counts.

Roger Stafford

Dear Roger,

Thanks for the starter, never really learned matlab programming in this way. Perhaps thats my own fault. I implemented the suggestions you made and I made a huge improvement. You were also right it has shown me some new possibilities for the rest of my code.

Thanks alot.

Regards,

Sven

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <ia43bc$9d5$1@fred.mathworks.com>...

> "Sven " <sven.molenaar.prive@gmail.com> wrote in message <ia3f8a$od2$1@fred.mathworks.com>...

> > Dear all,

> >

> > I am struggling a bit with a piece of my code. This actual piece seems to be the bottleneck in my code (according to profiler). This is mostly due to the for/if loops.

> > I was wondering if it is possible to vectorize some part (or completely) of it.

> >

> > The code:

> >

> > for i=1:ngrids-1

> > sumk = zeros(ngrids,1);

> > for k = 1:i

> > Vdif = Vhalf(i+1)-V(k);

> > if Vdif < Vhalf(2)

> > Vdif = Vhalf(2);

> > end

> >

> > for j=2:length(Vhalf)

> > if Vdif <= Vhalf(j) && Vdif > Vhalf(j-1)

> > alpha=j;

> > end

> > end

> >

> > int1 = zeros(ngrids,1);

> > for j = alpha:ngrids

> > int1(j)=f(j)/V(i)*(Vhalf(j+1)-Vhalf(j))*agglom((i*2),(k*2));

> > end

> >

> > int2=f(alpha-1)/(Vhalf(alpha)+Vhalf(i+1)-V(k))*(Vhalf(alpha)-Vhalf(i+1)-V(k))*agglom((((2*alpha)-1)+((2*i)+1)-(k*2))/2);

> > sumk (k) = (sum(int1)+int2)*(Vhalf(k+1)-Vhalf(k))*f(k);

> > end

> > Fphalf (i) = sum(sumk);

> > end

> >

> > If anyone of you could give me some pointers it would be much appreciated.

> - - - - - - - - - - -

> The two innermost for-loops involving j are presumably crucial to the efficiency of your algorithm. I see a few ways these could be improved.

>

> As for the first of these, the way it is written you are seeking the last index j for which the given inequalities hold. You should therefore be going backward with j starting from j = length(Vhalf) and moving downwards towards j = 2 and seeking the first j for which the inequalities hold and then doing a 'break'. You can economize further by seeking (while still moving backwards) the first j for which Vdif <= Vhalf(j) and breaking. Then continuing with that j, seek the first j for which Vdif > Vhalf(j-1) and again breaking. You will have arrived at alpha. This should cut down the expected length of array you have to cover and the number of inequalities that need calculating while doing so.

>

> The second j-for-loop can be greatly improved. In the subsequent code you never use int1 for any other purpose than taking its sum. To avoid adding up the same quantities in this for-loop over and over again, you can establish a cumulative sum of the quantities f(j)*(Vhalf(j+1)-Vhalf(j)) but working backwards from ngrids. That is,

>

> c = -cumsum(f(ngrids:-1:2).*diff(Vhalf(ngrids+1:-1:2));

>

> can be computed just once before ever entering into any of the for-loops. Then instead of this second for-loop you would just write

>

> sumint1 = c(ngrids+1-alpha)*agglom((i*2),(k*2))/V(i);

>

> which you would use in place of the sum(int1) term in computing sumk(k). There would be no need to allocate space for an int1 array.

>

> A third improvement might be to avoid the repeated sumk allocation. Just keep a running sum of sumk which you can place in Fphalf(i) when you exit from the "for k = 1:i" loop.

>

> Your calculation of Vdif can be simplified to

>

> Vdif = max(Vhalf(i+1)-V(k),Vhalf2);

>

> though this may be only a saving in the number of lines of code.

>

> Anyway this is a starter for you. Perhaps you will be inspired to find many other ways of improving this code. Note that it isn't necessarily the for-loops that are the source of the excessive computation time but what you do within these loops. Vectorization per se does not necessarily save computation time. It is the algorithm that counts.

>

> Roger Stafford

>

You can think of your watch list as threads that you have bookmarked.

You can add tags, authors, threads, and even search results to your watch list. This way you can easily keep track of topics that you're interested in. To view your watch list, click on the "My Newsreader" link.

To add items to your watch list, click the "add to watch list" link at the bottom of any page.

To add search criteria to your watch list, search for the desired term in the search box. Click on the "Add this search to my watch list" link on the search results page.

You can also add a tag to your watch list by searching for the tag with the directive "tag:tag_name" where tag_name is the name of the tag you would like to watch.

To add an author to your watch list, go to the author's profile page and click on the "Add this author to my watch list" link at the top of the page. You can also add an author to your watch list by going to a thread that the author has posted to and clicking on the "Add this author to my watch list" link. You will be notified whenever the author makes a post.

To add a thread to your watch list, go to the thread page and click the "Add this thread to my watch list" link at the top of the page.

The newsgroups are a worldwide forum that is open to everyone. Newsgroups are used to discuss a huge range of topics, make announcements, and trade files.

Discussions are threaded, or grouped in a way that allows you to read a posted message and all of its replies in chronological order. This makes it easy to follow the thread of the conversation, and to see what’s already been said before you post your own reply or make a new posting.

Newsgroup content is distributed by servers hosted by various organizations on the Internet. Messages are exchanged and managed using open-standard protocols. No single entity “owns” the newsgroups.

There are thousands of newsgroups, each addressing a single topic or area of interest. The MATLAB Central Newsreader posts and displays messages in the comp.soft-sys.matlab newsgroup.

**MATLAB Central**

You can use the integrated newsreader at the MATLAB Central website to read and post messages in this newsgroup. MATLAB Central is hosted by MathWorks.

Messages posted through the MATLAB Central Newsreader are seen by everyone using the newsgroups, regardless of how they access the newsgroups. There are several advantages to using MATLAB Central.

**One Account**

Your MATLAB Central account is tied to your MathWorks Account for easy access.

**Use the Email Address of Your Choice**

The MATLAB Central Newsreader allows you to define an alternative email address as your posting address, avoiding clutter in your primary mailbox and reducing spam.

**Spam Control**

Most newsgroup spam is filtered out by the MATLAB Central Newsreader.

**Tagging**

Messages can be tagged with a relevant label by any signed-in user. Tags can be used as keywords to find particular files of interest, or as a way to categorize your bookmarked postings. You may choose to allow others to view your tags, and you can view or search others’ tags as well as those of the community at large. Tagging provides a way to see both the big trends and the smaller, more obscure ideas and applications.

**Watch lists**

Setting up watch lists allows you to be notified of updates made to postings selected by author, thread, or any search variable. Your watch list notifications can be sent by email (daily digest or immediate), displayed in My Newsreader, or sent via RSS feed.

- Use a newsreader through your school, employer, or internet service provider
- Pay for newsgroup access from a commercial provider
- Use Google Groups
- Mathforum.org provides a newsreader with access to the comp.soft sys.matlab newsgroup
- Run your own server. For typical instructions, see: http://www.slyck.com/ng.php?page=2