A fast algorithm for matrix multiplication and its efficient realization on systolic arrays

被引：10
作者：
Elfimova L.D. [1 ]
Kapitonova Y.V. [1 ]
机构：
[1] Cybernetics Institute, National Academy of Sciences of Ukraine, Kiev
来源：
Cybernetics and Systems Analysis | 2001年 / 37卷 / 1期
关键词：
Fast algorithm; Matrix multiplication; Strassen algorithm; Systolic arrays; Winograd algorithm;
D O I：
10.1023/A:1016676318988
中图分类号：
学科分类号：
摘要：
A new fast matrix multiplication algorithm is proposed, which, as compared to the Winograd algorithm, has a lower multiplicative complexity equal to WM ≈0.437n3 multiplication operations. Based on a goal-directed transfonnation of its basic graph, new optimized architectures of systolic arrays are synthesized. A systolic variant of the Strassen algorithm is presented for the first time. © 2001 Kluwer Academic/Plenum Publishers.
引用
收藏
页码：109 / 121
页数：12
相关论文
共 39 条
[1]  
Kung H.T., Leiserson C.E., "Systolic Arrays for VLSI," In: Proc. Sparse Matrix Symp.
[2]  
Kunq H.T., "Why Systolic Architectures?" Computer
[3]  
Kung S.Y., H. I. Whitehouse, and T. Kailath (Eds.), VLSI and Modern Signal Processing, Prentice-Hall. Englewood Cliffs, NJ (1985).
[4]  
Uhlman D., Computational Aspects of VLSI [Russian Translation]. Radio i Svyaz', Moscow (1990).
[5]  
Faddeev D.K., Faddeeva V.N., Computational Methods of Linear Algebra [in Russian]
[6]  
Vajtersic M., "Matrix Multiplication Algorithms for Matrices of Size N
[7]  
Bjorstad P., F. Manne, T. Sorevik et Al., "Efficient Matrix Multiplication on SIMD Computers," SIAM J. Matrix Anal. Appl.
[8]  
Bailey D.H., "Extra High Speed Matrix Multiplication on the Cray-2," SIAM J. Sci. Statist. Comput.
[9]  
Dafaux F., Kunt M., "Matrix Multiplication on An Associative String Processor," In: P. Quinten and Y. Robert (Eds.). Algorithm and Parallel VLSI Architecture, Elsevier, Amsterdam (1992), Pp.
[10]  
Kak S., "A Two-layered Mesh Array for Matrix Multiplication." Parallel Comput.
1234