転送行列編：http://d.hatena.ne.jp/ita/20120915/p1 の続き
「おぬしらのアイディアはこうじゃな。真ん中のところの状態をi番目の状態に固定して、それで左と右で許される経路の数を数える。それをLi, RiとおけばΣLiRiが求める答え、と」
「じゃあ更に分割して三人で手分けしたらどうなるかの。」
真ん中を二箇所で分割して状態をiとjに固定、そこでLiとRj、それに真ん中で許される経路の数Mijを数え上げる。最終的な答えはΣLiMijRj となるわのう。で、これはな、ベクトルL、行列M、ベクトルRをかけたのと同じ式じゃ。簡単にこう書こう ＜L|M|R＞。
（口調めんどうなんで以下普通）
もっと分割を増やすとどうなるか。
ここで重要なのはiとjではさまれた部分と、jとkではさまれた部分は条件が全く同じということ。なので図で書いた行列Mと行列Nは同じものを使える。最後の答えは＜L|M^2|R＞。
これを同様に繰り返せば、横にどんどん伸ばせる。一旦行列を計算してしまえば、それをどんどん掛けるだけで4x100でも4x1000でもすぐに計算できてしまう。これが転送行列のアイディア。
一番効率的なのは行列で表す領域の幅を一番狭くして、iとjが隣り合っているときの行列を使う事。4x4グリッドの場合、状態の数は30あるけど、この場合の行列を実際計算すると以下のようになる。
状態 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 S 0 1 1 0 1 0 0 0 1 0 1 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 S U L 0 1 1 1 1 1 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 S U L 0 0 1 1 1 1 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 S U L 0 1 1 1 1 1 1 1 0 0 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 S U L 0 0 1 1 1 1 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 S U L 0 1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 S U U L L 0 0 0 0 1 1 0 1 1 0 0 0 0 1 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 S U L 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 S U L U L 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 S 0 1 1 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 S U L 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 S U L 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 S U L 1 1 0 0 0 0 0 0 0 1 1 0 0 1 1 1 1 1 0 0 1 1 0 0 0 0 0 0 1 0 S 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 S U L 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 1 0 U L S 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 U L S U L 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 1 1 1 1 1 0 0 1 0 1 0 1 0 S 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 1 0 0 0 U L S 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 0 1 0 1 0 U L S 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 1 0 1 0 U L S 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 S 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 1 1 0 1 0 0 0 1 U L S 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 U L S 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 1 0 0 0 U L S 1 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 U L S 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 1 1 1 1 0 1 0 U L S 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 U U L L S 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 1 1 0 1 1 U L S 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 U L U L S
状態の数はグリッドが増えると、どんどん増えるので、行列を格納するメモリが途中で足らなくなる
| グリッド | 状態数 | 行列のメモリ | |
| 8 | 1353 | ||
| 9 | 3610 | ||
| 10 | 9713 | 94M | |
| 11 | 26324 | 692M | |
| 12 | 71799 | 5.1Gb | |
| 13 | 196938 | 39Gb | |
| 14 | 542895 | 294Gb | |
| 19 | 91695540 | ? | |
| 20 | 258215664 | ? |
ちなみに9x9の場合の行列を画像にするとこんな感じ
もっと大きい場合はまっすぐに切らずに途中で曲がって切る、という若干トリッキーな手法を使えばメモリの問題は解消する。
http://arxiv.org/abs/cond-mat/0506341
20x20の場合はまだ計算例なし。計算量的に、19x19の場合の10倍まではいかないと思う。ちなみに19x19の場合は2005年に1000以上のプロセッサで並列計算が行われている。やってる人がいないだけで、いまなら更新は十分可能。
