Matrix Sequence Multiplication

• eg. 1:

  

  • Left to right evaluation requires more than 12K multiplications.
  • needs only 690 multiplications (minimum needed).
  • Greedy Algorithm: Largest Common Dimension First
    
• eg. 2:

  

  • Largest Common Dimension First imposes following order:

    

    which needs 240 multiplications.

  • Best order:

    

    which needs 68 multiplications.

  • Another Greedy Algorithm: Smallest Common Dimension First but did not work for eg. 1.