シュトラッセンのアルゴリズムの証明
アルゴリズム
$k \in \mathbb{N}$について$n=2^{k}$としよう。$A, B \in \mathbb{R}^{n \times n}$に対してジョルダンブロックの行列表現を使って、以下の8つの${{n} \over {2}} \times {{n} \over {2}}$行列$A_{i}$、$B_{i}$を考えよう。 $$ AB= \begin{bmatrix} A_{1} & A_{2} \\ A_{3} & A_{4} \end{bmatrix} \begin{bmatrix} B_{1} & B_{2} \\ B_{3} & B_{4} \end{bmatrix} = \begin{bmatrix} C_{1} & C_{2} \\ C_{3} & C_{4} \end{bmatrix} = C $$ $C = AB$を計算するため、以下を計算する。 $$ P_{1} = A_{1} ( B_{2} - B_{4} ) \\ P_{2} = ( A_{1} + A_{2} ) B_{4} \\ P_{3} = ( A_{3} + A_{4} ) B_{1} \\ P_{4} = A_{4} ( B_{3} - B_{1} ) \\ P_{5} = (A_{1} + A_{4}) ( B_{1} + B_{4} ) \\ P_{6} = (A_{2} - A_{4}) ( B_{3} + B_{4} ) \\ P_{7} = (A_{3} - A_{1}) ( B_{1} + B_{2} ) $$
$$ C_{1} = -P_{2} + P_{4}+ P_{5} + P_{6} \\ C_{2} = P_{1} + P_{2} \\ C_{3} = P_{3} + P_{4} \\ C_{4} = P_{1} - P_{3} + P_{5} + P_{7} $$ $A_{i} B_{j}$を計算する時も同じ方法を繰り返すと、その時間複雑性は$\Theta ( n^{2.807} )$である。
- もちろん、$n \ne 2^{k}$として使えないわけではなく、サイズを調整してそのまま適応してもいい。
説明
当たり前で、すぐに思いつく行列の乗算は $$ C_{1} = A_{1}B_{1} + A_{2} B_{3} \\ C_{2} = A_{1}B_{2} + A_{2} B_{4} \\ C_{3} = A_{3}B_{1} + A_{4} B_{3} \\ C_{4} = A_{3}B_{2} + A_{4} B_{4} $$ この計算を続ければいいが、ここにかかる時間が$\Theta ( n^3 )$だということは疑う余地がなかった。シュトラッセンが生まれる前まではね。
このアルゴリズムは非常に革新的で、本来は1つの$C_{i}$を計算するのには必ず2回の行列乗算が必要だった。合わせて一度計算するたびに8回計算しなければならなかったが、シュトラッセンはこれを7回に減らした。そもそも別の方法があるかもしれないと考えたことからして異常なセンスで、本当に見つけたことは不思議とさえ言えるだろう。このアルゴリズムの開発によって、行列計算に使われたであろう資源を少しでも、いや、大量に節約できる。
証明
パート 1. 計算可能性
直接計算してみるしかない。
パート 1-1. $C_{1} = A_{1}B_{1} + A_{2} B_{3}$
$$ \begin{align*} C_{1} =& -P_{2} + P_{4} + P_{5} + P_{6} \\ =& ( {\color{red}- A_{1} B_{4}} - A_{2} B_{4} ) + P_{4} + ( A_{1}B_{1} + {\color{red} A_{1}B_{4} } + A_{4} B_{1} + A_{4}B_{4} ) + P_{6} \\ =& - A_{2} B_{4} + (A_{4} B_{3} {\color{red}- A_{4} B_{1} }) + A_{1}B_{1} + {\color{red} A_{4} B_{1} } + A_{4}B_{4} + P_{6} \\ =& {\color{red} - A_{2} B_{4} } + \color{blue}{A_{4} B_{3} } + A_{1}B_{1} + \color{green}{A_{4}B_{4}} + ( A_{2} B_{3} + {\color{red} A_{2} A_{4} } \color{blue}{ - A_{4} B_{3} }- \color{green}{A_{4} B_{4}}) \\ =& A_{1}B_{1} + A_{2} B_{3} \end{align*} $$
パート 1-2. $C_{2} = A_{1}B_{2} + A_{2} B_{4}$
$$ \begin{align*} C_{2} =& P_{1} + P_{2} \\ =& (A_{1}B_{2} {\color{red}- A_{1} B_{4}}) + ( {\color{red}A_{1} B_{4}} + A_{2} B_{4}) \\ =& A_{1}B_{2} + A_{2} B_{4} \end{align*} $$
パート 1-3. $C_{3} = A_{3}B_{1} + A_{4} B_{3}$
$$ \begin{align*} C_{3} =& P_{3} + P_{4} \\ =& (A_{3}B_{1} + {\color{red} A_{4}B_{1}}) + (A_{4}B_{3} {\color{red}- A_{4}B_{1}}) \\ =& A_{3}B_{1} + A_{4} B_{3} \end{align*} $$
パート 1-4. $C_{4} = A_{3}B_{2} + A_{4} B_{4}$
$$ \begin{align*} C_{4} =& P_{1} - P_{3} + P_{5} + P_{7} \\ =& (A_{1}B_{2} {\color{red} - A_{1} B_{4} } ) - P_{3} + ( A_{1}B_{1} + {\color{red} A_{1}B_{4} } + A_{4}B_{1} + A_{4}B_{4}) + P_{7} \\ =& A_{1}B_{2} + (- A_{3}B_{1} - {\color{red}A_{4}B_{1}}) + A_{1}B_{1} + {\color{red}A_{4}B_{1}} + A_{4}B_{4} + P_{7} \\ =& {\color{red} A_{1}B_{2}} - \color{blue}{A_{3}B_{1}} + \color{green}{A_{1}B_{1}}+ A_{4}B_{4} + ( \color{blue}{A_{3}B_{1}} + A_{3}B_{2} - \color{green}{A_{1}B_{1}} {\color{red}- A_{1}B_{2}}) \\ =& A_{3}B_{2} + A_{4} B_{4} \end{align*} $$
パート 2. 時間複雑性
本質的には、元の計算法が$\Theta ( n^3 )$と認識されたことを証明した方法と同じだ。1回の計算にかかる時間が$T(n)$で、繰り返しの外での実行時間が$c$であれば、$\displaystyle T(n) = 7 T \left( {{n} \over {2}} \right) + c$であるため、
$$ \begin{align*} T(n) =& 7 T \left( {{n} \over {2}} \right) + c \\ =& 7 \left[ 7 T \left( {{n} \over {4}} \right) + c \right] + c \\ =& 7 \left[ 49 T \left( {{n} \over {8}} \right) + 7 c + c \right] + c \\ =& 7^3 T \left( {{n} \over {8}} \right) + (1+7+7^2)c \\ =& 7^3 T \left( {{n} \over {8}} \right) + {{7^3 - 1} \over {7 - 1}}c \\ & \vdots & \\ \approx& 7^{\log_{2} n} ( T(1) + c ) \\ =& n^{\log_{2} 7} ( T(1) + c ) \\ =& n^{2.807} ( T(1) + c ) \\ =& \Theta \left( n{^2.807} \right) \end{align*} $$
■