DAA - LAB 03
Q1. Write a program in C language to multiply two matrices using Strassen’s matrix
multiplication technique using divide-and-conquer strategy with O(n2.81) time complexity.
#include <stdio.h>
#include <stdlib.h>
void additionOfMatrix(int n, int **a, int **b, int **result)
{ for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
{ result[i][j] = a[i][j] + b[i][j];
}
}
}
void subtractionOfMatrix(int n, int **a, int **b, int **result)
{ for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
{ result[i][j] = a[i][j] - b[i][j];
}
}
}
int **allocateMatrix(int n) {
int **matrix = (int **)malloc(n * sizeof(int *));
for (int i = 0; i < n; i++) {
matrix[i] = (int *)malloc(n * sizeof(int));
}
return matrix;
}
void freeMatrix(int **matrix, int n)
{ for (int i = 0; i < n; i++) {
free(matrix[i]);
}
free(matrix);
}
int **strassenMatrixMultiplication(int n, int **a, int **b)
{ int **C = allocateMatrix(n);
if (n == 1) {
C[0][0] = a[0][0] * b[0][0];
return C;
}
if (n == 2) {
int P = (a[0][0] + a[1][1]) * (b[0][0] + b[1][1]);
int Q = (a[1][0] + a[1][1]) * b[0][0];
int R = a[0][0] * (b[0][1] - b[1][1]);
int S = a[1][1] * (b[1][0] - b[0][0]);
int T = (a[0][0] + a[0][1]) * b[1][1];
int U = (a[1][0] - a[0][0]) * (b[0][0] + b[0][1]);
int V = (a[0][1] - a[1][1]) * (b[1][0] + b[1][1]);
C[0][0] = P + S - T + V;
C[0][1] = R + T;
C[1][0] = Q + S;
C[1][1] = P + R - Q + U;
return C;
}
int k = n / 2;
// Allocate submatrices
int **A11 = allocateMatrix(k);
int **A12 = allocateMatrix(k);
int **A21 = allocateMatrix(k);
int **A22 = allocateMatrix(k);
int **B11 = allocateMatrix(k);
int **B12 = allocateMatrix(k);
int **B21 = allocateMatrix(k);
int **B22 = allocateMatrix(k);
// Fill submatrices
for (int i = 0; i < k; i++)
{ for (int j = 0; j < k; j++)
{
A11[i][j] = a[i][j];
A12[i][j] = a[i][j + k];
A21[i][j] = a[i + k][j];
A22[i][j] = a[i + k][j + k];
B11[i][j] = b[i][j];
B12[i][j] = b[i][j + k];
B21[i][j] = b[i + k][j];
B22[i][j] = b[i + k][j + k];
}
}
// Allocate matrices for intermediate sums
int **sum1 = allocateMatrix(k);
int **sum2 = allocateMatrix(k);
int **sum3 = allocateMatrix(k);
int **sub1 = allocateMatrix(k);
int **sub2 = allocateMatrix(k);
int **sum4 = allocateMatrix(k);
int **sub3 = allocateMatrix(k);
int **sum5 = allocateMatrix(k);
int **sub4 = allocateMatrix(k);
int **sum6 = allocateMatrix(k);
// Calculate sums and differences
additionOfMatrix(k, A11, A22, sum1);
additionOfMatrix(k, B11, B22, sum2);
additionOfMatrix(k, A21, A22, sum3);
subtractionOfMatrix(k, B12, B22, sub1);
subtractionOfMatrix(k, B21, B11, sub2);
additionOfMatrix(k, A11, A12, sum4);
subtractionOfMatrix(k, A21, A11, sub3);
additionOfMatrix(k, B11, B12, sum5);
subtractionOfMatrix(k, A12, A22, sub4);
additionOfMatrix(k, B21, B22, sum6);
// Recursive multiplications
int **P = strassenMatrixMultiplication(k, sum1, sum2);
int **Q = strassenMatrixMultiplication(k, sum3, B11);
int **R = strassenMatrixMultiplication(k, A11, sub1);
int **S = strassenMatrixMultiplication(k, A22, sub2);
int **T = strassenMatrixMultiplication(k, sum4, B22);
int **U = strassenMatrixMultiplication(k, sub3, sum5);
int **V = strassenMatrixMultiplication(k, sub4, sum6);
// Compute result quadrants
for (int i = 0; i < k; i++) {
for (int j = 0; j < k; j++) {
C[i][j] = P[i][j] + S[i][j] - T[i][j] + V[i][j];
C[i][j + k] = R[i][j] + T[i][j];
C[i + k][j] = Q[i][j] + S[i][j];
C[i + k][j + k] = P[i][j] + R[i][j] - Q[i][j] + U[i][j];
}
}
return C;
}
int main()
{ int n = 4;
// Allocate matrices
int **mat1 = allocateMatrix(n);
int **mat2 = allocateMatrix(n);
// Initialize matrices
int values1[4][4] = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}
};
int values2[4][4] = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}
};
for (int i = 0; i < n; i++)
{ for (int j = 0; j < n; j++)
{
mat1[i][j] = values1[i][j];
mat2[i][j] = values2[i][j];
}
}
// Perform multiplication
int **result = strassenMatrixMultiplication(n, mat1, mat2);
// Print input matrices
printf("Input Matrix 1:\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
{ printf("%d ", mat1[i][j]);
}
printf("\n");
}
printf("\nInput Matrix 2:\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
printf("%d ", mat2[i][j]);
}
printf("\n");
}
// Print result matrix
printf("\nResult of Strassen Multiplication:\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
{ printf("%d ", result[i][j]);
}
printf("\n");
}
return 0;
}
OUTPUT:
