https://twitter.com/kinaba のログ (twilog の方が便利です。)
| ツイート… | |
| ネタ元の論文読んでて面白かったのでタイトルでググって見つけた記事 http://www.siam.org/news/news.php?id=174 "Toward an Optimal Algorithm for Matrix Multiplication" を読んでた。わかりやすいかもしれない。群論おもしろいなあ。 | |
| たとえば A[1..N][1..M] な行列を Σ(A[i][j] x^i y^j) と思って同様に Σ(B[j][k] y^j z^k) と思って、ただしy^M=1とすると、行列積AB[i][k]は多項式の積のx^i z^k成分に等しくなる。 | |
| で、多項式の積的なものは、フーリエ変換的なものでスピードアップできる。ただし、ただのN次１変数多項式なら要素同士の掛け算N個に落とせて凄い速いんだけど、もっと複雑なのの積はフーリエ変換的なことをすると小さい行列同士の掛け算になる。なのでこの小さい行列の掛け算を再帰的に処理ると速い | |
| ただし行列を多項式に落とすのは結局効率がよくなくて、もっと怪しげな群に埋め込まなければ3乗より速いアルゴリズムにならない。てなわけで、行列乗算を埋め込める怪しげな群で、サイズが小さくて、しかもフーリエ変換的なことをしたときに出来るだけ小さい行列積にバラせる群を探せ！という物語 | |
| @m0h1can 実際に計算機で動かすアルゴリズムとしては、明らかに、そういう風に外に合わせて組むのが良いんでしょうけど、「それはそれとして脇に置いといて、実用がどうだろうがO(n^2)でできたらロマンがあるだろ！」という勢いで研究されてる気がしますね | |
| http://www.eonet.ne.jp/~fu-yareyare/index_2.html のCrazy Walker 6というFlashのBGMのアレンジというかremixが好きで時々BGMとして聴いてたんだけど、久々に開いたらFlashのバージョンチェックに引っかかるようになってた。右クリック→再生で飛ばせるからいいんだけど | |
| http://www.scratchbrain.net/blog/ver2/entries/000481.html こんな感じの、桁数の問題かなにかかなあ |