4.
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.
code
#include <stdio.h>
#include <stdlib.h>
// Size of the matrix (must be power of 2 for Strassen)
#define SIZE 4
#define HALF SIZE/2
// Function to add two matrices
void addMatrix(int a[HALF][HALF], int b[HALF][HALF], int result[HALF][HALF]) {
for (int i = 0; i < HALF; i++)
for (int j = 0; j < HALF; j++)
result[i][j] = a[i][j] + b[i][j];
// Function to subtract two matrices
void subMatrix(int a[HALF][HALF], int b[HALF][HALF], int result[HALF][HALF]) {
for (int i = 0; i < HALF; i++)
for (int j = 0; j < HALF; j++)
result[i][j] = a[i][j] - b[i][j];
// Function to multiply two 2x2 matrices using Strassen's algorithm
void strassen2x2(int A[2][2], int B[2][2], int C[2][2]) {
int M1 = (A[0][0] + A[1][1]) * (B[0][0] + B[1][1]);
int M2 = (A[1][0] + A[1][1]) * B[0][0];
int M3 = A[0][0] * (B[0][1] - B[1][1]);
int M4 = A[1][1] * (B[1][0] - B[0][0]);
int M5 = (A[0][0] + A[0][1]) * B[1][1];
int M6 = (A[1][0] - A[0][0]) * (B[0][0] + B[0][1]);
int M7 = (A[0][1] - A[1][1]) * (B[1][0] + B[1][1]);
C[0][0] = M1 + M4 - M5 + M7;
C[0][1] = M3 + M5;
C[1][0] = M2 + M4;
C[1][1] = M1 - M2 + M3 + M6;
// Strassen’s method for 4x4 matrix multiplication
void strassen4x4(int A[SIZE][SIZE], int B[SIZE][SIZE], int C[SIZE][SIZE]) {
// Divide matrices into 2x2 blocks
int A11[HALF][HALF], A12[HALF][HALF], A21[HALF][HALF], A22[HALF][HALF];
int B11[HALF][HALF], B12[HALF][HALF], B21[HALF][HALF], B22[HALF][HALF];
int C11[HALF][HALF], C12[HALF][HALF], C21[HALF][HALF], C22[HALF][HALF];
int temp1[HALF][HALF], temp2[HALF][HALF];
// Splitting input matrices
for (int i = 0; i < HALF; i++) {
for (int j = 0; j < HALF; j++) {
A11[i][j] = A[i][j];
A12[i][j] = A[i][j + HALF];
A21[i][j] = A[i + HALF][j];
A22[i][j] = A[i + HALF][j + HALF];
B11[i][j] = B[i][j];
B12[i][j] = B[i][j + HALF];
B21[i][j] = B[i + HALF][j];
B22[i][j] = B[i + HALF][j + HALF];
// Calculate C submatrices
int P1[HALF][HALF], P2[HALF][HALF], P3[HALF][HALF], P4[HALF][HALF];
int P5[HALF][HALF], P6[HALF][HALF], P7[HALF][HALF];
int Atemp1[HALF][HALF], Atemp2[HALF][HALF];
int Btemp1[HALF][HALF], Btemp2[HALF][HALF];
// P1 = (A11 + A22)(B11 + B22)
addMatrix(A11, A22, Atemp1);
addMatrix(B11, B22, Btemp1);
strassen2x2(Atemp1, Btemp1, P1);
// P2 = (A21 + A22)B11
addMatrix(A21, A22, Atemp1);
strassen2x2(Atemp1, B11, P2);
// P3 = A11(B12 - B22)
subMatrix(B12, B22, Btemp1);
strassen2x2(A11, Btemp1, P3);
// P4 = A22(B21 - B11)
subMatrix(B21, B11, Btemp1);
strassen2x2(A22, Btemp1, P4);
// P5 = (A11 + A12)B22
addMatrix(A11, A12, Atemp1);
strassen2x2(Atemp1, B22, P5);
// P6 = (A21 - A11)(B11 + B12)
subMatrix(A21, A11, Atemp1);
addMatrix(B11, B12, Btemp1);
strassen2x2(Atemp1, Btemp1, P6);
// P7 = (A12 - A22)(B21 + B22)
subMatrix(A12, A22, Atemp1);
addMatrix(B21, B22, Btemp1);
strassen2x2(Atemp1, Btemp1, P7);
// C11 = P1 + P4 - P5 + P7
addMatrix(P1, P4, Atemp1);
subMatrix(Atemp1, P5, Atemp2);
addMatrix(Atemp2, P7, C11);
// C12 = P3 + P5
addMatrix(P3, P5, C12);
// C21 = P2 + P4
addMatrix(P2, P4, C21);
// C22 = P1 - P2 + P3 + P6
subMatrix(P1, P2, Atemp1);
addMatrix(Atemp1, P3, Atemp2);
addMatrix(Atemp2, P6, C22);
// Combine 4 submatrices into result matrix C
for (int i = 0; i < HALF; i++) {
for (int j = 0; j < HALF; j++) {
C[i][j] = C11[i][j];
C[i][j + HALF] = C12[i][j];
C[i + HALF][j] = C21[i][j];
C[i + HALF][j + HALF] = C22[i][j];
// Function to print matrix
void printMatrix(int M[SIZE][SIZE]) {
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++)
printf("%4d ", M[i][j]);
printf("\n");
int main() {
int A[SIZE][SIZE] = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9,10,11,12},
{13,14,15,16}
};
int B[SIZE][SIZE] = {
{1, 0, 0, 1},
{0, 1, 1, 0},
{1, 0, 1, 0},
{0, 1, 0, 1}
};
int C[SIZE][SIZE] = {0};
strassen4x4(A, B, C);
printf("Result of A x B:\n");
printMatrix(C);
return 0;