问题描述:

I've been trying to code the divide and conquer matrix multiplication algorithm

There's problem that when I try to divide matrix into four quarters it gives me an error ArrayOutOfIndexBound

  • I'm not sure if I'm right about the base case, so can you help me out guys?

The problem that I get is at double[][] a21

 public static double[][] divideAndConquer(double[][] a , double[][] b, int dimension){

if (a.length == 1){

double[][] result = new double[1][1];

result[0][0]= a[0][0]*b[0][0];

return result;

}

else {

int m = dimension/2;

double[][] a11 = new double[m][m];

for(int i = 0; i < m ; i++){

for (int j = 0 ; j< m ; j++)

a11[i][j]= a[i][j];

}

double[][] a21 = new double[m][m];

for(int i = m; i < dimension; i++){

for (int j = 0 ; j< m ; j++)

a21[i][j]= a[i][j];

}

double[][] a12 = new double[m][m];

for(int i = 0; i < m ; i++){

for (int j = m ; j< dimension ; j++)

a12[i][j]= a[i][j];

}

double[][] a22 = new double[m][m];

for(int i = m; i < dimension; i++){

for (int j = m; j < dimension; j++)

a21[i][j]= a[i][j];

}

double[][] b11 = new double[m][m];

for(int i = 0; i < m ; i++){

for (int j = 0 ; j< m ; j++)

b11[i][j]= b[i][j];

}

double[][] b12 = new double[m][m];

for(int i = 0; i < m ; i++){

for (int j = m ; j< dimension ; j++)

b12[i][j]= b[i][j];

}

double[][] b21 = new double[m][m];

for(int i = m; i < dimension; i++){

for (int j = 0 ; j< m ; j++)

b21[i][j]= b[i][j];

}

double[][] b22 = new double[m][m];

for(int i = m; i < dimension; i++){

for (int j = m; j < dimension; j++)

b21[i][j]= b[i][j];

}

double[][] x1 = divideAndConquer(a11,b11,m);

double[][] x2 = divideAndConquer(a12,b21,m);

double[][] x3 = divideAndConquer(a11,b12,m);

double[][] x4 = divideAndConquer(a12,b22,m);

double[][] x5 = divideAndConquer(a21,b11,m);

double[][] x6 = divideAndConquer(a22,b21,m);

double[][] x7 = divideAndConquer(a21,b12,m);

double[][] x8 = divideAndConquer(a22,b22,m);

..........................etc

网友答案:

As written, your problem is that you need to subtract off the array offset; e.g.,

a12[i][j]= a[i][j];

should be

a12[i][j-dimension]= a[i][j];

Your bigger problem is that you're creating 4 new submatrices, which is going to generate tons of garbage. Once you've gotten this working, I would strongly think about ways of doing this "in-place" by manipulating array indexes.

E.g., your new api would look like

public static double[][] divideAndConquer(double[][] a , double[][] b, int aMinIndex, int aMaxIndex, int bMinIndex, bMaxIndex){

and your divide and conquer would build subsets of the min & max indices.

网友答案:

How about using this for the partitioning? Please consider that it's in C and N/2 is the block size of each partition

for (int i = 0; i < N / 2; i++) {
    for (int j = 0; j < N / 2; j++) {

        ha11[i][j] = hA[i][j]; // top left
        ha12[i][j] = hA[i][j + N / 2]; // top right
        ha21[i][j] = hA[i + N / 2][j]; // bottom left
        ha22[i][j] = hA[i + N / 2][j + N / 2]; // bottom right

        hb11[i][j] = hB[i][j]; // top left
        hb12[i][j] = hB[i][j + N / 2]; // top right
        hb21[i][j] = hB[i + N / 2][j]; // bottom left
        hb22[i][j] = hB[i + N / 2][j + N / 2]; // bottom right
    }
}
相关阅读:
Top