翻訳と辞書 Words near each other ・ シュトラウブ・ブルノー ・ シュトラウプ・ブルノー ・ シュトラスブルク ・ シュトラスブルク (軽巡洋艦) ・ シュトラスブルクの誓い ・ シュトラスブルクの誓約 ・ シュトラスブルク大学 ・ シュトラスブルグ大学 ・ シュトラッケア (小惑星) ・ シュトラッサー ・ シュトラッセンのアルゴリズム ・ シュトラルズント ・ シュトラースブルク ・ シュトラースブルク (軽巡洋艦) ・ シュトラースブルクの戦い ・ シュトラースブルクの誓い ・ シュトラースブルクの誓約 ・ シュトラースブルク包囲戦 ・ シュトラースブルク大学 ・ シュトラールズント Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク シュトラッセンのアルゴリズム ： ウィキペディア日本語版 シュトラッセンのアルゴリズム シュトラッセンのアルゴリズム（Strassen algorithm）は、行列の積を高速に計算するアルゴリズムである。通常、$N\; \backslash times\; N$行列同士の積を計算するには$O(N^3)$の時間が必要だが、このアルゴリズムを用いると、$O(N^)\; \backslash approx\; O(N^)$の時間で計算できる。1969年、フォルカー・シュトラッセン(Volker Strassen)が開発した〔〔 Strassen, Volker, ''Gaussian Elimination is not Optimal'', Numer. Math. 13, p. 354-356, 1969 〕。 便宜上、$N$を偶数と考えて、以下のように$\backslash frac\; \backslash times\; \backslash frac$部分行列に分解する。 :$$ \begin C_ & C_ \\ C_ & C_ \\ \end = \begin A_ & A_ \\ A_ & A_ \\ \end \begin B_ & B_ \\ B_ & B_ \\ \end そして、以下の七つの行列をつくる。 :$P\_1\; =\; (A\_\; +\; A\_)(B\_\; +\; B\_)$ :$P\_2\; =\; (A\_\; +\; A\_)B\_$ :$P\_3\; =\; A\_(B\_\; -\; B\_)$ :$P\_4\; =\; A\_(B\_\; -\; B\_)$ :$P\_5\; =\; (A\_\; +\; A\_)B\_$ :$P\_6\; =\; (A\_\; -\; A\_)(B\_\; +\; B\_)$ :$P\_7\; =\; (A\_\; -\; A\_)(B\_\; +\; B\_)$ このとき、 :$C\_\; =\; P\_1\; +\; P\_4\; -\; P\_5\; +\; P\_7$ :$C\_\; =\; P\_3\; +\; P\_5$ :$C\_\; =\; P\_2\; +\; P\_4$ :$C\_\; =\; P\_1\; +\; P\_3\; -\; P\_2\; +\; P\_6$ の関係が成り立つ。 この関係を利用して計算すると、部分行列同士の乗算が、通常の方法では8回必要なのに、この方法では7回ですむようになり、計算時間が削減される。部分行列への分割を再帰的に行うことにより、さらに計算時間を削減することができる。 == 脚注 == 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「シュトラッセンのアルゴリズム」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.