《矩阵乘法综述》由会员分享，可在线阅读，更多相关《矩阵乘法综述（10页珍藏版）》请在金锄头文库上搜索。
1、矩阵乘法综述摘要：本文重点对不同矩阵乘法算法的所用时间进行了分析。在本论 文中，对Karatsuba和Strassen发明的方法进彳亍了分析和实现；对理论和实 际时间进行了计算。之后对Karatsuba和Strassen算法进行了合并，并结合 这两种算法设计了一种新算法，它可以被看作是一个降低吋间复杂度的方 法。关键词：时间复杂度，分治法1.介绍在各种数学方法和科学分支中，矩阵乘法均被广泛的应用。例如，在 生成如光通过浮动的水的这类具冇反射和失真效果的计算机图像中，矩阵 的数学方法被广泛的应用。除此之外，光科学利用这一种数学方法来解释 反射和折射。同样的，它也被用来计算电路的电气性能。在数学中
2、，矩阵 符号也已应用于图论，一个临近矩阵可以表示临域关系。概率论和数理统 计领域同样可以利用矩阵来表示。例如，一个概率向量可以表示一个试验 中不同结果的概率。除此之外，计算机利用随机矩阵来运行马尔可夫链, 以实现包括赌博、天气预报或量子力学的建模预测。矩阵数学通过提供一 个更紧凑的方式来处理组中的线性代数方程组的方式简化了线性代数。因 此，矩阵乘法被大量的应用于软件的实际施行当中。然而，矩阵乘法的软 件操作变得非常缓慢，成为整个系统运行的障碍。硬件乘法器可以被应用 于高速逻辑模块，但是其具冇昂贵且缺少延伸能力的缺点。在矩阵乘法中, 时间是一个重要的指标。木文的主要关注点是提出了一种矩阵乘法算法
3、可 以在实际运行中减少矩阵乘法的数量。本论文致力于提出一种利用分治法 来减小乘法运算数量的方法。这篇文章以以下的方式进行组织。第二部分包含了在矩阵乘法部分之 前工作的总结。第三部分描述了不同矩阵乘法的算法。第四部分展示了不同 的实验和他们为矩阵乘法做出的准备。第五部分分析了实验的结果。第六 部分总结全文并提出展望。2.前期工作大量的研究者对于矩阵乘法的吋间和内存损耗进行了大量的研究，为 了得到快速切不合并的方形矩阵的算法，前人进行了以下的研究工作。项不为零的情况下计算AB的问题。如果在相应计算Lingasfl,研究 在最多?？点中的每一项均为零，那么可以将这个矩阵视为平凡零矩阵。矩阵中 相乘计
4、算中数冃中的?？非零项。Lingas证明了这种的零可能来自于取消，所以它 可以远大于?？0.188）o对于?？ =?2针对快速方形矩阵乘法的简化可以将时间复杂 度缩减到0（?2?时间复杂度可以达到0 ?2.276 ,此结果由Coppersmith和Winograd 完成界定。n）o Lingas观察到通过一种列一行的组合算法，时间复杂度可以达到0(?2 + ?对于输入为稀疏矩阵的算法，Yuster和Zwick得出了一种根据矩阵划 分思想的快速算法。随后Amossen和pagh将这种算法延伸到了输出矩阵 也为稀疏矩阵的计算中。Iwen和Spencer提出了利用压缩感知，对于任何已知常数 >
5、O,计 算AB的算法，其时间复杂度为0(?2+?)o当AB每一行包含最多?0.29462 个非零值时，为特殊情况。Strassen利用分治的思想提出了一种算法，其计算速度高于标准的矩 阵相乘算法。在实际的大矩阵运算中具有优势，但是对于极端情况下的超 大矩阵情况其速度低于已知的最快算法。3不同种类的矩阵乘法算法3.1常规矩阵相乘算法相乘的前提是两个矩阵必须一个矩阵的行数需要与另一个矩阵的列 数相等。伪代码PROCEDURE Main()FOR i=0 to n-1FOR j=0 to n-1C(ij)=0Fork=0 to n-1C(ij)=C(ij)+A(iJ)*B(kj)END FOREND
6、 FOREND FOREND PROCEDRE3.2 Strassen 算法简单的分治法同样可以达到0(?3)的时间复杂度。在这种方法中，导 致高时间复杂度的主因为8个递归调用。Strassen的主要思想是将8个递 归调用缩减为7个。伪代码PROCEDURE Strassen(An,Bn，Cn,s)IF(n=l)C(0z0)=A(al,a2)*B(bl,b2)ELSE/Construct plFORi=0 to s/2FOR i=0 to s/2T(ij)二A(ij)+A(i+s/2)(j+s/2)END FOREND FORFOR 1=0 to s/2FOR i=0 ro s/2R(ij)二
7、 B(ij)+B(i+s/2)(j+s/2)END FOREND FORn=s/2StrassenCCR,pl,s/2)Strassen (T R, p7, s/2)/ Con struct c using the in termediate matrices cll = pl+ p4 - p5 + p7cl2 = p3+p5c2l = p2+p4c22 = pl+ p3 - p2 + p6END IFEND PROCEDURE3.3 Karatsuba 算法利用Karatsuba的发现可以用很少的操作完成大数乘法。伪代码：PROCEDURE Karatsuba(x, y)IF(x<10
8、| |y<10)RETURN x*yELSEm = (Iogl0(x)+1 >loglO(y)+l)/loglO(x)+l:loglO(y)+lm2 = m/2t = pow(10, m2)highl = x/t lowl = x % thigh2 = y/tIow2 = y % tzO = Karatsuba(lowl, Iow2)zl = Karatsuba(lowl+highl), (Iow2+high2)long longint z2 = Karatsuba(highl, high2)RETURN(z2*pow(10/(2*m2)+(zl-z2-z0)*pow(10/(m2
9、)+(z0)END IFEND PROCEDURE3.4 Proposed Method 提出的方法伪代码：PROCEDURE Strassen (A, al, a2, B, bl, b2, C, n) IF (n=l)C(0,0)= Karatsuba(A(al, a2), B(bl, b2)ELSEn 二 n/2/Same as Strassens algorithm afterwards END IFEND PROCEDUREPROCEDURE Karatsuba(x, y) IF(x&It; 10 | | y< 10)RETURN x*y/Same as Karatsuba al
10、gorithm afterwards END IFEND PROCEDURE4测试计算机配置1：处理器：Intel core i5 CPU 2.40GHz内存：8GB,系统类型：64位操作系统.计算机配置2:处理器：AMD C-60 APU with Radeon(tm)(2 CPUs), J.OGHz2048MB内存，系统类型:32位操作系统.建立试验：表1:分析64位和32位操作系统中矩阵的大小5.试验结果与分析表1展示了在64位和32位操作系统中测试用例的大小。表2展示了 被探究的大小的矩阵完成一般矩阵乘法所需的执行时间。结果表明，在64 位操作系统8X8矩阵和32位操作系统2X2的矩阵
11、之后的测试用例，执 行时间大约是以指数增长的。例如，完成16X16矩阵的矩阵乘法的时间 为0.047秒，而32X32的矩阵则需要0.17秒。表3展示了通过Strassen 的方法得出的相同类型的试验结果。在Strassen的方法得出的结果中可以 看出，在64位操作系统4位32X32矩阵和32位操作系统2X2的矩阵之 后的测试用例，系统执行时间大约是以指数增长的。表4展示了 Karatsuba 方法的执行时间。结果显示，在64位操作系统8X8矩阵和32位操作系 统2X2的矩阵之后的测试用例，执行时间大约是以指数增长的。表2: 一般矩阵乘法所需时间表5:木文提出方法矩阵乘法所需时间表5展示了本文提
12、出方法的执行时间。使用本文提出方法可以得出， 在64位操作系统32X32矩阵和32位操作系统8X8的矩阵Z后的测试 用例，执行时间大约是以指数增长的。图1展示了木文提到的四种方法的时间比较。比较中采用64位操作系统下的2X2, 4X4, 8X8,16X16, 32 X 32, 64X 64和128 X 128矩阵。柱状图展示了本文提出的 方法时间复杂度相较于其他方法更低。其中4X4的矩阵所需的时间几乎 为0。图1：本文所探究的四种方法的时间比较。比较用例的输入数据釆用64 位操作系统 4 位整型 2X2, 4X4, 8X8, 16X16,32X32, 64X64 和 128X128矩阵图2提供
13、了本文提到的四种方法的时间比较。比较中釆用64位操作系统下的2X2,4X4, 8X8,16X 16, 32X 32, 64X64和128X 128矩阵。柱状图展示了本文提出的 方法在一直到128X128矩阵测试用例的时间复杂度相较于其他方法更低。 其中4X4的矩阵所需的时间几乎为Oo图2:提供了本文所探究的四种方法的时间比较。比较用例的输入数据采用64位操作系统1位整型2 X乙4 X 4, 8 X & 16 X 16, 32 X 32, 64 X 64 和128X128矩阵图3展示了本文提到的四种方法的吋间比较。比较中采用32位操作 系统下的2X2,4X4, 8X8,16X16, 32X32,
14、 64X64和128X128矩阵。柱状图展示了本文提出的方法在一直到128X128矩阵测试用例的吋间复杂度相较于其他方法更低。 图3:本文所探究的四种方法的时间比较。比较用例的输入数据采用32 位操作系统 1 位整型 2X2, 4X4, 8X8, 16X16,32X32, 64X64 和 128 X128矩阵图4展示了本文提到的四种方法的时间比较。比较中采用32位操作 系统下的2X2,4X4, 8X8,16X16, 32X32, 64X64和128X128矩阵。柱状图展示了本文提出的方法在一直到128X128矩阵测试用例的吋间复杂度相较于其他方法更低。 图4:本文所探究的四种方法的时间比较。比
15、较用例的输入数据釆用32 位操作系统 4 位整型 2X2, 4X4, 8X8, 16X16,32X32, 64X64 和 128 X128矩阵6.结论在数值算法中，矩阵乘法是一个极其重要的中心步骤。我们研究出了一个新的方法用于分析计算矩阵乘法结构。我们得出的结论是，如果这个 方法是完美的，那么它将被用于不同的算法，以建立混合算法。在这篇文章中，我们主耍关注了以下几点：算法分析，首先我们运用64位操作系统进行试验。我们展示了对于 128X128矩阵，一般矩阵成比Strassen矩阵乘法花费的时间多，同时 Strassen矩阵乘法比Karatsuba矩阵乘法花费的时间多。第二，我们测试了 32位操作系统。我们展示了对于128X128矩阵, 一般矩阵成比Strassen矩阵乘法花费的时间多，同时Strassen矩阵乘法比 Karatsuba矩阵乘法花费的时间多。最后，我们测试了本文提出方法。对于大型矩阵Strassen算法将递归 调用的次数从8次缩减到了 7次。Karatsuba算法用于位较长的数据，所以它适合减少操作次数。我们的方法将
