Matrix Chain Multiplication Greedy Approach

Question

In the question Matrix Chain Multiplication you are given a chain of Matrices and is required to find the optimal way to multiply the matrices together. Normally this is solved using Dynamic Programming but I have found a greedy approach to this problem.

For example a chain of Matrices of the size of:

   A        B       C       D
40 * 20  20 * 30 30 * 10 10 * 30

First list all of the possible consecutive pairs, and the 2 different dimensions of the pair:

        X
AB:  40 * 30
BC:  20 * 10 <----
CD:  30 * 30

Then multiply the pair that has the lowest product in the X column and the list will turn into:

   A       BC      D
40 * 20 20 * 10 10 * 30

Repeat the first 2 steps until all of the matrices are multiplied together:

          X
A(BC): 40 * 10 <----
(BC)D: 20 * 30

  ABC      D
40 * 10 10 * 30

             X
(A(BC))D: 40 * 30 <----

This have a time complexity of $O(2n^2 + 2n\log n)$.

I have tested a Java implementation on smaller test cases and it runs fine.

Does this method work, or is there a something I have overlooked?

Answer 1

You don't state why you think that your algorithm is correct. In fact, it is incorrect. Here is an example. Consider the problem of computing the product of matrices of dimensions $2\times 1$, $1\times 2$, $2 \times 5$. Your algorithm first multiplies the first two at a cost of $4$, and then multiplies the remaining matrices at a cost of $20$, to a total of $24$. In contrast, the other option has complexity $10 + 10 = 20$.

According to Wikipedia, Hu and Shing came up with an $O(n\log n)$ algorithm, which is more efficient than your algorithm, and moreover is provably correct.