下载文档原格式
一、介绍三阶Strassen矩阵乘法是一种优化的矩阵乘法算法，它可以在一定程度上减少乘法的次数，提高矩阵相乘的效率。
在本文中，我们将介绍三阶Strassen矩阵乘法的原理和实现方法，并使用Python语言进行编写和演示。
二、原理传统的矩阵乘法需要进行n^3次乘法操作，其中n为矩阵的维度。
而Strassen矩阵乘法可以将这一次数减少到n^(log2 7) ≈ n^2.81 次。
其基本原理是将两个矩阵分块，并通过一定的运算得到所需的乘积。
具体而言，设A、B为两个3阶矩阵：A = [[a1, a2, a3],[a4, a5, a6],[a7, a8, a9]]B = [[b1, b2, b3],[b4, b5, b6],[b7, b8, b9]]可以将矩阵A、B分块为四个2阶子矩阵：A11 = [[a1, a2],[a4, a5]],A12 = [[a3],[a6]],A21 = [[a7, a8]],A22 = [[a9]]B11 = [[b1, b2],[b4, b5]],B12 = [[b3],[b6]],B21 = [[b7, b8]],B22 = [[b9]]则矩阵乘积C可以表示为：C = [[c1, c2, c3],[c4, c5, c6],[c7, c8, c9]]其中，c1 = p1 + p4 - p5 + p7,c2 = p3 + p5,c3 = p2 + p4,c4 = p1 + p3 - p2 + p6,c5 = p1 + p4,c6 = p2 - p1 + p3 + p6,c7 = p3 - p5 + p7,c8 = p4 + p5,c9 = p1 - p3 + p2 + p7这里p1至p7的计算分别为：p1 = a1 * (b2 - b4),p2 = (a1 + a2) * b4,p3 = (a3 + a2) * b1,p4 = a2 * (b3 - b1),p5 = (a1 + a3) * b4,p6 = (a4 + a5) * b6,p7 = (a6 - a4) * (b5 + b6)三、Python实现接下来，我们将使用Python语言来实现三阶Strassen矩阵乘法。
strassen算法实现矩阵相乘，当输⼊为偶数，奇数，任意数的实现1.使⽤随机数⽣成两个矩阵，并实现输出⽅法。
public void makeMatrix(int[][] matrixA, int[][] matrixB, int length){ //⽣成矩阵Random random=new Random();for(int i=0;i<length;i++){for (int j=0;j<length;j++){matrixA[i][j]=random.nextInt(5);matrixB[i][j]=random.nextInt(5);}}}public void printMatrix(int[][] matrixA,int length){ //输出for(int i=0;i<length;i++){for (int j=0;j<length;j++){System.out.print(matrixA[i][j]+" ");if((j+1)%length==0)System.out.println();}}}2.使⽤Strassen算法需要涉及到矩阵的加减。
所以先准备好⽅法。
public void add(int[][] matrixA,int[][] matrixB,int[][] matrixC,int length){for(int i=0;i<length;i++) {for (int j = 0; j < length; j++) {matrixC[i][j]= matrixA[i][j]+ matrixB[i][j];}}}public void jian(int[][] matrixA,int[][] matrixB,int[][] matrixC,int length){for(int i=0;i<length;i++) {for (int j = 0; j < length; j++) {matrixC[i][j]= matrixA[i][j] - matrixB[i][j];}}}public void cheng(int[][] matrixA,int[][] matrixB,int[][] matrixC,int length){for(int i=0;i<length;i++) {for (int j = 0; j < length; j++) {matrixC[i][j]=0;for(int k=0;k<length;k++){matrixC[i][j] = matrixC[i][j]+ matrixA[i][k] * matrixB[k][j];}}}}3.当矩阵的阶数为 2的k次⽅//阶数为 2 的 K 次⽅的时候 Strassen算法public void strassen(int[][] matrixA,int[][] matrixB,int[][] matrixC,int N){int newsize=N/2;if(N==2){cheng(matrixA,matrixB,matrixC,N);return;}int[][] A11=new int[newsize][newsize];int[][] A12=new int[newsize][newsize];int[][] A21=new int[newsize][newsize];int[][] A22=new int[newsize][newsize];int[][] B11=new int[newsize][newsize];int[][] B12=new int[newsize][newsize];int[][] B21=new int[newsize][newsize];int[][] B22=new int[newsize][newsize];int[][] C11=new int[newsize][newsize];int[][] C12=new int[newsize][newsize];int[][] C21=new int[newsize][newsize];int[][] C22=new int[newsize][newsize];int[][] M1=new int[newsize][newsize];int[][] M2=new int[newsize][newsize];int[][] M3=new int[newsize][newsize];int[][] M4=new int[newsize][newsize];int[][] M5=new int[newsize][newsize];int[][] M6=new int[newsize][newsize];int[][] M7=new int[newsize][newsize];int[][] Aresult=new int[newsize][newsize];int[][] Bresult=new int[newsize][newsize];//分别给 A11 A12 A21 A22赋值for(int i=0;i<N/2;i++){for(int j=0;j<N/2;j++){A11[i][j]=matrixA[i][j];A12[i][j]=matrixA[i][j+N/2];A21[i][j]=matrixA[i+N/2][j];A22[i][j]=matrixA[i+N/2][j+N/2];B11[i][j]=matrixB[i][j];B12[i][j]=matrixB[i][j+N/2];B21[i][j]=matrixB[i+N/2][j];B22[i][j]=matrixB[i+N/2][j+N/2];}}//计算M1 到M7add(A11,A22,Aresult,newsize);add(B11,B22,Bresult,newsize);strassen(Aresult,Bresult,M1,newsize);//M2add(A21,A22,Aresult,newsize);strassen(Aresult,B11,M2,newsize);//M3jian(B12,B22,Bresult,newsize);strassen(A11,Bresult,M3,newsize);//M4jian(B21,B11,Bresult,newsize);strassen(A22,Bresult,M4,newsize);//M5add(A11,A12,Aresult,newsize);strassen(Aresult,B22,M5,newsize);//M6jian(A21,A11,Aresult,newsize);add(B11,B12,Bresult,newsize);strassen(Aresult,Bresult,M6,newsize);//M7jian(A12,A22,Aresult,newsize);add(B21,B22,Bresult,newsize);strassen(Aresult,Bresult,M7,newsize);//C11add(M1,M4,Aresult,newsize);jian(M5,M7,Bresult,newsize);jian(Aresult,Bresult,C11,newsize);//C12add(M3,M5,C12,newsize);//C21add(M2,M4,C21,newsize);//C22add(M1,M3,Aresult,newsize);jian(M2,M6,Bresult,newsize);jian(Aresult,Bresult,C22,newsize);//把C的值填充for(int i=0;i<N/2;i++){for(int j=0;j<N/2;j++){matrixC[i][j]=C11[i][j];matrixC[i][j+N/2]=C12[i][j];matrixC[i+N/2][j]=C21[i][j];matrixC[i+N/2][j+N/2]=C22[i][j];}}}4.当阶数为偶数的时候假设阶数为 n ，所以 n=m*2^k 。
4-2.矩阵乘法的Strassen 算法详解题⽬描述请编程实现矩阵乘法，并考虑当矩阵规模较⼤时的优化⽅法。
思路分析根据wikipedia 上的介绍：两个矩阵的乘法仅当第⼀个矩阵B 的列数和另⼀个矩阵A 的⾏数相等时才能定义。
如A 是m×n 矩阵和B 是n×p 矩阵，它们的乘积AB 是⼀个m×p 矩阵，它的⼀个元素其中 1 ≤ i ≤ m,1 ≤ j ≤ p 。
值得⼀提的是，矩阵乘法满⾜结合律和分配率，但并不满⾜交换律，如下图所⽰的这个例⼦，两个矩阵交换相乘后，结果变了：下⾯咱们来具体解决这个矩阵相乘的问题。
解法⼀、暴⼒解法其实，通过前⾯的分析，我们已经很明显的看出，两个具有相同维数的矩阵相乘，其复杂度为O （n^3），参考代码如下：解法⼆、Strassen 算法在解法⼀中，我们⽤了3个for 循环搞定矩阵乘法，但当两个矩阵的维度变得很⼤时，O （n^3）的时间复杂度将会变得很⼤，于是，我们需要找到⼀种更优的解法。
⼀般说来，当数据量⼀⼤时，我们往往会把⼤的数据分割成⼩的数据，各个分别处理。
遵此思路，如果丢给我们⼀个很⼤的两个矩阵呢，是否可以考虑分治的⽅法循序渐进处理各个⼩矩阵的相乘，因为我们知道⼀个矩阵是可以分成更多⼩的矩阵的。
如下图，当给定⼀个两个⼆维矩阵A B 时：这两个矩阵A B 相乘时，我们发现在相乘的过程中，有8次乘法运算，4次加法运算：矩阵乘法的复杂度主要就是体现在相乘上，⽽多⼀两次的加法并不会让复杂度上升太多。
故此，我们思考，是否可以让矩阵乘法的运算过程中乘法的运算次数减少，从⽽达到降低矩阵乘法的复杂度呢？答案是肯定的。
1969年，德国的⼀位数学家Strassen 证明O （N^3）的解法并不是矩阵乘法的最优算法，他做了⼀系列⼯作使得最终的时间复杂度降低到了O(n^2.80)。
他是怎么做到的呢？还是⽤上⽂A B 两个矩阵相乘的例⼦，他定义了7个变量：如此，Strassen算法的流程如下：；表⾯上看，Strassen 算法仅仅⽐通⽤矩阵相乘算法好⼀点，因为通⽤矩阵相乘算法时间复杂度是，⽽Strassen 算法复杂度只是。
大整数乘法和strassen矩阵乘法大整数乘法和Strassen矩阵乘法是计算机科学中两个非常重要的算法。
在我们的日常生活中，我们经常需要比较大的数字，例如，考虑到我们的身份证号码或者信用卡号码中的位数就很大。
对于这些大数字的计算，实现乘法运算的标准方法导致了效率低下。
这就要依靠大整数乘法的算法来完成。
同样的，矩阵乘法是人们常用的数据分析和机器学习等领域的基础算法之一，Strassen矩阵乘法则是一种可以在更短时间内完成的矩阵乘法算法。
在接下来的文档中，我将详细讲解大整数乘法和Strassen矩阵乘法。
一、大整数乘法大整数乘法是指对于两个比较大的数字，我们如何快速且准确的计算它们的乘积。
在介绍大整数乘法的算法之前，先考虑乘法的基本方法。
在日常乘法中，乘法运算是通过对乘数和被乘数的每一位进行相乘并将结果相加而得到的。
例如，计算96 ×57，我们将乘数96 和被乘数57 的每一位相乘，去得到：``` 96 × 57 ------- 672 (6 x 7) 480 (9 x 5) <<1> +57600 (9 x 5 << 2> ) ------- 5472 ```我们在这个过程中需要进行至Less 2次的延时计算，6次的加法，这在数字比较小时的时候是可行的。
但是，如果数字的位数变得更大，传统的乘法算法就会非常不切实际，执行效率非常慢。
在大整数乘法中，我们需要考虑实现优化的算法以处理大量位数的数字，其中最流行和普遍使用的算法有以下两种：1.传统的分治算法2.卡拉茨巴乘法1.传统的分治算法传统的分治算法涉及将大的数字分解为更小的数字部分进行乘法运算，并且在计算此过程之间能够快速地进行组合。
该算法需要依靠递归算法的思想，在整个运算过程中采用分治策略。
如果给定两个长度为n的数字，我们可以将这些数字分成两个较小，长度为 n/2 的数字，然后将它们相乘。
在递归调用中，相同的方法会被重复递归调用。
用Strassen算法实现矩阵乘法#coding=utf-8'''第10题：用Strassen的思想实现两个n×n矩阵的乘法'''import mathfrom numpy import *#check函数用来检查num是否是2的整数次幂def check(num):i = 1;while (True):if (i > num):return Falseif (i == num):return Truei = i * 2#Multiply函数即为实现方法def Matrix_Multiply(A,B):#由于本题只考虑两个n×n矩阵的乘法，且n为2的整数次幂的情况，故做一些判断去掉不合法的输入if A.shape!=B.shape:print '本题只考虑两个n×n矩阵的乘法，且n为2的整数次幂的情况'return Noneif A.shape[0]!=A.shape[1]:print '本题只考虑两个n×n矩阵的乘法，且n为2的整数次幂的情况'return Noneif check(A.shape[0])==False:print '本题只考虑两个n×n矩阵的乘法，且n为2的整数次幂的情况'return Nonen = A.shape[0]result = zeros([n,n])if(n == 2):#最基本的情况A11=A[0,0]A12=A[0,1]A21=A[1,0]A22=A[1,1]B11=B[0,0]B12=B[0,1]B21=B[1,0]B22=B[1,1]P1 = A11*(B12-B22)P2 = (A11+A12)*B22P3 = (A21+A22)*B11P4 = A22*(B21-B11)P5 = (A11+A22)*(B11+B22)P6 = (A12-A22)*(B21+B22)P7 = (A11-A21)*(B11+B12)else:#输入复杂的情况就采取divide-and-conquer策略A11=A[:n/2,:n/2]A12=A[:n/2,n/2:]A21=A[n/2:,:n/2]A22=A[n/2:,n/2:]B11=B[:n/2,:n/2]B12=B[:n/2,n/2:]B21=B[n/2:,:n/2]B22=B[n/2:,n/2:]#combineP1 = Matrix_Multiply(A11,B12-B22)P2 = Matrix_Multiply(A11+A12,B22)P3 = Matrix_Multiply(A21+A22,B11)P4 = Matrix_Multiply(A22,B21-B11)P5 = Matrix_Multiply(A11+A22,B11+B22)P6 = Matrix_Multiply(A12-A22,B21+B22)P7 = Matrix_Multiply(A11-A21,B11+B12)result[:n/2,:n/2] = P4 + P5 + P6 - P2 #C11result[:n/2,n/2:] = P1 + P2 #C12result[n/2:,:n/2] = P3 + P4 #C21result[n/2:,n/2:] = P1 + P5 - P3 - P7 #C22return result'''demo'''print '矩阵A='a = array([[1.1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]) print aprint '计算A×A'print ''result = Matrix_Multiply(a,a)print '本题所实现的方法结果是：' print resultprint '正确结果应为：'print dot(a,a)。
实验2 Strassen矩阵乘法一、 实验目的1.理解Strassen矩阵乘法的分治思想Strassen矩阵乘法的分治法设计模式是：半分+混合2.改进Strassen矩阵乘法对内存的需求若按Strassen矩阵乘法的直接表述实现，则空间复杂度将是O(3n2)，本实验将试图改进这个方面。
3.Strassen矩阵乘法的性能问题改进Strassen矩阵乘法的内存需求，并不一定能改进Strassen矩阵乘法的效率，本实验将试图测试一些较大规模(n>=1024)的n阶方阵的Strassen矩阵乘，探讨其效率问题。
二、 实验环境C/C++编程环境或任何编程语言环境三、 实验内容1． Strassen矩阵乘法描述尽管Strassen矩阵乘法的实用价值在当今的多核计算环境下可能不是那么显著，但其理论价值仍值得我们研究。
Strassen矩阵乘法体现了一类重要的分治算法设计模式，即半分+混合，同样具有这种算法设计模式的是FFT(Fast Fourier Transform)-“由于FFT这个卓越算法在实践上的重要意义，有些人把它看作是有史以来人们发明的最重要的算法之一。
”[1]Strassen 矩阵乘法的基本思想，可由下述矩阵乘法概括：输入：两个n=2k 维方阵A 和B （若A 和B 的维度不是2k ，则通过增加元素为0的行和列，以使A 和B 均为2k 维的方阵）输出：n 维方阵C(1)1+41+443-11+24134.12-43+4113.123-11+224.3424.1314.11.2412.4-4344+=A B =A B =A B =A B =A B M =A B M =A M M B M M M(2)为方便表示，这里采用与书本不同的下标表示法，如对于1个n/2维矩阵14.14M ，下标14.14表示其由两个矩阵A 1+4和B 1+4乘积而成，A 1+4表示A1+A4，同理B 1+4表示B1+B4，同理12.4M 表示A1+2与B4的乘积。
一、概述1.介绍矩阵乘法的概念和意义2.引出递归与分治法在矩阵乘法中的应用二、传统矩阵乘法算法1.介绍传统的矩阵乘法算法原理2.分析传统算法的时间复杂度和空间复杂度3.讨论传统算法在大规模矩阵计算中的局限性三、Strassen矩阵乘法算法原理1.介绍Strassen算法的基本思想和原理2.引出递归与分治法在Strassen算法中的运用3.分析Strassen算法的时间复杂度和空间复杂度四、递归与分治法在Strassen算法中的运用1.详细解释递归与分治法在Strassen算法中的具体应用过程2.分析递归与分治法对算法性能的影响3.讨论递归与分治法在其他算法中的推广应用五、实例分析1.通过具体实例演示Strassen算法和传统算法的计算过程2.对比分析两种算法的计算效率和精度3.总结实例分析结果，展示递归与分治法在Strassen算法中的优势六、改进和优化1.讨论现有Strassen算法的局限性和不足2.提出改进和优化的方案，探讨递归与分治法在算法优化中的作用3.展望递归与分治法在矩阵计算领域的未来发展方向七、结论1.总结文中讨论的内容，强调递归与分治法在Strassen算法中的重要性和价值2.展望递归与分治法在矩阵计算领域的广阔应用前景3.对读者提出建议，鼓励更多的研究者投身于这一领域的研究和探索。
六、改进和优化1. Strassen算法的局限性和不足尽管Strassen算法在理论上具有较低的时间复杂度，但实际应用中也存在一些局限性和不足。
Strassen算法中涉及到的矩阵分块操作会引入额外的运算开销和存储开销，使得在小规模矩阵计算中，并不能体现出明显的优势。
Strassen算法要求矩阵的维度必须为2的幂次方，而实际场景中的矩阵往往难以满足这一条件，限制了算法的适用范围。
另外，由于Strassen算法引入了额外的递归调用，对于小规模矩阵，递归调用会使得算法的性能反而不如传统的矩阵乘法算法。
2. 改进和优化的方案针对Strassen算法的局限性和不足，可以考虑一些改进和优化的方案。
矩阵连乘和strassen矩阵乘法矩阵连乘问题和 Strassen 矩阵乘法是计算机科学中的两个重要问题。
矩阵常常被用来表示线性算法问题，而矩阵的乘法则是表示两个矩阵之间运算的一种方法。
本文将对这两个问题分别进行介绍，以便更深入地了解矩阵的应用和计算方法。
矩阵连乘问题矩阵连乘问题是指给定一组矩阵，求其乘积的最小计算次数，并构造出相应的计算方法。
在算法中，我们通常采用递归的思想来解决这个问题。
递归过程中，我们根据矩阵的大小将矩阵划分成更小的子矩阵，然后再对这些子矩阵进行计算。
设矩阵连乘的矩阵序列为 A1, A2, A3, ..., An，其中矩阵 Ai 的行数和列数分别为 pi - 1 和 pi。
那么，计算这个矩阵序列的最小计算次数可以表示为递推式：m[i,j] = min{m[i,k] + m[k+1,j] + pi-1 * pk * pj} (i <= k < j)这个式子的意思是将矩阵序列Ai, Ai+1,...,Aj-1, Aj划分为两个子序列Ai, Ai+1,...,Ak和Ak+1,...,Aj，然后在这两个子序列中分别计算矩阵乘积所需的最小计算次数，其中pi-1 * pk * pj表示计算Ai到Aj乘积时需要的乘法次数。
由此，我们可以得出矩阵连乘的递归算法：Matrix Chain Multiply(A, p, i, j)if i == jreturn A[i]elsek = iM = Matrix Chain Multiply(A, p, i, k)N = Matrix Chain Multiply(A, p, k+1, j)return M * N其中，A是矩阵序列，p是矩阵的行列数，i和j表示矩阵序列的起止下标。
在递归过程中，我们用k将矩阵序列划分为两个部分，并分别计算左边和右边的矩阵乘积。
最后将两个部分的计算结果相乘即可。
这种算法的时间复杂度为O(n^3)，在处理大规模的矩阵乘积时效率较低。
