Strassen's Algorithm

Multiplying two matrices is one of the most executed operations in computing — it sits at the core of graphics, scientific simulation, machine learning, and cryptography. Every student learns the schoolbook method: to multiply two n×n matrices, compute each of the $n^{2}$ entries by taking the dot product of a row and a column, costing n multiplications apiece. Total: $n^{3}$ multiplications. Simple, obvious — and, as it turns out, not optimal.

In 1969, the German mathematician Volker Strassen published a stunning surprise. He showed that two 2×2 matrices can be multiplied using only 7 scalar multiplications instead of the naive 8 — at the cost of some extra additions. Because matrix multiplication is recursive, that one saved multiply per level compounds across the recursion tree, pushing the total cost from $O(n^{3})$ to $O(n^{2.807})$. For large matrices the difference is enormous.

The algorithm launched an entire research program. Strassen's result was the first proof that the schoolbook bound is not a law of nature, and the race to find the true exponent $\omega$ has not stopped since.

Enter any two 2×2 matrices below. Click Multiply (Strassen) to compute the product using exactly 7 scalar multiplications — M1 through M7 — plus some additions and subtractions. Then click Multiply (Schoolbook) to see all 8 multiplications used the naive way.

<div class="demo-wrap">
  <div class="matrices">
    <div class="mat-block">
      <div class="mat-label">{{matrix_a}}</div>
      <div class="mat-grid">
        <input id="a00" type="number" value="1" /><input id="a01" type="number" value="2" />
        <input id="a10" type="number" value="3" /><input id="a11" type="number" value="4" />
      </div>
    </div>
    <div class="times-sign">×</div>
    <div class="mat-block">
      <div class="mat-label">{{matrix_b}}</div>
      <div class="mat-grid">
        <input id="b00" type="number" value="5" /><input id="b01" type="number" value="6" />
        <input id="b10" type="number" value="7" /><input id="b11" type="number" value="8" />
      </div>
    </div>
    <div class="equals-sign">=</div>
    <div class="mat-block result-block">
      <div class="mat-label">{{result_c}}</div>
      <div class="mat-grid">
        <div class="res-cell" id="c00">?</div><div class="res-cell" id="c01">?</div>
        <div class="res-cell" id="c10">?</div><div class="res-cell" id="c11">?</div>
      </div>
    </div>
  </div>
  <div class="btns">
    <button id="btn-strassen" type="button">{{btn_strassen}}</button>
    <button id="btn-schoolbook" type="button" class="ghost">{{btn_schoolbook}}</button>
    <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
  </div>
  <div class="counters">
    <div class="counter-box" id="box-strassen">
      <div class="counter-label">{{lbl_strassen_mults}}</div>
      <div class="counter-num" id="cnt-strassen">–</div>
    </div>
    <div class="counter-box" id="box-schoolbook">
      <div class="counter-label">{{lbl_schoolbook_mults}}</div>
      <div class="counter-num" id="cnt-schoolbook">–</div>
    </div>
  </div>
  <div id="steps-panel" class="steps-panel"></div>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.demo-wrap { max-width: 540px; margin: 0 auto; }
.matrices { display: flex; align-items: center; gap: .6rem; flex-wrap: wrap; margin-bottom: .8rem; }
.mat-block { display: flex; flex-direction: column; align-items: center; gap: .3rem; }
.mat-label { font-size: .78rem; font-weight: 700; color: #1d3557; text-transform: uppercase; letter-spacing: .05em; }
.mat-grid { display: grid; grid-template-columns: 1fr 1fr; gap: 4px; }
.mat-grid input { width: 52px; height: 44px; font: 700 16px ui-monospace, monospace; text-align: center;
                  border: 1.5px solid #c0cad4; border-radius: 8px; background: #f4f7fa; color: #1d3557;
                  padding: 0; -moz-appearance: textfield; }
.mat-grid input::-webkit-outer-spin-button,
.mat-grid input::-webkit-inner-spin-button { -webkit-appearance: none; }
.mat-grid input:focus { outline: none; border-color: #1d3557; background: #fff; }
.times-sign, .equals-sign { font-size: 1.6rem; font-weight: 300; color: #5a7088; align-self: center; }
.result-block .mat-grid { gap: 4px; }
.res-cell { width: 52px; height: 44px; display: flex; align-items: center; justify-content: center;
            font: 700 16px ui-monospace, monospace; background: #e8eef3; border-radius: 8px;
            border: 1.5px solid #c0cad4; color: #1d3557; transition: background .3s; }
.res-cell.lit { background: #d4edda; border-color: #0a7d33; color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .8rem; }
button { font: 600 13px system-ui, sans-serif; padding: .45rem .85rem; border: 1.5px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; white-space: nowrap; }
button.ghost { background: #fff; color: #1d3557; }
button:hover { opacity: .88; }
.counters { display: flex; gap: .6rem; margin-bottom: .8rem; }
.counter-box { flex: 1; background: #f4f7fa; border-radius: 8px; padding: .5rem .7rem; text-align: center;
               border: 1.5px solid #c0cad4; transition: border-color .3s; }
.counter-box.active { border-color: #1d3557; }
.counter-label { font-size: .73rem; font-weight: 600; color: #5a7088; margin-bottom: .25rem; }
.counter-num { font: 700 2rem ui-monospace, monospace; color: #1d3557; }
.counter-num.highlight { color: #0a7d33; }
.steps-panel { background: #f4f7fa; border-radius: 8px; padding: .6rem .8rem; font-size: .82rem;
               line-height: 1.7; min-height: 2rem; border: 1.5px solid #e0e6ec; display: none; }
.steps-panel.visible { display: block; }
.step-row { display: flex; gap: .4rem; align-items: baseline; }
.step-name { font-weight: 700; color: #1d3557; min-width: 2.4rem; }
.step-val { font: 600 .82rem ui-monospace, monospace; color: #333; }
.method-title { font-weight: 700; font-size: .85rem; color: #1d3557; margin-bottom: .3rem; }
.divider { border: none; border-top: 1px solid #d0d8e0; margin: .5rem 0; }

// Code not found

Watch the multiplication counter on each side. The schoolbook needs 8 multiplications; Strassen uses only 7. For a single 2×2 case the savings look modest, but recurse this on n×n blocks and the gap grows to $O(n^{2.807})$ vs $O(n^{3})$.

The schoolbook algorithm satisfies the recurrence $T(n) = 8 \cdot T(n/2) + O(n^{2})$, which the Master Theorem resolves to $O(n^{3})$. Strassen's key insight is to reorganize the 2×2 multiply so that 7 recursive calls replace 8 — at the price of 18 additions instead of 4. The recurrence becomes $T(n) = 7 \cdot T(n/2) + O(n^{2})$, giving:

$$T(n) = O\!\left(n^{\log_2 7}\right) \approx O(n^{2.807})$$

The exponent shrinks because $\log_{2}7 \approx 2.807 < 3$. Additions are cheap compared to multiplications in this analysis — and in practice, for large n, the lower asymptotic exponent wins.

Status: solved, with an open frontier.

• Strassen (1969) proved $\omega \le \log_2 7 \approx 2.807$ — the first sub-cubic result, and a fact established beyond any doubt.
• The question of the true exponent $\omega$ of matrix multiplication — the smallest possible power — is still open. Many researchers conjecture $\omega = 2$ (i.e., it might be doable in nearly quadratic time).
• The current best published bound is $\omega < 2.371552$ (Williams et al., 2024), using algebraic techniques far removed from Strassen's elegant 7-product formula.
• For practical sizes, Strassen (or a small constant number of recursive levels) often wins over schoolbook, but cache effects and constant factors mean implementations switch between methods at runtime.

Strassen's algorithm lives in the solved camp for the original question he asked: "Is $O(n^{3})$ optimal for matrix multiplication?" The answer is definitively no. What remains open is how far below 3 the exponent $\omega$ can go.

Matrix multiplication is the inner loop of modern computing. Making it faster has cascading benefits:

• Deep learning: training large neural networks is dominated by matrix multiplications in each layer. Every fraction of an exponent saved translates to real time and energy savings at scale.
• Scientific computing: fluid dynamics, quantum chemistry, and finite-element analysis all reduce to solving large linear systems — which in turn reduce to matrix products.
• Computer graphics and computer vision: transformation pipelines, rendering, and convolutional operations are matrix multiplications under the hood.
• Theoretical reductions: dozens of other algorithmic problems — computing determinants, matrix inversion, solving linear systems, polynomial multiplication — are known to be equivalent to matrix multiplication in complexity. Faster matrix multiply automatically speeds all of them up.
• Cryptography: some post-quantum schemes rely on lattice operations that decompose into matrix products over modular rings.

The practical BLAS libraries used by NumPy, PyTorch, and TensorFlow all apply Strassen-style tricks (or hardware-optimized equivalents) for large matrices. The theoretical race for ω matters not just for theoreticians but for every GPU-hours budget on the planet.

See also fast multiplication for how the same divide-and-conquer insight appears in integer and polynomial multiplication.

Strassen's algorithm is a masterpiece of algorithmic thinking: a handful of clever algebraic identities that save a single multiplication per recursive step, compounding across levels into a provably faster algorithm for one of the most fundamental operations in computing.

The schoolbook method was assumed optimal for centuries. Strassen showed in 1969 that assumption was wrong, and the search for the true matrix-multiplication exponent $\omega$ has driven theoretical computer science ever since. We know $\omega < 2.372$ today, and many believe $\omega = 2$ — but the proof remains elusive.

The next time you run a neural network or solve a linear system, billions of multiplications are executing somewhere along the recursion tree that Strassen first climbed. And at each branching point, 7 is doing the work that 8 used to — a small miracle of mathematics that scales.