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

被引：0

作者：

Faculty of Mathematics and Computer Science, Quanzhou Normal University, Quanzhou 362000, China ^{[1
]}

不详 ^{[2
]}

机构：

[1] Faculty of Mathematics and Computer Science, Quanzhou Normal University

[2] Faculty of Mathematics and Computer Science, Fuzhou University

来源：

J. Comput. Inf. Syst. | / 10卷 / 4299-4306期

关键词：

Algorithms; Convex polygon partition; Dynamic programming; Matrix chain ordering;

D O I：

10.12733/jcis10313

中图分类号：

学科分类号：

摘要：

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.

引用

页码：4299 / 4306

页数：7