Winograd矩阵乘法算法用于任意阶矩阵时的种新处理方法

20年 6月 04J n .20 u e, 0 4

应用数学与计算数学学报COM M . ON APP M A L. TH. AND C0M PUT

第 1卷第 1 8期Vl.8 0 1 No1 1 .

Wi ga n rd矩阵乘法算法用于任意阶矩阵时的 o一

种新处理方法

谭福平刘洪刚上海大学理学院数学系，上海， 046 203

摘要：矩阵乘法 Sr s t s n算法及其变形 Wi ga ae n rd算法用分而治之的方法把矩阵乘 o法时间复杂性由传统的 0 n ) (。改进到 0。 . ( g但是对于奇数阶矩阵， 2在划分子矩阵时， 要作特殊处理才能继续使用此算法.本文提出了一种非等阶“”十字架划分方法，可以最

少化填零，最大化性能，使得奇数阶矩阵乘法的时间复杂性更加接近偶数阶矩阵乘法的效果.计算实例显示该方法是有效的.

关键词：矩阵乘法， Wi g d算法 n r oa

1引言 .提高矩阵乘法的运算速度对缩短计算时间是十分重要的.因此有许多研究成果， 其中有著名 Sr s算法【及其改进算法. ts n ae ] Sr s算法把矩阵乘法的乘法运算次数由传统算法的 O(。减少到 O(l2) t sn ae n) ng . o Wi ga n r o d算法[是 Sr s算法的变形，需要 7 2] ts n ae次子矩阵乘法运算，但是只需要 1 5

次子矩阵加、减法运算.该算法是所有基于将矩阵 2分块的递归矩阵乘法中使用×2 乘法和加、减法的运算次数最少的.此算法适用于偶数阶矩阵乘法，对于奇数阶矩阵则需要某些处理，一般有如下三种处理方法：方法一是静态填充法，在计算之前对矩阵A B进行填 0,,使之以后的每次迭代计

算中都为偶数阶矩阵.但其代价是增加了内存消耗和无效的计算.例如当 n=2+1 时，要填充到 n d阶，其中 d为计算的迭代深度，这样会导致矩阵元素的成倍+2一1增加.

方法二是动态重叠法【此方法分解出来的子矩阵会有 1引，行或 1列重叠，在迭代

中同时计算重叠行或列，最后忽略其中一个.这也会增加额外的计算.而且程序复杂. 般用得多的方法是动态去边法【_ 4这种方法把矩阵划分出 4个】阶的子矩一

阵，对余下的边再单独计算.于是对边的计算不能再利用 Wi ga算法来减少计算 n rd o

量了.例如当 n 时，每次迭代都要进行去边处理 .这种方法比较节省内存，=2一1 但是

程序比静态填充法复杂.本文提出的非等阶“”十字架划分方法，可适用于奇数阶矩阵的乘法.本文 20年 4月 1日 04收到

谭福平，刘洪刚： Wi ga矩阵乘法算法用于任意阶矩阵时的一种新处理方法 n rd o

9 3

2“’架划分方法 .十’字上述三种处理方法都存在一定缺点，因此希望能找到一种既不额外增加无效计算量，又能充分利用 Wi ga算法来减少计算量的方法.首先我们采用类似动态去边 n rd o的策略，但是去掉的不是边，而是去掉 1“”个十字架，即矩阵中间的 1 1行列.其次

我们尽量把“字架的部分计算归并到子矩阵的计算中去十”“”十字架划分方法如下：设，,均为 n阶方阵，其中n=2 B m+1为奇数，对矩阵 B作如下分块：,,

A:

( );三= )薹 =\= ( ) )龛，1 B B l] 7毫 )1= A2 1+ A2 2T1= B1 B1 2~ 185 3 acl——at2

其中， i C Bj都是 m阶方阵， c biC是 m×1, ai c C,, i阶子矩阵， r b,r是 ai r c, i i1 m阶子矩阵.×

此时的算法为：= 1一 A1, 1=

S a= A1 1一 A2 1

:

A1 2一

B2 2一 T, 1at2— at1

乃=B2 1 2一B 2t 1 b 2一 b 1 r r r,

T 4: B2一 1

8 r4

t4 b 2— c c c—b l

Q1=X1×y1 1 1

/ l xB 1 c× r l x c+al , l 1+al bl l l c xb A A b m、 a1 1+a b1 a1 l m x m/ t xB 1 m x r t x c+a , b b

/ l 1, l 2 Q Q、

Q I Q/P=×T+a2 r, 3 1 1 c xtl

( 1 )

P=A1 xB 1 2 2 2, G=

(

):=× ( ( )尸=5×B2 6 4 2, =A 2 2×U 3= U2— 5 LP

P=×+83一r) 5 死 5×(b, 2

U=Ql+P=Al xBl+al r+P 1 l z l l c×bl 2u: Q1+Gl 2 1 lU=+P, 4 7 U=+P, 6 3

u=+P 5 3 u=+P 7 6

应用数学与计算数学学报

1 8卷

c C=Q 2 2 l+G1+A2

2 2×t4Cl

r2

4×B2 . 2 Ql 2+G2+8' 1/ mm=

Ql+A1×b2 2 2 c,

1=Q2+ n 2× B2 ." 1 1 r 1

Q2 r c 2+n2×b2

定理 1在上述条件下，Cl= Ul l,C Cl Cl, CI l"

U, 4C仇=

2= U, C1 U7 5 2=,m m, CC2 C 2, Cr2 r2

证明：. =

Sl— Al l= A2 1+ A2 2一 Al, l Al 2一 .= A1 2一 A2一 A2 1 2+ Al, lB2 2一 B2 1一= B2 2一 B1 2+ Bl, l = B2 1一 B2 2+ B1 2一 Bl, l

=

一==

=

Ql+P=Al×B l c×bl l 2 l l+al r+A1×B 1 2 2=Cl l, U+P=Ql+Gl+B 2 5 l lA l l+a l r+.×+83 r+.×乃+83 r l×B l c×bl C×tl C×b 2

=

=

=

Al B l c× r+(2+A2 l (2一B2 l l× l+al bl A 1 2一A 1B 2 1+B1 ) )+( l c×(2 r+(l—A 1×(2一B2 a—a2 b一b1 Al 2 c ) r ) ) B2 1 )+( l c×(b2 a—a2一r) c )

=

A l B l 2×( 2一B 2 l+a2 bl 2× l+A 2 B 2 1+B 1 c× r, )u+P=l+A 2 4 U+A 2 B 1 2+B 2 1 3 7 l 3 2×T= 3 2×( 2一B 2 1一B 1 )A2 l× Bl l+ A2 2× B2 1+ a 2×b l= l c r,

=

=

=

u+P=A 1 B l 2×(2一B2 l 3 3 2× l+A2 B 2 1+B 1 )+ a 2×b l+ Sl× c r + a 2×t l c r

=

A l l+A 2 B 2 1+B 1+a2 r 2×B l 2×( 2一B 2 l ) c×b l

+(2+A2(1一B1+a2 b2 r) A1 2 B2 l ) ) c×(一b1 r=

A2× Bl+ A2 B2+ a 2×b 2= C 2 l 2 2× 2 c r 2,+P 3+ P6

U1 U6+ P6= ==

Ql+G l l +a2 r+×B 2 l l+S× c×tl 2

=

A l B l c×bl A 1 2一A1 B2 1+B 1 l× l+al r+(2+A2 l (2一B2 l ) )+( l c) b一b1+(2+A2 B2 l a—a2×( 2 r) A 1 2 (1一B 1

c r ) )+a2 b一b1+(1一(2+A2 l ) B 2 c×( 2 r) A2 A 1 2一A1× 2 r )

=

Al l×Bl+ a l×b2+ A2× B2 l c r 1 2= C1, 2

Cl=

Ql+A 2 c=A l c+a1 m+A 2×b2 c, 2 1×b2 l×bl c×b 1 c=cl

1期

谭福平，刘洪刚： Wiord矩阵乘法算法用于任意阶矩阵时的一种新处理方法 nga

9 5

r=Q2+a2 2=a2 2=c1 l 1 r×B 1 r×B 1 r, mm=Q2+a2 e=- r×b1 m×b 2 t×b2 - I c+a a m+a2×b2 m, r c=c C=Q1+G 2 z×t4 2 2 1+A z c=

A n×b+al m+S×b+(8 ) m 2×(2 c) C, c c×b l 2 c - C×b A2 b一b1=C l 3 c 2

r=Q2+G 1 r×B 2 2 1 2+84 2 =al u+a×bl r×T+a×( t1+84 2 c2 r×B m r~al 2 m - r) r×B 2 r.

定理得证.从而 (式给出一种礼为奇数时计算 C=A×B的算法. 1 )

3计算结果与讨论 .我们用 C语言在 Wi o s 00M下实现了“字架划分方法、 n w 0T d 2十”动态去边法、和静态填充法 (直接计算礼+2~1 矩阵)算法.在配置为 P (4 )5M D A的计 4 .,6 S R M 2G 2

算机上计算，实际计算时间如下表：矩阵阶数 1 2迭代深度 …… 此处隐藏：4500字，全部文档内容请下载后查看。喜欢就下载吧 ……