Strassenのアルゴリズムを打ち消すアルゴリズム

-4

教授Caesarは、Strassenのアルゴリズムよりも漸進的に速いの行列乗算アルゴリズムを開発したいと考えています。彼のアルゴリズムは、各マトリックスをサイズn/4 x n/4の断片に分割し、分割と結合のステップを一緒にすると、シータ（n^2）時間になる分割と征服の方法を使用します。Strassenのアルゴリズムを打ち消すアルゴリズム

出典

2016-10-02 useruser1412

これを解決するための*あらゆる努力を実証できますか？ –

@ScottHunter私はこの解決策をオンラインで見つけましたが、私はそれを理解しませんでした。 http://clrs.skanev.com/04/05/02.html – useruser1412

どのような解決策ですか？私には解決策はありません。 –

あなたは本当に質問がここにあるかどうかを指定していませんが、この単純なアルゴリズムがStrassenより速く実行されることは間違いです。

は（4 K、あなたの質問にされた）X（N/K）（N/K）あなたがブロックに次元のそれぞれを、あなたの行列を分割すると言います。各マトリックスは、Kブロックを有するであろう、そしてKブロック乗算（第1行列の各ブロックは、第2の行列にKブロックにより乗算される）が存在することになります。これにより、複雑再発は

T（N）= K T（N/K）+ Θ（N ）あります。 case 1 of the Master theoremにより

、これは、T（N）= Θ（N ^{ログ_K（K ）}）= Θ（N ）

ことを意味します。

これは、通常の行列乗算と同じです。明らかにStrassenを打ち負かすことはありません。

出典

2016-10-03 06:52:41

"行列をk個のブロックに分割する...各行列はk^2個のブロックを持つ"？ –

@ScottHunter多くの感謝！それはひどいタイプミスでした。 –

いいえ、それは華麗なタイプミスでした:) –

Strassenのアルゴリズムを打ち消すアルゴリズム

答えて

関連する問題