一种改进的小矩阵连乘算法

Improved serial multiplication algorithm for small matrixes

首先引入了矩阵的连乘优先因子,接着采用连乘优先因子最小的贪心选择策略,提出了最小连乘因子优先算法。它确定125的连乘次序不一定是最优次序,但在确定连乘次序方面比动态规划法花费的时间和空间少。最后通过实例对比测试,表明该算法在计算小矩阵连乘时,总体效率优于动态规划法。

Priority factor of serial matrix multiplication is presented in the first part of the paper.Then adopting greedy selection strategy based on minimum priority factor of serial matrix multiplication,minimum serial multiplication factor first algorithm is put forward.Computation sequence obtained from this algorithm is not always optimal,but it spends less time and space than dynamic programming.Finally,the experiment result indicates that the proposed algorithm is more effective than dynamic programming for small matrixes on the whole.