Computation of Matrix Chain Products. Part II
Computation of Matrix Chain Products. Part II
复制标题
矩阵链积的计算。
DOI：
--
复制
发表时间：
1984
期刊：
影响因子：
--
通讯作者：
M. Shing
中科院分区：
文献类型：
--
作者：
T. C. Hu;M. Shing
本文讨论了矩阵链积M_1×M_2×M_cdots\×M_(n-1)的计算。如果矩阵的维度不同，则乘积的计算顺序会影响运算的数量。最优顺序是使操作总数最小化的顺序。我们给出了一些关于计算矩阵的最佳顺序的定理。在这些定理的基础上，第二部分将给出一个寻找最优阶的$O(n\logn)$算法。
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 product is computed affects the number of operations. An optimum order is an order which minimizes the total number of operations. We present some theorems about an optimum order of computing the matrices. Based on these theorems, an $O(n\log n)$ algorithm for finding an optimum order will be presented in Part II.