java - 如何将一些矩阵合并为一个？

Question

我正在尝试用分治法进行矩阵乘法。所以，我认为，我已经将部分分解为子问题(递归情况和基本情况)。

因此，我有四个象限(左上、左下、右上、右下)，我正在考虑如何将它们组合成结果矩阵，但我不知道。

我正在使用Java，所以我有matrixA和matrixB，并且我有一些索引，例如matrixRowsA，matrixColumnsA，matrixRowsB，matrixColumnsB

通过这种方式，我可以避免创建新的矩阵和所有那些只会使问题解决成本更高的东西。

所以基本问题是，如何将 4 个子矩阵连接成一个填充矩阵？

所以该方法是调用divideAndConquer:

private static int[][] divideAndConquer(int[][]matrixA, int beginRowsA, int endRowsA, int beginColumnsA,
                                        int endColumnsA, int[][]matrixB, int beginRowsB, int endRowsB,
                                        int beginColumnsB, int endColumnsB)
{
    // Base case
    if(lengthOfBothMatrix()==1)
    {
        return multiplyMatrix(matrixA,matrixB);
    }
    }
    else
    {
        int middleRowsA = obtainMiddleRowsB();
        int middleColumnsA = obtainMiddleColumnsA();
        int middleRowsB = obtainMiddleRowsB();
        int middleColumnsB = obtainMiddleColumnsB();

        int[][] leftSuperiorQuadrant = matrixAddition(divideAndConquer(matrixA, beginRowsA, middleRowsA, beginColumnsA, middleColumnsA, matrixB, beginRowsB,
                middleRowsB, beginColumnsB, middleColumnsB),
                divideAndConquer(matrixA, beginRowsA, middleRowsA, middleColumnsA+1, endColumnsA,
                        matrixB, middleRowsB+1, endRowsB, beginColumnsB, middleColumnsB));
        int[][] leftInferiorQuadrant = matrixAddition(divideAndConquer(matrixA, middleRowsA+1, endRowsA, beginColumnsA, middleColumnsA,
                matrixB, beginRowsB,middleRowsB, beginColumnsB, middleColumnsB),
                divideAndConquer(matrixA, middleRowsA+1, endRowsA, middleColumnsA+1, endColumnsA,
                        matrixB, middleRowsB+1, endRowsB, beginColumnsB, middleColumnsB));

        int[][] rightSuperiorQuadrant = matrixAddition(divideAndConquer(matrixA, beginRowsA, middleRowsA, beginColumnsA, middleColumnsA,
                matrixB, beginRowsB, middleRowsB, middleColumnsB+1, endColumnsB),
                divideAndConquer(matrixA, beginRowsA, middleRowsA, middleColumnsA+1, endColumnsA,
                        matrixB, middleRowsB+1, endRowsB, middleColumnsB+1, endColumnsB));
        int[][] rightInferiorQuadrant =matrixAddition(divideAndConquer(matrixA, middleRowsA+1, endRowsA, beginColumnsA, middleColumnsA,
                matrixB, beginRowsB, middleRowsB, middleColumnsB+1, endColumnsB),
                divideAndConquer(matrixA, middleRowsA+1, endRowsA, middleColumnsA+1, endColumnsA,
                        matrixB, middleRowsB+1, endRowsB, middleColumnsB+1, endColumnsB));

我正在使用两个矩阵进行测试，例如:

1 | 2 | 3 | 4 | 
1 | 2 | 3 | 4 | 
1 | 2 | 3 | 4 | 
1 | 2 | 3 | 4 | 

1 | 2 | 3 | 4 | 
1 | 2 | 3 | 4 | 
1 | 2 | 3 | 4 | 
1 | 2 | 3 | 4 | 

Answer 1

首先，您可以将左矩阵(leftSuperiorQuadrant & leftInferiorQuadrant)和右矩阵(rightSuperiorQuadrant & rightInferiorQuadrant)垂直连接成一个新的列矩阵 System.arraycopy() :

    int leftSuperiorQuadrant [][] = {{1, 2}, {3, 4}};
    int rightSuperiorQuadrant [][] = {{5, 6}, {7, 8}};
    int leftInferiorQuadrant [][] = {{9, 10}, {11, 12}};
    int rightInferiorQuadrant [][] = {{13, 14}, {15, 16}};

    int m_intermediate_left[][] = new int[leftSuperiorQuadrant.length+leftInferiorQuadrant.length][];
    int m_intermediate_right[][] = new int[rightSuperiorQuadrant.length+rightInferiorQuadrant.length][];

    // Concat leftSuperiorQuadrant and leftInferiorQuadrant in column
    System.arraycopy(leftSuperiorQuadrant, 0, m_intermediate_left, 0, leftSuperiorQuadrant.length);
    System.arraycopy(leftInferiorQuadrant, 0, m_intermediate_left, leftSuperiorQuadrant.length, leftInferiorQuadrant.length);

    // Concat rightSuperiorQuadrant and rightInferiorQuadrant in column
    System.arraycopy(rightSuperiorQuadrant, 0, m_intermediate_right, 0, rightSuperiorQuadrant.length);
    System.arraycopy(rightInferiorQuadrant, 0, m_intermediate_right, rightSuperiorQuadrant.length, rightInferiorQuadrant.length);

    System.out.println(Arrays.deepToString(m_intermediate_left));
    System.out.println(Arrays.deepToString(m_intermediate_right));

这将返回:

[[1, 2], [3, 4], [9, 10], [11, 12]]

1  | 2
3  | 4
9  | 10
11 | 12

[[5, 6], [7, 8], [13, 14], [15, 16]]

5  | 6   
7  | 8  
13 | 14 
15 | 16

然后，您可以手动水平连接这些结果矩阵:

    int m_final[][] = new int[m_intermediate_left.length][m_intermediate_left[0].length+m_intermediate_right[0].length];

    // For each row of the final matrix
    for(int i = 0; i < m_final.length; i++) {
      // For each column of the final matrix     
      for (int j = 0; j < m_final[0].length; j++) {
        // If j corresponds to the left columns, add left matrix values 
        if (j < m_intermediate_left[0].length) {
            m_final[i][j] = m_intermediate_left[i][j];
        }
        // If j corresponds to the right columns, add the right matrix values
        else {
            m_final[i][j] = m_intermediate_right[i][j - m_intermediate_left[0].length];
        }
      }
    }

    System.out.println(Arrays.deepToString(m_final));

这将返回您的愿望矩阵:

[[1, 2, 5, 6], [3, 4, 7, 8], [9, 10, 13, 14], [11, 12, 15, 16]]

1  | 2   | 5  | 6 
3  | 4   | 7  | 8
9  | 10  | 13 | 14
11 | 12  | 15 | 16

请注意，如果您的象限大小不同，它将不起作用。

最佳