http://www.mathworks.com/matlabcentral/newsreader/view_thread/297461
MATLAB Central Newsreader  Speed up the nested loops (slower than inverse a large matrix)
Feed for thread: Speed up the nested loops (slower than inverse a large matrix)
enus
©19942014 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, 27 Nov 2010 02:14:05 +0000
Speed up the nested loops (slower than inverse a large matrix)
http://www.mathworks.com/matlabcentral/newsreader/view_thread/297461#799685
Ximing xu
I have a large matrix correlation R (n by n), a design matrix F (n by k) and I want to calculate <br>
<br>
the sum of F(i,j)^t *R(i,j)^(1)*F(i,j) for all possible pair i,j , where F(i,j) is a 2byk matrix with the ith, jth row of F ; R(i,j) is a 2by2matrix with entries of the intersection of i,j th row and i,jth column of R.<br>
<br>
I use the for loops for i=1:n1 <br>
for j=i+1:n<br>
which turns out very slow compared with inv(R) which is theoretically O(n^3) operation.<br>
<br>
Any one know how to speed up the loops in my case ? Is it possible faster than the builin function inv(R)? Thanks a lot .<br>
<br>
<br>
Simon <br>
<br>

Sat, 27 Nov 2010 02:32:03 +0000
Re: Speed up the nested loops (slower than inverse a large matrix)
http://www.mathworks.com/matlabcentral/newsreader/view_thread/297461#799690
Matt Fig
Post more code, specifically what is in the FOR loop. <br>
Also, would backslash help in this case?

Sat, 27 Nov 2010 03:16:04 +0000
Re: Speed up the nested loops (slower than inverse a large matrix)
http://www.mathworks.com/matlabcentral/newsreader/view_thread/297461#799696
Roger Stafford
"Ximing xu" <siemenxu@gmail.com> wrote in message <icpphd$cb2$1@fred.mathworks.com>...<br>
> .......<br>
> the sum of F(i,j)^t *R(i,j)^(1)*F(i,j) for all possible pair i,j , where F(i,j) is a 2byk matrix with the ith, jth row of F ; R(i,j) is a 2by2matrix with entries of the intersection of i,j th row and i,jth column of R.<br>
> .......<br>
> I use the for loops for i=1:n1 <br>
> for j=i+1:n<br>
> .......<br>
         <br>
I am puzzled by your description "sum of F(i,j)^t *R(i,j)^(1)*F(i,j) for all possible pair i,j". The range of j in F is presumably different from the range of j in R^1, so how can we speak of using "all possible pair i,j"? Can you please clarify that statement and how can we make it compatible with the given nested for loops in which i ranges from 1 to n1 and j ranges from i+1 to n?<br>
<br>
I wonder if you are actually referring to the matrix product F.'*(R^1)*F? If so, are you asking for the sum of all its elements, and if not, what kind of a sum do you have in mind? If you answer Matt's question thoroughly, that will probably answer mine.<br>
<br>
Roger Stafford

Sat, 27 Nov 2010 04:38:03 +0000
Re: Speed up the nested loops (slower than inverse a large matrix)
http://www.mathworks.com/matlabcentral/newsreader/view_thread/297461#799701
Ximing xu
Thanks for your quick reply. <br>
F is a k*n matrix , R is a n*n matrix. the loop is <br>
A=zeros(k,k);<br>
for i=1:n1<br>
for j=i+1:n <br>
A=A+F([i,j],:)'/ R([i,j],[i,j])*F([i,j],:) ;<br>
end<br>
end <br>
A<br>
<br>
I hope this code is clear. I hope this loop should be faster than inverse of R, but for n=100 and 1000, inverse of R is much faster than this loop. <br>
<br>
Thanks,<br>
<br>
Ximing<br>
<br>
"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <icpt5k$2q$1@fred.mathworks.com>...<br>
> "Ximing xu" <siemenxu@gmail.com> wrote in message <icpphd$cb2$1@fred.mathworks.com>...<br>
> > .......<br>
> > the sum of F(i,j)^t *R(i,j)^(1)*F(i,j) for all possible pair i,j , where F(i,j) is a 2byk matrix with the ith, jth row of F ; R(i,j) is a 2by2matrix with entries of the intersection of i,j th row and i,jth column of R.<br>
> > .......<br>
> > I use the for loops for i=1:n1 <br>
> > for j=i+1:n<br>
> > .......<br>
>          <br>
> I am puzzled by your description "sum of F(i,j)^t *R(i,j)^(1)*F(i,j) for all possible pair i,j". The range of j in F is presumably different from the range of j in R^1, so how can we speak of using "all possible pair i,j"? Can you please clarify that statement and how can we make it compatible with the given nested for loops in which i ranges from 1 to n1 and j ranges from i+1 to n?<br>
> <br>
> I wonder if you are actually referring to the matrix product F.'*(R^1)*F? If so, are you asking for the sum of all its elements, and if not, what kind of a sum do you have in mind? If you answer Matt's question thoroughly, that will probably answer mine.<br>
> <br>
> Roger Stafford

Sat, 27 Nov 2010 04:39:04 +0000
Re: Speed up the nested loops (slower than inverse a large matrix)
http://www.mathworks.com/matlabcentral/newsreader/view_thread/297461#799702
Ximing xu
"Matt Fig" <spamanon@yahoo.com> wrote in message <icpqj3$hu3$1@fred.mathworks.com>...<br>
> Post more code, specifically what is in the FOR loop. <br>
> Also, would backslash help in this case? <br>
Thanks for your quick reply. <br>
F is a k*n matrix , R is a n*n matrix. the loop is <br>
A=zeros(k,k);<br>
for i=1:n1<br>
for j=i+1:n <br>
A=A+F([i,j],:)'/ R([i,j],[i,j])*F([i,j],:) ;<br>
end<br>
end <br>
A<br>
<br>
I hope this code is clear (my original complete code is in another computer). I hope this loop should be faster than inverse of R, but for n=100 and 1000, inverse of R is much faster than this loop. <br>
<br>
Thanks,<br>
<br>
Ximing

Sat, 27 Nov 2010 08:25:06 +0000
Re: Speed up the nested loops (slower than inverse a large matrix)
http://www.mathworks.com/matlabcentral/newsreader/view_thread/297461#799716
Bruno Luong
"Ximing xu" <siemenxu@gmail.com> wrote in message <icq218$3ib$1@fred.mathworks.com>...<br>
<br>
> F is a k*n matrix , R is a n*n matrix. the loop is <br>
> A=zeros(k,k);<br>
> for i=1:n1<br>
> for j=i+1:n <br>
> A=A+F([i,j],:)'/ R([i,j],[i,j])*F([i,j],:) ;<br>
> end<br>
> end <br>
> A<br>
> <br>
> I hope this code is clear (my original complete code is in another computer). I hope this loop should be faster than inverse of R, but for n=100 and 1000, inverse of R is much faster than this loop. <br>
<br>
What you might try is to extract once all the 2x2 submatrices of R and put it on 3D array, and use this FEX to solve the system than sum them back:<br>
<br>
<a href="http://www.mathworks.com/matlabcentral/fileexchange/27762smallsizelinearsolver">http://www.mathworks.com/matlabcentral/fileexchange/27762smallsizelinearsolver</a><br>
<br>
Bruno

Sat, 27 Nov 2010 09:05:14 +0000
Re: Speed up the nested loops (slower than inverse a large matrix)
http://www.mathworks.com/matlabcentral/newsreader/view_thread/297461#799718
Roger Stafford
"Ximing xu" <siemenxu@gmail.com> wrote in message <icq1vb$t6d$1@fred.mathworks.com>...<br>
> Thanks for your quick reply. <br>
> F is a k*n matrix , R is a n*n matrix. the loop is <br>
> A=zeros(k,k);<br>
> for i=1:n1<br>
> for j=i+1:n <br>
> A=A+F([i,j],:)'/ R([i,j],[i,j])*F([i,j],:) ;<br>
> end<br>
> end <br>
> A<br>
> <br>
> I hope this code is clear. I hope this loop should be faster than inverse of R, but for n=100 and 1000, inverse of R is much faster than this loop. <br>
> <br>
> Thanks,<br>
> <br>
> Ximing<br>
         <br>
I am still puzzled, this time by your statement "I hope this loop should be faster than inverse of R, but for n=100 and 1000, inverse of R is much faster than this loop." What does the inverse of the n by n matrix R have to do with this calculation? That is a very different operation from computing the inverses of individual pairs of two rows and columns in R. Why are you comparing them? For each trip within your nested forloops you are doing an order(k^2) algorithm because of all the pairs of rows of F, which makes the overall algorithm order(k^2*n^2), but for large k this is principally occupied with computing the k^2 elements of A rather than just finding the inverse of the 2 by 2 matrix R([i,j],[i,j]). This latter should be very fast in comparison. In fact it is quite possible that using inv(R([i,j],[i,j])) would be faster than using the backslash operator as you have done <br>
here. After all, the inverse of a 2 x 2 correlation matrix [1,a;a,1] is simply: <br>
<br>
[1/(1a^2),a/(1a^2);a/(1a^2),1/(1a^2)]<br>
<br>
This is a far cry from computing the inverse of an entire n x n correlation matrix, but this in turn is a far cry from doing your entire operation with the F matrix to obtain the k x k matrix A.<br>
<br>
Roger Stafford

Sat, 27 Nov 2010 09:27:10 +0000
Re: Speed up the nested loops (slower than inverse a large matrix)
http://www.mathworks.com/matlabcentral/newsreader/view_thread/297461#799722
Bruno Luong
Ximing, yes, I agree with Roger than your calculation of sum over 2x2 matrices are very odd. May be there is some rough approximation that leads you to compute such sum. But it looks suspiciously unjustified IMO.<br>
<br>
Bruno

Sat, 27 Nov 2010 17:25:04 +0000
Re: Speed up the nested loops (slower than inverse a large matrix)
http://www.mathworks.com/matlabcentral/newsreader/view_thread/297461#799778
Ximing xu
I try to compare two statistical methods: the old method and my new method. For the old method I need to calculate the inverse of R , but for the new method I only need to calculate the inverse of 2by2 matrix. The code I show you is just part of my method. The motivation for my method is that the sum shown in my code is only O(n^2), which is much faster than inversion of R which is O(n^3). <br>
<br>
The k is very small. I also tried to write the he inverse of a 2 x 2 correlation matrix [1,a;a,1] as [1/(1a^2),a/(1a^2);a/(1a^2),1/(1a^2)]; but the loop is still very slow. <br>
<br>
I also tried Bruno's idea to extract all the 2x2 submatrices of R (also the F) and put it on 3D array; but it turn out the procedure to do the extraction is just as slow as doing the sum directly.<br>
<br>
Thanks,<br>
<br>
Ximing <br>
<br>
"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <icqhka$6og$1@fred.mathworks.com>...<br>
> "Ximing xu" <siemenxu@gmail.com> wrote in message <icq1vb$t6d$1@fred.mathworks.com>...<br>
> > Thanks for your quick reply. <br>
> > F is a k*n matrix , R is a n*n matrix. the loop is <br>
> > A=zeros(k,k);<br>
> > for i=1:n1<br>
> > for j=i+1:n <br>
> > A=A+F([i,j],:)'/ R([i,j],[i,j])*F([i,j],:) ;<br>
> > end<br>
> > end <br>
> > A<br>
> > <br>
> > I hope this code is clear. I hope this loop should be faster than inverse of R, but for n=100 and 1000, inverse of R is much faster than this loop. <br>
> > <br>
> > Thanks,<br>
> > <br>
> > Ximing<br>
>          <br>
> I am still puzzled, this time by your statement "I hope this loop should be faster than inverse of R, but for n=100 and 1000, inverse of R is much faster than this loop." What does the inverse of the n by n matrix R have to do with this calculation? That is a very different operation from computing the inverses of individual pairs of two rows and columns in R. Why are you comparing them? For each trip within your nested forloops you are doing an order(k^2) algorithm because of all the pairs of rows of F, which makes the overall algorithm order(k^2*n^2), but for large k this is principally occupied with computing the k^2 elements of A rather than just finding the inverse of the 2 by 2 matrix R([i,j],[i,j]). This latter should be very fast in comparison. In fact it is quite possible that using inv(R([i,j],[i,j])) would be faster than using the backslash operator as you have <br>
done <br>
> here. After all, the inverse of a 2 x 2 correlation matrix [1,a;a,1] is simply: <br>
> <br>
> [1/(1a^2),a/(1a^2);a/(1a^2),1/(1a^2)]<br>
> <br>
> This is a far cry from computing the inverse of an entire n x n correlation matrix, but this in turn is a far cry from doing your entire operation with the F matrix to obtain the k x k matrix A.<br>
> <br>
> Roger Stafford

Sat, 27 Nov 2010 18:51:03 +0000
Re: Speed up the nested loops (slower than inverse a large matrix)
http://www.mathworks.com/matlabcentral/newsreader/view_thread/297461#799801
Bruno Luong
"Ximing xu" <siemenxu@gmail.com> wrote in message <icretg$4gm$1@fred.mathworks.com>...<br>
<br>
> I also tried Bruno's idea to extract all the 2x2 submatrices of R (also the F) and put it on 3D array; but it turn out the procedure to do the extraction is just as slow as doing the sum directly.<br>
> <br>
<br>
I guess timing depends *how* you do the extraction. A forloop would not be optimal.<br>
<br>
Bruno

Sun, 28 Nov 2010 21:21:03 +0000
Re: Speed up the nested loops (slower than inverse a large matrix)
http://www.mathworks.com/matlabcentral/newsreader/view_thread/297461#800010
Ximing xu
Thanks, Bruno. I agree with you; I think using forloop is not efficient to do the extraction or to do the sum. Is there any (possible) alternative to do the extraction in my case? <br>
<br>
If I want to compare the speed of my method (double sums) and the traditional method (inverse R) more precisely , should I use some basic language like C to do the programming rather than use the builtin functions in Matlab? <br>
<br>
Thanks,<br>
<br>
Ximing<br>
<br>
<br>
"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <icrjun$oe5$1@fred.mathworks.com>...<br>
> "Ximing xu" <siemenxu@gmail.com> wrote in message <icretg$4gm$1@fred.mathworks.com>...<br>
> <br>
> > I also tried Bruno's idea to extract all the 2x2 submatrices of R (also the F) and put it on 3D array; but it turn out the procedure to do the extraction is just as slow as doing the sum directly.<br>
> > <br>
> <br>
> I guess timing depends *how* you do the extraction. A forloop would not be optimal.<br>
> <br>
> Bruno

Sun, 28 Nov 2010 21:41:04 +0000
Re: Speed up the nested loops (slower than inverse a large matrix)
http://www.mathworks.com/matlabcentral/newsreader/view_thread/297461#800014
Bruno Luong
"Ximing xu" <siemenxu@gmail.com> wrote in message <icuh3v$i51$1@fred.mathworks.com>...<br>
> Thanks, Bruno. I agree with you; I think using forloop is not efficient to do the extraction or to do the sum. Is there any (possible) alternative to do the extraction in my case? <br>
> <br>
> If I want to compare the speed of my method (double sums) and the traditional method (inverse R) more precisely , should I use some basic language like C to do the programming rather than use the builtin functions in Matlab? <br>
> <br>
<br>
I think you should, because the traditional method of inversion of R benefits a very efficient implementation of BLAS/LAPACK. <br>
<br>
Your method should be implemented in low level language to be fair. But even that I'm not optimistic it can win on traditional processor because your method needs data to be moved a lot in the memory and that takes time. However it can be efficiently parallelized such as GPU computing.<br>
<br>
Good luck,<br>
<br>
Bruno