Monks & Matrices

Project Overview

This project explores matrix multiplication in C. We compare a regular matrix multiplication algorithm with a monk-based version that uses Strassen’s method for 2x2 block multiplication.

The main idea is simple: instead of one worker doing everything alone, we divide the work between several “monks.” Each monk is responsible for one part of the task, such as generating matrices, splitting matrices, calculating result blocks, or combining the final result.

The program randomly generates 4x4 matrices, multiplies them repeatedly based on user input, and measures the total running time.

The Problem We Are Solving

Matrix multiplication is used in many areas of computing, including graphics, engineering, data analysis, and machine learning. However, multiplying matrices can become computationally expensive as matrix size grows.

Regular matrix multiplication has a time complexity of:

O(n³)

This means that as matrices become larger, the amount of work grows very quickly. Our project explores whether a different structure, inspired by Strassen’s algorithm and parallel work, can help organize this computation more efficiently.

Two Matrix Multiplication Methods

1. Regular Matrix Multiplication

The regular method uses three nested loops. Each cell in the result matrix is calculated by multiplying one row from the first matrix by one column from the second matrix.

for (i = 0; i < 4; i++) {
    for (j = 0; j < 4; j++) {
        result[i][j] = 0;

        for (k = 0; k < 4; k++) {
            result[i][j] += A[i][k] * B[k][j];
        }
    }
}

Complexity: O(n³)

2. Monk-Based Strassen Multiplication

The Strassen version splits each 4x4 matrix into four 2x2 blocks. Instead of treating the matrix as one large structure, the code breaks it into smaller pieces.

First matrix: [ A B ]
[ C D ]

Second matrix: [ E F ]
[ G H ]

The result blocks are calculated as:

R1 = AE + BG
R2 = AF + BH
R3 = CE + DG
R4 = CF + DH

Theoretical Strassen complexity: O(n²·⁸⁰⁷)

The 9 Monk System

In our project, the monks represent divided tasks in the program. Each monk has one responsibility.

🧘 Monk 1

Randomly generates Matrix 1.

🧘 Monk 2

Randomly generates Matrix 2.

🧘 Monk 3

Splits both matrices into 2x2 blocks.

🧘 Monk 4

Calculates R1 = AE + BG.

🧘 Monk 5

Calculates R2 = AF + BH.

🧘 Monk 6

Calculates R3 = CE + DG.

🧘 Monk 7

Calculates R4 = CF + DH.

🧘 Monk 8

Combines the four result blocks.

🧘 Monk 9

Receives the final 4x4 matrix.

How the Programs Work

Program Flow

The program asks the user how many times the multiplication should be repeated.
It randomly generates two 4x4 matrices.
It multiplies the matrices.
It prints progress, such as Multiplication 1 completed.
It measures the total running time.
It prints the average time per multiplication.

Files

File	Description
`regular_matrix_timer.c`	Regular 4x4 matrix multiplication using the standard triple-loop method.
`monk_strassen_timer.c`	Monk-based matrix multiplication using threads and Strassen-style 2x2 block multiplication.
`README.md`	Explains how to compile, run, and test the project.
`DOCUMENTATION.md`	Explains the project purpose, goals, target audience, theory, and limitations.

Compilation Commands

Regular version:

gcc regular_matrix_timer.c -o regular_matrix_timer

Monk-based Strassen version:

gcc monk_strassen_timer.c -o monk_strassen_timer -pthread

Our Findings

In theory, Strassen’s algorithm has better complexity than regular matrix multiplication. However, in our 4x4 matrix tests, the parallelized Strassen version took longer than the regular method.

            Why? For small matrices, the overhead of splitting matrices, creating threads,
            combining results, and doing extra additions/subtractions can be larger than the time saved by reducing
            multiplication.
        

This means that faster theoretical complexity does not always mean faster performance in small practical tests. The advantages of Strassen’s algorithm are more likely to appear with much larger matrices and a more optimized recursive implementation.

What We Learned

Algorithms Matter

The same problem can be solved in different ways, and each method has advantages and disadvantages.

Parallelization Has Overhead

Dividing work between threads can help, but thread creation and management also take time.

Real Performance Depends on Context

A method that is faster in theory may not be faster for small inputs.

View README View Documentation