strassen

3 min read 16-10-2024

Strassen's Algorithm: A Faster Way to Multiply Matrices

Matrix multiplication is a fundamental operation in computer science, appearing in a wide range of applications from machine learning to computer graphics. While the standard algorithm has a time complexity of O(n^3), Strassen's algorithm provides a more efficient approach with a complexity of O(n^log₂7). This article explores the workings of Strassen's algorithm, its advantages and limitations, and provides a code example.

What is Strassen's Algorithm?

Strassen's algorithm, developed by Volker Strassen in 1969, is a divide-and-conquer algorithm for matrix multiplication. It cleverly breaks down the original matrices into smaller sub-matrices, performs a series of recursive multiplications and additions on these sub-matrices, and finally recombines the results to obtain the final product.

The key insight: Strassen's algorithm reduces the number of multiplications required compared to the standard algorithm by utilizing a specific set of seven multiplications instead of the usual eight. This reduction in multiplications leads to the lower time complexity of O(n^log₂7).

How Does It Work?

Divide: Given two n x n matrices, A and B, we divide them into four sub-matrices of size n/2 x n/2.
Conquer: We recursively multiply the sub-matrices using Strassen's algorithm itself.
Combine: We use seven specific multiplications and additions to combine the results of the sub-matrix multiplications to obtain the final product matrix.

Here's a simplified breakdown of the seven multiplications:

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)

The final product matrix C is obtained by adding and subtracting these P values:

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

Example:

Let's consider two 2x2 matrices:

A = [[1, 2],
     [3, 4]]

B = [[5, 6],
     [7, 8]]

Divide: We split A and B into sub-matrices:

A11 = [1], A12 = [2], A21 = [3], A22 = [4]
B11 = [5], B12 = [6], B21 = [7], B22 = [8]

Conquer: We recursively multiply the sub-matrices using Strassen's algorithm (which would involve further splitting for larger matrices).
Combine: We use the seven multiplications and additions as described above to get the final product matrix C.

Advantages and Disadvantages:

Advantages:

Faster than standard matrix multiplication: For large matrices, Strassen's algorithm offers significant performance improvements, especially for matrices with high dimensions.
Wide applicability: Strassen's algorithm finds use in various fields, including linear algebra, numerical analysis, and machine learning.

Disadvantages:

Overhead for small matrices: For smaller matrices, the overhead associated with the recursive calls and additions may outweigh the gains from reduced multiplications.
Numerical stability: Strassen's algorithm can be less numerically stable than standard matrix multiplication, particularly for matrices with high condition numbers.

Conclusion:

Strassen's algorithm offers a powerful alternative to standard matrix multiplication, providing significant performance gains for large matrices. However, it's crucial to consider the trade-offs between its advantages and disadvantages. In practice, choosing the optimal algorithm depends on the specific application and matrix size.

References:

Strassen's Matrix Multiplication Algorithm (Wikipedia)
Strassen's Matrix Multiplication (GeeksforGeeks)

Code Example (Python):

def strassen_matrix_multiply(A, B):
    n = len(A)

    # Base case: For small matrices, use standard multiplication
    if n <= THRESHOLD: 
        return [[sum(A[i][k] * B[k][j] for k in range(n)) 
                  for j in range(n)] for i in range(n)]

    # Divide matrices into sub-matrices
    A11, A12, A21, A22 = split_matrix(A)
    B11, B12, B21, B22 = split_matrix(B)

    # Recursively compute the seven products
    P1 = strassen_matrix_multiply(A11 + A22, B11 + B22)
    P2 = strassen_matrix_multiply(A21 + A22, B11)
    P3 = strassen_matrix_multiply(A11, B12 - B22)
    P4 = strassen_matrix_multiply(A22, B21 - B11)
    P5 = strassen_matrix_multiply(A11 + A12, B22)
    P6 = strassen_matrix_multiply(A21 - A11, B11 + B12)
    P7 = strassen_matrix_multiply(A12 - A22, B21 + B22)

    # Combine sub-results
    C11 = add_matrices(P1, P4)
    C12 = add_matrices(P3, P5)
    C21 = add_matrices(P2, P4)
    C22 = add_matrices(P1, P6)
    C22 = add_matrices(C22, P3)
    C22 = add_matrices(C22, P7)

    # Merge sub-matrices
    C = merge_matrices(C11, C12, C21, C22)

    return C

# Helper functions for splitting, adding, and merging matrices 
# (Implementations omitted for brevity)

THRESHOLD = 16 # Experiment with different threshold values

This code snippet demonstrates the recursive implementation of Strassen's algorithm. The THRESHOLD value defines the size of sub-matrices below which standard multiplication is used, as Strassen's algorithm becomes less efficient for smaller matrices. You can experiment with different threshold values to find the optimal balance for your application.