help-octave
[Top][All Lists]

## 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?
```

```