C++で学ぶシュトラッセンの行列乗算アルゴリズム｜7つの式を簡単に覚える方法

シュトラッセンのアルゴリズムとは

シュトラッセンのアルゴリズム（Strassen's Algorithm）は、分割統治法に基づく行列乗算アルゴリズムです。同じサイズの2つの行列を乗算する際に使用され、従来の手法と比べて乗算の回数を削減できることで知られています。

通常の行列乗算

2つの行列の積を求める場合、一般的には以下のように計算します。

シュトラッセンのアルゴリズムによる乗算

シュトラッセンのアルゴリズムでは、乗算の手順を簡略化することで計算のオーバーヘッドを削減します。具体的には、以下の7つの積（M1〜M7）を求めます。

M1 = a × (f − h)
M2 = (a + b) × h
M3 = (c + d) × e
M4 = d × (g − e)
M5 = (a + d) × (e + h)
M6 = (b − d) × (g + h)
M7 = (a − c) × (e + f)

7つの式を簡単に覚えるコツ

これらの式は、いくつかのルールを押さえておけば簡単に記憶でき、アルゴリズムのコードも自然と導き出せるようになります。まず、以下の6つのポイントを覚えましょう。

• AHED：M1〜M4の最初の4つの値は「AHED」の順で覚えます。
• 対角乗算：M5は対角成分同士の掛け算で求めます。
• 後ろのCR：M6は「行列1の最後の列」と「行列2の最後の行」の組み合わせ（CR）を使用します。
• 前のCR：M7は「行列1の最初の列」と「行列2の最初の行」の組み合わせ（CR）を使用します。
• 行は足し算、列は引き算：行の要素を扱う場合は加算し、列の要素を扱う場合は減算します。
• 隣接する値で更新：その後、隣接する値を使って各値を更新していきます。

これらのルールを活用すれば、M1〜M7の値を無理なく覚えることができ、シュトラッセンのアルゴリズムをC++で実装する際にも大いに役立ちます。