Square Matrix Multiply Recursive vs. Traditional Way-CodePudding

I implemented two algorithms for square matrix multiplication. multiply_normal is the traditional way, which uses 3 nested for loops and multiply is a recursive approach.

However, even though the multiply_normal algorithm gives the correct output, the other algorithm seems to fail to output correct result.

Here is the whole code:

public class App {
    public static void main(String[] args) throws Exception {
        int a[][] = { { 1, 1, 1 }, { 2, 2, 2 }, { 3, 3, 3 } };
        int b[][] = { { 1, 1, 1 }, { 2, 2, 2 }, { 3, 3, 3 } };

        print(multiply_normal(a, b));

        System.out.println();

        print(multiply(a, b));

    }

    public static int[][] multiply(int[][] A, int[][] B) {

        int n = A.length;

        int[][] R = new int[n][n];

        if (n == 1)

            R[0][0] = A[0][0] * B[0][0];

        else {

            int[][] A11 = new int[n / 2][n / 2];
            int[][] A12 = new int[n / 2][n / 2];
            int[][] A21 = new int[n / 2][n / 2];
            int[][] A22 = new int[n / 2][n / 2];
            int[][] B11 = new int[n / 2][n / 2];
            int[][] B12 = new int[n / 2][n / 2];
            int[][] B21 = new int[n / 2][n / 2];
            int[][] B22 = new int[n / 2][n / 2];

            split(A, A11, 0, 0);
            split(A, A12, 0, n / 2);
            split(A, A21, n / 2, 0);
            split(A, A22, n / 2, n / 2);

            split(B, B11, 0, 0);
            split(B, B12, 0, n / 2);
            split(B, B21, n / 2, 0);
            split(B, B22, n / 2, n / 2);

            // P:=M2 M3−M6−M7
            int[][] C11 = add(multiply(A11, B11), multiply(A12, B21));

            // Q:=M4 M6
            int[][] C12 = add(multiply(A11, B12), multiply(A12, B22));

            // R:=M5 M7
            int[][] C21 = add(multiply(A21, B11), multiply(A22, B21));

            // S:=M1−M3−M4−M5
            int[][] C22 = add(multiply(A21, B12), multiply(A22, B22));

            // Step 3: Join 4 halves into one result matrix
            join(C11, R, 0, 0);
            join(C12, R, 0, n / 2);
            join(C21, R, n / 2, 0);
            join(C22, R, n / 2, n / 2);
        }

        // Step 4: Return result
        return R;
    }

    // Method 2
    // Function to subtract two matrices
    public int[][] sub(int[][] A, int[][] B) {
        //
        int n = A.length;

        //
        int[][] C = new int[n][n];

        // Iterating over elements of 2D matrix
        // using nested for loops

        // Outer loop for rows
        for (int i = 0; i < n; i  )

            // Inner loop for columns
            for (int j = 0; j < n; j  )

                // Subtracting corresponding elements
                // from matrices
                C[i][j] = A[i][j] - B[i][j];

        // Returning the resultant matrix
        return C;
    }

    // Method 3
    // Function to add two matrices
    public static int[][] add(int[][] A, int[][] B) {

        //
        int n = A.length;

        // Creating a 2D square matrix
        int[][] C = new int[n][n];

        // Iterating over elements of 2D matrix
        // using nested for loops

        // Outer loop for rows
        for (int i = 0; i < n; i  )

            // Inner loop for columns
            for (int j = 0; j < n; j  )

                // Adding corresponding elements
                // of matrices
                C[i][j] = A[i][j]   B[i][j];

        // Returning the resultant matrix
        return C;
    }

    // Method 4
    // Function to split parent matrix
    // into child matrices
    public static void split(int[][] P, int[][] C, int iB, int jB) {
        // Iterating over elements of 2D matrix
        // using nested for loops

        // Outer loop for rows
        for (int i1 = 0, i2 = iB; i1 < C.length; i1  , i2  )

            // Inner loop for columns
            for (int j1 = 0, j2 = jB; j1 < C.length; j1  , j2  )

                C[i1][j1] = P[i2][j2];
    }

    // Method 5
    // Function to join child matrices
    // into (to) parent matrix
    public static void join(int[][] C, int[][] P, int iB, int jB)

    {
        // Iterating over elements of 2D matrix
        // using nested for loops

        // Outer loop for rows
        for (int i1 = 0, i2 = iB; i1 < C.length; i1  , i2  )

            // Inner loop for columns
            for (int j1 = 0, j2 = jB; j1 < C.length; j1  , j2  )

                P[i2][j2] = C[i1][j1];
    }

    public static int[][] multiply_normal(int[][] A, int[][] B) {
        int n = A.length;

        int C[][] = new int[n][n];

        for (int i = 0; i < n; i  ) {
            for (int j = 0; j < n; j  ) {
                C[i][j] = 0;
                for (int k = 0; k < n; k  ) {
                    C[i][j] = C[i][j]   A[i][k] * B[k][j];
                }
            }
        }

        return C;
    }

    public static void print(int[][] a) {
        for (int i = 0; i < a.length; i  ) {
            for (int k = 0; k < a.length; k  ) {
                System.out.print(a[i][k]   " ");
            }
            System.out.println();
        }
    }
}

The output of multiply_normal (inputs are in the main method):

6 6 6 
12 12 12 
18 18 18

The output of multiply:

3 3 0 
6 6 0 
0 0 0

So, where am I mistaken? What should I do to fix that? I would really appreciate if you can help me.

CodePudding user response：

After having reviewed the code briefly: In the given example n/2 equals 1 which is probably not what you wanted.
I expect both methods to produce the same result for an even size (say 4x4) matrix.

CodePudding user response：

Try using an alternative recursive algorithm implementation. Here's one which is guaranteed to work. Scroll down to see the Java code example.