The Matrix Chain Ordering Problem is a well studied optimization problem, aiming at finding optimal parentheses assignment for minimizing the number of arithmetic operations required when computing a chain of matrix multiplications. Existing algorithms include the O(N3) dynamic programming of Godbole (1973) and the faster O(N log N) algorithm of Hu and Shing (1982). We show that both may result in suboptimal parentheses assignment on modern machines as they do not take into account inter-processor communication costs that often dominate the running time. Further, the optimal solution may change when using fast matrix multiplication algorithms. We show that the O(N3) dynamic-programing algorithm easily adapts to provide optimal solutions for modern matrix multiplication algorithms, and obtain an adaption of the O(N log N) algorithm that guarantees a constant approximation.

The matrix chain ordering problem aims to reduce the number of arithmetic operations required for evaluating the product of $N$ matrices. Using a dynamic programming algorithm this problem can be solved in $O(N^3)$ time. Hu and Shing obtained a sophisticated algorithm that solves the problem in $O ( N\log{N} )$ [ SIAM J. Comput., 11 (1982), pp. 362--373]. Unfortunately, as we show here, the correctness proof of their algorithm is wrong. This flaw affects another algorithm for the same problem, by Wang, Zhu, and Tian (2013), and algorithms for many other problems that use chain matrix multiplication as a building block. We present an alternative proof for the correctness of the first two algorithms and show that a third algorithm by Nimbark, Gohel, and Doshi (2011) is beyond repair.