Sparse Arrays

Juliaは、SparseArrays標準ライブラリモジュールでスパースベクトルとsparse matricesをサポートしています。スパース配列は、ゼロが十分に含まれている配列であり、特別なデータ構造に格納することで、密な配列と比較して、スペースと実行時間の節約が可能になります。

異なるスパースストレージタイプ、マルチディメンショナルスパース配列などを実装する外部パッケージは、Noteworthy External Sparse Packages で見つけることができます。

Compressed Sparse Column (CSC) Sparse Matrix Storage

Juliaでは、スパース行列はCompressed Sparse Column (CSC) formatに格納されます。Juliaのスパース行列の型はSparseMatrixCSC{Tv,Ti}であり、ここでTvは格納される値の型、Tiは列ポインタと行インデックスを格納するための整数型です。SparseMatrixCSCの内部表現は次のようになります：

struct SparseMatrixCSC{Tv,Ti<:Integer} <: AbstractSparseMatrixCSC{Tv,Ti}
    m::Int                  # Number of rows
    n::Int                  # Number of columns
    colptr::Vector{Ti}      # Column j is in colptr[j]:(colptr[j+1]-1)
    rowval::Vector{Ti}      # Row indices of stored values
    nzval::Vector{Tv}       # Stored values, typically nonzeros
end

圧縮スパース列ストレージは、スパース行列の列内の要素に簡単かつ迅速にアクセスできるようにしますが、行によるスパース行列へのアクセスはかなり遅くなります。CSC構造内で以前に保存されていなかったエントリを1つずつ挿入するような操作は遅くなる傾向があります。これは、挿入ポイントを超えるスパース行列のすべての要素を1つずつ移動させる必要があるためです。

すべてのスパース行列に対する操作は、パフォーマンスを最大限に引き出すためにCSCデータ構造を利用し、高コストの操作を回避するように慎重に実装されています。

CSC形式のデータが他のアプリケーションやライブラリからある場合、Juliaにインポートする際は1ベースのインデックスを使用することを確認してください。すべての列の行インデックスはソートされている必要があり、そうでない場合、行列は正しく表示されません。SparseMatrixCSCオブジェクトにソートされていない行インデックスが含まれている場合、ソートする簡単な方法はダブル転置を行うことです。転置操作は遅延されるため、各転置を具現化するためにコピーを作成してください。

いくつかのアプリケーションでは、SparseMatrixCSCに明示的なゼロ値を格納することが便利です。これらはBaseの関数によって受け入れられます（ただし、変更操作で保持される保証はありません）。このように明示的に格納されたゼロは、多くのルーチンによって構造的な非ゼロとして扱われます。nnz関数は、構造的でないゼロを含むスパースデータ構造に明示的に格納された要素の数を返します。正確な数の数値的非ゼロをカウントするには、count(!iszero, x)を使用してください。これはスパース行列のすべての格納された要素を検査します。dropzerosおよびインプレースのdropzeros!は、スパース行列から格納されたゼロを削除するために使用できます。

julia> A = sparse([1, 1, 2, 3], [1, 3, 2, 3], [0, 1, 2, 0])
3×3 SparseMatrixCSC{Int64, Int64} with 4 stored entries:
 0  ⋅  1
 ⋅  2  ⋅
 ⋅  ⋅  0

julia> dropzeros(A)
3×3 SparseMatrixCSC{Int64, Int64} with 2 stored entries:
 ⋅  ⋅  1
 ⋅  2  ⋅
 ⋅  ⋅  ⋅

Sparse Vector Storage

スパースベクトルは、スパース行列の圧縮スパースカラム形式に近い形で保存されます。Juliaでは、スパースベクトルは型 SparseVector{Tv,Ti} を持ち、ここで Tv は保存される値の型、Ti はインデックスの整数型です。内部表現は次のようになります：

struct SparseVector{Tv,Ti<:Integer} <: AbstractSparseVector{Tv,Ti}
    n::Int              # Length of the sparse vector
    nzind::Vector{Ti}   # Indices of stored values
    nzval::Vector{Tv}   # Stored values, typically nonzeros
end

SparseMatrixCSCについて、SparseVector型は明示的に保存されたゼロも含むことができます。（Sparse Matrix Storageを参照してください。）

Sparse Vector and Matrix Constructors

スパース配列を作成する最も簡単な方法は、Juliaが密な配列を扱うために提供するzeros関数に相当する関数を使用することです。代わりにスパース配列を生成するには、同じ名前にspプレフィックスを付けて使用できます：

julia> spzeros(3)
3-element SparseVector{Float64, Int64} with 0 stored entries

sparse 関数は、スパース配列を構築する便利な方法です。例えば、スパース行列を構築するために、行インデックスのベクトル I、列インデックスのベクトル J、および保存された値のベクトル V を入力できます（これは COO (coordinate) format とも呼ばれます）。sparse(I,J,V) は、S[I[k], J[k]] = V[k] となるスパース行列を構築します。等価なスパースベクトルコンストラクタは sparsevec で、（行）インデックスベクトル I と保存された値のベクトル V を取り、スパースベクトル R を構築します。ここで、R[I[k]] = V[k] となります。

julia> I = [1, 4, 3, 5]; J = [4, 7, 18, 9]; V = [1, 2, -5, 3];

julia> S = sparse(I,J,V)
5×18 SparseMatrixCSC{Int64, Int64} with 4 stored entries:
⎡⠀⠈⠀⠀⠀⠀⠀⠀⢀⎤
⎣⠀⠀⠀⠂⡀⠀⠀⠀⠀⎦

julia> R = sparsevec(I,V)
5-element SparseVector{Int64, Int64} with 4 stored entries:
  [1]  =  1
  [3]  =  -5
  [4]  =  2
  [5]  =  3

sparse および sparsevec 関数の逆は findnz であり、これはスパース配列を作成するために使用された入力（ゼロに等しい保存されたエントリを含む）を取得します。 findall(!iszero, x) は x の非ゼロエントリのカルテジアンインデックスを返します（ゼロに等しい保存されたエントリは含まれません）。

julia> findnz(S)
([1, 4, 5, 3], [4, 7, 9, 18], [1, 2, 3, -5])

julia> findall(!iszero, S)
4-element Vector{CartesianIndex{2}}:
 CartesianIndex(1, 4)
 CartesianIndex(4, 7)
 CartesianIndex(5, 9)
 CartesianIndex(3, 18)

julia> findnz(R)
([1, 3, 4, 5], [1, -5, 2, 3])

julia> findall(!iszero, R)
4-element Vector{Int64}:
 1
 3
 4
 5

別の方法として、sparse 関数を使用して、密な配列を疎な配列に変換することができます：

julia> sparse(Matrix(1.0I, 5, 5))
5×5 SparseMatrixCSC{Float64, Int64} with 5 stored entries:
 1.0   ⋅    ⋅    ⋅    ⋅
  ⋅   1.0   ⋅    ⋅    ⋅
  ⋅    ⋅   1.0   ⋅    ⋅
  ⋅    ⋅    ⋅   1.0   ⋅
  ⋅    ⋅    ⋅    ⋅   1.0

julia> sparse([1.0, 0.0, 1.0])
3-element SparseVector{Float64, Int64} with 2 stored entries:
  [1]  =  1.0
  [3]  =  1.0

他の方向に進むには、Array コンストラクタを使用できます。issparse 関数は、行列がスパースであるかどうかを照会するために使用できます。

julia> issparse(spzeros(5))
true

Sparse matrix operations

Arithmetic operations on sparse matrices also work as they do on dense matrices. Indexing of, assignment into, and concatenation of sparse matrices work in the same way as dense matrices. Indexing operations, especially assignment, are expensive, when carried out one element at a time. In many cases it may be better to convert the sparse matrix into (I,J,V) format using findnz, manipulate the values or the structure in the dense vectors (I,J,V), and then reconstruct the sparse matrix.

Correspondence of dense and sparse methods

次の表は、スパース行列の組み込みメソッドと、それに対応する密行列タイプのメソッドとの対応関係を示しています。一般に、スパース行列を生成するメソッドは、密行列の対応するメソッドとは異なり、結果として得られる行列が与えられたスパース行列 S と同じスパースパターンに従うか、または結果として得られるスパース行列が密度 d を持つこと、すなわち各行列要素が非ゼロである確率 d を持つことが特徴です。

詳細は標準ライブラリリファレンスの Sparse Vectors and Matrices セクションにあります。

Sparse	Dense	Description
`spzeros(m,n)`	`zeros(m,n)`	Creates a m-by-n matrix of zeros. (`spzeros(m,n)` is empty.)
`sparse(I,n,n)`	`Matrix(I,n,n)`	Creates a n-by-n identity matrix.
`sparse(A)`	`Array(S)`	Interconverts between dense and sparse formats.
`sprand(m,n,d)`	`rand(m,n)`	Creates a m-by-n random matrix (of density d) with iid non-zero elements distributed uniformly on the half-open interval $[0, 1)$.
`sprandn(m,n,d)`	`randn(m,n)`	Creates a m-by-n random matrix (of density d) with iid non-zero elements distributed according to the standard normal (Gaussian) distribution.
`sprandn(rng,m,n,d)`	`randn(rng,m,n)`	Creates a m-by-n random matrix (of density d) with iid non-zero elements generated with the `rng` random number generator

SparseArrays API

SparseArrays.AbstractSparseArray — Type

AbstractSparseArray{Tv,Ti,N}

Tv型の要素とTi型のインデックスを持つN次元スパース配列（または配列のような型）のスーパークラスです。 SparseMatrixCSC、SparseVectorおよびSuiteSparse.CHOLMOD.Sparseはこのサブタイプです。