An efficient algorithm for chain multiplication of dense matrices and its computer implementation

In this work, we consider the matrix chain ordering problem to determine the optimal computation order of the matrix chain products. A new algorithm for the matrix chain ordering problem is presented. The time complexity of the presented algorithm is O(n logm), where n is the number of matrices in the chain and m is the number of local minimums in the dimension sequence of the given matrix chain. When m is a fixed constant, the new algorithm requires only O(n) time. The new algorithm is not only an improvement on the time complexity compared to the O(n log n) time algorithm of Hu and Shing, but also substantially simpler than the Hu-Shing algorithm. 1553-9105/Copyright © 2014 Binary Information Press.