Goでお手軽に行列の積を爆速並列計算 - QiitaTL;DR Go言語で行列の積を並列計算する実装例を示した(たぶんよりよい書き方あるので誰か教えて) ローカルのマシンとAWSのc4.8xlargeで実験すると、それなりに爆速になった まえがき 競技プログラミングにおいて、行列累乗の計算が要求されることがよくあります。典型的な例は、複数の項の漸化式を行列の形に直すものでしょう。 行列の累乗の計算量は n を行列のサイズ、P を乗数とすると、繰り返し二乗法を用いることにより O(n^3logP) です。これは、行列同士の掛け算の部分が O(n^3) でボトルネックになっています。今回はこれを Goを用いて並列処理します。 Goの並列処理の仕組み 一言でまとめると、Goroutine(ゴルーチンと読む)という存在が複数のスレッド上で走っていて、そいつらは channelというものを介して相互に値をやり取りできます。 Goroutineを生成す
