CoreSource checked

Strassen Algorithm

Multiplies matrices by replacing eight block multiplications with seven recursive products.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Numerical Methods
Difficulty: Intermediate
Family: Matrix Multiplication
Tier: Core
Status: Verified
Review: Source Checked
Sources: 3
Formulas: 1
Relationships: 6
Code example: Ready
Visualization: Ready

Overview

Strassen's Algorithm splits matrices into blocks and combines seven carefully chosen block products to reduce multiplication work below the classical cubic method.

Core Concepts

matrix multiplicationrecursionnumerical methods

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n^2)

Average

O(n^3)

Worst

O(n^3)

Space

O(n^2)

When to Use

Use it for sufficiently large dense square matrices where recursive overhead pays off.
Use it as part of a hybrid routine that falls back to classical multiplication on small blocks.
Use it when reduced multiplication count matters more than simple implementation.

When Not to Use

Avoid it for small matrices where extra additions dominate.
Avoid it when numerical stability or memory overhead is more important than asymptotic speed.
Avoid it for sparse matrices without preserving sparsity.

What It Does

Multiplies square matrices
Trades extra additions for fewer recursive multiplications

Use Cases

Large dense matrix multiplication
Teaching asymptotically faster matrix multiplication
Hybrid multiplication routines

Inputs

Numbers, vectors, matrices, or functions
Tolerance or precision settings

Outputs

Computed numeric result
Residual, factorization, or approximation

Key Formulas (1)

Recursive multiplication count

T(n) = 7·T(n/2) + O(n²)

T(n) = 7*T(n/2) + O(n^2)

Uses seven recursive block products instead of eight.

Pseudocode

1.Split each matrix into four blocks.
2.Form Strassen's seven block products from sums and differences.
3.Combine the products into the four output blocks.
4.Recurse on large blocks and use classical multiplication below the cutoff.
5.Return the product matrix.

Canonical Example

Input: two 2x2 matrices split into scalar blocks
Output: their 2x2 product
Explanation: Seven combined products are recombined to produce the four output blocks.

Implementation Notes

Pad or peel dimensions that are not powers of two.
Use a cutoff to switch to classical or blocked multiplication.
Reuse temporary buffers where possible.

Common Pitfalls

Using Strassen below a size threshold where it is slower than classical multiplication.
Allocating too many temporary matrices.
Ignoring padding and odd matrix dimensions.

Interactive Mechanism Walkthrough

Iterative Convergence & State Trajectory

Show reducing two-by-two block multiplication to seven recursive products on a small matrix multiplication example.

Step 1 of 5: Split each matrix into four blocks.

numerical-methods-mechanism

Notes

Strassen Algorithm operates in O(n^3) time and O(n^2) space within the Matrix Multiplication family. Key governing relation: T(n) = 7*T(n/2) + O(n^2). Often compared with Blocked Matrix Multiplication and Winograd Matrix Multiplication.