矩阵乘法综述.doc

《矩阵乘法综述.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、矩阵乘法综述摘要：本文重点对不同矩阵乘法算法的所用时间进行了分析。在本论文中，对Karatsuba和Strassen发明的方法进彳亍了分析和实现；对理论和实际时间进行了计算。之后对Karatsuba和Strassen算法进行了合并，并结合这两种算法设计了一种新算法，它可以被看作是一个降低吋间复杂度的方法。关键词：时间复杂度，分治法1.介绍在各种数学方法和科学分支屮，矩阵乘法均被广泛的应用。例如，在生成如光通过浮动的水的这类具冇反射和失真效果的计算机图像中，矩阵的数学方法被广泛的应用。除此之外，光科学利用这一种数学方法来解

2、释反射和折射。同样的，它也被用来计算电路的电气性能。在数学中，矩阵符号也已应用于图论，一个临近矩阵可以表示临域关系。概率论和数理统计领域同样可以利用矩阵来表示。例如，一个概率向量可以表示一个试验中不同结果的概率。除此之外，计算机利用随机矩阵来运行马尔可夫链,以实现包括赌博、天气预报或量子力学的建模预测。矩阵数学通过提供一个更紧凑的方式来处理组中的线性代数方程组的方式简化了线性代数。因此，矩阵乘法被大量的应用于软件的实际施行当中。然而，矩阵乘法的软件操作变得非常缓慢，成为整个系统运行的障碍。硬件乘法器可以被应用于高速逻辑模

3、块，但是其具冇昂贵且缺少延伸能力的缺点。在矩阵乘法中,时间是一个重要的指标。木文的主要关注点是提出了一种矩阵乘法算法可以在实际运行中减少矩阵乘法的数量。本论文致力于提出一种利用分治法来减小乘法运算数量的方法。这篇文章以以下的方式进行组织。第二部分包含了在矩阵乘法部分之前工作的总结。第三部分描述了不同矩阵乘法的算法。第四部分展示了不同的实验和他们为矩阵乘法做出的准备。第五部分分析了实验的结果。第六部分总结全文并提出展望。2.前期工作大量的研究者对于矩阵乘法的吋间和内存损耗进行了大量的研究，为了得到快速切不合并的方形矩阵的算

4、法，前人进行了以下的研究工作。项不为零的情况下计算AB的问题。如果在相应计算Lingasfl],研究在最多?？点中的每一项均为零，那么可以将这个矩阵视为平凡零矩阵。矩阵中相乘计算中数冃中的?？非零项。Lingas证明了这种的零可能来自于取消，所以它可以远大于?？0.188）o对于?？=??2针对快速方形矩阵乘法的简化可以将时间复杂度缩减到0（??2??时间复杂度可以达到0??2.276,此结果由Coppersmith和Winograd完成界定。n）oLingas观察到通过一种列一行的组合算法，时间复杂度可以达到0(??2

5、+??对于输入为稀疏矩阵的算法，Yuster和Zwick得出了一种根据矩阵划分思想的快速算法。随后Amossen和pagh将这种算法延伸到了输出矩阵也为稀疏矩阵的计算中。Iwen和Spencer提出了利用压缩感知，对于任何已知常数£>O,计算AB的算法，其时间复杂度为0(??2+??)o当AB每一行包含最多??0.29462个非零值时，为特殊情况。Strassen利用分治的思想提出了一种算法，其计算速度高于标准的矩阵相乘算法。在实际的大矩阵运算中具有优势，但是对于极端情况下的超大矩阵情况其速度低于已知的最快算法。3

6、•不同种类的矩阵乘法算法3.1常规矩阵相乘算法相乘的前提是两个矩阵必须一个矩阵的行数需要与另一个矩阵的列数相等。伪代码PROCEDUREMain()FORi=0ton-1FORj=0ton-1C(ij)=0Fork=0ton-1C(ij)=C(ij)+A(iJ)*B(kj)ENDFORENDFORENDFORENDPROCEDRE3.2Strassen算法简单的分治法同样可以达到0(??3)的时间复杂度。在这种方法中，导致高时间复杂度的主因为8个递归调用。Strassen的主要思想是将8个递归调用缩减为7个。伪代码PRO

7、CEDUREStrassen(A[n],B[n]，C[][n],s)IF(n==l)C(0z0)=A(al,a2)*B(bl,b2)ELSE//ConstructplFORi=0tos/2FORi=0tos/2T(i’j)二A(ij)+A(i+s/2)(j+s/2)ENDFORENDFORFOR1=0tos/2FORi=0ros/2R(ij)二B(ij)+B(i+s/2)(j+s/2)ENDFORENDFORn=s/2StrassenCCR,pl,s/2)Strassen(TR,p7,s/2)//Constructc[]

8、[]usingtheintermediatematricesc[l][l]=pl+p4-p5+p7c[l][2]=p3+p5c[2][l]=p2+p4c[2][2]=pl+p3-p2+p6ENDIFENDPROCEDURE3.2Karatsuba算法利用Karatsuba的发现可以用很少的操作完成大数乘法。伪代码：P