Computation of Matrix Chain Products. Part II
T. C. Hu, Man‐Tak Shing · SIAM Journal on Computing · 1984
This paper considers the computation of matrix chain products of the form $M_1 \times M_2 \times \cdots \times M_{n - 1} $. If the matrices are of different dimensions, the order in which the matrices are computed affects the number of operations. An optimum order is an order which minimizes the total number of operations. Some theorems about an optimum order of computing the matrices have been presented in Part I [SIAM J. Comput., 11 (1982), pp. 362–373]. Based on those theorems, an $O(n\log n)$ algorithm for finding the optimum order is presented here.