CS 3343/3341
  Introduction to Algorithms  
Spring 2012
Matrix Multiplication

The Java programs below are made simple for illustrative purposes. All array processing and declarations are hardwired for 2-by-2 arrays, and the Java code doesn't query for array dimensions. In examples in class I will normally use the long date type to get 64-bit integers, rather than 32-bit integers.

Java, without returning a matrix Java, returns a matrix
// Mat.java: multiply matrices, no returns
public class Mat {

   // z = x*y, mult of 2-by-2 matrices
   void mult(int x[][], int y[][], int z[][]){
      for (int i = 0; i < 2; i++) { //rows
         for (int j = 0; j < 2; j++) { //cols
            z[i][j] = 0;
            for (int k = 0; k < 2; k++)
               z[i][j] += x[i][k] * y[k][j];
         }
      }
   }



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

   public static void main(String[] argv) {
      Mat mat = new Mat();
      int [][] a = {{1, 2}, {4, 3}};
      int [][] b = {{4, 2}, {3, 5}};
      int [][] c = new int[2][2];
      mat.mult(a, b, c);
      mat.printMat(a);
      mat.printMat(b);
      mat.printMat(c);
   }
}

// Matr.java: multiply matrices, with returns
public class Matr {

   // z = x*y, mult of 2-by-2 matrices
   int[][] mult(int x[][], int y[][]){
      int[][] z = new int[2][2];
      for (int i = 0; i < 2; i++) { //rows
         for (int j = 0; j < 2; j++) { //cols
            z[i][j] = 0;
            for (int k = 0; k < 2; k++)
               z[i][j] += x[i][k] * y[k][j];
         }
      }
      return z;
   }

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

   public static void main(String[] argv) {
      Matr matr = new Matr();
      int [][] a = {{1, 2}, {4, 3}};
      int [][] b = {{4, 2}, {3, 5}};
      int [][] c = matr.mult(a, b);
      matr.printMat(a);
      matr.printMat(b);
      matr.printMat(c);
   }
}

Here again, the C code below on the left is another vanilla-flavored program, made especially simple. The C program on the right returns a matrix from a function. This is not possible directly as with the Java code above. Instead the way illustrated uses a typedef statement to create a type which is a pointer to a 2-by-2 array of ints. This is confusing enough, but the program also allocates storage dynamically down in the function mult, which under heavy usage would need to be deallocated. Normally in C one wants to allocate storage in the calling program to facilitate deallocation. (The Java program on the above right also allocates storage inside mult, but Java uses a garbage collector.) One could also use a C struct that contains only the array. Then this struct or a pointer to it could be returned from the function. Both approaches are pretty ugly.

C code, without returning a matrix C code, returns a pointer to a matrix
// mat.c: multiply matrices, no returns.
#include <stdio.h>

// z = x*y, mult of 2-by-2 matrices
void mult(int x[2][2], int y[2][2],
          int z[2][2]){
   int i, j, k;
   for (i = 0; i < 2; i++) {  // row
      for (j = 0; j < 2; j++) {  // col
         z[i][j] = 0;
         for (k = 0; k < 2; k++)
            z[i][j] += x[i][k] * y[k][j];
      }
   }
}





void printmat(int x[2][2]){
   int i, j;
   for (i = 0; i < 2; i++){
      printf("|");
      for (j = 0; j < 2; j++)
        printf("%3i ", x[i][j]);
      printf("|\n");
   }
   printf("\n");
}

int main(){
   int a[2][2] = {{1, 2}, {4, 3}}; 
   int b[2][2] = {{4, 2}, {3, 5}}; 
   int c[2][2];
   mult(a, b, c);
   printmat(a);
   printmat(b);
   printmat(c);
}

#include <stdio.h>   // for printf
#include <stdlib.h>  // for malloc
typedef int (*matrix)[2][2]; 

// z = x*y, mult of 2-by-2 matrices
matrix mult(matrix x, matrix y){
   // allocate storage; z is a pointer!
   matrix z = (matrix)malloc(4*sizeof(int));
   int i, j, k;
   for (i = 0; i < 2; i++) {  // each row
      for (j = 0; j < 2; j++) {  // each col
         (*z)[i][j] = 0;
         for (k = 0; k < 2; k++)
            (*z)[i][j] +=
               (*x)[i][k] * (*y)[k][j];
      }
   }
   return z;
}

void printmat(matrix x){
   int i, j;
   for (i = 0; i < 2; i++){
      printf("|");
      for (j = 0; j < 2; j++)
        printf("%3i ", (*x)[i][j]);
      printf("|\n");
   }
   printf("\n");
}

int main() {
   matrix a = (matrix) malloc(4*sizeof(int));
   (*a)[0][0]=1; (*a)[0][1]=2;
   (*a)[1][0]=4; (*a)[1][1]=3;
   matrix b = (matrix) malloc(4*sizeof(int));
   (*b)[0][0]=4; (*b)[0][1]=2;
   (*b)[1][0]=3; (*b)[1][1]=5;
   matrix c = mult(a, b);
   printmat(a);
   printmat(b);
   printmat(c);
}

All four programs here print the same 3 matrices:

| 1  2 |
| 4  3 |

| 4  2 |
| 3  5 |

| 10  12 |
| 25  23 |

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