Matrix Multiplication Algorithms Comparison

This project implements and compares two matrix multiplication algorithms: the standard O(n³) algorithm and Strassen's O(n^log₂(7)) algorithm. The implementation includes performance testing and correctness verification.

Overview

Matrix multiplication is a fundamental operation in linear algebra and computer science. This project demonstrates the trade-offs between different algorithmic approaches:

• Standard Algorithm: Simple, straightforward implementation with O(n³) time complexity
• Strassen Algorithm: More complex divide-and-conquer approach with O(n^log₂(7)) ≈ O(n^2.81) time complexity

Files Description

Core Implementation Files

standard_multiply.py

Contains the standard matrix multiplication algorithm:

• Time Complexity: O(n³)
• Space Complexity: O(n²)
• Algorithm: Three nested loops performing dot product for each element
• Best for: Small matrices or when simplicity is preferred

strassen.py

Implements Strassen's matrix multiplication algorithm:

• Time Complexity: O(n^log₂(7)) ≈ O(n^2.81)
• Space Complexity: O(n²)
• Algorithm: Divide-and-conquer approach using 7 recursive multiplications instead of 8
• Best for: Large matrices where the asymptotic improvement matters

Key Functions:

• add_matrix(A, B): Matrix addition
• sub_matrix(A, B): Matrix subtraction
• split_matrix(M): Divides matrix into four quadrants
• combine_quadrants(C11, C12, C21, C22): Combines quadrants into result matrix
• strassen_multiply(A, B): Main Strassen algorithm implementation

compare.py

Performance comparison and testing script:

• Generates random test matrices
• Measures execution time for both algorithms
• Verifies correctness by comparing results
• Tests matrices of sizes 2×2, 4×4, and 8×8

Documentation

pseudocode.pdf

Contains the mathematical pseudocode and algorithm description for Strassen's matrix multiplication algorithm.

Algorithm Details

Standard Matrix Multiplication

The standard algorithm uses the definition of matrix multiplication:

C[i][j] = Σ(A[i][k] * B[k][j]) for k = 0 to n-1

Steps:

1. Initialize result matrix C with zeros
2. For each element C[i][j]:
   • Calculate dot product of row i from A and column j from B
   • Store result in C[i][j]

Strassen's Algorithm

Strassen's algorithm reduces the number of recursive multiplications from 8 to 7 by cleverly combining matrix operations.

Key Insight: Instead of computing 8 submatrix multiplications:

• A11×B11, A11×B12, A12×B21, A12×B22
• A21×B11, A21×B12, A22×B21, A22×B22

Strassen computes 7 products:

• P1 = A11 × (B12 - B22)
• P2 = (A11 + A12) × B22
• P3 = (A21 + A22) × B11
• P4 = A22 × (B21 - B11)
• P5 = (A11 + A22) × (B11 + B22)
• P6 = (A12 - A22) × (B21 + B22)
• P7 = (A11 - A21) × (B11 + B12)

Then combines them:

• C11 = P5 + P4 - P2 + P6
• C12 = P1 + P2
• C21 = P3 + P4
• C22 = P1 + P5 - P3 - P7

Installation and Requirements

Prerequisites

• Python 3.6 or higher
• NumPy library

Installation

pip install numpy

Usage

Running the Comparison

To run the performance comparison:

python compare.py

This will:

1. Generate random matrices of sizes 2×2, 4×4, and 8×8
2. Measure execution time for both algorithms
3. Verify correctness by comparing results
4. Display performance metrics

Expected Output

=== Comparison with 2x2 matrix ===
Standard multiplication time: 0.000012 seconds
Strassen multiplication time: 0.000045 seconds
✅ Results match!

=== Comparison with 4x4 matrix ===
Standard multiplication time: 0.000045 seconds
Strassen multiplication time: 0.000123 seconds
✅ Results match!

=== Comparison with 8x8 matrix ===
Standard multiplication time: 0.000234 seconds
Strassen multiplication time: 0.000456 seconds
✅ Results match!

=== Comparison with 1000x1000 matrix ===
Standard multiplication time: 52.808272 seconds
Strassen multiplication time: 40.234893 seconds
✅ Results match!

Using Individual Algorithms

Standard Multiplication

from standard_multiply import standard_matrix_multiply

A = [[1, 2], [3, 4]]
B = [[5, 6], [7, 8]]
result = standard_matrix_multiply(A, B)
print(result)  # [[19, 22], [43, 50]]

Strassen Multiplication

from strassen import strassen_multiply

A = [[1, 2], [3, 4]]
B = [[5, 6], [7, 8]]
result = strassen_multiply(A, B)
print(result)  # [[19, 22], [43, 50]]

Testing

Automated Testing

The compare.py script automatically tests both algorithms with:

• Random matrices of different sizes
• Correctness verification using NumPy's allclose() function
• Performance timing measurements

Manual Testing

You can create custom test cases:

import numpy as np
from standard_multiply import standard_matrix_multiply
from strassen import strassen_multiply

# Create test matrices
A = np.random.randint(0, 10, (4, 4)).tolist()
B = np.random.randint(0, 10, (4, 4)).tolist()

# Test both algorithms
result_standard = standard_matrix_multiply(A, B)
result_strassen = strassen_multiply(A, B)

# Verify correctness
print("Results match:", np.allclose(result_standard, result_strassen))

Performance Analysis

Time Complexity Comparison

Algorithm	Time Complexity	Space Complexity
Standard	O(n³)	O(n²)
Strassen	O(n^log₂(7))	O(n²)

When to Use Each Algorithm

Use Standard Algorithm when:

• Matrices are small (n < 100)
• Simplicity and readability are important
• Memory usage is a concern
• Working with non-square matrices

Use Strassen Algorithm when:

• Matrices are large (n > 100)
• Performance is critical
• Working with square matrices that are powers of 2
• The overhead of recursive calls is acceptable

Performance Notes

• For small matrices, the standard algorithm often performs better due to lower overhead
• Strassen's algorithm shows its advantage with larger matrices
• The crossover point depends on implementation details and hardware
• Strassen's algorithm requires matrices to be square and preferably powers of 2

Limitations

Strassen Algorithm Limitations

1. Matrix Size: Works best with square matrices that are powers of 2
2. Numerical Stability: May introduce more floating-point errors due to additional operations
3. Memory Overhead: Higher memory usage due to recursive calls and temporary matrices
4. Implementation Complexity: More complex to implement and debug

General Limitations

1. Matrix Requirements: Both algorithms assume square matrices
2. Memory Constraints: Large matrices may cause memory issues
3. Numerical Precision: Floating-point arithmetic limitations

Future Improvements

1. Hybrid Approach: Use Strassen for large matrices and standard for small ones
2. Padding: Handle non-power-of-2 matrices by padding
3. Parallelization: Implement parallel versions for better performance
4. Memory Optimization: Reduce memory usage in Strassen implementation
5. Numerical Stability: Improve floating-point precision handling

References

• Strassen, V. (1969). "Gaussian elimination is not optimal". Numerische Mathematik.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). "Introduction to Algorithms" (3rd ed.). MIT Press.

License

This project is for educational purposes. Feel free to use and modify the code for learning and research.