矩阵乘法的Strassen算法
最近比较忙，一直都感觉没有时间。
昨天算法实验课，做的strassen算法以为做对了，今天才发现自己是多么的愚蠢和自负。
不过总算还是知道自己自负了，希望还不晚！
现将其代码公布如下。
编译语言：Java
编译工具：visual studio 2005 &eclipse
代码：
package Strassen;
import java.util.*;
public class Strassen
{
public static void main(String[] args)
{
int n = 8;
int[][] A = new int[n][n];
int[][] B = new int[n][n];
int[][] C = new int[n][n];
createMatrix(A, n);
createMatrix(B, n);
Date a=new Date();
for(int i=0;i<1000;i++)
{
win(A,B,C,n);
}
Date b=new Date();
System.out.println("这是Strassen算法相乘的结果"+"（所用时间："+(b.getTime()-a.getTime())+"毫秒)（运行1000次）");
print(C,n);
Date c=new Date();
for(int i=0;i<100000;i++)
{
multiply(A, B, C, n);
}
Date d=new Date();
System.out.println("这是普通算法相乘结果："+"(所用时间："+(d.getTime()-c.getTime()+"毫秒)(运行100000次)"));
print(C, n);
}
public static void win(int[][]A,int[][]B,int[][]C,int n)
{
if(n==1)
{
C[n-1][n-1]=A[n-1][n-1]*B[n-1][n-1];
}
else
{
int m=n/2;
int[][] unused = new int[m][m];
int[][] assi = new int[m][m];
int[][] a = new int[m][m];
int[][] b = new int[m][m];
int[][] c = new int[m][m];
int[][] d = new int[m][m];
int[][] e = new int[m][m];
int[][] f = new int[m][m];
int[][] g = new int[m][m];
int[][] h = new int[m][m];
int[][] r = new int[m][m];
int[][] s = new int[m][m];
int[][] t = new int[m][m];
int[][] u = new int[m][m];
int[][] A1 = new int[m][m];
int[][] A2 = new int[m][m];
int[][] A3 = new int[m][m];
int[][] A4 = new int[m][m];
int[][] A5 = new int[m][m];
int[][] A6 = new int[m][m];
int[][] A7 = new int[m][m];
int[][] B1 = new int[m][m];
int[][] B2 = new int[m][m];
int[][] B3 = new int[m][m];
int[][] B4 = new int[m][m];
int[][] B5 = new int[m][m];
int[][] B6 = new int[m][m];
int[][] B7 = new int[m][m];
int[][] P1 = new int[m][m];
int[][] P2 = new int[m][m];
int[][] P3 = new int[m][m];
int[][] P4 = new int[m][m];
int[][] P5 = new int[m][m];
int[][] P6 = new int[m][m];
int[][] P7 = new int[m][m];
divide(A,a,b,c,d,m);
divide(B,e,f,g,h,m);
A1=a;
sub(f, h, B1, m);//B1=f-h
add(a, b, A2, m);//A2=a+b
B2=h;
add(c, d, A3, m);//A3=c+d
B3=e;
A4=d;
sub(g, e, B4, m);//B4=g-e
add(a, d, A5, m);//A5=a+d
add(e, h, B5, m);//B5=e+h
sub(b, d, A6, m);//A6=b-d
add(g, h, B6, m);//B6=g+h
sub(a, c, A7, m);//A7=a-c
add(e, f, B7, m);//B7=e+f
win(A1,B1,P1,m);
win(A2,B2,P2,m);
win(A3,B3,P3,m);
win(A4,B4,P4,m);
win(A5,B5,P5,m);
win(A6,B6,P6,m);
win(A7,B7,P7,m);
add(P1,P2,s,m);
add(P3, P4, t, m);
add(P5, P4, unused, m);//P5+p4
sub(unused, P2, assi, m);//p5+P4-P2
add(assi, P6, r, m);//r=P5+P4-P2+P6
add(P5, P1, unused, m);//P5+P1
add(P3, P7, assi, m);//P3+P7
sub(unused, assi, u, m);//u=P5+P1-P3-P7
merge(C,r,s,t,u,m);
}
}
public static void multiply(int[][] A, int[][] B, int[][] C, int m)//C为A和B相乘后赋予的结果
{
for (int i = 0; i <m; i++)
{
for (int j = 0; j <m; j++)
{
C[i][j] = 0;
for (int k = 0; k <m; k++)
{
C[i][j] += A[i][k] * B[k][j];
}
}
}
}
public static void createMatrix(int[][] A, int n)
{
for (int i = 0; i <n; i++)
{
for (int j = 0; j <n; j++)
{
A[i][j] = 1;
}
}
}
public static void add(int[][] A, int[][] B, int[][] C, int m)
{
for (int i = 0; i <m; i++)
{
for (int j = 0; j <m; j++)
{
C[i][j] = 0;
C[i][j] += A[i][j] + B[i][j];
}
}
}
public static void sub(int[][] A, int[][] B, int[][] C, int m)
{
for (int i = 0; i <m; i++)
{
for (int j = 0; j <m; j++)
{
C[i][j] = 0;
C[i][j] += A[i][j] - B[i][j];
}
}
}
public static void merge(int[][] A, int[][] B, int[][] C, int[][] D, int[][] E, int m)
{
for (int i = 0; i <m; i++)
{
for (int j = 0; j <m; j++)
{
A[i][j] = B[i][j];
}
}
for (int i = 0; i <m; i++)
{
for (int j = 0; j <m; j++)
{
A[i][j + m] = C[i][j];
}
}
for (int i = 0; i <m; i++)
{
for (int j = 0; j <m; j++)
{
A[i + m][j] = D[i][j];
}
}
for (int i = 0; i <m; i++)
{
for (int j = 0; j <m; j++)
{
A[i + m][j + m] = E[i][j];
}
}
}
public static void divide(int[][] A, int[][] B, int[][] C, int[][] D, int[][] E, int m)
{
for (int i = 0; i <m; i++)
{
for (int j = 0; j <m; j++)
{
B[i][j] = 0;
B[i][j] = A[i][j];
}
}
for (int i = 0; i <m; i++)
{
for (int j = 0; j <m; j++)
{
C[i][j] = 0;
C[i][j] = A[i][j + m];
}
}
for (int i = 0; i <m; i++)
{
for (int j = 0; j <m; j++)
{
D[i][j] = 0;
D[i][j] = A[i + m][j];
}
}
for (int i = 0; i <m; i++)
{
for (int j = 0; j <m; j++)
{
E[i][j] = 0;
E[i][j] = A[i + m][j + m];
}
}
}
public static void print(int[][] A, int m)
{
for (int i = 0; i <m; i++)
{
for (int j = 0; j <m; j++)
{
System.out.print(A[i][j] + " ");
if (j == (m - 1))
{
System.out.println();
}
}
}
}
}
运行结果：
