Posts

Juliaの行列ベクトル積について(疎行列編)

科学技術計算では行列ベクトル積が頻繁に登場し,これを効率よく計算することはとても重要です. 行列サイズ $n$ に対して計算量は $\mathrm{O}(n^2)$ ですが,行列は疎行列(ほとんどの要素が $0$)であることが多く,定義通りに計算すると $0$ を掛けたり足したりする無駄な演算が多く発生してしまいます. 以下では疎行列とベクトルの積の計算について解説します. (もっとも,Juliaで行列ベクトル積 $A\boldsymbol{b}$ を計算するには A*b と書けばよく,これは $A$ が疎行列の場合でも同様なので,疎行列のパッケージがあることさえ知っていれば実用上は十分なことが多いのですが,とはいえ,チューニングを行ったり,上三角部分など行列の一部とベクトルの積を計算したりしたいときには,疎行列とベクトルの積がどのように計算されているか理解しておくことが重要です.) まず,行列 $A$ を適当に定義して,疎行列に変換してみましょう. julia> using SparseArrays julia> A = [1 2 5; 0 3 0; 0 4 6] 3×3 Array{Int64,2}: 1 2 5 0 3 0 0 4 6 julia> A = sparse(A) 3×3 SparseMatrixCSC{Int64,Int64} with 6 stored entries: [1, 1] = 1 [1, 2] = 2 [2, 2] = 3 [3, 2] = 4 [1, 3] = 5 [3, 3] = 6 マニュアルによれば,圧縮列格納方式 (CSC) が採用されています.