Improved serial multiplication algorithm for small matrixes

doi:10.3778/j.issn.1002-8331.2010.17.011

Computer Engineering and Applications ›› 2010, Vol. 46 ›› Issue (17): 39-40.DOI: 10.3778/j.issn.1002-8331.2010.17.011

• 研究、探讨 • Previous Articles Next Articles

Improved serial multiplication algorithm for small matrixes

HE Li，WU Li-xian

Department of Mathematics and Information Technology，Hanshan Teachers’ College，Chaozhou，Guangdong 521041，China

Received:2008-12-18 Revised:2009-03-05 Online:2010-06-11 Published:2010-06-11
Contact: HE Li

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

和力，吴丽贤

韩山师范学院数学与信息技术系，广东潮州 521041

通讯作者: 和力

Abstract

Abstract: 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.

Key words: serial matrix multiplication, minimum serial multiplication factor first algorithm, dynamic programming, greedy algorithm

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

关键词: 矩阵连乘, 最小连乘因子优先算法, 动态规划法, 贪心算法

CLC Number:

TP301.6

HE Li，WU Li-xian. Improved serial multiplication algorithm for small matrixes[J]. Computer Engineering and Applications, 2010, 46(17): 39-40.

和力，吴丽贤. 一种改进的小矩阵连乘算法 [J]. 计算机工程与应用, 2010, 46(17): 39-40.

[1]	ZHOU Ruimin, LI Hui. Path Planning of Mobile Robot Based on Improved Dynamic Programming Algorithm [J]. Computer Engineering and Applications, 2020, 56(21): 20-24.
[2]	CHEN Junjie, TONG Shurong, NIE Yafei, ZHANG Jingwen. R&D Program Scheduling and Staff Assignment with Hierarchical Levels of Competency [J]. Computer Engineering and Applications, 2019, 55(3): 209-218.
[3]	LIAN Wei. Globally Optimal Shape Matching Algorithm Using Tree Representation [J]. Computer Engineering and Applications, 2019, 55(1): 217-225.
[4]	ZHANG Yu, CUI Yaodong, LIANG Zehua. Two-dimensional cutting stock problem of multiple logs [J]. Computer Engineering and Applications, 2018, 54(19): 266-270.
[5]	XIAO Hongde. Calculation of minimum count of money and determination of money denomination [J]. Computer Engineering and Applications, 2018, 54(16): 266-270.
[6]	ZHANG Nana, ZHAO Zuopeng, LI Xiaobo. Non-uniform node distribution routing protocol adopted semi-greedy optimization idea [J]. Computer Engineering and Applications, 2017, 53(23): 60-66.
[7]	ZHU Xu, NIU Cunliang, BAI Xiaoli. Improved ZigBee tree routing algorithm [J]. Computer Engineering and Applications, 2016, 52(5): 114-118.
[8]	SUN Peishuang, HAN Qirui. Improved optimal stitching line applied to image stitching [J]. Computer Engineering and Applications, 2016, 52(21): 218-221.
[9]	LIN Ruonan, LI Qiang. Template-based task scheduling strategy and algorithm in cloud computing environment [J]. Computer Engineering and Applications, 2016, 52(19): 48-52.
[10]	FANG Gang1, ZHANG Shemin2. 3-gram statistical language model optimization to expression vector design [J]. Computer Engineering and Applications, 2016, 52(15): 60-64.
[11]	ZHANG Xingong, WANG Hui, BAI Shikun. Two-agent scheduling on single machine to minimize number of tardy jobs [J]. Computer Engineering and Applications, 2016, 52(14): 32-36.
[12]	LIN Huazhou, ZHANG Dakun, HUANG Cui. Research on low-power mapping for three-dimensional network-on-chip based on inproved genetic algorithm [J]. Computer Engineering and Applications, 2016, 52(1): 76-80.
[13]	MOU Lianming1，2, LUO Kaibao1, CHEN Lin1, LUO Shiming1. Semi-automatic visualization stitching method of image fragments [J]. Computer Engineering and Applications, 2016, 52(1): 206-209.
[14]	LI Huiguang, LI Feng, SHAO Nuan, SHA Xiaopeng, WANG Shuai. Segment-based stereo matching method with ground control points [J]. Computer Engineering and Applications, 2015, 51(23): 160-163.
[15]	ZHANG Yu, XU Hongze, CHEN Jianqiang,ZHANG Luning. Research on optimization strategy of train route control in metallurgical enterprises [J]. Computer Engineering and Applications, 2015, 51(17): 250-254.

Improved serial multiplication algorithm for small matrixes

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics