Stressen矩阵乘法
思想是：
减少乘法的次数
由八次变为7次
要多做加法和减法
import java.util.Scanner;
public class Strassen矩阵乘法 {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();//两个矩阵的维度,先假设是4，可以分解成4个2*2的矩阵
int arrayA[][]=new int[n][n];//存A矩阵
int arrayB[][]=new int[n][n];//存B矩阵
int res[][]=new int[n][n];
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
arrayA[i][j]=sc.nextInt();
}
}
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
arrayB[i][j]=sc.nextInt();
}
}
Stressen(arrayA,arrayB,n,res);
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++){
if(j != n-1) System.out.print(res[i][j] + " ");
else System.out.println(res[i][j]);
}
}
private static void Stressen(int[][] arrayA, int[][] arrayB, int n,int [][]res) {
if(n==1) {
res[0][0] = arrayA[0][0] * arrayB[0][0];
return;
}
else {
int halfsize=n/2;
int A11[][]=new int[halfsize][halfsize];
int A12[][]=new int[halfsize][halfsize];
int A21[][]=new int[halfsize][halfsize];
int A22[][]=new int[halfsize][halfsize];
int B11[][]=new int[halfsize][halfsize];
int B12[][]=new int[halfsize][halfsize];
int B21[][]=new int[halfsize][halfsize];
int B22[][]=new int[halfsize][halfsize];
int tempA[][]=new int[halfsize][halfsize];//中间变量
int tempB[][]=new int[halfsize][halfsize];//中间变量
int[][] A1 = new int[halfsize][halfsize];
int[][] A2 = new int[halfsize][halfsize];
int[][] A3 = new int[halfsize][halfsize];
int[][] A4 = new int[halfsize][halfsize];
int[][] A5 = new int[halfsize][halfsize];
int[][] A6 = new int[halfsize][halfsize];
int[][] A7 = new int[halfsize][halfsize];
int[][] C11 = new int[halfsize][halfsize];
int[][] C12 = new int[halfsize][halfsize];
int[][] C21 = new int[halfsize][halfsize];
int[][] C22 = new int[halfsize][halfsize];
for(int i=0;i<halfsize;i++) {
for(int j=0;j<halfsize;j++) {
A11[i][j]=arrayA[i][j];
B11[i][j]=arrayB[i][j];
A12[i][j]=arrayA[i][j+halfsize];
B12[i][j]=arrayB[i][j+halfsize];
A21[i][j]=arrayA[i+halfsize][j];
B21[i][j]=arrayB[i+halfsize][j];
A22[i][j]=arrayA[i+halfsize][j+halfsize];
B22[i][j]=arrayB[i+halfsize][j+halfsize];
}
}
sub(B12,B22,tempB);
Stressen(A11,tempB,halfsize,A1);
add(A11,A12,tempA);
Stressen(B22,tempA,halfsize,A2);
add(A21,A22,tempA);
Stressen(B11,tempA,halfsize,A3);
sub(B21,B11,tempB);
Stressen(A22,tempB,halfsize,A4);
add(A11,A22,tempA);
add(B11,B22,tempB);
Stressen(tempA,tempB,halfsize,A5);
sub(A11,A22,tempA);
add(B21,B22,tempB);
Stressen(tempA,tempB,halfsize,A6);
sub(A11,A21,tempA);
add(B11,B12,tempB);
Stressen(tempA,tempB,halfsize,A7);
add(A5,A4,tempA);
sub(A6,A2,tempB);
add(tempA,tempB,C11);
add(A1,A2,C12);
add(A3,A4,C21);
sub(A5,A3,tempA);
sub(A1,A7,tempB);
add(tempA,tempB,C22);
for(int i=0;i<halfsize;i++) {
for(int j=0;j<halfsize;j++) {
res[i][j] = C11[i][j];
res[i][j + halfsize] = C12[i][j];
res[i + halfsize][j] = C21[i][j];
res[i + halfsize][j + halfsize] = C22[i][j];
}
}
}
}
private static void add(int[][] a11, int[][] a12, int[][] tempA) {
for(int i=0;i<a12.length;i++) {
for(int j=0;j<a12.length;j++) {
tempA[i][j]=a12[i][j]+a11[i][j];
}
}
}
private static void sub(int[][] b12, int[][] b22, int[][] tempB) {
for(int i=0;i<b12.length;i++) {
for(int j=0;j<b12.length;j++) {
tempB[i][j]=b12[i][j]-b22[i][j];
}
}
}
}