java - 分而治之递归矩阵乘法

Question

我开始研究分而治之的概念，并且遇到了矩阵乘法。我可以使用 for 循环执行以下代码，但为了递归练习，我又采取了一步并尝试自己完成。

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
    int bigA[][];
    int bigB[][];
    public Codechef (int bigA[][], int bigB[][]) {
        this.bigA = bigA;
        this.bigB = bigB;
    }

    public int[][] recursiveMatrixMultipy (int A[][], int B[][], int n) {
        int c[][] = new int[n][n];
        if (n == 1) {
            c[0][0] = bigA[ A[0][0] ][ A[1][0] ] * bigB[ B[0][0] ][ B[1][0] ];
        } else {
            int r_start = A[0][0];
            int r_end = A[0][1];
            int c_start = A[1][0];
            int c_end = A[1][1];
            int r_mid = r_start + (r_end - r_start) / 2;
            int c_mid = c_start + (c_end - c_start) / 2;
            int a11[][] = {{r_start, r_mid}, {c_start, c_mid}};
            int a12[][] = {{r_start, r_mid}, {c_mid + 1, c_end}};
            int a21[][] = {{r_mid + 1, r_end}, {c_start, c_mid}};
            int a22[][] = {{r_mid + 1, r_end}, {c_mid + 1, c_end}};

            int b11[][] = {{r_start, r_mid}, {c_start, c_mid}};
            int b12[][] = {{r_start, r_mid}, {c_mid + 1, c_end}};
            int b21[][] = {{r_mid + 1, r_end}, {c_start, c_mid}};
            int b22[][] = {{r_mid + 1, r_end}, {c_mid + 1, c_end}};
            System.out.println ("A " +  Arrays.deepToString(A));
            System.out.println ("B " +  Arrays.deepToString(B));
            System.out.println (n);
            System.out.println ("a11 " +  Arrays.deepToString(a11));
            System.out.println ("a12 " +  Arrays.deepToString(a12));
            System.out.println ("a21 " +  Arrays.deepToString(a21));
            System.out.println ("a22 " +  Arrays.deepToString(a22));

            int c11[][] = addMatrix(recursiveMatrixMultipy (a11, b11, n / 2),
                            recursiveMatrixMultipy (a12, b21, n / 2) );

            int c12[][] = addMatrix(recursiveMatrixMultipy (a11, b12, n / 2), 
                            recursiveMatrixMultipy (a12, b22, n / 2) );

            int c21[][] = addMatrix(recursiveMatrixMultipy (a21, b11, n / 2), 
                            recursiveMatrixMultipy (a22, b21, n / 2) );

            int c22[][] = addMatrix(recursiveMatrixMultipy (a21, b12, n / 2), 
                            recursiveMatrixMultipy (a22, b22, n / 2) );
            c = merge (c11, c12, c21, c22);
        }
        return c;
    }


    public int[][] addMatrix (int A[][], int B[][]) {
        int n = A[0].length;
        int c[][] = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                c[i][j] = A[i][j] + B[i][j];
            }
        }
        return c;
    }

    public int[][] merge (int c11[][], int c12[][], int c21[][], int c22[][]) {      
        int n_C = c11[0].length;          
        int n = 2 * n_C;
        int C[][] = new int[n][n];
        for (int i = 0; i < n_C; i++) {
            for (int j = 0; j < n_C; j++) {
               C[i][j] = c11[i][j];
               C[i][j + n_C] = c12[i][j];
               C[i + n_C][j] = c21[i][j];
               C[i + n_C][j + n_C] = c22[i][j];
            }
        }
        return C;
    }

    public static void main (String[] args) throws java.lang.Exception
    {

        int matrix[][] = {{1,2,3,4},{1,2,3,4},{1,2,3,4},{1,2,3,4}};
        int n = matrix[0].length;

        //checks if power of 2
        if ((n > 0) && ( ( n & ( n - 1 ) ) == 0 ) ) {
            Codechef matrixDivAndConquer = new Codechef (matrix, matrix);
            int A[][] = {{0, n - 1},{0, n  - 1}};
            int B[][] = {{0, n - 1},{0, n  - 1}};
            int C[][] = matrixDivAndConquer.recursiveMatrixMultipy (A, B, n);
            System.out.println (Arrays.deepToString(C));
        }
    }
}



A [[0, 3], [0, 3]]
B [[0, 3], [0, 3]]
4
a11 [[0, 1], [0, 1]]
a12 [[0, 1], [2, 3]]
a21 [[2, 3], [0, 1]]
a22 [[2, 3], [2, 3]]
A [[0, 1], [0, 1]]
B [[0, 1], [0, 1]]
2
a11 [[0, 0], [0, 0]]
a12 [[0, 0], [1, 1]]
a21 [[1, 1], [0, 0]]
a22 [[1, 1], [1, 1]]
A [[0, 1], [2, 3]]
B [[2, 3], [0, 1]]
2
a11 [[0, 0], [2, 2]]
a12 [[0, 0], [3, 3]]
a21 [[1, 1], [2, 2]]
a22 [[1, 1], [3, 3]]
A [[0, 1], [0, 1]]
B [[0, 1], [2, 3]]
2
a11 [[0, 0], [0, 0]]
a12 [[0, 0], [1, 1]]
a21 [[1, 1], [0, 0]]
a22 [[1, 1], [1, 1]]
A [[0, 1], [2, 3]]
B [[2, 3], [2, 3]]
2
a11 [[0, 0], [2, 2]]
a12 [[0, 0], [3, 3]]
a21 [[1, 1], [2, 2]]
a22 [[1, 1], [3, 3]]
A [[2, 3], [0, 1]]
B [[0, 1], [0, 1]]
2
a11 [[2, 2], [0, 0]]
a12 [[2, 2], [1, 1]]
a21 [[3, 3], [0, 0]]
a22 [[3, 3], [1, 1]]
A [[2, 3], [2, 3]]
B [[2, 3], [0, 1]]
2
a11 [[2, 2], [2, 2]]
a12 [[2, 2], [3, 3]]
a21 [[3, 3], [2, 2]]
a22 [[3, 3], [3, 3]]
A [[2, 3], [0, 1]]
B [[0, 1], [2, 3]]
2
a11 [[2, 2], [0, 0]]
a12 [[2, 2], [1, 1]]
a21 [[3, 3], [0, 0]]
a22 [[3, 3], [1, 1]]
A [[2, 3], [2, 3]]
B [[2, 3], [2, 3]]
2
a11 [[2, 2], [2, 2]]
a12 [[2, 2], [3, 3]]
a21 [[3, 3], [2, 2]]
a22 [[3, 3], [3, 3]]

现在这似乎没有给我正确的答案。我在这里缺少什么？

我在输出之间粘贴了一些内容，以便更容易理解我在做什么。我的输出:

[[24, 34, 24, 34], [24, 34, 24, 34], [24, 34, 24, 34], [24, 34, 24, 34]]

上述矩阵的正确答案:

[[10, 20, 30, 40], [10, 20, 30, 40], [10, 20, 30, 40], [10, 20, 30, 40]]

Answer 1

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
    int bigA[][];
    int bigB[][];
    public Codechef (int bigA[][], int bigB[][]) {
        this.bigA = bigA;
        this.bigB = bigB;
    }

    public int[][] recursiveMatrixMultipy (int A[][], int B[][], int n) {
        int c[][] = new int[n][n];
        if (n == 1) {
            c[0][0] = bigA[ A[0][0] ][ A[1][0] ] * bigB[ B[0][0] ][ B[1][0] ];
        } else {
            int [][] a11 = new int[2][2];
            int [][] a12 = new int[2][2];
            int [][] a21 = new int[2][2];
            int [][] a22 = new int[2][2];
            int [][] b11 = new int[2][2];
            int [][] b12 = new int[2][2];
            int [][] b21 = new int[2][2];
            int [][] b22 = new int[2][2];

            partitionMatrix (A, a11, a12, a21, a22);
            partitionMatrix (B, b11, b12, b21, b22);

            int c11[][] = addMatrix(recursiveMatrixMultipy (a11, b11, n / 2),
                            recursiveMatrixMultipy (a12, b21, n / 2) );

            int c12[][] = addMatrix(recursiveMatrixMultipy (a11, b12, n / 2), 
                            recursiveMatrixMultipy (a12, b22, n / 2) );

            int c21[][] = addMatrix(recursiveMatrixMultipy (a21, b11, n / 2), 
                            recursiveMatrixMultipy (a22, b21, n / 2) );

            int c22[][] = addMatrix(recursiveMatrixMultipy (a21, b12, n / 2), 
                            recursiveMatrixMultipy (a22, b22, n / 2) );
            c = merge (c11, c12, c21, c22);
        }
        return c;
    }


    public int[][] addMatrix (int A[][], int B[][]) {
        int n = A[0].length;
        int c[][] = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                c[i][j] = A[i][j] + B[i][j];
            }
        }
        return c;
    }

    public void partitionMatrix (int T[][], int t11[][], int t12[][], int t21[][], int t22[][]) {
        int r_start = T[0][0];
        int r_end = T[0][1];
        int c_start = T[1][0];
        int c_end = T[1][1];

        int r_mid = r_start + (r_end - r_start) / 2;
        int c_mid = c_start + (c_end - c_start) / 2;

        t11[0][0] = r_start;
        t11[0][1] = r_mid;
        t11[1][0] = c_start;
        t11[1][1] = c_mid;

        t12[0][0] = r_start;
        t12[0][1] = r_mid;
        t12[1][0] = c_mid + 1;
        t12[1][1] = c_end;

        t21[0][0] = r_mid + 1;
        t21[0][1] = r_end;
        t21[1][0] = c_start;
        t21[1][1] = c_mid;

        t22[0][0] = r_mid + 1;
        t22[0][1] = r_end;
        t22[1][0] = c_mid + 1;
        t22[1][1] = c_end;
    }

    public int[][] merge (int c11[][], int c12[][], int c21[][], int c22[][]) {
        int n_C = c11[0].length;

        int n = 2 * n_C;
        int C[][] = new int[n][n];
        for (int i = 0; i < n_C; i++) {
            for (int j = 0; j < n_C; j++) {
               C[i][j] = c11[i][j];
               C[i][j + n_C] = c12[i][j];
               C[i + n_C][j] = c21[i][j];
               C[i + n_C][j + n_C] = c22[i][j];
            }
        }

        return C;
    }

    public static void main (String[] args) throws java.lang.Exception
    {

        int matrix[][] = {{1,2,3,4},{1,2,3,4},{1,2,3,4},{1,2,3,4}};

        int n = matrix[0].length;

        //checks if power of 2
        if ((n > 0) && ( ( n & ( n - 1 ) ) == 0 ) ) {
            Codechef matrixDivAndConquer = new Codechef (matrix, matrix);
            int A[][] = {{0, n - 1},{0, n  - 1}};
            int B[][] = {{0, n - 1},{0, n  - 1}};
            int C[][] = matrixDivAndConquer.recursiveMatrixMultipy (A, B, n);
            System.out.println (Arrays.deepToString(C));
        }
    }
}

嗯，我的错误是当我将矩阵划分为子矩阵时。

==================================下面的施特拉森算法========== =================

import java.util.*;
import java.lang.*;
import java.io.*;

class StrassenAlgo
{
    public int[][] recursiveMatrixMultipy (int A[][], int B[][], int a[][], int b[][], int n) {
        int c[][] = new int[n][n];
        if (n == 1) {
            c[0][0] = A[ a[0][0] ][ a[1][0] ] * B[ b[0][0] ][ b[1][0] ];
        } else {
            int [][] a11 = new int[2][2];
            int [][] a12 = new int[2][2];
            int [][] a21 = new int[2][2];
            int [][] a22 = new int[2][2];
            int [][] b11 = new int[2][2];
            int [][] b12 = new int[2][2];
            int [][] b21 = new int[2][2];
            int [][] b22 = new int[2][2];

            partitionMatrix (a, a11, a12, a21, a22);
            partitionMatrix (b, b11, b12, b21, b22);

            int s1[][] = substractMatrix (B, B, b12, b22);
            int s2[][] = addMatrix (A, A, a11, a12);
            int s3[][] = addMatrix (A, A, a21, a22);
            int s4[][] = substractMatrix (B, B, b21, b11);
            int s5[][] = addMatrix (A, A, a11, a22);
            int s6[][] = addMatrix (B, B, b11, b22);
            int s7[][] = substractMatrix (A, A, a12, a22);
            int s8[][] = addMatrix (B, B, b21, b22);
            int s9[][] = substractMatrix (A, A, a11, a21);
            int s10[][] = addMatrix (B, B, b11, b12);


            int ss[][] = {{0, s1.length - 1}, {0, s1.length - 1}};

            int p1[][] = recursiveMatrixMultipy (A, s1, a11, ss, n / 2);
            int p2[][] = recursiveMatrixMultipy (s2, B, ss, b22, n / 2);
            int p3[][] = recursiveMatrixMultipy (s3, B, ss, b11, n / 2);
            int p4[][] = recursiveMatrixMultipy (A, s4, a22, ss, n / 2);
            int p5[][] = recursiveMatrixMultipy (s5, s6, ss, ss, n / 2);
            int p6[][] = recursiveMatrixMultipy (s7, s8, ss, ss, n / 2);
            int p7[][] = recursiveMatrixMultipy (s9, s10, ss, ss, n / 2 );

            int pp[][] = {{0, p1.length - 1}, {0, p1.length - 1}};

            // c11 = p5 + p4 - p2 + p6
            int c11[][] = substractMatrix (addMatrix (p4, addMatrix (p5, p6, pp, pp), pp, pp), p2, pp, pp);
            // c12 = p1 + p2
            int c12[][] = addMatrix (p1, p2, pp, pp);
            // c21 = p3 + p4
            int c21[][] = addMatrix (p3, p4, pp, pp);
            // c22 = p5 + p1 - p3 - p7
            int c22[][] = substractMatrix(addMatrix (p1, p5, pp, pp), addMatrix(p3, p7, pp, pp), pp, pp);
            c = merge (c11, c12, c21, c22);
        }
        return c;
    }


    public int[][] addMatrix (int A[][], int B[][], int a[][], int b[][]) {
        int n = a[0][1] - a[0][0] + 1;
        int c[][] = new int[n][n];

        for (int i = a[0][0], u = b[0][0], x = 0; i <= a[0][1]; i++, u++, x++) {
            for (int j = a[1][0], v = b[1][0], y = 0; j <= a[1][1]; j++, v++, y++) {
                c[x][y] = A[i][j] + B[u][v];
            }
        }

        return c;
    }

    public int[][] substractMatrix (int A[][], int B[][], int a[][], int b[][]) {
        int n = a[0][1] - a[0][0] + 1;
        int c[][] = new int[n][n];

        for (int i = a[0][0], u = b[0][0], x = 0; i <= a[0][1]; i++, u++, x++) {
            for (int j = a[1][0], v = b[1][0], y = 0; j <= a[1][1]; j++, v++, y++) {
                c[x][y] = A[i][j] - B[u][v];
            }
        }

        return c;
    }

    public void partitionMatrix (int T[][], int t11[][], int t12[][], int t21[][], int t22[][]) {
        int r_start = T[0][0];
        int r_end = T[0][1];
        int c_start = T[1][0];
        int c_end = T[1][1];

        int r_mid = r_start + (r_end - r_start) / 2;
        int c_mid = c_start + (c_end - c_start) / 2;

        t11[0][0] = r_start;
        t11[0][1] = r_mid;
        t11[1][0] = c_start;
        t11[1][1] = c_mid;

        t12[0][0] = r_start;
        t12[0][1] = r_mid;
        t12[1][0] = c_mid + 1;
        t12[1][1] = c_end;

        t21[0][0] = r_mid + 1;
        t21[0][1] = r_end;
        t21[1][0] = c_start;
        t21[1][1] = c_mid;

        t22[0][0] = r_mid + 1;
        t22[0][1] = r_end;
        t22[1][0] = c_mid + 1;
        t22[1][1] = c_end;
    }

    public int[][] merge (int c11[][], int c12[][], int c21[][], int c22[][]) {
        int n_C = c11[0].length;
        int n = 2 * n_C;
        int C[][] = new int[n][n];
        for (int i = 0; i < n_C; i++) {
            for (int j = 0; j < n_C; j++) {
               C[i][j] = c11[i][j];
               C[i][j + n_C] = c12[i][j];
               C[i + n_C][j] = c21[i][j];
               C[i + n_C][j + n_C] = c22[i][j];
            }
        }
        return C;
    }

    public static void main (String[] args) throws java.lang.Exception
    {
        int matrix[][] = {{1,2,3,4},{1,2,3,4},{1,2,3,4},{1,2,3,4}};

        int n = matrix[0].length;

        if ((n > 0) && ( ( n & ( n - 1 ) ) == 0 ) ) {
            StrassenAlgo matrixDivAndConquer = new StrassenAlgo ();
            int a[][] = {{0, n - 1},{0, n  - 1}};
            int b[][] = {{0, n - 1},{0, n  - 1}};
            int C[][] = matrixDivAndConquer.recursiveMatrixMultipy 
            (matrix, matrix, a, b, n);
            System.out.println (Arrays.deepToString(C));
        }
    }
}