CS 3343/3341
  Introduction to Algorithms  
Ordinary Matrix Multiplication
Using Divide and Conquer

Here the programs are instrumented to record the number of multiplications and additions of ordinary numbers. (The changes are in red.) On the left is the normal 4-by-4 matrix multiplication. On the right is the 4-by-4 case done using divide and conquer, the 4-by-4 divided into 2-by-2s of 2-by-2s. In this second case, all the multiplication is done using 2-by-2 multiplication and addition. In the end the two approaches have exactly the same number of additions and multiplications.

4-by-4 Matrices 2-by-2 of 2-by-2 Matrices
// MatrRec.java: multiply matrices
//  Also record # of muls and # of adds
public class MatrRec {
   int muls = 0; // total multiplications
   int adds = 0; // total additions

   // C = A*B, mult of 4-by-4 matrices
   int[][] mult(int A[][], int B[][]){
      int[][] C = new int[4][4];
      for (int i = 0; i < 4; i++) { //rows
         for (int j = 0; j < 4; j++) { //cols
            C[i][j] = A[i][0] * B[0][j];
            muls++;
            for (int k = 1; k < 4; k++) {
               C[i][j] = C[i][j] + A[i][k] *
                  B[k][j];
               muls++;
               adds++;
            }
         }
      }
      return C;
   }

   void printMat(int A[][]){
      for (int i = 0; i < 4; i++){
         System.out.print("|");
         for (int j = 0; j < 4; j++)
           System.out.print(" "+A[i][j]+" ");
         System.out.print("|\n");
      }
      System.out.print("\n");
   }

   public static void main(String[] argv) {
      MatrRec matr = new MatrRec();
      int [][] A = {{2, 3, 1, 6},
                    {4, 0, 0, 2},
                    {4, 2, 0, 1},
                    {0, 3, 5, 2}};
      int [][] B = {{3, 0, 4, 3},
                    {1, 2, 0, 2},
                    {0, 3, 1, 4},
                    {5, 1, 3, 2}};
      int [][] C = matr.mult(A, B);
      matr.printMat(A);
      matr.printMat(B);
      matr.printMat(C);
      System.out.println("Total muls: " +
         matr.muls);
      System.out.println("Total adds: " +
         matr.adds);
   }
}

// Matr2Rec.java: multiply matrices
//  Also record # of muls and # of adds
public class Matr2Rec {
   int muls = 0;
   int adds = 0;

   // C = A*B, mult of 2-by-2 matrices
   int[][] mult(int A[][], int B[][]){
      int[][] C = new int[2][2];
      for (int i = 0; i < 2; i++) { //rows
         for (int j = 0; j < 2; j++) { //cols
            C[i][j] = A[i][0] * B[0][j];
            muls++;
            for (int k = 1; k < 2; k++) {
               C[i][j] = C[i][j] + A[i][k] *
                  B[k][j];
               muls++;
               adds++;
            }
         }
      }
      return C;
   }

   // C = A + B, addition of 2-by-2 matrices
   int[][] add(int A[][], int B[][]){
      int[][] C = new int[2][2];
      for (int i = 0; i < 2; i++) { //rows
         for (int j = 0; j < 2; j++) { //cols
            C[i][j] = A[i][j] + B[i][j];
            adds++;
         }
      }
      return C;
   }

   void printMat(int A[][]){
      for (int i = 0; i < 2; i++){
         System.out.print("|");
         for (int j = 0; j < 2; j++)
           System.out.print(" "+A[i][j]+" ");
         System.out.print("|\n");
      }
      System.out.print("\n");
   }

   public static void main(String[] argv) {
      Matr2Rec matr = new Matr2Rec();
      int [][] A11 = {{2, 3},
                      {4, 0}};
      int [][] A12 = {{1, 6},
                      {0, 2}};
      int [][] A21 = {{4, 2},
                      {0, 3}};
      int [][] A22 = {{0, 1},
                      {5, 2}};
      int [][] B11 = {{3, 0},
                      {1, 2}};
      int [][] B12 = {{4, 3},
                      {0, 2}};
      int [][] B21 = {{0, 3},
                      {5, 1}};
      int [][] B22 = {{1, 4},
                      {3, 2}};
      int [][] C11 = 
          matr.add(matr.mult(A11, B11),
                   matr.mult(A12, B21));
      matr.printMat(A11);
      matr.printMat(B11);
      matr.printMat(A12);
      matr.printMat(B21);
      matr.printMat(C11);
      System.out.println("-----------");
      int [][] C12 =
          matr.add(matr.mult(A11, B12),
                   matr.mult(A12, B22));
      matr.printMat(A11);
      matr.printMat(B12);
      matr.printMat(A12);
      matr.printMat(B22);
      matr.printMat(C12);
      System.out.println("-----------");
      int [][] C21 =
          matr.add(matr.mult(A21, B11),
                   matr.mult(A22, B21));
      matr.printMat(A21);
      matr.printMat(B11);
      matr.printMat(A22);
      matr.printMat(B21);
      matr.printMat(C21);
      System.out.println("-----------");
      int [][] C22 =
          matr.add(matr.mult(A21, B12),
                   matr.mult(A22, B22));
      matr.printMat(A21);
      matr.printMat(B12);
      matr.printMat(A22);
      matr.printMat(B22);
      matr.printMat(C22);
      System.out.println("-----------");
      System.out.println("Total muls: " +
         matr.muls);
      System.out.println("Total adds: " +
         matr.adds);
   }
}

First outputSecond Output
| 2  3  1  6 |
| 4  0  0  2 |
| 4  2  0  1 |
| 0  3  5  2 |

| 3  0  4  3 |
| 1  2  0  2 |
| 0  3  1  4 |
| 5  1  3  2 |

| 39  15  27  28 |
| 22   2  22  16 |
| 19   5  19  18 |
| 13  23  11  30 |

Total muls: 64
Total adds: 48

| 2  3 |
| 4  0 |

| 3  0 |
| 1  2 |

| 1  6 |
| 0  2 |

| 0  3 |
| 5  1 |

| 39  15 |
| 22   2 |


| 2  3 |
| 4  0 |

| 4  3 |
| 0  2 |

| 1  6 |
| 0  2 |

| 1  4 |
| 3  2 |

| 27  28 |
| 22  16 |


| 4  2 |
| 0  3 |

| 3  0 |
| 1  2 |

| 0  1 |
| 5  2 |

| 0  3 |
| 5  1 |

| 19   5 |
| 13  23 |


| 4  2 |
| 0  3 |

| 4  3 |
| 0  2 |

| 0  1 |
| 5  2 |

| 1  4 |
| 3  2 |

| 19  18 |
| 11  30 |

Total muls: 64
Total adds: 48

Revision date: 2012-09-26. (Please use ISO 8601, the International Standard Date and Time Notation.)