30

誰かが直感的な方法で行列乗算のための Strassen のアルゴリズムを説明できますか? 本と wiki の説明を確認しました (まあ、確認しようとしました) が、2 階をクリックしていません。正式な表記法などではなく英語を多く使用している Web 上のリンクも役立ちます。このアルゴリズムを暗記せずにゼロから構築するのに役立つ類似点はありますか?

4

3 に答える 3

41

次のように、2つの2x2行列を乗算することを検討してください。

A B * E F = AE+BG AF+BH
C D   G H   CE+DG CF+DH

右側を計算する明白な方法は、8つの乗算と4つの加算を行うことです。しかし、乗算は加算よりもはるかに高価であると想像してください。したがって、可能な限り乗算の数を減らしたいと考えています。Strassenはトリックを使用して、乗算を1つ減らし、加算（および減算）を大幅に増やして右側を計算します。

これが7つの乗算です：

M1 = (A + D) * (E + H) = AE + AH + DE + DH
M2 = (A + B) * H = AH + BH
M3 = (C + D) * E = CE + DE
M4 = A * (F - H) = AF - AH
M5 = D * (G - E) = DG - DE
M6 = (C - A) * (E + F) = CE + CF - AE - AF
M7 = (B - D) * (G + H) = BG + BH - DG - DH

したがって、AE + BGを計算するには、M1 + M7（AEとBGの項を取得）から始めて、AE + BGがすべて残るまで、他のMのいくつかを加算/減算します。奇跡的に、MはM1 + M7-M2+M5が機能するように選択されます。必要な他の3つの結果と同じです。

ここで、これが2x2行列だけでなく、A..Hが部分行列である任意の（偶数）サイズの行列に対して機能することを理解してください。

于 2009-12-17T18:01:54.983 に答える
29

私の意見では、あなたが得る必要がある3つのアイデアがあります：

  1. 行列をブロックに分割し、数値の行列の場合と同じように、結果のブロックの行列を操作できます。特に、このような2つのブロック行列を乗算して（もちろん、一方のブロック行の数が他方のブロック列の数と一致する限り）、元の数値行列を乗算する場合と同じ結果を得ることができます。

  2. 2x2ブロック行列の乗算の結果を表現するために必要なブロックには、元の式が示すよりも少ない乗算でそれらを計算できるようにするのに十分な共通の要素があります。これは、トニーの答えで説明されているトリックです。

  3. 再帰。

Strassenアルゴリズムは、上記の単なるアプリケーションです。その複雑さの分析を理解するには、Ronald Graham、Donald Knuth、およびOrenPatashnikによる「 ConcreteMathematics 」または同様の本を読む必要があります。

于 2009-12-17T09:30:06.467 に答える
26

ウィキペディアをざっと見てみると、このアルゴリズムは、方程式を再配置することによって必要な乗算の数をわずかに削減しているように見えます。

ここに類推があります。の乗算は何回x*x + 5*x + 6ですか? 2つですよね？の乗算は何回(x+2)(x+3)ですか? 1つですよね？でも表情は同じ！

注意してください、これがアルゴリズムの深い理解を提供するとは思いません.アルゴリズムが計算の複雑さの改善にどのようにつながる可能性があるかを理解できる直感的な方法です.

于 2009-12-17T07:58:21.673 に答える