java分治矩阵乘法基本情况+如何将矩阵拆分为4个四分之一
我一直在尝试编写分治矩阵乘法算法
有一个问题是,当我试图将矩阵分成四个四分之一时,它会给我一个错误ArrayOutOfIndexBound
- 我不确定我对基本情况的看法是否正确,所以你们能帮我吗李>
我遇到的问题是在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
# 1 楼答案
如前所述,您的问题是需要减去数组偏移量;e、 g
应该是
你更大的问题是你正在创建4个新的子矩阵,这将产生吨的垃圾。一旦你能做到这一点,我会强烈地思考通过操纵数组索引来“就地”实现这一点的方法
例如,你的新api看起来像
你的分而治之将建立min&;最大指数
# 2 楼答案
用这个分区怎么样?请考虑C和N/2是每个分区的块大小