Revisiting “Computation of Matrix Chain Products''
Oded Schwartz, Elad Weiss · SIAM Journal on Computing · 2019
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.