实验二Strassen矩阵乘法

实验2-Strassen 矩阵乘法 written by yjf66@qq.com 实验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] 实验2-Strassen 矩阵乘法 written by yjf66@qq.com 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-43 44+= AB= A B= AB= A B= ABM= ABM= AMMBMMM (2) 为方便表示，这里采用与书本不同的下标表示法，如对于1 个n/2 维矩阵14.14M，下标14.14 表示其由两个矩阵A1+4 和B1+4 乘积而成，A1+4 表示A1+A4，同理B1+4 表示B1+B4，同理12.4M表示A1+2 与B4 的乘积。采用这种表示法，目的是为了记住每个M 矩阵是由A 和B 的哪一个或两个子矩阵得到的，从而方便后面的内存分配设计。 1）第一步：半分(半分指维度，若指面积也许应叫1/4 分) 将A 和B 两个n 维方阵各分解为4 份，每份n/2 维，即A1,A2,A3,A4 和B1,B2,B3,B4。 2）第二步：混合 将维度为n/2 的7 个子矩阵的“混合”（加减运算混合法），存入维度为n 的结果矩阵C 的4 个位置中，即C 的4 个n/2 维的子矩阵依次是： =4.13124.14.1444312.MC-+ MMM+ 1.241 422.MMC =+ 34.14 33.1MMC =+ (3)实验2-Strassen 矩阵乘法 writ...