本連載の目的
本連載では, 高校数学レベルの知識を前提に,
Strassen（シュトラッセン）の行列積アルゴリズムについて解説します.
原論文は
Strassen, Volker (1969).
"Gaussian Elimination is not Optimal". Numer. Math. 13 (4): 354–356.
第1回では, 通常の（ナイーブな）行列積には8回の乗算が必要であることを確認し,
「この乗算回数を8回から7回に減らすことはできないか？」
という問いを提示しました.
第2回（最終回）となる今回は, その問いに対する解答として, Strassenが発見したアルゴリズムの具体的な構成を紹介し, 実際に計算が合うことを確かめます.
目次
前回 (Part 1/2)
- (ナイーブな)行列積アルゴリズムの復習
- 2次の実正方行列とは
- 2次の実正方行列同士の加算と減算
- 2次の実正方行列同士の乗算(ナイーブな行列積)
- 問いへの導入
- 中間値の定義（乗算パート）
- 行列積の再構成（加算パート）
- 問い：乗算回数を「7回」に減らせるか？
今回 (part 2/2)
- Strassenの行列積アルゴリズム
- 7個の中間値の構成（乗算パート）
- 行列積の再構成（加減算パート）
- 検証：本当に合っているのか？
- なぜ「7回」が重要なのか
- Strassenのその後
- Strassenの行列積は「パズル」か？
- 2次正方行列の行列積の乗算回数は「6回」に減らせるか？
- Strassenより高速な行列積アルゴリズムはあるのか？
- まとめ
Strassenの行列積アルゴリズム
行列積の乗算回数は7回に減らすことができます.
一方, 加減算の乗算回数は18回に増えます.
これを1969年に示したのがVolker Strassenです.
$n$を正の整数とすると,
ナイーブな行列積アルゴリズムは$n$次実正方行列に対して,
Strassenの行列積アルゴリズムは$2^n$次実正方行列に対して,
それぞれ定義可能です.
前回と同様, 簡単のため, 2次の実正方行列の場合を考えます.
前回の復習として, 2つの行列$A, B \in M_{2}(\mathbb{R})$を以下とします:
$$
A = \begin{pmatrix} a_{11} & a_{12} \\
a_{21} & a_{22} \end{pmatrix}, \quad
B = \begin{pmatrix} b_{11} & b_{12} \\
b_{21} & b_{22} \end{pmatrix}
$$ 目標は, 行列積 $$C := A \times B = \begin{pmatrix}
c_{11} & c_{12} \\
c_{21} & c_{22}
\end{pmatrix} \in M_{2}(\mathbb{R})$$ の各成分$c_{11}, c_{12}, c_{21}, c_{22}$を, 7回の乗算（7個の中間値）と加減算のみで表すことです.
1. 7個の中間値の構成（乗算パート）
ここがStrassenのアルゴリズムの核心部分です.
前回定義したナイーブな中間値とは異なり, 要素の和や差を掛け合わせることで,
以下の7個の中間値$P_{1}, \dots, P_{7}$を生成します.
$$
\begin{aligned}
P_1 &:= (a_{11}+a_{22}) \times (b_{11}+b_{22}) \\
P_2 &:= (a_{21}+a_{22}) \times b_{11} \\
P_3 &:= a_{11} \times (b_{12}-b_{22}) \\
P_4 &:= a_{22} \times (b_{21}-b_{11}) \\
P_5 &:= (a_{11}+a_{12}) \times b_{22} \\
P_6 &:= (a_{21}-a_{11}) \times (b_{11}+b_{12}) \\
P_7 &:= (a_{12}-a_{22}) \times (b_{21}+b_{22})
\end{aligned}
$$ 一見すると複雑で, どのような意図でこの組み合わせが選ばれたのか直感的には分かりにくいかもしれません.
しかし, 成分同士の乗算（$\times$）の回数を数えるだけなら簡単です.
各中間値$P_{i}$の生成では成分同士の乗算回数は1回,
7個の中間値 $P_{1}, \dots, P_{7}$の生成では成分同士の乗算回数の合計は7回です.
2. 行列積の再構成（加減算パート）
次に, これら7個の中間値 $P_{1}, \dots, P_{7}$ の加減算のみを使って, 行列積$C$の各成分を復元します.
$$
C = \begin{pmatrix}
c_{11} & c_{12} \\
c_{21} & c_{22}
\end{pmatrix}
= \begin{pmatrix}
P_1 + P_4 - P_5 + P_7 & P_3 + P_5 \\
P_2 + P_4 & P_1 + P_3 - P_2 + P_6
\end{pmatrix}
$$ これがStrassenによる解答です.
従って, 乗算回数の合計は7回, 加減算の合計回数は18回です.
(後述しますが, 実は, 加減算の回数が増えるのは一時的で,
行列サイズが大きくなると加減算の回数も減るようです).
第1回の「問い」で提示した形式に当てはめると, 例えば$c_{11}$は
$$
c_{11} = P_1 + P_4 - P_5 + P_7
$$ という形で, 4つの中間値の和と差のみで表現されています.
検証：本当に合っているのか？
「本当にこれで正しい行列積になるのか？」と疑問に思う方も多いでしょう.
例として, 左上成分$c_{11}$について計算を確認してみます.
本来（ナイーブな定義）であれば, $c_{11}$は以下の値になるはずです.
$$c_{11} = a_{11}b_{11} + a_{12}b_{21}$$ Strassenの式$P_1 + P_4 - P_5 + P_7$を展開して, これと一致するか確かめます.
ステップ1：各中間値を展開する $$
\begin{aligned}
P_1 &= (a_{11}+a_{22})(b_{11}+b_{22}) = a_{11}b_{11} + a_{11}b_{22} + a_{22}b_{11} + a_{22}b_{22} \\
P_4 &= a_{22}(b_{21}-b_{11}) = a_{22}b_{21} - a_{22}b_{11} \\
P_5 &= (a_{11}+a_{12})b_{22} = a_{11}b_{22} + a_{12}b_{22} \\
P_7 &= (a_{12}-a_{22})(b_{21}+b_{22}) = a_{12}b_{21} + a_{12}b_{22} - a_{22}b_{21} - a_{22}b_{22}
\end{aligned}
$$
ステップ2：式に代入して整理する
これらを $c_{11} = P_1 + P_4 - P_5 + P_7$ に代入します.
$$\begin{aligned}
c_{11} &= a_{11}b_{11} + a_{11}b_{22} + a_{22}b_{11} + a_{22}b_{22} & (\rightarrow P_{1})\\
&+ a_{22}b_{21} - a_{22}b_{11} & (\rightarrow P_{4})\\
&- (a_{11}b_{22} + a_{12}b_{22}) & (\rightarrow -P_{5})\\
&+ a_{12}b_{21} + a_{12}b_{22} - a_{22}b_{21} - a_{22}b_{22} & (\rightarrow P_{7})
\end{aligned}
$$
ステップ3：項を打ち消す
じっくり見ると, 多くの項がプラスとマイナスで打ち消し合います.
- $a_{11}b_{22}$ と $-a_{11}b_{22}$
- $a_{22}b_{11}$ と $-a_{22}b_{11}$
- $a_{22}b_{22}$ と $-a_{22}b_{22}$
- $a_{22}b_{21}$ と $-a_{22}b_{21}$
- $-a_{12}b_{22}$ と $a_{12}b_{22}$
これらがすべて消え, 残るのは...
$$
c_{11} = a_{11}b_{11} + a_{12}b_{21}
$$ 見事に, 本来の定義と一致しました！
他の成分$c_{12}, c_{21}, c_{22}$についても, 興味のある方はぜひ手を動かして確かめてみてください.
なぜ「7回」が重要なのか
最後に, この「1回の削減」が持つ意味について簡単に触れます.
「たった1回減っただけではないか」と思われるかもしれませんが,
行列のサイズが大きくなったときに劇的な差が生まれます.
$n$を正の整数とします. $2^n$次の正方行列に対して,
各アルゴリズムにおける乗算回数は以下になります
(ただし, Strassenの行列積アルゴリズムは再帰的に適用します).
- ナイーブな手法: $8^{n}$
- Strassenの手法: $7^{n}$
乗算回数を表に書いたのが以下です.
| $n$ | 行列のサイズ ($2^n$次正方行列) | ナイーブな手法 ($8^n$回) | Strassenの手法 ($7^n$回) | Strassen / ナイーブ $(\frac{7}{8})^n倍$ |
|---|---|---|---|---|
| 1 | 2 | 8 | 7 | 0.8750 |
| 2 | 4 | 64 | 49 | 0.7656 |
| 3 | 8 | 512 | 343 | 0.6699 |
| 4 | 16 | 4,096 | 2,401 | 0.5862 |
| 5 | 32 | 32,768 | 16,807 | 0.5129 |
| 6 | 64 | 262,144 | 117,649 | 0.4488 |
| 7 | 128 | 2,097,152 | 823,543 | 0.3927 |
| 8 | 256 | 16,777,216 | 5,764,801 | 0.3436 |
| 9 | 512 | 134,217,728 | 40,353,607 | 0.3007 |
| 10 | 1,024 | 1,073,741,824 | 282,475,249 | 0.2631 |
$n$が大きくなるにつれ, 乗算回数の差は大きくなっていくことが分かります.
一方, 加減算回数を表に書いたのが以下です.
| $n$ | 行列のサイズ ($2^n$次) | ナイーブな手法 ($8^{n}-4^{n}$回) | Strassenの手法 ($6(7^n - 4^{n})$回) | Strassen / ナイーブ |
|---|---|---|---|---|
| 1 | 2 | 4 | 18 | 4.5000 |
| 2 | 4 | 48 | 198 | 4.1250 |
| 3 | 8 | 448 | 1,674 | 3.7366 |
| 4 | 16 | 3,840 | 12,870 | 3.3516 |
| 5 | 32 | 31,744 | 94,698 | 2.9832 |
| 6 | 64 | 258,048 | 681,318 | 2.6403 |
| 7 | 128 | 2,080,768 | 4,842,930 | 2.3275 |
| 8 | 256 | 16,711,680 | 34,201,398 | 2.0466 |
| 9 | 512 | 133,955,584 | 240,544,314 | 1.7957 |
| 10 | 1,024 | 1,072,693,248 | 1,688,510,790 | 1.5741 |
| 11 | 2,048 | 8,585,732,096 | 11,850,560,946 | 1.3803 |
| 12 | 2,048 | 68,702,699,520 | 83,083,728,918 | 1.2093 |
| 13 | 8,192 | 549,705,826,304 | 581,894,809,794 | 1.0586 |
| 14 | 16,384 | 4,397,914,210,304 | 4,073,812,014,582 | 0.9263 |
| 15 | 32,768 | 35,183,923,200,000 | 28,517,544,310,200 | 0.8105 |
実は, $n$が大きくなるにつれて, ナイーブと比べると,
Strassenの加減算の回数も減っていくようです.
Strassenのその後
Strassenの行列積は「パズル」か？
Strassenの行列積を学ぶ際, 多くの人が抱くのが
「あのような複雑な中間値の組み合わせを, パズル的な発想ではなく,
数学的根拠に基づいて自然に導けないのか？」
という疑問です.
これらの中間値の構成は一見技巧的ですが, 以下の論文は代数的な構造や対称性を用いることで, それらを必然的なものとして導き出す「概念的な視点（conceptual perspective）」を与えてくれます
Christian Ikenmeyer, Vladimir Lysikov,
Strassen’s 2×2 matrix multiplication algorithm: A conceptual perspective ,
ANNALI DELL'UNIVERSITA' DI FERRARA, Volume 65, pages 241–248, (2019)
2次正方行列の行列積の乗算回数は「6回」に減らせるか？
Strassenの7回という乗算回数をさらに減らして6回にすることはできないのでしょうか？
結論から言いますと,
2次正方行列の行列積には「7回」の乗算が数学的に不可欠（下限値）であることが数学的に証明されています.
これは, 行列積という演算を3階のテンソルと見なした際の「テンソルランク」が7であるという事実に由来します.
大雑把には, このランク（階数）は, その演算を構成するのに必要な最小の乗算回数を意味します.
つまり, 2次正方行列の行列積における「7回」の乗算は数学的な下限であり, これ未満の回数で計算を行うアルゴリズムは理論上存在し得ないことが証明されています.
Strassenより高速な行列積アルゴリズムはあるのか？
例えば, 長方形行列($m \times n$行列と$n \times p$行列)に対するStrassenより高速な行列積アルゴリズムとして, 以下があります
Victor Ya. Pan,
Strassen's algorithm is not optimal: Trilinear technique of aggregating, uniting and canceling for constructing fast algorithms for matrix operations,
IEEE Symposium on Foundations of Computer Science; FOCS 1978
また, Strassen法よりも漸近的に高速な行列積アルゴリズムとして, 以下のような手法が知られており, そこで導入された独創的なアイデア(導入されたテンソル)は現代の最先端研究においても使われているようです
D. Coppersmith and S. Winograd,
Matrix multiplication via arithmetic
progressions,
Journal of Symbolic Computation 9 (1990), no. 3, 251–280.
以上, いくつか論文を紹介しました.
正直なところ, 私自身どれも深く理解できているわけではないのですが,
ぜひ各論文を参照してみてください.
まとめ
本連載では, 全2回にわたりStrassenの行列積アルゴリズムを紹介しました.
- 2次正方行列に対する通常の行列積は, 8回の中間値生成（乗算）と加算で構成される.
- 2次正方行列に対するStrassenの行列積は中間値を巧みに構成することで, 乗算を7回に減らすことができる.
- Strassenの手法を$2^n$次正方行列へ再帰的に適用することで, 乗算回数の削減効果は指数関数的$((\frac{7}{8})^{n}$倍)に積み重なり, サイズが大きくなるほどその差は開く.
一見不思議なパズルのような数式の裏側に, 計算機科学の重要なアイデアが詰まっています.
本連載が, アルゴリズムの面白さに触れるきっかけになれば幸いです.
本連載の記事の執筆にあたり, @0917laplaceさんに何度もレビューをいただきました.
この場を借りて感謝申し上げます.