Sparse Arrays

Julia, seyrek vektörler ve sparse matrices için SparseArrays stdlib modülünde destek sunmaktadır. Seyrek diziler, yeterince sıfır içeren dizilerdir; bu dizileri özel bir veri yapısında saklamak, yoğun dizilere kıyasla alan ve yürütme süresinde tasarruf sağlar.

Farklı seyrek depolama türlerini, çok boyutlu seyrek dizileri ve daha fazlasını uygulayan harici paketler Noteworthy External Sparse Packages içinde bulunabilir.

Compressed Sparse Column (CSC) Sparse Matrix Storage

Julia'da seyrek matrisler Compressed Sparse Column (CSC) format içinde saklanır. Julia seyrek matrislerinin tipi SparseMatrixCSC{Tv,Ti} şeklindedir; burada Tv saklanan değerlerin tipi ve Ti sütun işaretçileri ve satır indekslerini saklamak için kullanılan tam sayı tipidir. SparseMatrixCSC'nin içsel temsili aşağıdaki gibidir:

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

Sıkıştırılmış seyrek sütun depolama, seyrek bir matrisin sütunundaki elemanlara erişimi kolay ve hızlı hale getirirken, seyrek matrisi satırlar halinde erişmek oldukça daha yavaştır. CSC yapısında daha önce depolanmamış girişlerin birer birer eklenmesi gibi işlemler yavaş olma eğilimindedir. Bunun nedeni, ekleme noktasının ötesindeki seyrek matrisin tüm elemanlarının bir yer kaydırılması gerektiğidir.

Seyrek matrisler üzerindeki tüm işlemler, performans için CSC veri yapısını kullanacak şekilde dikkatlice uygulanmıştır ve pahalı işlemlerden kaçınılmıştır.

Eğer farklı bir uygulamadan veya kütüphaneden CSC formatında veriniz varsa ve bunu Julia'ya aktarmak istiyorsanız, 1 tabanlı indeksleme kullandığınızdan emin olun. Her sütundaki satır indeksleri sıralı olmalıdır ve eğer sıralı değillerse, matris yanlış bir şekilde görüntülenecektir. Eğer SparseMatrixCSC nesneniz sıralanmamış satır indeksleri içeriyorsa, bunları sıralamanın hızlı bir yolu çift transpoz yapmaktır. Transpoz işlemi tembel olduğu için, her transpozun somutlaşması için bir kopya oluşturun.

Bazı uygulamalarda, SparseMatrixCSC içinde açık sıfır değerlerini saklamak kullanışlıdır. Bu değerler Base içindeki fonksiyonlar tarafından kabul edilir (ancak mutasyona uğrayan işlemlerde korunacaklarına dair bir garanti yoktur). Açıkça saklanan bu sıfırlar, birçok rutin tarafından yapısal sıfır olmayanlar olarak değerlendirilir. nnz fonksiyonu, yapısal olmayan sıfırlar da dahil olmak üzere, seyrek veri yapısında açıkça saklanan elemanların sayısını döndürür. Sayısal sıfır olmayanların tam sayısını saymak için, her bir saklanan elemanı inceleyen count(!iszero, x) fonksiyonunu kullanın. dropzeros ve yerinde dropzeros! fonksiyonları, saklanan sıfırları seyrek matrisinden kaldırmak için kullanılabilir.

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

Seyrek vektörler, seyrek matrisler için sıkıştırılmış seyrek sütun formatına yakın bir şekilde saklanır. Julia'da, seyrek vektörlerin tipi SparseVector{Tv,Ti} şeklindedir; burada Tv saklanan değerlerin tipi ve Ti ise indeksler için tam sayı tipidir. İçsel temsil aşağıdaki gibidir:

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 için SparseVector türü ayrıca açıkça saklanan sıfırlar da içerebilir. (Bkz. Sparse Matrix Storage.)

Sparse Vector and Matrix Constructors

En basit seyrek dizi oluşturma yolu, Julia'nın yoğun dizilerle çalışmak için sağladığı zeros fonksiyonuna eşdeğer bir fonksiyon kullanmaktır. Bunun yerine seyrek bir dizi üretmek için, aynı ismi sp ön eki ile kullanabilirsiniz:

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

sparse fonksiyonu genellikle seyrek diziler oluşturmak için kullanışlı bir yoldur. Örneğin, bir seyrek matris oluşturmak için bir satır indeksleri vektörü I, bir sütun indeksleri vektörü J ve saklanan değerler vektörü V girebiliriz (bu aynı zamanda COO (coordinate) format olarak bilinir). sparse(I,J,V) ardından S[I[k], J[k]] = V[k] olacak şekilde bir seyrek matris oluşturur. Eşdeğer seyrek vektör yapıcı sparsevec olup, (satır) indeks vektörü I ve saklanan değerlerle birlikte vektör V alır ve R[I[k]] = V[k] olacak şekilde bir seyrek vektör R oluşturur.

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 ve sparsevec fonksiyonlarının tersinin findnz olduğu, seyrek diziyi oluşturmak için kullanılan girdileri (sıfıra eşit olan saklanan girişler dahil) geri getirdiği belirtilmektedir. findall(!iszero, x) ise x içindeki sıfıra eşit olmayan girişlerin Kartezyen indekslerini döndürmektedir (sıfıra eşit olan saklanan girişler dahil değildir).

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

Başka bir seyrek dizi oluşturmanın bir yolu, yoğun bir diziyi sparse fonksiyonunu kullanarak seyrek bir diziye dönüştürmektir:

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

Diğer yönde Array yapıcısını kullanarak gidebilirsiniz. issparse fonksiyonu, bir matrisin seyrek olup olmadığını sorgulamak için kullanılabilir.

julia> issparse(spzeros(5))
true

Sparse matrix operations

Seyrek matrisler üzerinde aritmetik işlemler, yoğun matrislerde olduğu gibi çalışır. Seyrek matrislerin indekslenmesi, atanması ve birleştirilmesi, yoğun matrisler gibi aynı şekilde çalışır. İndeksleme işlemleri, özellikle atama, bir seferde bir eleman üzerinde gerçekleştirildiğinde pahalıdır. Birçok durumda, seyrek matrisi findnz formatına dönüştürmek, değerleri veya yapıyı yoğun vektörlerde (I,J,V) manipüle etmek ve ardından seyrek matrisi yeniden inşa etmek daha iyi olabilir.

Correspondence of dense and sparse methods

Aşağıdaki tablo, seyrek matrisler üzerindeki yerleşik yöntemler ile yoğun matris türlerindeki karşılık gelen yöntemler arasındaki ilişkiyi vermektedir. Genel olarak, seyrek matrisler üreten yöntemler, sonuçta elde edilen matrisin belirli bir seyrek matris S ile aynı seyreklik desenini takip etmesi veya sonuçta elde edilen seyrek matrisin yoğunluğunun d olması, yani her matris elemanının sıfır olmama olasılığının d olması açısından yoğun karşıtlarından farklıdır.

Detaylar, standart kütüphane referansının Sparse Vectors and Matrices bölümünde bulunabilir.

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

Sparse Linear Algebra

Seyrek matris çözücüleri SuiteSparse adresinden fonksiyonlar çağırır. Aşağıdaki faktorizasyonlar mevcuttur:

Type	Description
`CHOLMOD.Factor`	Cholesky and LDLt factorizations
`UMFPACK.UmfpackLU`	LU factorization
`SPQR.QRSparse`	QR factorization

Bu faktorizasyonlar, Sparse Linear Algebra API section içinde daha ayrıntılı olarak açıklanmaktadır:

SparseArrays API

SparseArrays.AbstractSparseArray — Type

AbstractSparseArray{Tv,Ti,N}

Tv türünde ve Ti indeks türünde elemanlara sahip N-boyutlu seyrek diziler (veya dizi benzeri türler) için süpertip. SparseMatrixCSC, SparseVector ve SuiteSparse.CHOLMOD.Sparse bunun alt türleridir.

Bileşen	Açıklama
`L`	`LU`'nun `L` (alt üçgen) kısmı
`U`	`LU`'nun `U` (üst üçgen) kısmı
`p`	sağ permütasyon `Vector`
`q`	sol permütasyon `Vector`
`Rs`	ölçekleme faktörlerinin `Vector`'ı
`:`	`(L,U,p,q,Rs)` bileşenleri

Bileşen	Açıklama
`F.L`	`LU`'nun `L` (alt üçgen) kısmı
`F.U`	`LU`'nun `U` (üst üçgen) kısmı
`F.p`	(sağ) permütasyon `Vector`
`F.P`	(sağ) permütasyon `Matrix`

Desteklenen işlev	`LU`	`LU{T,Tridiagonal{T}}`
`/`	✓
`\`	✓	✓
`inv`	✓	✓
`det`	✓	✓
`logdet`	✓	✓
`logabsdet`	✓	✓
`size`	✓	✓