New fast hybrid matrix multiplication algorithms
- PDF / 99,194 Bytes
- 8 Pages / 595.276 x 793.701 pts Page_size
- 72 Downloads / 234 Views
NEW FAST HYBRID MATRIX MULTIPLICATION ALGORITHMS UDC 681.322.012
L. D. Jelfimova
Abstract. New hybrid algorithms are proposed for multiplying ( n ´ n ) matrices. They are based on Laderman’s algorithm for multiplying ( 3´ 3)-matrices. As compared with well-known hybrid matrix multiplication algorithms, the new algorithms are characterized by the minimum computational complexity. The multiplicative, additive, and overall complexities of the algorithms are estimated. Keywords: linear algebra, hybrid matrix multiplication algorithm, Laderman’s algorithm for multiplying ( 3´ 3)-matrices. At the present time, fast hybrid algorithms are developed that multiply ( n ´ n ) matrices [1, 2] and are constructed with the use of Strassen algorithms for multiplying ( 2´ 2) matrices [3], the Winograd–Strassen algorithm for multiplying ( 2´ 2) matrices [4], and the Winograd algorithm [5]. In the mentioned hybrid algorithms, in contrast to well-known algorithms widely used in practice, for example, [3–5], the simultaneous minimization of multiplicative and additive complexities is first achieved, which determines their least total computational complexity. The objective of the present work is the optimization of the computational complexity of hybrid matrix multiplication algorithms. This article considers new fast hybrid algorithms for multiplying ( n ´ n ) matrices that are constructed with the use of Laderman’s algorithms for multiplying ( 3´ 3) matrices [6] and the Winograd algorithm [5], which leads to the minimization of the multiplicative, additive, and total complexities in comparison with well-known hybrid algorithms. FAST HYBRID ALGORITHM MULTIPLYING MATRICES OF ORDER n = 3 m ( m > 1) An algorithm for multiplying two square matrices A = {a ij }and B = {bij }of the mentioned order n is constructed using of the bottom-up scheme of computations [7] in which Laderman’s algorithm is used as its internal algorithm for multiplying ( 3´ 3) matrices [6]. In this case, the properties of commutativity and associativity of the addition operation are involved. The computing core of the proposed algorithm consists of the following regular computations: m
m
s1ij = å a1ik × b3 k -1, 3 j -1 , sij2
k =1 m
=å
k =1 m
2 a ik
×
4 × b 4kj , sij5 = å a ik
b1kj ,
sij6
sij3 = å a 3 i -1, 3 k -1 × b 2kj , sij4
k =1 m
=å
k =1
3 a ik
×
k =1 m
= å a 3 i - 2 ,3 k - 2 × b3 k - 2 ,3 j - 2 , k =1 m
5 sij7 = å a ik × b 5kj ,
b 3kj ,
sij8
k =1 m
6 = å a ik × b 6kj , k =1
V. M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine, [email protected]. Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 59–67, November–December 2011. Original article submitted March 23, 2010. 1060-0396/11/4706-0881
©
2011 Springer Science+Business Media, Inc.
881
m
m
7 sij9 = å a ik × b 7kj ,
12 12 s16 ij = å a ik × b kj ,
8 s10 ij = å a ik × b 3 k -1, 3 j ,
13 13 s17 ij = å a ik × b kj ,
k =1 m
s11 ij
k =1 m
=å
k =1 m
a 3 i ,3 k -1 × b 8kj ,
9 9 s12 ij = å a ik × b kj ,
s13 ij
k =1 m
=å
k
Data Loading...
