Computer Science Life Just another WordPress weblog

First post

Welcome to my blog. In my first post I will talk have a programing topic, more exactly a Divide and conquer problem : Matrix multiplication using this programming technique. We will show the simplest way, using  a particular case of matrices, square matrices with dimension being an even number (in order to keep the thing clear and concise ).

The idea is the follow : split each matrix in 4 square matrices till the dimension of this matrices is 2 . In this case, we will apply the known matrix multiplication.  Our function will have as arguments the input matrices, their dimension , the left upper corner coordinates ( line and column ) and the current dimension.

When the algorithm reaches matrices with dimension equal to 2 , proper elements in the matrix result are computed.

Here is the algorithm, written in C :

 


#include  <stdio.h>


#include <stdlib.h>


 


int **d = NULL ;        // global result matrix


/*


 *  reading  function


 * file_name file input name


 * n   dimension of the matrix


 * a, b   operand matrices


 */


void read(char* file_name, int *n, int ***a, int ***b) {


 int i, j;


 FILE *fd = fopen(file_name, "r");


 


 // dimension of the matrix


 fscanf(fd, "%i", n);


 


 // elements of  A


 *a = (int**)malloc((*n) * sizeof(int*));


 for (i = 0; i < *n; i++) {


  (*a)[i] = (int*)malloc((*n) * sizeof(int));


  for (j = 0; j < *n; j++) {


   fscanf(fd, "%i", &((*a)[i][j]));


  }


 }


 


 // elements of B


 *b = (int**)malloc((*n) * sizeof(int*));


 for (i = 0; i < *n; i++) {


  (*b)[i] = (int*)malloc((*n) * sizeof(int));


  for (j = 0; j < *n; j++) {


   fscanf(fd, "%i", &((*b)[i][j]));


  }


 }


 


 fclose(fd);


}


 


/*


 * iterative algorithm for multiplication


 * n  dimension


 * a, b  operands


 * c result  


 */


void matrix_multiply(int n, int **a, int **b, int ***c) {


 int i, j, k;


 


 *c = (int**)malloc((n) * sizeof(int*));


 // inmultire matrice 


 for (i = 0; i < n; i++) {


  (*c)[i] = (int*)malloc((n) * sizeof(int));


  for (j = 0; j < n; j++) {


   (*c)[i][j] = 0;


   for (k = 0; k < n; k++) {


    (*c)[i][j] += a[i][k] * b[k][j];


   }


  }


 }


}


 


 


/*


 * compare matrices


 * n dimension


 * a,b matrices


 * return 1/0  different/equal


 */


int matrix_cmp(int n, int **a, int **b) {


 int i, j;


 


 if ( (a == NULL) || (b == NULL) ) {


  return 1;


 }


 


 for (i = 0; i < n; i++) {


  for (j = 0; j < n; j++) {


   if (a[i][j] != b[i][j]) {


    return 1;


   }


  }


 }


 


 return 0;


}


 


/*


 * free memory


 * n dimension


 * a matrix


 */ 


void free_matrix(int n, int **a) {


 int i;


 for (i = 0; i < n; i++) {


  free(a[i]);


 }


 free(a);


}


 


 


void print_matrix(int n, int **a)


{


 for(int i=0; i<n; i++)


       {


         for (int j=0; j<n; j++)


         {


   printf("%i ",a[i][j]);


  }


 printf("\n");


       }


}


 


void DI_mm(int n, int **a, int **b, int lia, int cia, int lib, int cib, int dim) 


{


 int i;


 


 if ( dim == 2 )


 {


  d[lia][cib] += a[lia][cia] * b[lib][cib] + a[lia][cia + 1] * b[lib + 1][cib] ;


  d[lia][cib + 1] += a[lia][cia] * b[lib][cib + 1] + a[lia][cia + 1] * b[lib + 1][cib + 1] ;


  d[lia + 1][cib] += a[lia + 1][cia] * b[lib][cib] + a[lia + 1][cia + 1] * b[lib + 1][cib] ;


  d[lia + 1][cib + 1] += a[lia + 1][cia] * b[lib][cib + 1] + a[lia + 1][cia + 1] * b[lib + 1][cib + 1] ;


 }


 


 else


 {


  dim = dim / 2 ;


  DI_mm(n,a,b,lia,cia,lib,cib,dim); // 1


  DI_mm(n,a,b,lia,cia + dim,lib + dim,cib,dim); // 2


  DI_mm(n,a,b,lia,cia,lib,cib + dim,dim); // 3


  DI_mm(n,a,b,lia,cia + dim,lib + dim,cib + dim,dim);  // 4


  DI_mm(n,a,b,lia + dim,cia,lib,cib,dim);  // 5


  DI_mm(n,a,b,lia + dim,cia + dim,lib + dim,cib,dim); // 6


  DI_mm(n,a,b,lia + dim,cia,lib,cib + dim,dim); // 7


  DI_mm(n,a,b,lia + dim,cia + dim,lib + dim,cib + dim,dim);  // 8


 }


 


 


}


 


int main(int argc, char** argv) {


 


 int n; // dimensiune matrice


 int **a, **b, **c; // matrices


 char *in_file; // in file


  


 if (argc < 2) {


  fprintf(stderr,"Usage %s in_file\n", argv[0]);


  exit(1);


 }


  


 in_file = argv[1];


 


 // read matrices and their dimension


 read(in_file, &n, &a, &b);


 


 // iterative matrix multiply (c = a * b)


 matrix_multiply(n, a, b, &c);


 


 // matrix multiplication using DivideAndConquer (d = a * b)


 d = (int**)malloc((n) * sizeof(int*));


 


 for (int i = 0; i < n; i++) 


 {


 d[i] = (int*)malloc((n) * sizeof(int));


 } 


 


 for (int i = 0; i < n ;i++)


    for(int j = 0; j < n ;j++)


     d[i][j]  = 0;


 


 printf("a = \n");


 print_matrix(n,a);


 printf("\nb = \n");


  print_matrix(n,b);


 printf("\nc = \n");


 print_matrix(n,c);


 


 DI_mm(n,a,b,0,0,0,0,n);


 printf("\nd = \n");


 print_matrix(n,d);


 


 // verificare rezultat


 if (matrix_cmp(n, c, d)) {


  printf("Wrong answer\n");


 }


 else {


  printf("Corect\n");


 }


 


 // free memory


 free_matrix(n, a);


 free_matrix(n, b);


 free_matrix(n, c);


 // TODO free_matrix(n, d);


 


 return 0;


}