【Python】疎行列計算が高速にできるようになる記事 - Qiita

はじめに 疎行列とは、行列の要素の大部分が0である行列のことを言います。数値計算や機械学習、グラフ理論など幅広い分野で扱われている(と思います)。行列内のほとんどが0という特徴から、0を無視する工夫をすれば、高速に行列計算を実施することが可能になります。例えば、9割近くが0の大規模疎行列(100万行×100万列とか)で非ゼロ部分だけ用いて計算すれば、計算時間が約1/10になり計算が早く終わらせることが可能になることが容易に想像できます。つまり、工夫すれば、1反復あたりの計算量を$O(N^2)$から$O(N)$に落として計算することが可能になります。 本記事では、Python・Numpy・Scipyを用いて、こうした疎行列計算について解説していきます。追加したいことが出てきたら適宜更新していきます。間違い等ございましたら、コメントにてご連絡して頂けたら幸いです。 対象読者 Pythonを扱え