# Strassen’s Matrix Multiplication

April 27, 2023

Strassen’s Matrix Multiplication Algorithm is an algorithm used to multiply two matrices, resulting in a third matrix that contains the product of the two input matrices. The algorithm is used in a variety of scientific and engineering applications, including computer vision, machine learning, and numerical simulations.

The Strassen’s Matrix Multiplication Algorithm was first introduced by Volker Strassen in 1969. At the time, it was a revolutionary approach to matrix multiplication, as it was faster than the traditional matrix multiplication algorithm. Strassen’s algorithm was the first known algorithm that was faster than the traditional matrix multiplication algorithm, and it inspired further research into fast matrix multiplication algorithms.

Since its introduction, Strassen’s algorithm has been further developed and optimized by researchers around the world. Today, it remains an important algorithm in the field of numerical computation.

## Key Concepts and Principles

The key concept behind Strassen’s Matrix Multiplication Algorithm is the recursive decomposition of matrices. The algorithm works by dividing the two matrices into smaller submatrices, and then recursively multiplying these submatrices to obtain the product of the original matrices.

The algorithm requires that the matrices being multiplied have dimensions that are powers of 2. If the dimensions are not powers of 2, the matrices must be padded with zeros until they have dimensions that are powers of 2.

The algorithm also uses a set of seven multiplication operations and ten addition/subtraction operations to compute the product of the matrices.

## Pseudocode and Implementation Details

The pseudocode for Strassen’s Matrix Multiplication Algorithm is as follows:

``````function strassen(matrix A, matrix B):
if A and B are 1x1 matrices:
return A*B

n = size(A)[0]
mid = n/2

A11, A12, A21, A22 = A[:mid,:mid], A[:mid,mid:], A[mid:,:mid], A[mid:,mid:]
B11, B12, B21, B22 = B[:mid,:mid], B[:mid,mid:], B[mid:,:mid], B[mid:,mid:]

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

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

return concatenate(C11, C12, C21, C22)``````

The implementation details of the algorithm involve dividing the matrices into smaller submatrices, recursively multiplying the submatrices, and then combining them to obtain the product of the original matrices. The algorithm also uses a set of seven multiplication operations and ten addition/subtraction operations to compute the product of the matrices.

## Examples and Use Cases

Strassen’s Matrix Multiplication Algorithm has numerous applications in scientific and engineering fields, including computer vision, machine learning, and numerical simulations.

One example of using Strassen’s algorithm is in computer vision, where it can be used to compute the inner product of large vectors. Another example is in machine learning, where it can be used to compute the dot product of matrices, which is a common operation in many machine learning algorithms.