Matrix chain multiplication

An algorithm published in 1981 by Hu and Shing achieves O(n log n) computational complexity.[2][3][4] They showed how the matrix chain multiplication problem can be transformed (or reduced) into the problem of triangulation of a regular polygon. The polygon is oriented such that there is a horizontal bottom side, called the base, which represents the final result. The other n sides of the polygon, in the clockwise direction, represent the matrices. The vertices on each end of a side are the dimensions of the matrix represented by that side. With n matrices in the multiplication chain there are n−1 binary operations and C_n−1 ways of placing parentheses, where C_n−1 is the (n−1)-th Catalan number. The algorithm exploits that there are also C_n−1 possible triangulations of a polygon with n+1 sides.

This image illustrates possible triangulations of a regular hexagon. These correspond to the different ways that parentheses can be placed to order the multiplications for a product of 5 matrices.

For the example below, there are four sides: A, B, C and the final result ABC. A is a 10×30 matrix, B is a 30×5 matrix, C is a 5×60 matrix, and the final result is a 10×60 matrix. The regular polygon for this example is a 4-gon, i.e. a square:

The matrix product AB is a 10x5 matrix and BC is a 30x60 matrix. The two possible triangulations in this example are:

• 
  Polygon representation of (AB)C
• 
  Polygon representation of A(BC)

The cost of a single triangle in terms of the number of multiplications needed is the product of its vertices. The total cost of a particular triangulation of the polygon is the sum of the costs of all its triangles:

(AB)C: (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 multiplications

A(BC): (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 multiplications

Hu & Shing developed an algorithm that finds an optimum solution for the minimum cost partition problem in O(n log n) time.

In the introduction of [4] an approximating algorithm, the Chin-Hu-Shing approximating algorithm, is presented. While this algorithm produces an approximation of the optimal triangulation it is worth explaining it since it makes the understanding of the techniques utilized by Hu-Shing in their work easier.

To each vertex V of the polygon is associated a weight w. Suppose we have three consecutive vertices ${\displaystyle V_{i-1},V_{i},V_{i+1}}$, and that ${\displaystyle V_{min}}$ is the vertex with minimum weight ${\displaystyle w_{min}}$. We look at the quadrilateral with vertices ${\displaystyle V_{min},V_{i-1},V_{i},V_{i+1}}$ (in clockwise order). We can triangulate it in two ways:

• ${\displaystyle (V_{min},V_{i-1},V_{i})}$ and ${\displaystyle (V_{min},V_{i+1},V_{i})}$, with cost ${\displaystyle w_{min}w_{i-1}w_{i}+w_{min}w_{i+1}w_{i}}$
• ${\displaystyle (V_{min},V_{i-1},V_{i+1})}$ and ${\displaystyle (V_{i-1},V_{i},V_{i+1})}$ with cost ${\displaystyle w_{min}w_{i-1}w_{i+1}+w_{i-1}w_{i}w_{i+1}}$.

Therefore if

${\displaystyle w_{min}w_{i-1}w_{i+1}+w_{i-1}w_{i}w_{i+1}<w_{min}w_{i-1}w_{i}+w_{min}w_{i+1}w_{i}}$

or equivalently

${\displaystyle {\frac {1}{w_{i}}}+{\frac {1}{w_{min}}}<{\frac {1}{w_{i+1}}}+{\frac {1}{w_{i-1}}}}$

we remove the vertex ${\displaystyle V_{i}}$ from the polygon and add the side ${\displaystyle (V_{i-1},V_{i+1})}$ to the triangulation. We repeat this process until no ${\displaystyle V_{i}}$ satisfies the condition above. For all the remaining vertices ${\displaystyle V_{n}}$, we add the side ${\displaystyle (V_{min},V_{n})}$ to the triangulation. This gives us a nearly optimal triangulation.