[Top][All Lists]

[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
    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?

reply via email to

[Prev in Thread] Current Thread [Next in Thread]