bugGNU Octave - Bugs: bug #49076, Should perform matrix chain...

 
 

bug #49076: Should perform matrix chain multiplication optimization

Submitter:  None
Submitted:  Mon 12 Sep 2016 10:44:38 PM UTC
   
 
Category:  Performance Severity:  1 - Wish
Priority:  3 - Low Item Group:  Performance
Status:  Confirmed Assigned to:  None
Originator Name:  Bernardo Sulzbach Originator Email:  -email is unavailable-
Open/Closed:  * Open Release:  * dev
Operating System:  * Any Fixed Release:  None
Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Sun 10 Sep 2017 11:51:28 PM UTC, comment #3: 

Comment:

This problem shows up frequently in CS textbooks as a pedagogic example on dynamic programming but nobody can show real-life code where the following all apply:

  • Should be three or many more matrices that are not square OR equally and oppositely rectangular. This eliminates most problems in optimization (BFGS) and linear algebra (SVD) which use either x'BB'x or x'Ax both better solved by symmetric decomposition.


  • Should be large matrices for the effect to be significant. This removes the common case of chain multiplication: transformation matrices for computer graphics and 3D manipulation. They never exceed 4x4 and many of them are hardware-optimized as well.


  • Should be dynamically changing sizes, otherwise static offline analysis of the matrix chain is just fine.


  • The user should be likely enough to encounter instances of matrix chain multiplication but not be aware of the associativity relation or the benefit of offline static analysis. This is the biggest stopper.


Recommendation: There really are no such real-life problems that make it worth implementing such a just-in-time performance analysis for numerical software. Much better to leave it as a pedagogic example.

Anonymous
Fri 16 Sep 2016 01:27:08 AM UTC, comment #2: 

I understand your concerns. However, this is not meant to be a new default behavior. I would like this to be a function provided by octave. Using the * with matrices should still call mtimes and not this new function.

After rereading my last paragraph I see that it only hints at a different function calling mtimes. However, I don't mean that multiple usages of * should lead into a call to this function rather than mtimes. I am not proposing any changes to the current behavior of matrix multiplication in Octave.

The main point of the enhancement is to allow more efficient code for large enough matrices where overflow should not happen without requiring men hours to optimize the order manually when the optimization is not trivial.




As a last note, you are referring to -fassociative-math (and some other options) which allow the compiler to assume that FP math is associative. The optimizations I am talking about will, evidently, reorder multiplications. This is just another reason not to make this behavior the new default, which I don't want it to become.

Bernardo Sulzbach <mafagafogigante>
Thu 15 Sep 2016 12:35:14 PM UTC, comment #1: 

You know that floating-point multiplication is not associative. Yes, it can well be that an optimization with respect to performance is also advantageous in terms of the accumulation of floating-point round errors, but do not forget arithmetic overflow.

In any case, such an optimization would cost you due to added complexity in the interpreter with every matrix multiplication. However, it would pay off only for larger matrices, where such an optimization can always done by hand (you demonstrate the solution for your particular case, and also I remember instances in actual code where I took care to order the multiplications optimally). So I am not certain whether your proposal would actually correspond to a gain in the averaged case, even disregarding implementation and maintenance effort, introduced bugs and so on. Note that this is different from questions such as just-in-time compilation, where the added complexity to the interpreter leads to less as opposed to more work being done in the interpreter (provided the heuristics work).

Finally, I appreciate the present case where internally the natural thing happens, as opposed to where I have to parenthesize all running products to define the behaviour. Note that, as far as I know, for instance also gcc without explicit instructions otherwise would not reorder floating-point operations.

Anonymous
Mon 12 Sep 2016 10:44:38 PM UTC, original submission:  

Octave always performs matrix 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.


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.

---

This is a known problem (https://en.wikipedia.org/wiki/Matrix_chain_multiplication) and should likely be solved by a special function which would determine the best multiplication order before calling mtimes.

Anonymous

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by mafagafogigante (Posted a comment)
  • -email is unavailable- added by siko1056 (Updated the item)
  • -email is unavailable- added by None (Submitted the item)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only group members can vote.

     

    Follow 3 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2016-09-14 siko1056 Severity3 - Normal 1 - Wish
        Priority5 - Normal 3 - Low
        StatusNone Confirmed

    Back to the top

    Powered by Savane 3.13-02a9.
    Corresponding source code