翻訳と辞書 Words near each other ・ Stories (飯塚雅弓のアルバム) ・ Story (AIの曲) ・ Story (MONKEY MAJIKの曲) ・ Story (ピコの曲) ・ Storyteller (VALSHEのアルバム) ・ Storyteller II 〜the Age Limits〜 ・ Strange Circus 奇妙なサーカス ・ Strange fruits -奇妙な果実- ・ Stranger (星野源のアルバム) ・ Stranski-Krastanovモード ・ Strassenのアルゴリズム ・ Strategy パターン ・ Stratosphere-ストラトスフィア- ・ Stratosphere‐ストラトスフィア‐ ・ Straw Color〜Single Collection&More〜 ・ Straw Color～Single Collection&More～ ・ Strawberry (CoCoのアルバム) ・ Strawberry Cream Soda Pop “Daydream” ・ Strawberry JAM (アルバム) ・ Strawberry Panic (アニメ) Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Strassenのアルゴリズム ： ウィキペディア日本語版 シュトラッセンのアルゴリズム シュトラッセンのアルゴリズム（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）』 ■ウィキペディアで「シュトラッセンのアルゴリズム」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 Strassen algorithm 」があります。 スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.