矩阵乘法综述
摘要：本文重点对不同矩阵乘法算法的所用时间进行了分析。在本论文中，对Karatsuba和Strassen发明的方法进行了分析和实现；对理论和实际时间进行了计算。之后对Karatsuba和Strassen算法进行了合并，并结合这两种算法设计了一种新算法，它可以被看作是一个降低时间复杂度的方法。
关键词：时间复杂度，分治法
1. 介绍
在各种数学方法和科学分支中，矩阵乘法均被广泛的应用。例如，在生成如光通过浮动的水的这类具有反射和失真效果的计算机图像中，矩阵的数学方法被广泛的应用。除此之外，光科学利用这一种数学方法来解释反射和折射。同样的，它也被用来计算电路的电气性能。在数学中，矩阵符号也已应用于图论，一个临近矩阵可以表示临域关系。概率论和数理统计领域同样可以利用矩阵来表示。例如，一个概率向量可以表示一个试验中不同结果的概率。除此之外，计算机利用随机矩阵来运行马尔可夫链，以实现包括赌博、天气预报或量子力学的建模预测。矩阵数学通过提供一个更紧凑的方式来处理组中的线性代数方程组的方式简化了线性代数。因此，矩阵乘法被大量的应用于软件的实际施行当中。然而，矩阵乘法的软件操作变得非常缓慢，成为整个系统运行的障碍。硬件乘法器可以被应用于高速逻辑模块，但是其具有昂贵且缺少延伸能力的缺点。在矩阵乘法中，时间是一个重要的指标。本文的主要关注点是提出了一种矩阵乘法算法可以在实际运行中减少矩阵乘法的数量。本论文致力于提出一种利用分治法来减小乘法运算数量的方法。
这篇文章以以下的方式进行组织。第二部分包含了在矩阵乘法部分之前工作
的总结。第三部分描述了不同矩阵乘法的算法。第四部分展示了不同的实验和他们为矩阵乘法做出的准备。第五部分分析了实验的结果。第六部分总结全文并提出展望。
2.前期工作
大量的研究者对于矩阵乘法的时间和内存损耗进行了大量的研究，为了得到快速切不合并的方形矩阵的算法，前人进行了以下的研究工作。
项不为零的情况下计算AB的问题。如果在相应计算Lingas[1]，研究在最多??
点中的每一项均为零，那么可以将这个矩阵视为平凡零矩阵。矩阵中相乘计算中 数目中的?? 非零项。Lingas证明了这种的零可能来自于取消，所以它可以远大于??
0.188)。对于?? ＝??2针对快速方形矩阵乘法的简化可以将时间复杂度缩减到O(??2??
时间复杂度可以达到O ??2.276 ，此结果由Coppersmith和Winograd完成界定。 n)。 Lingas观察到通过一种列－行的组合算法，时间复杂度可以达到O(??2＋??
对于输入为稀疏矩阵的算法，Yuster和Zwick得出了一种根据矩阵划分思想的快速算法。随后Amossen和pagh将这种算法延伸到了输出矩阵也为稀疏矩阵的计算中。
Iwen和Spencer提出了利用压缩感知，对于任何已知常数ε>0，计算AB的算法，其时间复杂度为O(??2+??)。当AB每一行包含最多??0.29462个非零值时，为特殊情况。
Strassen利用分治的思想提出了一种算法，其计算速度高于标准的矩阵相乘算法。在实际的大矩阵运算中具有优势，但是对于极端情况下的超大矩阵情况其速度低于已知的最快算法。
3.不同种类的矩阵乘法算法
3.1 常规矩阵相乘算法
相乘的前提是两个矩阵必须一个矩阵的行数需要与另一个矩阵的列数相等。 伪代码
PROCEDURE Main() FOR i=0 to n-1 FOR j=0 to n-1 C(i,j)=0 Fork=0 to n-1 C(i,j)=C(i,j)+A(i,j)*B(k,j) END FOR END FOR END FOR END PROCEDRE 3.2 Strassen 算法
简单的分治法同样可以达到O(??3)的时间复杂度。在这种方法中，导致高时间复杂度的主因为8个递归调用。Strassen的主要思想是将8个递归调用缩减为7个。
伪代码
PROCEDURE Strassen(A[n],B[n],C[][n],s) IF(n==1)
C(0,0)=A(a1,a2)*B(b1,b2) ELSE
//Construct p1
FORi=0 to s/2 FOR i=0 to s/2
T(i,j)=A(i,j)+A(i+s/2)(j+s/2) END FOR END FOR FOR I=0 to s/2 FOR i=0 ro s/2
R(i,j)=B(i,j)+B(i+s/2)(j+s/2) END FOR END FOR n=s/2
Strassen(T,R,p1,s/2) . . .
Strassen (T, R, p7, s/2)
// Construct c[][] using the intermediate matrices c[1][1] = p1+ p4 - p5 + p7 c[1][2] = p3+p5 c[2][1] = p2+p4
c[2][2] = p1+ p3 – p2 + p6 END IF
END PROCEDURE 3.3 Karatsuba算法
利用Karatsuba的发现可以用很少的操作完成大数乘法。
伪代码：
PROCEDURE Karatsuba(x, y) IF(x<10||y<10) RETURN x*y ELSE
m = (log10(x)+1>log10(y)+1)/log10(x)+1:log10(y)+1 m2 = m/2 t = pow(10, m2) high1 = x / t low1 = x % t high2 = y / t low2 = y % t
z0 = Karatsuba(low1, low2)
z1 = Karatsuba((low1+high1), (low2+high2)) long longint z2 = Karatsuba(high1, high2) RETURN
(z2*pow(10,(2*m2)))+((z1-z2-z0)*pow(10,(m2)))+(z0) END IF
END PROCEDURE
3.4 Proposed Method 提出的方法
矩阵乘法综述
