Prev: error when using "imshow" within a "parfor" loop
Next: Simulink 3D Animation Joystick
From: Bruno Luong on 19 Jun 2010 06:52
Based on wikipedia, I have programmed the best order of multiple-matrix product. I'll submit on FEX after some cleaning.

function P = mmtimes(varargin)
% P = mmtimes(M1, M2, ... Mn)
% multiple matrices product
% P = M1*M2* ... *Mn
%
% MMTIMES usings optimal order of binary product to reduce the computation
%
% See also: mtimes
%
% Author: Bruno Luong <brunoluong@...>
% Orginal: 19-Jun-2010

Matrices = varargin;
% Size of matrices
p = [cellfun('size',Matrices,1) size(Matrices{end},2)];

m = MatrixChainOrder(p);
P = ProdEngine(1,length(Matrices),m, Matrices);

end % mmtimes

%%
function m = MatrixChainOrder(p)
% Top-down dynamic programming, complexity O(n^3)
% http://en.wikipedia.org/wiki/Matrix_chain_multiplication

n = length(p)-1;
m = zeros(n);

for L=2:n
for i=1:n-L+1
j = i+L-1;
m(i,j) = Inf;
for k=i:j-1
q = m(i,k) + m(k+1,j) + p(i)*p(k+1)*p(j+1);
if (q < m(i,j))
m(i,j) = q;
m(j,i) = k;
end
end
end
end

end % MatrixChainOrder

%%
function P = ProdEngine(i,j,m,Matrices)
% Perform matrix product from the optimal order
if i==j
P = Matrices{i};
else
P1 = ProdEngine(i,m(j,i),m,Matrices);
P2 = ProdEngine(m(j,i)+1,j,m,Matrices);
P = P1*P2;
end

end % ProdEngine
From: Merciadri Luca on 20 Jun 2010 07:03
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

"Bruno Luong" <b.luong(a)fogale.findmycountry> writes:

> Based on wikipedia, I have programmed the best order of multiple-matrix product. I'll submit on FEX after some cleaning.
>
> function P = mmtimes(varargin)
> % P = mmtimes(M1, M2, ... Mn)
> % multiple matrices product
> % P = M1*M2* ... *Mn
> %
> % MMTIMES usings optimal order of binary product to reduce the computation
> %
> % See also: mtimes
> %
> % Author: Bruno Luong <brunoluong@...>
> % Orginal: 19-Jun-2010
>
> Matrices = varargin;
> % Size of matrices
> p = [cellfun('size',Matrices,1) size(Matrices{end},2)];
>
> m = MatrixChainOrder(p);
> P = ProdEngine(1,length(Matrices),m, Matrices);
>
> end % mmtimes
>
> %%
> function m = MatrixChainOrder(p)
> % Top-down dynamic programming, complexity O(n^3)
> % http://en.wikipedia.org/wiki/Matrix_chain_multiplication
>
> n = length(p)-1;
> m = zeros(n);
>
> for L=2:n
> for i=1:n-L+1
> j = i+L-1;
> m(i,j) = Inf;
> for k=i:j-1
> q = m(i,k) + m(k+1,j) + p(i)*p(k+1)*p(j+1);
> if (q < m(i,j))
> m(i,j) = q;
> m(j,i) = k;
> end
> end
> end
> end
>
> end % MatrixChainOrder
>
> %%
> function P = ProdEngine(i,j,m,Matrices)
> % Perform matrix product from the optimal order
> if i==j
> P = Matrices{i};
> else
> P1 = ProdEngine(i,m(j,i),m,Matrices);
> P2 = ProdEngine(m(j,i)+1,j,m,Matrices);
> P = P1*P2;
> end
>
> end % ProdEngine
Thanks!
- --
Merciadri Luca
See http://www.student.montefiore.ulg.ac.be/~merciadri/
- --

Necessity is the mother of all invention.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Processed by Mailcrypt 3.5.8 <http://mailcrypt.sourceforge.net/>

iEYEARECAAYFAkwd9W0ACgkQM0LLzLt8MhxY0ACgn/SAYCklbDRasWn7lMeSrYfX
1AIAnisby1Ho21VxeZ4OrNLzM5A0Pd9Z
=GteA
-----END PGP SIGNATURE-----
From: Steven Lord on 22 Jun 2010 16:18

"Merciadri Luca" <Luca.Merciadri(a)student.ulg.ac.be> wrote in message
news:878w6cuukn.fsf(a)merciadriluca-station.MERCIADRILUCA...
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Hi,
>
> How does MATLAB exploit matrix multiplication's associativity? Given A
> B C such that their product is possible (in matrix terms), it often
> happens that
> complexity(A(BC)) != complexity((AB)C).
>
> So, how does MATLAB guess this? Is there a well-known algorithm about
> this?

MATLAB does not exploit associativity; it performs the operations from left
to right, taking sets of parentheses into account.

One reason for this is that while operations may _theoretically_ be
associative, in _practice_ they may not be. For example, take a look at
simple addition:

x = -1 + (1+1e-30);
y = (-1 + 1) + 1e-30;
areTheyEqual = (x==y) % false!

And this is NOT a bug; the answers of 0 for x and 1e-30 for y are BOTH
correct, given the computations performed. Search for "associative" in this
document for some discussion as to why this occurs:

http://docs.sun.com/source/806-3568/ncg_goldberg.html

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?

--
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: Merciadri Luca on 23 Jun 2010 05:05
-----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...
>> -----BEGIN PGP SIGNED MESSAGE-----
>> Hash: SHA1
>>
>> Hi,
>>
>> How does MATLAB exploit matrix multiplication's associativity? Given A
>> B C such that their product is possible (in matrix terms), it often
>> happens that
>> complexity(A(BC)) != complexity((AB)C).
>>
>> So, how does MATLAB guess this? Is there a well-known algorithm about
>> this?
>
> MATLAB does not exploit associativity; it performs the operations from left
> to right, taking sets of parentheses into account.
>
> One reason for this is that while operations may _theoretically_ be
> associative, in _practice_ they may not be. For example, take a look at
> simple addition:
>
> x = -1 + (1+1e-30);
> y = (-1 + 1) + 1e-30;
> areTheyEqual = (x==y) % false!
>
> And this is NOT a bug; the answers of 0 for x and 1e-30 for y are BOTH
> correct, given the computations performed. Search for "associative" in this
> document for some discussion as to why this occurs:
>
> http://docs.sun.com/source/806-3568/ncg_goldberg.html
>
> 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.
- --
Merciadri Luca
See http://www.student.montefiore.ulg.ac.be/~merciadri/
- --

Laugh and the world laughs with you ... Cry and you will find no one
with tears.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Processed by Mailcrypt 3.5.8 <http://mailcrypt.sourceforge.net/>

iEYEARECAAYFAkwhzkMACgkQM0LLzLt8MhyxswCfXa4pHEKS734L4Jlm6XCNMCl6
LWMAnjJg7ZpihbruHM6Ux+/MaiHQtn+/
=SA8P
-----END PGP SIGNATURE-----
From: Merciadri Luca on 23 Jun 2010 05:06
-----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...
>> -----BEGIN PGP SIGNED MESSAGE-----
>> Hash: SHA1
>>
>> Hi,
>>
>> How does MATLAB exploit matrix multiplication's associativity? Given A
>> B C such that their product is possible (in matrix terms), it often
>> happens that
>> complexity(A(BC)) != complexity((AB)C).
>>
>> So, how does MATLAB guess this? Is there a well-known algorithm about
>> this?
>
> MATLAB does not exploit associativity; it performs the operations from left
> to right, taking sets of parentheses into account.
>
> One reason for this is that while operations may _theoretically_ be
> associative, in _practice_ they may not be. For example, take a look at
> simple addition:
>
> x = -1 + (1+1e-30);
> y = (-1 + 1) + 1e-30;
> areTheyEqual = (x==y) % false!
>
> And this is NOT a bug; the answers of 0 for x and 1e-30 for y are BOTH
> correct, given the computations performed. Search for "associative" in this
> document for some discussion as to why this occurs:
>
> http://docs.sun.com/source/806-3568/ncg_goldberg.html
>
> 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?
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!
- --
Merciadri Luca
See http://www.student.montefiore.ulg.ac.be/~merciadri/
- --

Life is like a box of chocolate, you never know what you're gonna
get.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Processed by Mailcrypt 3.5.8 <http://mailcrypt.sourceforge.net/>

iEYEARECAAYFAkwhznsACgkQM0LLzLt8MhwDlgCgjdGdVDje+3JyyZJiZuPeKqGN
XP8An2HU8mNJCKCmCsr074xq3CBVJwQ/
=ZrwK
-----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