[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
## Order of matrix multiplication

**From**: |
Bernardo Sulzbach |

**Subject**: |
Order of matrix multiplication |

**Date**: |
Mon, 12 Sep 2016 10:05:44 -0300 |

**User-agent**: |
Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.2.0 |

`I noticed today that Octave always performs multiplication from left to
``right.
`
This is, as one could expect, properly documented:
-- Built-in Function: mtimes (X1, X2, ...)
Return the matrix multiplication product of inputs.
This function and x * y are equivalent. If more arguments are
given, the multiplication is applied cumulatively from left to
right (...)

`This is evidently not the best solution from a performance point of view
``if a multiplication substantially reduces the size of the product.
`
Locally, profiling
m * m * m * m * x
against
m * (m * (m * (m * x)));

`when the size of m is [2048 2048] and the size of x is [2048 1] produces
``the following results
`
Took 9.752126 seconds when using the default order.
Took 0.035902 seconds when going from right to left.
Maximum difference is 0.000732422.

`I may be oversimplifying the analysis of numerical error here, but I
``would say that the second solution introduces less error as the number
``of floating-point operations is much smaller.
`
---

`Understanding that trying to determine the "best" order of matrix
``multiplication during execution may not be a trivial task, I still
``wonder why Octave approach is so naive.
`

`Additionally, would there be any function out there which I could use
``instead of mtimes which performed some analysis on the dimensions of the
``input matrices and optimized the order of multiplication without
``requiring me to do it manually?
`

**Order of matrix multiplication**,
*Bernardo Sulzbach* **<=**
**Re: Order of matrix multiplication**, *Nicholas Jankowski*, `2016/09/12`
**Re: Order of matrix multiplication**, *Nicholas Jankowski*, `2016/09/12`
**Re: Order of matrix multiplication**, *Yu Liu*, `2016/09/12`
**Re: Order of matrix multiplication**, *Nicholas Jankowski*, `2016/09/12`
**Re: Order of matrix multiplication**, *Bernardo Sulzbach*, `2016/09/12`
**Re: Order of matrix multiplication**, *Nicholas Jankowski*, `2016/09/12`
**Re: Order of matrix multiplication**, *Mike Miller*, `2016/09/12`
**Re: Order of matrix multiplication**, *Bernardo Sulzbach*, `2016/09/12`
**Re: Order of matrix multiplication**, *siko1056*, `2016/09/13`
**Re: Order of matrix multiplication**, *Bernardo Sulzbach*, `2016/09/13`