Strassenův algoritmus – blokové násobení matic

Vizualizace dělení na bloky A₁₁, A₁₂, A₂₁, A₂₂ a B₁₁, …, sedm mezimatic M₁…M₇ a rekonstrukce výsledných podmatic R₁₁…R₂₂. + Interaktivní příklad s maticemi 4×4 (bloky 2×2).

Vstupní matice A (4×4)

Rozdělení na bloky 2×2: A = \[ [A₁₁, A₁₂]; [A₂₁, A₂₂] \]

Vstupní matice B (4×4)

Rozdělení na bloky 2×2: B = \[ [B₁₁, B₁₂]; [B₂₁, B₂₂] \]

Bloková vizualizace

A (4×4)

A₁₁

A₁₂

A₂₁

A₂₂

B (4×4)

B₁₁

B₁₂

B₂₁

B₂₂

Strassen – 7 mezimatic

Operace probíhají na úrovni bloků (zde 2×2). Násobení je maticové 2×2; sčítání/odčítání je po prvcích.

M1 = (A11 + A22)(B11 + B22)

M2 = (A21 + A22)B11

M3 = A11(B12 − B22)

M4 = A22(B21 − B11)

M5 = (A11 + A12)B22

M6 = (A21 − A11)(B11 + B12)

M7 = (A12 − A22)(B21 + B22)

Rekonstrukce výsledku R = A·B

R11 = M1 + M4 − M5 + M7

R12 = M3 + M5

R21 = M2 + M4

R22 = M1 − M2 + M3 + M6

Výsledek (4×4)

Tento 4×4 výsledek vznikne složením bloků R₁₁, R₁₂, R₂₁, R₂₂.

Poznámky

Ukázka pracuje pro 4×4 matice jako 2×2 bloky (každý blok je 2×2 numerická matice).
Formule jsou obecné pro bloky libovolné velikosti, pokud jdou sčítat/odčítat a násobit.
Výhodnost Strassenova algoritmu se projeví při rekurzivním dělení velkých matic.