分而治之递归矩阵乘法
Divide and conquer recursive matrix multiplication
我开始研究分而治之的概念，并且遇到了矩阵乘法。我可以使用 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]]
/* 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));
}
}
}
嗯，我的错误是当我将矩阵划分为子矩阵时。
===============================下面的Strassen算法====== =====================
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));
}
}
}
我开始研究分而治之的概念，并且遇到了矩阵乘法。我可以使用 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]]
/* 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));
}
}
}
嗯，我的错误是当我将矩阵划分为子矩阵时。
===============================下面的Strassen算法====== =====================
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));
}
}
}