由上可见,Strassen矩阵乘法是通过递归实现的,它将一般情况下二阶矩阵乘法(可扩展到n阶,但Strassen矩阵乘法要求n是2的幂)所需的8次乘法降低为7次,其C++实现代码如下:
#include <iostream>
using namespace std;
const int N = 6; //Define the size of the Matrix
template<typename T>
void Strassen(int n, T A[][N], T B[][N], T C[][N]);
template<typename T>
void input(int n, T p[][N]);
template<typename T>
void output(int n, T C[][N]);
int main() {
//Define three Matrices
int A[N][N],B[N][N],C[N][N];
//对A和B矩阵赋值,随便赋值都可以,测试用
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
A[i][j] = i * j;
B[i][j] = i * j;
}
}
//调用Strassen方法实现C=A*B
Strassen(N, A, B, C);
//输出矩阵C中值
output(N, C);
system("pause");
return 0;
}
/**The Input Function of Matrix*/
template<typename T>
void input(int n, T p[][N]) {
for(int i=0; i<n; i++) {
cout<<"Please Input Line "<<i+1<<endl;
for(int j=0; j<n; j++) {
cin>>p[i][j];
}
}
}
/**The Output Fanction of Matrix*/
template<typename T>
void output(int n, T C[][N]) {
cout<<"The Output Matrix is :"<<endl;
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
cout<<C[i][j]<<" "<<endl;
}
}
}
/**Matrix Multiplication as the normal algorithm*/
template<typename T>
void Matrix_Multiply(T A[][N], T B[][N], T C[][N]) { //Calculating A*B->C
for(int i=0; i<2; i++) {
for(int j=0; j<2; j++) {
C[i][j] = 0;
for(int t=0; t<2; t++) {
C[i][j] = C[i][j] + A[i][t]*B[t][j];
}
}
}
}
/**Matrix Addition*/
template <typename T>
void Matrix_Add(int n, T X[][N], T Y[][N], T Z[][N]) {
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
Z[i][j] = X[i][j] + Y[i][j];
}
}
}
/**Matrix Subtraction*/
template <typename T>
void Matrix_Sub(int n, T X[][N], T Y[][N], T Z[][N]) {
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
Z[i][j] = X[i][j] - Y[i][j];
}
}
}
/**
* 参数n指定矩阵A,B,C的阶数,因为随着递归调用Strassen函数
* 矩阵A,B,C的阶数是递减的N只是预留足够空间而已
*/
template <typename T>
void Strassen(int n, T A[][N], T B[][N], T C[][N]) {
T A11[N][N], A12[N][N], A21[N][N], A22[N][N];
T B11[N][N], B12[N][N], B21[N][N], B22[N][N];
T C11[N][N], C12[N][N], C21[N][N], C22[N][N];
T M1[N][N], M2[N][N], M3[N][N], M4[N][N], M5[N][N], M6[N][N], M7[N][N];
T AA[N][N], BB[N][N];
if(n == 2) { //2-order
Matrix_Multiply(A, B, C);
} else {
//将矩阵A和B分成阶数相同的四个子矩阵,即分治思想。
for(int i=0; i<n/2; i++) {
for(int j=0; j<n/2; j++) {
A11[i][j] = A[i][j];
A12[i][j] = A[i][j+n/2];
A21[i][j] = A[i+n/2][j];
A22[i][j] = A[i+n/2][j+n/2];
B11[i][j] = B[i][j];
B12[i][j] = B[i][j+n/2];
B21[i][j] = B[i+n/2][j];
B22[i][j] = B[i+n/2][j+n/2];
}
}
//Calculate M1 = (A0 + A3) × (B0 + B3)
Matrix_Add(n/2, A11, A22, AA);
Matrix_Add(n/2, B11, B22, BB);
Strassen(n/2, AA, BB, M1);
//Calculate M2 = (A2 + A3) × B0
Matrix_Add(n/2, A21, A22, AA);
Strassen(n/2, AA, B11, M2);
//Calculate M3 = A0 × (B1 - B3)
Matrix_Sub(n/2, B12, B22, BB);
Strassen(n/2, A11, BB, M3);
//Calculate M4 = A3 × (B2 - B0)
Matrix_Sub(n/2, B21, B11, BB);
Strassen(n/2, A22, BB, M4);
//Calculate M5 = (A0 + A1) × B3
Matrix_Add(n/2, A11, A12, AA);
Strassen(n/2, AA, B22, M5);
//Calculate M6 = (A2 - A0) × (B0 + B1)
Matrix_Sub(n/2, A21, A11, AA);
Matrix_Add(n/2, B11, B12, BB);
Strassen(n/2, AA, BB, M6);
//Calculate M7 = (A1 - A3) × (B2 + B3)
Matrix_Sub(n/2, A12, A22, AA);
Matrix_Add(n/2, B21, B22, BB);
Strassen(n/2, AA, BB, M7);
//Calculate C0 = M1 + M4 - M5 + M7
Matrix_Add(n/2, M1, M4, AA);
Matrix_Sub(n/2, M7, M5, BB);
Matrix_Add(n/2, AA, BB, C11);
//Calculate C1 = M3 + M5
Matrix_Add(n/2, M3, M5, C12);
//Calculate C2 = M2 + M4
Matrix_Add(n/2, M2, M4, C21);
//Calculate C3 = M1 - M2 + M3 + M6
Matrix_Sub(n/2, M1, M2, AA);
Matrix_Add(n/2, M3, M6, BB);
Matrix_Add(n/2, AA, BB, C22);
//Set the result to C[][N]
for(int i=0; i<n/2; i++) {
for(int j=0; j<n/2; j++) {
C[i][j] = C11[i][j];
C[i][j+n/2] = C12[i][j];
C[i+n/2][j] = C21[i][j];
C[i+n/2][j+n/2] = C22[i][j];
}
}
}
}
相关推荐
strassen矩阵乘法的C代码 【问题描述】 从文件arr.in中读入一个m行k列的整数矩阵a和一个k行n列的整数矩阵b(1 , k, n ),在标准输出上输出这两个矩阵的乘积。 【输入形式】 输入文件arr.in中有m+k行,前m...
算法设计与分析实验,Strassen矩阵乘法,java实现,输入矩阵阶数后由系统自动生成两个矩阵,然后用Strassen方法,和普通方法分别计算乘法结果。
Strassen矩阵乘法和棋盘覆盖和自然合并排序算法Strassen矩阵乘法和棋盘覆盖和自然合并排序算法Strassen矩阵乘法和棋盘覆盖和自然合并排序算法Strassen矩阵乘法和棋盘覆盖和自然合并排序算法Strassen矩阵乘法和棋盘...
//完成于2009.11.5 23:18 --龙建文 深圳大学 计算机科学与技术 /*STRASSEN n阶矩阵乘积算法 本程序既实现了自动计算两个8阶,12阶矩阵相乘的算法,又能选择计算两个n阶矩阵相乘 */
Strassen's的矩阵乘法算法的实现
基于MPI的Strassen矩阵乘法算法的并行计算研究与实现
Strassen是采用分治算法的思想,将所给矩阵分成2阶矩阵 分治的方法循序渐进处理各个小矩阵的相乘,一个矩阵可以分成更多小的矩阵的。
Strassen矩阵乘法的实现,我自己编写的代码,经过运行通过了
Strassen 算法 C++ 实现 任意矩阵相乘 用Command line 输入编制好的两个矩阵,输出相乘的结果矩阵。如果需要手动输入,删除程序里的相关语句,添加输入命令即可。
Strassen矩阵相乘算法的c++代码实现.docx
strassen矩阵相乘算法c++代码,可以计算算法速度。
一般情况下矩阵乘法需要三个for循环,时间复杂度为O(n^3),现在我们将矩阵分块如图:( 来自MIT算法导论 ) 一般算法需要八次乘法 r = a * e + b * g ; s = a * f + b * h ; t = c * e + d * g; u = c * f + d * h; ...
Strassen矩阵乘法算法的CUDA实现。
矩阵相乘,普通算法的时间界是10的3此方,而采用strassen算法可提高运算效率。
Strassen’s 矩阵乘法—分治法实现代码,能输出最终结果矩阵和每一次递归的S1~S7。
设计一个矩阵相乘的Strassen算法编程实现并做算法的时间复杂性分析。 其中:乘积矩阵C = A*B, A=(aij)n*n,B=(bij)n*n (1)考虑n为2的幂次方的情形,取n=8实现分治递归; (2)考虑n不是2的幂次方,n为偶数的...
算法作业题目,用Strassen算法求矩阵相乘问题,C++源代码,可运行
strassen算法实现矩阵相乘, 用matlab实现的,已经编译过 没问题