How to combine some matrix into one?

Question

I'm triying to do a matrix multiplication with divide and conquer. So, I think, I already have the descompose part into subproblems (the recursive case and the base case).

Thus, I have four quadrants (left superior, left inferior, right superior, right inferior) and I'm thinking about how to combine those into a result matrix, and I don't have an idea.

I'm working with Java, so I have matrixA and matrixB, and I have some indexes like, matrixRowsA, matrixColumnsA, matrixRowsB, matrixColumnsB

By this way I'm avoiding to create new matrix and all that stuff that only makes more expensive the problem resolution.

So the basic question is, how to join 4 submatrix into a fill one?

So the method is call 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));

I'm testing with two matrix like:

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

First, you can concat vertically the left matrices (leftSuperiorQuadrant & leftInferiorQuadrant) and right matrices (rightSuperiorQuadrant & rightInferiorQuadrant) into a new columns matrices with 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));

This returns:

[[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

Then, you can concat these resulting matrices horizontally manually:

    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));

This returns your desire matrix:

[[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

Note that it won't work if your quadrants have different sizes.

Best