本連載の目的
本連載では, 高校数学レベルの知識を前提に,
Strassen（シュトラッセン）の行列積アルゴリズムについて解説します.
原論文は
Strassen, Volker (1969).
"Gaussian Elimination is not Optimal". Numer. Math. 13 (4): 354–356.
特に, 高速化の鍵となる「乗算回数」に着目して話を進めていきます.
第1回(part1/2)となる今回は, 通常の（ナイーブな）行列積の計算手順を整理し,
本アルゴリズムの出発点となる「ある問い」を提示します.
第2回(part2/2)では, その問いに対する驚くべき解答として, Strassenの行列積アルゴリズムの核心に迫ります.
目次
今回 (Part 1/2)
- (ナイーブな)行列積アルゴリズムの復習
- 2次の実正方行列とは
- 2次の実正方行列同士の加算と減算
- 2次の実正方行列同士の乗算(ナイーブな行列積)
- 問いへの導入
- 中間値の定義（乗算パート）
- 行列積の再構成（加算パート）
- 問い：乗算回数を「7回」に減らせるか？
最終回 (part 2/2)
- Strassenの行列積アルゴリズム
- 7個の中間値の構成（乗算パート）
- 行列積の再構成（加減算パート）
- 検証：本当に合っているのか？
- なぜ「7回」が重要なのか
- Strassenのその後
- Strassenの行列積は「パズル」か？
- 2次正方行列の行列積の乗算回数は「6回」に減らせるか？
- Strassenより高速な行列積アルゴリズムはあるのか？
- まとめ
(ナイーブな)行列積アルゴリズムの復習
簡単のため, 本連載では2次の実正方行列のみを扱います.
以下では, $\mathbb{R}$を実数全体の集合とします.
集合$X$とその要素$a$に対し，$a$が$X$に属することを$a \in X$と表します.
2次の実正方行列とは
$a_{11}, a_{12}, a_{21}, a_{22} \in \mathbb{R}$とします.
$$A = \begin{pmatrix}
a_{11} & a_{12} \\
a_{21} & a_{22}
\end{pmatrix}$$ は, 4つの実数$a_{11}, a_{12}, a_{21}, a_{22}$を「縦に2行, 横に2列」に並べたものです.
このとき, $A$を2次の実正方行列と呼びます.
また, 行列の各要素を成分と呼び, $i$行$j$列に位置する成分を$(i,j)$成分と呼びます.
例えば, 行列$A$の$(1, 2)$成分は$a_{12}$です.
以下では, $M_{2}(\mathbb{R})$で2次の実正方行列全体の集合を表します.
2次の実正方行列同士の加算と減算
2つの行列
$$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} \in M_{2}(\mathbb{R})$$ に対して, 行列和$A + B \in M_{2}(\mathbb{R})$は以下で定義されます:
$$A + B := \begin{pmatrix}
a_{11}+b_{11} & a_{12}+b_{12} \\
a_{21}+b_{21} & a_{22}+b_{22}
\end{pmatrix} \in M_{2}(\mathbb{R}).$$
同様に, 行列差$A - B \in M_{2}(\mathbb{R})$は以下で定義されます:
$$A - B := \begin{pmatrix}
a_{11}-b_{11} & a_{12}-b_{12} \\
a_{21}-b_{21} & a_{22}-b_{22}
\end{pmatrix} \in M_{2}(\mathbb{R}).$$ 行列和や行列差と同様に行列積を定義することも考えられますが，
通常は次節で述べる定義を用います
(その理由は本題ではないため省略します).
2次の実正方行列同士の乗算(ナイーブな行列積)
まず, 2つの行列
$$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} \in M_{2}(\mathbb{R})$$ に対して, (ナイーブな)行列積$A \times B \in M_{2}(\mathbb{R})$は以下で定義されます:
$$A \times B := \begin{pmatrix}
a_{11} \times b_{11} + a_{12} \times b_{21} & a_{11} \times b_{12} + a_{12} \times b_{22} \\
a_{21} \times b_{11} + a_{22} \times b_{21} & a_{21} \times b_{12} + a_{22} \times b_{22}
\end{pmatrix} \in M_{2}(\mathbb{R}).$$ この定義において, 成分同士の乗算（$\times$）が何回行われているかを確認しましょう.
各成分に2回ずつ, 計4成分あるため, 乗算回数の合計は8回となります.
また, 加算回数の合計は4回です.
本連載では, 行列積における成分同士の乗算回数に着目します.
問いへの導入
(ナイーブな)行列積における「8回の乗算」を明確にするため,
以下の8個の中間値 $M_{1}, \dots, M_{8}$を導入して整理します:
1. 中間値の定義（乗算パート）
各中間値$M_{i}$の生成では, 成分同士の乗算回数は1回です.
したがって, 8個の中間値 $M_{1}, \dots, M_{8}$の生成では, 成分同士の乗算回数の合計は8回です.
$$\begin{align*}
M_1 &:= a_{11} \times b_{11} \\
M_2 &:= a_{12} \times b_{21} \\
M_3 &:= a_{11} \times b_{12} \\
M_4 &:= a_{12} \times b_{22} \\
M_5 &:= a_{21} \times b_{11} \\
M_6 &:= a_{22} \times b_{21} \\
M_7 &:= a_{21} \times b_{12} \\
M_8 &:= a_{22} \times b_{22}
\end{align*}$$
2. 行列積の再構成（加算パート）
これらの中間値$M_i$を用いると,
行列積$A \times B$は「中間値の和」のみで以下のように表せます:
$$A \times B := \begin{pmatrix}
M_{1} + M_{2} & M_{3} + M_{4} \\
M_{5} + M_{6} & M_{7} + M_{8}
\end{pmatrix} \in M_{2}(\mathbb{R}).$$ 特に, 行列積$A \times B \in M_{2}(\mathbb{R})$の各成分は中間値$M_{i} (1 \leq i \leq 8)$を使った和のみで書かれます.
以上により, 通常の行列積において「成分同士の乗算」が必要となるのは中間値$M_{1}, \dots, M_{8}$の生成時のみであり, その回数は8回であることが再確認できました.
問い：乗算回数を「7回」に減らせるか？
前節では, 8個の中間値を用いて, 行列積の計算に「8回の乗算と4回の加算」が必要であることを確認しました. 本連載では
「この乗算回数を8回から7回に減らすことはできないか？」
について考えてみます.
具体的には, 行列
$$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} \in M_{2}(\mathbb{R})$$ に対して,
- 7個の中間値 $P_{1}, \dots, P_{7}$ を「1回ずつの乗算」を用いて適切に構成する;
- それらの加減算のみを使って, 積行列
$$C := A \times B = \begin{pmatrix}
c_{11} & c_{12} \\
c_{21} & c_{22}
\end{pmatrix}$$ の各成分$c_{11}, c_{12}, c_{21}, c_{22}$を表現する.
つまり, 各成分$c_{11}, c_{12}, c_{21}, c_{22}$を以下のような形で表せないでしょうか？
$$\begin{align*}
c_{11} &= P_{?}\pm P_{?}\pm \dots \\
c_{12} &= P_{?}\pm P_{?}\pm \dots \\
c_{21} &= P_{?}\pm P_{?}\pm \dots \\
c_{22} &= P_{?}\pm P_{?}\pm \dots
\end{align*}$$
ただし, $?$は$1, 2, \ldots , 7$のいずれかであり, 重複を許すものとします.
もしこれが可能であれば, 「乗算」を1回分削減できることになります.
ぜひ, 少しだけ思考を巡らせてみてください.
Strassenによる驚きの解答は, 次回の記事でご説明します.