How does MATLAB exploit matrix multiplication's associativity?
in [Matlab]
|
From: Steven Lord on 23 Jun 2010 10:00 "Merciadri Luca" <Luca.Merciadri(a)student.ulg.ac.be> wrote in message news:87eifyktks.fsf(a)merciadriluca-station.MERCIADRILUCA... > -----BEGIN PGP SIGNED MESSAGE----- > Hash: SHA1 > > "Steven Lord" <slord(a)mathworks.com> writes: > >> "Merciadri Luca" <Luca.Merciadri(a)student.ulg.ac.be> wrote in message >> news:878w6cuukn.fsf(a)merciadriluca-station.MERCIADRILUCA... *snip* >> This group has had several discussions like this in the past -- mainly >> dealing with what's "the right way" to SUM a vector of numbers? > > Well, you're totally right, Steven. But there are some conditions > under which such rounding errors appear more often (just like finding > the inverse of a matrix and the relation with the condition > number). And MATLAB could verify, or at least warn, if the computation > is going to take a long time, and that, by modifying the parenthesis > order, it would take less time, with some given modification on the > result. Yes, MATLAB could check if you're multiplying together N+1 (for some large N) matrices in a chain and determine the most efficient way to perform that multiplication. But how common is it that you're performing such a multiplication with a large number of matrices? I believe it's fairly rare. Should we introduce a potentially time-consuming analysis like this in all cases where you perform matrix multiplication to try to save a bit of time in a rare case? I believe in previous releases we had a demo that did this sort of analysis when given the sizes of a set of matrices that you wanted to multiply together, but I don't see it in the list of demos anymore. I guess it wasn't used that often. -- Steve Lord slord(a)mathworks.com comp.soft-sys.matlab (CSSM) FAQ: http://matlabwiki.mathworks.com/MATLAB_FAQ To contact Technical Support use the Contact Us link on http://www.mathworks.com
From: Steven Lord on 23 Jun 2010 10:02 "Merciadri Luca" <Luca.Merciadri(a)student.ulg.ac.be> wrote in message news:87aaqmktj8.fsf(a)merciadriluca-station.MERCIADRILUCA... *snip* > And if we go until there, we could also say that `+' is not an > associative operator for reals, also because of reals' machine's encoding! "In theory, there is no difference between theory and practice. In practice, there is." http://en.wikiquote.org/wiki/Fact_and_theory Theoretically, addition is associative. In practice, for double precision values, it isn't. -- Steve Lord slord(a)mathworks.com comp.soft-sys.matlab (CSSM) FAQ: http://matlabwiki.mathworks.com/MATLAB_FAQ To contact Technical Support use the Contact Us link on http://www.mathworks.com
From: Bruno Luong on 23 Jun 2010 10:26 "Steven Lord" <slord(a)mathworks.com> wrote in message <hvt419$ql1$1(a)fred.mathworks.com>... > > "Merciadri Luca" <Luca.Merciadri(a)student.ulg.ac.be> wrote in message > news:87eifyktks.fsf(a)merciadriluca-station.MERCIADRILUCA... > > -----BEGIN PGP SIGNED MESSAGE----- > > Hash: SHA1 > > > > "Steven Lord" <slord(a)mathworks.com> writes: > > > >> "Merciadri Luca" <Luca.Merciadri(a)student.ulg.ac.be> wrote in message > >> news:878w6cuukn.fsf(a)merciadriluca-station.MERCIADRILUCA... > > > *snip* > > >> This group has had several discussions like this in the past -- mainly > >> dealing with what's "the right way" to SUM a vector of numbers? > > > > Well, you're totally right, Steven. But there are some conditions > > under which such rounding errors appear more often (just like finding > > the inverse of a matrix and the relation with the condition > > number). And MATLAB could verify, or at least warn, if the computation > > is going to take a long time, and that, by modifying the parenthesis > > order, it would take less time, with some given modification on the > > result. > > Yes, MATLAB could check if you're multiplying together N+1 (for some large > N) matrices in a chain and determine the most efficient way to perform that > multiplication. But how common is it that you're performing such a > multiplication with a large number of matrices? When multiplying more than 2 matrix, such question is pertinent. > I believe it's fairly rare. > Should we introduce a potentially time-consuming analysis like this in all > cases where you perform matrix multiplication to try to save a bit of time > in a rare case? The time consumed by the analysis is negligible even in my own Matlab implementation. One can of course programmed the analysis in C to make it even faster. Mathworks can even makes it even faster than faster because they can further more remove some of the overhead. Here is a quick test: >> A=rand(1000); >> B=rand(1000); >> C=rand(1000,1); >> tic; y1=A*B*C; toc Elapsed time is 0.094221 seconds. >> tic; y2=A*(B*C); toc Elapsed time is 0.004542 seconds. >> tic; y3=mmtimes(A,B,C); toc Elapsed time is 0.004994 seconds. >> TMW takes a pain to change the order of SUM two years ago (in the degree that user can't even access to the original order of summing from left to right). It should be trivial for them to make such analysis in chain MTIMES, unless if they consider breaking the compatibility is too risky. The big difference between SUM and MTIMES is that the smart MTIMES reduces the amount of computation, and not only splitting the intermediate results for different processors/cores, and I bet that the overall accuracy can also be improved. Bruno
From: Merciadri Luca on 26 Jun 2010 13:39 -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 "Steven Lord" <slord(a)mathworks.com> writes: > Yes, MATLAB could check if you're multiplying together N+1 (for some large > N) matrices in a chain and determine the most efficient way to perform that > multiplication. But how common is it that you're performing such a > multiplication with a large number of matrices? Not common. > I believe it's fairly rare. / > Should we introduce a potentially time-consuming analysis like this in all > cases where you perform matrix multiplication to try to save a bit of time > in a rare case? Might be interesting though. > I believe in previous releases we had a demo that did this sort of analysis > when given the sizes of a set of matrices that you wanted to multiply > together, but I don't see it in the list of demos anymore. I guess it > wasn't used that often. Okay. I did not know it. - -- Merciadri Luca See http://www.student.montefiore.ulg.ac.be/~merciadri/ - -- There is a thin line between love and hate. -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Processed by Mailcrypt 3.5.8 <http://mailcrypt.sourceforge.net/> iEYEARECAAYFAkwmOzUACgkQM0LLzLt8MhzPiACfan7dpJqSDbAG+OfvrZGG123u 9JYAoIwZYkkcaX0/XsPb829bDiFOt714 =aqpN -----END PGP SIGNATURE-----
From: Merciadri Luca on 26 Jun 2010 13:41 -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 "Bruno Luong" <b.luong(a)fogale.findmycountry> writes: > "Steven Lord" <slord(a)mathworks.com> wrote in message <hvt419$ql1$1(a)fred.mathworks.com>... >> >> "Merciadri Luca" <Luca.Merciadri(a)student.ulg.ac.be> wrote in message >> news:87eifyktks.fsf(a)merciadriluca-station.MERCIADRILUCA... >> > -----BEGIN PGP SIGNED MESSAGE----- >> > Hash: SHA1 >> > >> > "Steven Lord" <slord(a)mathworks.com> writes: >> > >> >> "Merciadri Luca" <Luca.Merciadri(a)student.ulg.ac.be> wrote in message >> >> news:878w6cuukn.fsf(a)merciadriluca-station.MERCIADRILUCA... >> >> >> *snip* >> >> >> This group has had several discussions like this in the past -- mainly >> >> dealing with what's "the right way" to SUM a vector of numbers? >> > >> > Well, you're totally right, Steven. But there are some conditions >> > under which such rounding errors appear more often (just like finding >> > the inverse of a matrix and the relation with the condition >> > number). And MATLAB could verify, or at least warn, if the computation >> > is going to take a long time, and that, by modifying the parenthesis >> > order, it would take less time, with some given modification on the >> > result. >> >> Yes, MATLAB could check if you're multiplying together N+1 (for some large >> N) matrices in a chain and determine the most efficient way to perform that >> multiplication. But how common is it that you're performing such a >> multiplication with a large number of matrices? > > When multiplying more than 2 matrix, such question is pertinent. > >> I believe it's fairly rare. >> Should we introduce a potentially time-consuming analysis like this in all >> cases where you perform matrix multiplication to try to save a bit of time >> in a rare case? > > The time consumed by the analysis is negligible even in my own Matlab implementation. One can of course programmed the analysis in C to make it even faster. Mathworks can even makes it even faster than faster because they can further more remove some of the overhead. Here is a quick test: > >>> A=rand(1000); >>> B=rand(1000); >>> C=rand(1000,1); >>> tic; y1=A*B*C; toc > Elapsed time is 0.094221 seconds. >>> tic; y2=A*(B*C); toc > Elapsed time is 0.004542 seconds. >>> tic; y3=mmtimes(A,B,C); toc > Elapsed time is 0.004994 seconds. >>> I suppose `mmtimes' is some function you defined in some homemade m-file. Well, how did you proceed to find the best way to achieve the product? (I do not know if there is an already-established, and efficient algorithm for doing this; it should not be difficult to find a good implementation of this, though.) > TMW takes a pain to change the order of SUM two years ago (in the degree that user can't even access to the original order of summing from left to right). It should be trivial for them to make such analysis in chain MTIMES, unless if they consider breaking the compatibility is too risky. The big difference between SUM and MTIMES is that the smart MTIMES reduces the amount of computation, and not only splitting the intermediate results for different processors/cores, and I bet that the overall accuracy can also be improved. - -- Merciadri Luca See http://www.student.montefiore.ulg.ac.be/~merciadri/ - -- The dog is nude though the clothing cost a penny. -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Processed by Mailcrypt 3.5.8 <http://mailcrypt.sourceforge.net/> iEYEARECAAYFAkwmO8cACgkQM0LLzLt8Mhyp/gCdHv7x4Jzk1O9Nop0Pae2TeY5k xj0An0vw/K6b2CaZL2meB/VbRvTwwA4J =bKcJ -----END PGP SIGNATURE-----
First
|
Prev
|
Next
|
Last
Pages: 1 2 3 4 5 Prev: error when using "imshow" within a "parfor" loop Next: Simulink 3D Animation Joystick |