矩阵乘法的一个最佳算法_蒋昌俊.pdf

《矩阵乘法的一个最佳算法_蒋昌俊.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、矩*阵乘法的一个最佳算法蒋昌俊吴哲辉,(山东矿业学院泰安)关、、、镇词算法矩阵乘法运算次数阶一、引言,.矩阵乘法是线性代数中常见的问题之一许多数值计算问题都包含着矩阵乘法的计算因,,.此降低矩阵乘法算法的时间复杂度问题多年来一直引起算法研究者们的高度重视,ssen。,〔1],1969年star提出了一个时间复杂度为O(矿“)的矩阵乘法算法第一次突破了,“”.,0(矿)的界限被誉为在代数复杂性理论中最激动人心的结果切以后又出现了一系列新的矩阵乘法算法3t一,].据了解,迄今最好的算法是1981年由Pan提出的

2、,其时间复杂度为`·。,钓呜`IJ.O()矩阵乘法的算法最少需要多少时间量呢Baes,”,?指出对于两个阶方阵的乘法来说记阶的乘除法运算是必须的.但他认为,达到这个下界的算法大概是不存在的`Js...,对”本文给出矩阵乘法的一个算法该算法适用于有理数矩阵于两个阶方阵相乘即,,。,,,.,。l,,,。,()问题只需要矿阶的运算次数对于行,列矩阵和行列矩阵的乘法即(,,.,)l问题运算次数的阶为0(。(+l))这样本文提出的算法其运算次数的阶已达到了理论下界。二、非负整数矩阵乘法的算法已知两个非负整数矩阵a`.

3、。`,,A~[]丑~b。,lox,,I求矩阵c`,.:t,C~I]使得c;,a`*.,,,,,,,一,。,1一12;,一l2习……,.对于这个问题可以通过下面的算法步骤来实现1:第步计算aaxa`,,,,。,,,,,~m毛}i〔毛l2…}及〔毛12…。}}b~max。,`1,2,,m,〔l,,,l,{b!友{…}i毛2…玉}本文1988年`月22日收到.1988年9月19日收到修改稿.国家自然科学苍全资助项目.第4期科学通报xm一卜a,bl~nax,一巨。y~mb十l:,,`,,r第2步对互一12二。用Ho

4、rne方法计算aa`*x`,艺一一.b,一,。,y一`习第3步:计算。一a声。习4:.,,,_:,,`r:,r:,价一:,:第步做除法依次求商峨姚…dl和余数…使满足cy十r:,0r:y一dl镇<一,d,y+r,,0r,y2,3,,价一成

5、`,0ri`x,,3,,。2灸川一乏+镇

6、数矩阵的(。O问题本节给出的算法其运算次数的阶为O(。(+止)).三、算法的正确性证明,.i,二,,在本节中我们证明上节给出的算法的正确性注意自.和久都是非负整数于是,。。和..b等都是正整数我们有。a。.一习,习一.·科·;.:`介,,`一`一ù喀)(客)学通报1989年`。,`’a一`*·一`b艺习艺广户`l诊吕1介=11,2,,,,l,2,,l,由于Vi〔{…}Vj〔{…}都有a`**,ma,<二,艺,蕊l,2,,l,且Vj〔{…}都有a、*b*,x`,max`,,艺习一成b一<呼=1介=1,`y十r

7、:所以由~风可得r:a`。*,:`,~习艺吞一成留1之=1a;。b,x`一`,一,一,·`~*,艺习习户.t`一1介一1进一步可以得到r,a`。.。,一,+:,:`,2,3,,一习习b一j~…或一t之一1于是c,a;。.,x`,l,2,,一,一i一…习习同样理由,我们可以得到r,;a《`+:》。。,,i~l,2,,。;1,2,,~卜b…j一…习所以c`,。;。,,,,,,,,,,.一习。,一12…;s一2…2、四讨论.,m`l,,n,,,,,1在第二节提出的算法中令~便可用于两个阶方阵的乘法即(叮.这时,问

8、题算法涉及的各种运算的次数为,,,比较运算2一2次,乘法运算2矿十2次,加法运算2矿一,+1次1.除法运算衬一次,n,n,,.因此对于非负整数矩阵的(的问题算法所需要的运算次数的阶为0(矿).a,,b,,.A、B2不难把算法推广到和为任意整数的情况这时可以把两个矩阵写成A~A+汉-一a,x。a.x~[人]一[反1一B~B+B-一,、,.二,,~[b去]一[好]第今期科学通报2,李,,。其中峨崛鱿和如都是非负整数而