Report Number: CS-TR-81-875
Institution: Stanford University, Department of Computer Science
Title: Computation of matrix chain products: Part I, Part II
Author: Hu, T. C.
Author: Shing, M. T.
Date: September 1981
Abstract: This paper considers the computation of matrix chain products of the form $M_1 x M_2 x ... x M_{n-1}$. If the matrices are of different dimensions, the order in which the product is 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 are presented in part I. Based on these theorems, an O(n log n) algorithm for finding an optimum order is presented in part II.
http://i.stanford.edu/pub/cstr/reports/cs/tr/81/875/CS-TR-81-875.pdf