分治法-Strassen-矩阵乘法详细代码

public class Matrix {

    //初始化一个随机nxn阶矩阵
    public static int[][] initializationMatrix(int n){
        int[][] result = new int[n][n];
        for(int i = 0;i < n;i++){
            for(int j = 0;j < n;j++){
                result[i][j] = (int)(Math.random()*10); //采用随机函数随机生成1~10之间的数
            }
        }
        return result;
    }

    //当n=2是直接求解求解两个2x2和2x2阶矩阵相乘
    public static int[][] MatrixMultiply(int[][] p,int[][] q){
        int[][] result = new int[2][2];
        for(int i=0;i<2;i++){
            for(int j=0;j<2;j++){
                result[i][j] = 0;
                for(int k=0;k<2;k++){
                    result[i][j] += p[i][k]*q[k][j];
                }
            }
        }
        return result;
    }

    //分治法求解两个nxn和nxn阶矩阵相乘
    public static int[][] Strassen(int[][] p,int[][] q,int n){
        int[][] result = new int[n][n];
        //当n为2时，返回矩阵相乘结果
        if(n == 2){
            result = MatrixMultiply(p,q);
            return result;
        }

        //当n大于3时，采用采用分治法，递归求最终结果
        if(n > 2){
            //矩阵拆分为4块
            int[][] A11 = QuarterMatrix(p,n,1);
            int[][] A12 = QuarterMatrix(p,n,2);
            int[][] A21 = QuarterMatrix(p,n,3);
            int[][] A22 = QuarterMatrix(p,n,4);


            //矩阵拆分为4块
            int[][] B11 = QuarterMatrix(q,n,1);
            int[][] B12 = QuarterMatrix(q,n,2);
            int[][] B21 = QuarterMatrix(q,n,3);
            int[][] B22 = QuarterMatrix(q,n,4);

            int[][] M1 = Strassen(A11, SubMatrix(B12, B22,n/2),n/2);

            int[][] M2 = Strassen(AddMatrix(A11, A12,n/2), B22 ,n/2);
            int[][] M3 = Strassen(AddMatrix(A21, A22,n/2), B11,n/2);
            int[][] M4 = Strassen(A22, SubMatrix(B21, B11,n/2),n/2);
            int[][] M5 = Strassen(AddMatrix(A11, A22, n/2), AddMatrix(B11, B22,n/2),n/2);
            int[][] M6 = Strassen(SubMatrix(A12, A22, n/2), AddMatrix(B21, B22,n/2),n/2);
            int[][] M7 = Strassen(SubMatrix(A11, A21, n/2), AddMatrix(B11, B12,n/2),n/2);

            int[][] C11 = AddMatrix(SubMatrix(AddMatrix(M5, M4, n/2), M2,n/2), M6, n/2);
            int[][] C12 = AddMatrix(M1, M2, n/2);
            int[][] C21 = AddMatrix(M3, M4, n/2);
            int[][] C22 = SubMatrix(SubMatrix(AddMatrix(M1, M5, n/2), M3, n/2), M7, n/2);

            result = TogetherMatrix(C11, C12, C21, C22,n/2);
        }
        return result;
    }

    //获取矩阵的四分之一，并决定返回哪一个四分之一
    public static int[][] QuarterMatrix(int[][] p,int n,int number){
        int rows = n/2;   //行数减半
        int cols = n/2;   //列数减半
        int[][] result = new int[rows][cols];
        switch(number){
            case 1 :
            {
                // result = new int[rows][cols];
                for(int i=0;i<rows;i++){
                    for(int j=0;j<cols;j++){
                        result[i][j] = p[i][j];
                    }
                }
                break;
            }

            case 2 :
            {
                // result = new int[rows][n-cols];
                for(int i=0;i<rows;i++){
                    for(int j=0;j<n-cols;j++){
                        result[i][j] = p[i][j+cols];
                    }
                }
                break;
            }

            case 3 :
            {
                // result = new int[n-rows][cols];
                for(int i=0;i<n-rows;i++){
                    for(int j=0;j<cols;j++){
                        result[i][j] = p[i+rows][j];
                    }
                }
                break;
            }

            case 4 :
            {
                // result = new int[n-rows][n-cols];
                for(int i=0;i<n-rows;i++){
                    for(int j=0;j<n-cols;j++){
                        result[i][j] = p[i+rows][j+cols];
                    }
                }
                break;
            }
            default:
                break;
        }

        return result;
    }

    //把均分为四分之一的矩阵，聚合成一个矩阵，其中矩阵a,b,c,d分别对应原完整矩阵的四分中1、2、3、4
    public static int[][] TogetherMatrix(int[][] a,int[][] b,int[][] c,int[][] d,int n){
        int[][] result = new int[2*n][2*n];
        for(int i=0;i<2*n;i++){
            for(int j=0;j<2*n;j++){
                if(i<n){
                    if(j<n){
                        result[i][j] = a[i][j];
                    }
                    else
                        result[i][j] = b[i][j-n];
                }
                else{
                    if(j<n){
                        result[i][j] = c[i-n][j];
                    }
                    else{
                        result[i][j] = d[i-n][j-n];
                    }
                }
            }
        }

        return result;
    }


    //求两个矩阵相加结果
    public static int[][] AddMatrix(int[][] p,int[][] q,int n){
        int[][] result = new int[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                result[i][j] = p[i][j]+q[i][j];
            }
        }
        return result;
    }

    public static int[][] SubMatrix(int[][] p,int[][] q,int n){
        int[][] result = new int[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                result[i][j] = p[i][j]-q[i][j];
            }
        }
        return result;
    }

    //控制台输出矩阵
    public static void PrintfMatrix(int[][] matrix,int n){
        for(int i=0;i<n;i++){
            System.out.println();
            for(int j=0;j<n;j++){
                System.out.print("\t");
                System.out.print(matrix[i][j]);
            }
        }

    }

    public static void main(String args[]){
        int n = 8;
        int[][] p = initializationMatrix(n);
        int[][] q = initializationMatrix(n);
        System.out.print("矩阵p初始化值为：");
        PrintfMatrix(p,n);
        System.out.println();
        System.out.print("矩阵q初始化值为：");
        PrintfMatrix(q,n);

        int[][] dac_result = Strassen(p,q,n);
        System.out.println();
        System.out.print("分治法计算矩阵p*q结果为：");
        PrintfMatrix(dac_result,n);
    }

}