An O(n) algorithm for determining a near-optimal computation order of matrix chain products
Francis Y. L. Chin · Communications of the ACM · 1978
This paper discusses the computation of matrix chain products of the form M 1 × M 2 2 × ··· × M n where M i 's are matrices. The order in which the matrices are computed affects the number of operations. A sufficient condition about the association of the matrices in the optimal order is presented. An O ( n ) algorithm to find an order of computation which takes less than 25 percent longer than the optimal time T opt is also presented. In most cases, the algorithm yields the optimal order or an order which takes only a few percent longer than T opt (less than 1 percent on the average).