Introduction

Matrix Multiplication, termed as Matrix dot Product as well, is a form of multiplication involving two matrices Χ (n ✗ n), Υ (n ✗ n)like below:

$$ Z_{ij} = \sum_{k = 1}^{n} X_{ik}Y{kj}. $$ In the matrix multiplication formula, Xᵢₖ represents the element in the i-th row and k-th column of matrix Χ, while Yₖⱼ represents the element in the k-th row and j-th column of matrix Υ. These elements are multiplied and summed over k to compute the dot product for the resulting matrix Z at position (i, j).

This calculation involves Ο(n²) entries and Ο(n) operations for each entry, yielding an overall complexity of Ο(n³).

Naive Matrix Split

It is intuitive to devise a DnC pattern like below:

$$ X = \begin{bmatrix} A & B \\ C & D \end{bmatrix}, Y = \begin{bmatrix} E & F \\ G & H \end{bmatrix} $$

Each matrix operation involves:

  • 8 recursive sub-matrix multiplications
  • 4 additions

The resulting matrix dot product has 8 sub matrix products, 4 more additions and we could formulate a recurrence relation:

1

Τ(n) = 8 Τ(n / 2) + Ο(n^2)

Applying the Master Theorem, the complexity resolves to Ο(n³), which demonstrates no performance advantage over standard multiplication.

Strassen Matrix Multiplication

Proposed by Volker Strassen in 1969, this algorithm reduces the number of multiplications to 7 by leveraging a systematic decomposition:

$$ XY = \begin{bmatrix} P_5 + P_4 - P_2 + P_6 & P_1 + P_2 \\ P_3 + P_4 & P_1 + P_5 - P_3 - P_7 \end{bmatrix} $$

where, here are the calculations for P₁ - P₇ :

1
2
3
4
5
6
7

P₁ = A · (F - H)
P₂ = (A + B) · H
P₃ = (C + D) · E
P₄ = D · (G - E)
P₅ = (A + D) · (E + H)
P₆ = (B - D) · (G + H)
P₇ = (A - C) · (E + F)

Complexity Analysis

Time

The recurrence relation for Strassen’s algorithm is as follows:

1

Τ(n) = 7 Τ(n / 2) + Ο(n²)

Using the Master Theorem, the running time resolves to Ο(n^log~2~7^) ≈ Ο(n^2.81^), which is faster than the naive method’s Ο(n³).

Space

  • Additional space required for sub-matrices and intermediate products: Ο(n²)

History

Strassen’s algorithm was introduced by Volker Strassen, a German mathematician, in 1969. He demonstrated that the traditional matrix multiplication method’s time complexity of Ο(n³) was not optimal. His key contribution was a novel approach that reduced the number of multiplications required, achieving a complexity of Ο(n^(log₂7)) ≈ Ο(n^2․81). This breakthrough spurred further research in matrix multiplication, leading to even faster algorithms, such as the Coppersmith-Winograd algorithm.

Algorithm Overview

Strassen’s method is a Divide and Conquer (DnC) algorithm. Matrices are divided into smaller sub-matrices, recursively computed, and merged to form the final result. For smaller values of n (less than 45), traditional methods are preferred as they outperform Strassen’s in practical scenarios.

Reasoning

Strassen’s algorithm reduces the total number of multiplications while leveraging additional matrix operations. This is essential to improve computations for larger matrices and is significant in theoretical and practical applications where performance matters.

Approach

  1. Recursive Decomposition:
    • Split the matrices into quadrants.
    • Generate intermediary matrices (P₁, P₂, …, P₇).
  2. Matrix Operations:
    • Perform multiplications and additions based on the decomposition.
  3. Combine Results:
    • Merge the results into the final computed matrix.
  4. Recursive Depth:
    • Recursion stops when the matrix size becomes trivial (1 × 1).

Application

Here are some applications:

  1. Graph Theory: To compute adjacency matrices, transitive closures, and shortest paths.
  2. Scientific Computing: In numerical simulations and finite element methods.
  3. Machine Learning: For efficient neural network computations.
  4. Cryptography: In secure and large-scale matrix-based computations.

Code