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)形式では、疎行列の列内の要素に簡単かつ高速にアクセスできます。一方、行を使ったアクセスはかなり遅くなります。CSC 構造に未格納の要素を一つずつ挿入するような操作は、一般に低速です。挿入位置より後ろにある疎行列の要素をすべて一つずつ移動する必要があるためです。
疎行列に対するすべての操作は、CSC データ構造を活用して性能を高め、高コストな処理を避けるよう、慎重に実装されています。
別のアプリケーションやライブラリから CSC 形式のデータを取り込みたい場合は、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
endSparseMatrixCSC と同様に、SparseVector 型にも明示的に格納されたゼロを含めることができます(Sparse Matrix Storage を参照)。
Sparse Vector and Matrix Constructors
疎配列を作成する最も簡単な方法は、Julia が密配列の操作用に提供する zeros 関数と同等の関数を使うことです。疎配列を作成するには、同じ名前の関数に sp 接頭辞を付けて使います。
julia> spzeros(3)
3-element SparseVector{Float64, Int64} with 0 stored entriessparse 関数は、疎配列の構築に便利です。たとえば、疎行列を作るには、行インデックスのベクトル I、列インデックスのベクトル J、格納する値のベクトル V を入力します(これは COO (coordinate) format とも呼ばれます)。sparse(I,J,V) は、S[I[k], J[k]] = V[k] を満たす疎行列を構築します。疎ベクトルを作る同等のコンストラクターは sparsevec です。これは、(行)インデックスのベクトル I と、格納する値のベクトル V を受け取り、R[I[k]] = V[k] を満たす疎ベクトル R を構築します。
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] = 3sparse 関数と 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))
trueSparse matrix operations
疎行列に対する算術演算は、密行列の場合と同様に行えます。疎行列のインデックス参照、代入、連結も、密行列と同じ方法で行えます。ただし、インデックス操作、特に代入は、要素を一つずつ処理すると高コストになります。多くの場合、findnz を使って疎行列を (I,J,V) 形式に変換し、密ベクトル (I,J,V) 内の値や構造を操作してから、疎行列を再構築するほうが効率的です。
Correspondence of dense and sparse methods
次の表は、疎行列に対する組み込みメソッドと、密行列型に対する対応メソッドを示しています。一般に、疎行列を生成するメソッドは、密行列用の対応メソッドとは異なり、指定した疎行列 S と同じ疎性パターンを持つ行列を生成するか、密度 d の疎行列を生成します。後者では、各行列要素が非ゼロである確率は d です。
詳細については、標準ライブラリリファレンスの Sparse Vectors and Matrices の節を参照してください。
| 疎行列 | 密行列 | 説明 |
|---|---|---|
spzeros(m,n) | zeros(m,n) | m 行 n 列のゼロ行列を作成します(spzeros(m,n) は空です)。 |
sparse(I,n,n) | Matrix(I,n,n) | n 行 n 列の単位行列を作成します。 |
sparse(A) | Array(S) | 密形式と疎形式の間で相互変換します。 |
sprand(m,n,d) | rand(m,n) | m 行 n 列のランダム行列を作成します(密度 d)。非ゼロ要素は独立同分布で、半開区間 $[0, 1)$ 上の一様分布に従います。 |
sprandn(m,n,d) | randn(m,n) | m 行 n 列のランダム行列を作成します(密度 d)。非ゼロ要素は独立同分布で、標準正規(ガウス)分布に従います。 |
sprandn(rng,m,n,d) | randn(rng,m,n) | rng 乱数生成器で生成した独立同分布の非ゼロ要素を持つ、m 行 n 列のランダム行列を作成します(密度 d)。 |
SparseArrays API
SparseArrays.AbstractSparseArray — Type
AbstractSparseArray{Tv,Ti,N}要素型がTv、インデックス型がTiである、N次元の疎配列(または配列に類する型)のスーパータイプ。SparseMatrixCSC、SparseVector、SuiteSparse.CHOLMOD.Sparseは、この型のサブタイプです。
SparseArrays.AbstractSparseVector — Type
AbstractSparseVector{Tv,Ti}要素型が Tv、インデックス型が Ti の、1 次元疎配列(または配列に類する型)のスーパータイプです。AbstractSparseArray{Tv,Ti,1} の別名です。
SparseArrays.AbstractSparseMatrix — Type
AbstractSparseMatrix{Tv,Ti}要素の型が Tv、インデックスの型が Ti である、2 次元疎配列(または配列に類する型)のスーパータイプ。AbstractSparseArray{Tv,Ti,2} の別名。
SparseArrays.SparseVector — Type
SparseVector{Tv,Ti<:Integer} <: AbstractSparseVector{Tv,Ti}疎ベクトルを格納するためのベクトル型です。ベクトルの長さ、ゼロでないインデックスを昇順に並べたベクトル、およびゼロでない値のベクトルを渡して作成できます。
たとえば、ベクトル [5, 6, 0, 7] は、次のように表せます。
SparseVector(4, [1, 2, 4], [5, 6, 7])これは、インデックス1の要素が5、インデックス2の要素が6、インデックス3の要素が zero(Int)、インデックス4の要素が7であることを示しています。
密ベクトルから sparse を使って疎ベクトルを直接作成するほうが便利な場合もあります。
sparse([5, 6, 0, 7])これにより、同じ疎ベクトルが得られます。
SparseArrays.SparseMatrixCSC — Type
SparseMatrixCSC{Tv,Ti<:Integer} <: AbstractSparseMatrixCSC{Tv,Ti}Compressed Sparse Column形式の疎行列を格納するための行列型です。SparseMatrixCSCは通常、sparse関数を使って構築します。spzeros、spdiagm、sprandも参照してください。
SparseArrays.sparse — Function
sparse(A::Union{AbstractVector, AbstractMatrix})ベクトルまたは行列 A を疎配列に変換します。A 内の数値的なゼロは、構造的なゼロに変換されます。
Examples
julia> A = Matrix(1.0I, 3, 3)
3×3 Matrix{Float64}:
1.0 0.0 0.0
0.0 1.0 0.0
0.0 0.0 1.0
julia> sparse(A)
3×3 SparseMatrixCSC{Float64, Int64} with 3 stored entries:
1.0 ⋅ ⋅
⋅ 1.0 ⋅
⋅ ⋅ 1.0
julia> [1.0, 0.0, 1.0]
3-element Vector{Float64}:
1.0
0.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.0sparse(I, J, V,[ m, n, combine])次元が m x n で、S[I[k], J[k]] = V[k] となる疎行列 S を作成します。重複要素の結合には combine 関数を使用します。m と n が指定されていない場合、それぞれ maximum(I) と maximum(J) に設定されます。combine 関数が指定されていない場合、combine の既定値は + です。ただし、V の要素が Boolean の場合は、combine の既定値は | になります。I のすべての要素は 1 <= I[k] <= m を満たし、J のすべての要素は 1 <= J[k] <= n を満たす必要があります。(I, J, V) 内の数値ゼロは構造上の非ゼロ要素として保持されます。数値ゼロを削除するには、dropzeros! を使用してください。
詳しいドキュメントとエキスパート向けドライバーについては、SparseArrays.sparse! を参照してください。
Examples
julia> Is = [1; 2; 3];
julia> Js = [1; 2; 3];
julia> Vs = [1; 2; 3];
julia> sparse(Is, Js, Vs)
3×3 SparseMatrixCSC{Int64, Int64} with 3 stored entries:
1 ⋅ ⋅
⋅ 2 ⋅
⋅ ⋅ 3SparseArrays.sparse! — Function
sparse!(I::AbstractVector{Ti}, J::AbstractVector{Ti}, V::AbstractVector{Tv},
m::Integer, n::Integer, combine, klasttouch::Vector{Ti},
csrrowptr::Vector{Ti}, csrcolval::Vector{Ti}, csrnzval::Vector{Tv},
[csccolptr::Vector{Ti}], [cscrowval::Vector{Ti}, cscnzval::Vector{Tv}] ) where {Tv,Ti<:Integer}sparseの親メソッドであり、効率的な利用のためのドライバーです。基本的な使い方についてはsparseを参照してください。このメソッドでは、以下で説明するように、sparseの中間オブジェクトと結果を格納するための領域を、あらかじめユーザーが確保して渡せます。この機能により、座標表現からSparseMatrixCSCを連続して構築する際の効率が向上します。また、追加コストなしで、結果の転置を列が未整列の表現として取り出せます。
このメソッドは、次の3つの主要なステップで構成されます。(1) 与えられた座標表現を計数ソートし、重複エントリを含む行が未整列のCSR形式に変換します。(2) CSR形式を走査しながら、目的のCSC形式の列ポインタ配列を計算し、重複エントリを検出するとともに、重複エントリを統合してCSR形式を再構成します。この段階で、重複エントリのない、行が未整列のCSR形式が得られます。(3) 先ほどのCSR形式を計数ソートし、重複エントリのない、完全に整列されたCSC形式に変換します。
入力配列csrrowptr、csrcolval、csrnzvalは、中間CSR形式を格納するためのもので、length(csrrowptr) >= m + 1、length(csrcolval) >= length(I)、length(csrnzval >= length(I))が必要です。第2段階の作業領域となる入力配列klasttouchには、length(klasttouch) >= nが必要です。省略可能な入力配列csccolptr、cscrowval、cscnzvalは、返されるCSC形式Sを格納するためのものです。必要に応じて、これらの配列はlength(csccolptr) = n + 1、length(cscrowval) = nnz(S)、length(cscnzval) = nnz(S)を満たすよう自動的にサイズ変更されます。そのため、nnz(S)が事前にわからない場合は、適切な型の空ベクトル(それぞれVector{Ti}()およびVector{Tv}())を渡せば十分です。または、cscrowvalとcscnzvalを省略して、sparse!メソッドを呼び出すこともできます。
戻り値として、csrrowptr、csrcolval、csrnzvalには、結果の転置を列が未整列の形式で表したものが格納されます。
入力配列の領域(I、J、V)は、出力配列(csccolptr、cscrowval、cscnzval)に再利用できます。たとえば、sparse!(I, J, V, csrrowptr, csrcolval, csrnzval, I, J, V)を呼び出せます。上記の条件を満たすよう、これらの配列はサイズ変更されることに注意してください。
効率を優先し、このメソッドでは1 <= I[k] <= mと1 <= J[k] <= n以外の引数チェックは行いません。注意して使用してください。--check-bounds=yesでテストしておくとよいでしょう。
このメソッドの実行時間はO(m, n, length(I))です。計数ソートを2回行うこのメソッドの方式は、F. Gustavsonの論文「Two fast algorithms for sparse matrices: multiplication and permuted transposition」(ACM TOMS 4(3), 250–269, 1978)で説明されているHALFPERMアルゴリズムに着想を得ています。
SparseArrays.sparse!(I, J, V, [m, n, combine]) -> SparseMatrixCSCsparse!のバリエーションで、最終的な行列の格納に入力ベクトル(I、J、V)を再利用します。構築後、入力ベクトルは行列のバッファをエイリアスします。S.colptr === I、S.rowval === J、S.nzval === Vが成立し、必要に応じてresize!されます。
一部の作業用バッファは引き続き割り当てられる点に注意してください。具体的には、このメソッドはsparse!(I, J, V, m, n, combine, klasttouch, csrrowptr, csrcolval, csrnzval, csccolptr, cscrowval, cscnzval)を呼び出す便利なラッパーです。このメソッドでは、適切なサイズのklasttouch、csrrowptr、csrcolval、csrnzvalを割り当てる一方、csccolptr、cscrowval、cscnzvalにはI、J、Vを再利用します。
引数m、n、combineのデフォルト値は、それぞれmaximum(I)、maximum(J)、+です。
SparseArrays.sparsevec — Function
sparsevec(I, V, [m, combine])長さがmで、S[I[k]] = V[k]となる疎ベクトルSを作成します。重複する要素はcombine関数でまとめられます。combine引数を指定しない場合、既定値は+です。ただし、Vの要素がブール値の場合、combineの既定値は|です。
Examples
julia> II = [1, 3, 3, 5]; V = [0.1, 0.2, 0.3, 0.2];
julia> sparsevec(II, V)
5-element SparseVector{Float64, Int64} with 3 stored entries:
[1] = 0.1
[3] = 0.5
[5] = 0.2
julia> sparsevec(II, V, 8, -)
8-element SparseVector{Float64, Int64} with 3 stored entries:
[1] = 0.1
[3] = -0.1
[5] = 0.2
julia> sparsevec([1, 3, 1, 2, 2], [true, true, false, false, false])
3-element SparseVector{Bool, Int64} with 3 stored entries:
[1] = 1
[2] = 0
[3] = 1sparsevec(d::Dict, [m])辞書のキーを非ゼロ要素のインデックス、辞書の値を非ゼロ要素の値として、長さが m の疎ベクトルを作成します。
Examples
julia> sparsevec(Dict(1 => 3, 2 => 2))
2-element SparseVector{Int64, Int64} with 2 stored entries:
[1] = 3
[2] = 2sparsevec(A)ベクトル A を、長さ m の疎ベクトルに変換します。A 内の数値的なゼロは、構造的なゼロに変換されます。
Examples
julia> sparsevec([1.0, 2.0, 0.0, 0.0, 3.0, 0.0])
6-element SparseVector{Float64, Int64} with 3 stored entries:
[1] = 1.0
[2] = 2.0
[5] = 3.0Base.similar — Method
similar(A::AbstractSparseMatrixCSC{Tv,Ti}, [::Type{TvNew}, ::Type{TiNew}, m::Integer, n::Integer]) where {Tv,Ti}指定された要素型、インデックス型、サイズを持つ未初期化の可変配列を、指定されたソース SparseMatrixCSC に基づいて作成します。新しい疎行列は、出力行列の次元が異なる場合を除き、元の疎行列の構造を維持します。
出力行列では、入力行列と同じ位置がゼロとなり、非ゼロの位置には未初期化の値が格納されます。
SparseArrays.issparse — Function
issparse(S)S が疎であれば true を返し、そうでなければ false を返します。
Examples
julia> sv = sparsevec([1, 4], [2.3, 2.2], 10)
10-element SparseVector{Float64, Int64} with 2 stored entries:
[1] = 2.3
[4] = 2.2
julia> issparse(sv)
true
julia> issparse(Array(sv))
falseSparseArrays.nnz — Function
nnz(A)疎配列に格納されている(値が設定された)要素の数を返します。
Examples
julia> A = sparse(2I, 3, 3)
3×3 SparseMatrixCSC{Int64, Int64} with 3 stored entries:
2 ⋅ ⋅
⋅ 2 ⋅
⋅ ⋅ 2
julia> nnz(A)
3SparseArrays.findnz — Function
findnz(A::SparseMatrixCSC)疎行列 A に格納されている(「構造的に非ゼロ」の)値の行インデックスと列インデックスをそれぞれ I、J とし、値のベクトルを V とするタプル (I, J, V) を返します。
Examples
julia> A = sparse([1 2 0; 0 0 3; 0 4 0])
3×3 SparseMatrixCSC{Int64, Int64} with 4 stored entries:
1 2 ⋅
⋅ ⋅ 3
⋅ 4 ⋅
julia> findnz(A)
([1, 1, 3, 2], [1, 2, 2, 3], [1, 2, 4, 3])SparseArrays.spzeros — Function
spzeros([type,]m[,n])長さがmの疎ベクトル、またはサイズがm x nの疎行列を作成します。この疎配列には非ゼロ値は含まれません。構築時に非ゼロ値用のストレージは割り当てられません。型を指定しない場合、デフォルトはFloat64です。
Examples
julia> spzeros(3, 3)
3×3 SparseMatrixCSC{Float64, Int64} with 0 stored entries:
⋅ ⋅ ⋅
⋅ ⋅ ⋅
⋅ ⋅ ⋅
julia> spzeros(Float32, 4)
4-element SparseVector{Float32, Int64} with 0 stored entriesspzeros([type], I::AbstractVector, J::AbstractVector, [m, n])構造的ゼロを S[I[k], J[k]] に持つ、次元 m x n の疎行列 S を作成します。
このメソッドは行列の疎性パターンの構築に使用でき、たとえば sparse(I, J, zeros(length(I))) を使うより効率的です。
詳しいドキュメントとエキスパート向けドライバーについては、SparseArrays.spzeros! を参照してください。
SparseArrays.spzeros! — Function
spzeros!(::Type{Tv}, I::AbstractVector{Ti}, J::AbstractVector{Ti}, m::Integer, n::Integer,
klasttouch::Vector{Ti}, csrrowptr::Vector{Ti}, csrcolval::Vector{Ti},
[csccolptr::Vector{Ti}], [cscrowval::Vector{Ti}, cscnzval::Vector{Tv}]) where {Tv,Ti<:Integer}中間オブジェクト用に事前割り当てしたストレージをユーザーが指定できる、spzeros(I, J)の親メソッドであり、専門的なドライバーメソッドです。このメソッドとspzerosの関係は、SparseArrays.sparse!とsparseの関係に相当します。詳細と必要なバッファー長については、SparseArrays.sparse!のドキュメントを参照してください。
SparseArrays.spzeros!(::Type{Tv}, I, J, [m, n]) -> SparseMatrixCSC{Tv}最終的な行列の格納に、入力ベクトルIとJを再利用する、spzeros!の変種です。構築後、入力ベクトルは行列のバッファをエイリアスします。S.colptr === IとS.rowval === Jが成り立ち、必要に応じてresize!されます。
一部の作業用バッファは引き続き割り当てられる点に注意してください。具体的には、このメソッドはspzeros!(Tv, I, J, m, n, klasttouch, csrrowptr, csrcolval, csccolptr, cscrowval)を呼び出す便利なラッパーです。このメソッドは適切なサイズのklasttouch、csrrowptr、csrcolvalを割り当てますが、csccolptrとcscrowvalにはIとJを再利用します。
引数mとnのデフォルト値は、それぞれmaximum(I)とmaximum(J)です。
SparseArrays.spdiagm — Function
spdiagm(kv::Pair{<:Integer,<:AbstractVector}...)
spdiagm(m::Integer, n::Integer, kv::Pair{<:Integer,<:AbstractVector}...)ベクトルや対角成分のPairから、疎な対角行列を構築します。各ベクトルkv.secondは、kv.first対角成分に配置されます。デフォルトでは行列は正方行列で、そのサイズはkvから推定されます。ただし、最初の引数としてm,nを渡すと、必要に応じてゼロで埋められる、m×nの非正方行列を指定できます。
Examples
julia> spdiagm(-1 => [1,2,3,4], 1 => [4,3,2,1])
5×5 SparseMatrixCSC{Int64, Int64} with 8 stored entries:
⋅ 4 ⋅ ⋅ ⋅
1 ⋅ 3 ⋅ ⋅
⋅ 2 ⋅ 2 ⋅
⋅ ⋅ 3 ⋅ 1
⋅ ⋅ ⋅ 4 ⋅spdiagm(v::AbstractVector)
spdiagm(m::Integer, n::Integer, v::AbstractVector)ベクトルの要素を対角成分とする疎行列を構築します。デフォルトでは(m と n を指定しない場合)、行列は正方行列で、そのサイズは length(v) によって決まります。ただし、最初の引数として m と n を渡すと、m×n の非正方行列を指定できます。
Examples
julia> spdiagm([1,2,3])
3×3 SparseMatrixCSC{Int64, Int64} with 3 stored entries:
1 ⋅ ⋅
⋅ 2 ⋅
⋅ ⋅ 3
julia> spdiagm(sparse([1,0,3]))
3×3 SparseMatrixCSC{Int64, Int64} with 2 stored entries:
1 ⋅ ⋅
⋅ ⋅ ⋅
⋅ ⋅ 3SparseArrays.sparse_hcat — Function
sparse_hcat(A...)次元 2 に沿って連結します。SparseMatrixCSC オブジェクトを返します。
SparseArrays.sparse_vcat — Function
sparse_vcat(A...)次元 1 に沿って連結します。SparseMatrixCSC オブジェクトを返します。
SparseArrays.sparse_hvcat — Function
sparse_hvcat(rows::Tuple{Vararg{Int}}, values...)1回の呼び出しで、疎な水平連結と垂直連結を行います。この関数はブロック行列構文で呼び出されます。最初の引数は、各ブロック行で連結する引数の数を指定します。
SparseArrays.blockdiag — Function
blockdiag(A...)行列をブロック対角に連結します。現在は疎行列にのみ対応しています。
Examples
julia> blockdiag(sparse(2I, 3, 3), sparse(4I, 2, 2))
5×5 SparseMatrixCSC{Int64, Int64} with 5 stored entries:
2 ⋅ ⋅ ⋅ ⋅
⋅ 2 ⋅ ⋅ ⋅
⋅ ⋅ 2 ⋅ ⋅
⋅ ⋅ ⋅ 4 ⋅
⋅ ⋅ ⋅ ⋅ 4SparseArrays.sprand — Function
sprand([rng],[T::Type],m,[n],p::AbstractFloat)
sprand([rng],m,[n],p::AbstractFloat,[rfn=rand])長さがランダムな疎ベクトル m、または m × n の疎行列を作成します。各要素が非ゼロとなる確率は独立に p で与えられます(したがって、非ゼロ要素の平均密度も正確に p です)。省略可能な rng 引数では乱数生成器を指定します。詳しくは Random Numbers を参照してください。省略可能な T 引数では要素の型を指定します。既定値は Float64 です。
既定では、非ゼロ値は rand 関数を使って一様分布からサンプリングされます。つまり、rand(T) によってサンプリングされます。rng が指定されている場合は rand(rng, T) によってサンプリングされます。既定の T=Float64 では、これは [0,1) から一様にサンプリングされた非ゼロ値に相当します。
rand の代わりにカスタムの rfn 関数を渡すと、別の分布から非ゼロ値をサンプリングできます。この関数は、指定した分布からサンプリングした k 個の乱数を含む配列を返す関数 rfn(k) である必要があります。また、rng が指定されている場合は、代わりに関数 rfn(rng, k) である必要があります。
Examples
julia> sprand(Bool, 2, 2, 0.5)
2×2 SparseMatrixCSC{Bool, Int64} with 2 stored entries:
1 1
⋅ ⋅
julia> sprand(Float64, 3, 0.75)
3-element SparseVector{Float64, Int64} with 2 stored entries:
[1] = 0.795547
[2] = 0.49425SparseArrays.sprandn — Function
sprandn([rng][,Type],m[,n],p::AbstractFloat)長さがmのランダムな疎ベクトル、またはサイズがm × nのランダムな疎行列を作成します。各要素が非ゼロとなる確率は、指定したp(各要素について独立)です。非ゼロ値は正規分布からサンプリングされます。省略可能なrng引数で乱数生成器を指定できます。詳細はRandom Numbersを参照してください。
Examples
julia> sprandn(2, 2, 0.75)
2×2 SparseMatrixCSC{Float64, Int64} with 3 stored entries:
-1.20577 ⋅
0.311817 -0.234641SparseArrays.nonzeros — Function
nonzeros(A)疎配列 A に格納されている構造上の非ゼロ値をベクトルとして返します。疎配列に明示的に格納されたゼロも含まれます。返されるベクトルは、A の内部の非ゼロ値ストレージを直接参照するため、返されたベクトルを変更すると A も変更されます。rowvals および nzrange を参照してください。
Examples
julia> A = sparse(2I, 3, 3)
3×3 SparseMatrixCSC{Int64, Int64} with 3 stored entries:
2 ⋅ ⋅
⋅ 2 ⋅
⋅ ⋅ 2
julia> nonzeros(A)
3-element Vector{Int64}:
2
2
2SparseArrays.rowvals — Function
rowvals(A)疎配列 A の行インデックスを格納したベクトルを返します。返されたベクトルを変更すると、A も変更されます。行インデックスの内部での格納方法にアクセスできるため、構造的な非ゼロ値を反復処理する際に便利です。nonzeros および nzrange も参照してください。
Examples
julia> A = sparse(2I, 3, 3)
3×3 SparseMatrixCSC{Int64, Int64} with 3 stored entries:
2 ⋅ ⋅
⋅ 2 ⋅
⋅ ⋅ 2
julia> rowvals(A)
3-element Vector{Int64}:
1
2
3SparseArrays.nzrange — Function
nzrange(A, col::Integer)疎配列 A の列 col における、構造的に非ゼロの値のインデックス範囲を返します。nonzeros および rowvals と組み合わせることで、疎行列を簡単に反復処理できます。
A = sparse(I,J,V)
rows = rowvals(A)
vals = nonzeros(A)
m, n = size(A)
for j = 1:n
for i in nzrange(A, j)
row = rows[i]
val = vals[i]
# perform sparse wizardry...
end
endnzrange(x::SparseVectorUnion, col)疎ベクトルの構造的な非ゼロ値のインデックス範囲を返します。列インデックス col は無視されます(1 とみなされます)。
SparseArrays.droptol! — Function
droptol!(A::AbstractSparseMatrixCSC, tol)Aから、絶対値がtol以下の値を削除します。
droptol!(x::AbstractCompressedVector, tol)xから、絶対値がtol以下の値を削除します。
SparseArrays.dropzeros! — Function
dropzeros!(x::AbstractCompressedVector)xから、格納されている数値のゼロを削除します。
非破壊版についてはdropzerosを、アルゴリズムの詳細についてはfkeep!を参照してください。
SparseArrays.dropzeros — Function
dropzeros(A::AbstractSparseMatrixCSC;)Aのコピーを生成し、そのコピーから格納されている数値のゼロを削除します。
インプレース版およびアルゴリズムの詳細については、dropzeros!を参照してください。
Examples
julia> A = sparse([1, 2, 3], [1, 2, 3], [1.0, 0.0, 1.0])
3×3 SparseMatrixCSC{Float64, Int64} with 3 stored entries:
1.0 ⋅ ⋅
⋅ 0.0 ⋅
⋅ ⋅ 1.0
julia> dropzeros(A)
3×3 SparseMatrixCSC{Float64, Int64} with 2 stored entries:
1.0 ⋅ ⋅
⋅ ⋅ ⋅
⋅ ⋅ 1.0dropzeros(x::AbstractCompressedVector)x のコピーを生成し、そのコピーから数値のゼロを取り除きます。
インプレース版とアルゴリズムの詳細については、dropzeros! を参照してください。
Examples
julia> A = sparsevec([1, 2, 3], [1.0, 0.0, 1.0])
3-element SparseVector{Float64, Int64} with 3 stored entries:
[1] = 1.0
[2] = 0.0
[3] = 1.0
julia> dropzeros(A)
3-element SparseVector{Float64, Int64} with 2 stored entries:
[1] = 1.0
[3] = 1.0SparseArrays.permute — Function
permute(A::AbstractSparseMatrixCSC{Tv,Ti}, p::AbstractVector{<:Integer},
q::AbstractVector{<:Integer}) where {Tv,Ti}Aを行と列の両方で並べ替え、PAQ(A[p,q])を返します。列の並べ替えに使うqの長さは、Aの列数(length(q) == size(A, 2))と一致する必要があります。行の並べ替えに使うpの長さは、Aの行数(length(p) == size(A, 1))と一致する必要があります。
エキスパートドライバーや詳細については、permute!を参照してください。
Examples
julia> A = spdiagm(0 => [1, 2, 3, 4], 1 => [5, 6, 7])
4×4 SparseMatrixCSC{Int64, Int64} with 7 stored entries:
1 5 ⋅ ⋅
⋅ 2 6 ⋅
⋅ ⋅ 3 7
⋅ ⋅ ⋅ 4
julia> permute(A, [4, 3, 2, 1], [1, 2, 3, 4])
4×4 SparseMatrixCSC{Int64, Int64} with 7 stored entries:
⋅ ⋅ ⋅ 4
⋅ ⋅ 3 7
⋅ 2 6 ⋅
1 5 ⋅ ⋅
julia> permute(A, [1, 2, 3, 4], [4, 3, 2, 1])
4×4 SparseMatrixCSC{Int64, Int64} with 7 stored entries:
⋅ ⋅ 5 1
⋅ 6 2 ⋅
7 3 ⋅ ⋅
4 ⋅ ⋅ ⋅Base.permute! — Method
permute!(X::AbstractSparseMatrixCSC{Tv,Ti}, A::AbstractSparseMatrixCSC{Tv,Ti},
p::AbstractVector{<:Integer}, q::AbstractVector{<:Integer},
[C::AbstractSparseMatrixCSC{Tv,Ti}]) where {Tv,Ti}Aを両側から並べ替え、結果をXに格納します(PAQ(A[p,q]))。中間結果(AQ)^T(transpose(A[:,q]))は、存在する場合、オプション引数Cに格納されます。X、A、および存在する場合はCが互いにエイリアスでないことが必要です。結果PAQをAに戻して格納するには、Xを使わない次の方法を使用してください。
permute!(A::AbstractSparseMatrixCSC{Tv,Ti}, p::AbstractVector{<:Integer},
q::AbstractVector{<:Integer}[, C::AbstractSparseMatrixCSC{Tv,Ti},
[workcolptr::Vector{Ti}]]) where {Tv,Ti}Xの次元はA(size(X, 1) == size(A, 1)およびsize(X, 2) == size(A, 2))の次元と一致している必要があります。また、Xには、A(length(rowvals(X)) >= nnz(A)およびlength(nonzeros(X)) >= nnz(A))内の割り当て済みエントリをすべて格納できるだけの容量が必要です。列置換qの長さは、Aの列数(length(q) == size(A, 2))と一致している必要があります。行置換pの長さは、Aの行数(length(p) == size(A, 1))と一致している必要があります。
Cの次元はtranspose(A)(size(C, 1) == size(A, 2)およびsize(C, 2) == size(A, 1))の次元と一致している必要があります。また、Cには、A(length(rowvals(C)) >= nnz(A)およびlength(nonzeros(C)) >= nnz(A))内の割り当て済みエントリをすべて格納できるだけの容量が必要です。
アルゴリズムの詳細、および引数チェックを省略するこれらのメソッドのバージョンについては、非公開の親メソッドunchecked_noalias_permute!およびunchecked_aliasing_permute!を参照してください。
permuteも参照してください。
SparseArrays.halfperm! — Function
halfperm!(X::AbstractSparseMatrixCSC{Tv,Ti}, A::AbstractSparseMatrixCSC{TvA,Ti},
q::AbstractVector{<:Integer}, f::Function = identity) where {Tv,TvA,Ti}列を並べ替えて A を転置し、A の各要素に f を同時に適用して、結果 (f(A)Q)^T(map(f, transpose(A[:,q])))を X に格納します。
X の要素型 Tv は、f(::TvA) と一致している必要があります。ここで、A の要素型は TvA です。X の次元は transpose(A) の次元(size(X, 1) == size(A, 2) および size(X, 2) == size(A, 1))と一致している必要があります。また、X には、A 内で割り当て済みのすべてのエントリ(length(rowvals(X)) >= nnz(A) および length(nonzeros(X)) >= nnz(A))を格納できるだけの容量が必要です。列置換 q の長さは、A の列数(length(q) == size(A, 2))と一致している必要があります。
このメソッドは、SparseMatrixCSC に対する転置および置換操作を行う複数のメソッドの親メソッドです。このメソッドは引数の検査を行わないため、直接使用するよりも、安全性の高い子メソッド([c]transpose[!]、permute[!])を使用してください。
このメソッドは、F. Gustavson の論文「Two fast algorithms for sparse matrices: multiplication and permuted transposition」(ACM TOMS 4(3), 250–269, 1978)で説明されている HALFPERM アルゴリズムを実装しています。このアルゴリズムの実行時間は O(size(A, 1), size(A, 2), nnz(A)) で、渡された領域以外の追加領域を必要としません。
SparseArrays.ftranspose! — Function
ftranspose!(X::AbstractSparseMatrixCSC{Tv,Ti}, A::AbstractSparseMatrixCSC{Tv,Ti}, f::Function) where {Tv,Ti}Aを転置し、非ゼロ要素に関数fを適用しながら、Xに格納します。fによって生じたゼロは削除されません。size(X)はsize(transpose(A))と等しくなければなりません。必要な場合にXのrowvalとnzvalのサイズを変更する以外、追加のメモリは割り当てられません。
halfperm!を参照してください。
Noteworthy External Sparse Packages
疎行列を実装する Julia パッケージとして、ほかにも次のものがあります。
- SuiteSparseGraphBLAS.jl は、高速なマルチスレッド対応 SuiteSparse:GraphBLAS C ライブラリのラッパーです。CPU では通常、最速の選択肢であり、MKLSparse を大幅に上回ることもよくあります。
- CUDA.jl は、GPU 上の疎行列演算用ライブラリ CUSPARSE を公開します。
- SparseMatricesCSR.jl は、Compressed Sparse Rows(CSR)形式を Julia でネイティブに実装しています。
- MKLSparse.jl は、Intel の MKL ライブラリを使って SparseArrays の疎行列と密行列の演算を高速化します。
- SparseArrayKit.jl は、多次元疎配列向けに利用できます。
- LuxurySparse.jl は、静的疎配列形式に加えて、座標形式も提供します。
- ExtendableSparse.jl は、新たに格納するインデックスを遅延方式で扱うことで、疎行列への高速な挿入を可能にします。
- Finch.jl は、ミニテンソル言語とコンパイラーを通じて、幅広い多次元疎配列形式と演算をすべて Julia ネイティブでサポートします。COO、CSF、CSR、CSC などの形式に加え、ブロードキャストやリダクションなどの演算、カスタム演算にも対応しています。
疎行列の直接法ソルバーを提供する外部パッケージ:
固有系や特異値分解を反復法で解くソルバーを提供する外部パッケージ:
グラフを扱うための外部パッケージ: