Strassen Multiplication

Strassen multiplication, also known as the Strassen algorithm, is a fast algorithm used for multiplying large matrices. It was developed by Volker Strassen in 1969 and offers a more efficient approach compared to the traditional matrix multiplication algorithm, particularly for large matrices.

The concept of Strassen multiplication is based on the divide-and-conquer strategy, where the matrix multiplication problem is divided into smaller subproblems recursively. The algorithm relies on the observation that the product of two matrices can be expressed in terms of several smaller matrix multiplications, requiring fewer arithmetic operations overall.

The algorithm follows these steps:

Divide: Given two matrices A and B of size n x n, each matrix is divided into four equal-sized submatrices of size n/2 x n/2.

Conquer: Recursively compute the following seven matrix products:

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

Combine: Compute the resulting matrix C by combining the partial products as follows:

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

The resulting matrix C is the product of matrices A and B.