Sparse Arrays

줄리아는 희소 벡터와 sparse matrices를 SparseArrays 표준 라이브러리 모듈에서 지원합니다. 희소 배열은 충분한 수의 0을 포함하고 있어, 이를 특별한 데이터 구조에 저장하면 밀집 배열에 비해 공간과 실행 시간에서 절약을 할 수 있습니다.

다양한 희소 저장 유형, 다차원 희소 배열 등을 구현하는 외부 패키지는 Noteworthy External Sparse Packages에서 찾을 수 있습니다.

Compressed Sparse Column (CSC) Sparse Matrix Storage

줄리아에서 희소 행렬은 Compressed Sparse Column (CSC) format에 저장됩니다. 줄리아 희소 행렬의 타입은 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 형식의 데이터가 다른 애플리케이션이나 라이브러리에서 온 경우, 이를 줄리아에 가져오려면 1 기반 인덱싱을 사용해야 합니다. 모든 열의 행 인덱스는 정렬되어 있어야 하며, 그렇지 않으면 행렬이 잘못 표시됩니다. SparseMatrixCSC 객체에 정렬되지 않은 행 인덱스가 포함되어 있는 경우, 이를 정렬하는 빠른 방법 중 하나는 이중 전치(transpose)를 수행하는 것입니다. 전치 연산은 지연(lazy) 방식으로 수행되므로, 각 전치를 구체화하기 위해 복사본을 만들어야 합니다.

일부 응용 프로그램에서는 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 유형이 명시적으로 저장된 0을 포함할 수 있습니다. (참조: 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

희소 행렬에 대한 산술 연산은 밀집 행렬에서와 동일하게 작동합니다. 희소 행렬의 인덱싱, 할당 및 연결은 밀집 행렬과 동일한 방식으로 작동합니다. 인덱싱 작업, 특히 할당은 한 번에 하나의 요소를 처리할 때 비용이 많이 듭니다. 많은 경우 희소 행렬을 findnz 형식의 (I,J,V)로 변환하고, 밀집 벡터 (I,J,V)에서 값이나 구조를 조작한 다음, 희소 행렬을 재구성하는 것이 더 나을 수 있습니다.

Correspondence of dense and sparse methods

다음 표는 희소 행렬의 내장 메서드와 밀집 행렬 유형의 해당 메서드 간의 대응 관계를 제공합니다. 일반적으로 희소 행렬을 생성하는 메서드는 결과 행렬이 주어진 희소 행렬 S와 동일한 희소성 패턴을 따르거나, 결과 희소 행렬이 밀도 d를 가지며, 즉 각 행렬 요소가 0이 아닐 확률이 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

Sparse Linear Algebra

희소 행렬 솔버는 SuiteSparse에서 함수를 호출합니다. 다음과 같은 분해가 가능합니다:

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

이러한 인수분해는 Sparse Linear Algebra API section에서 더 자세히 설명되어 있습니다:

SparseArrays API

SparseArrays.AbstractSparseArray — Type

AbstractSparseArray{Tv,Ti,N}

Tv 유형의 요소와 Ti 유형의 인덱스를 가진 N 차원 희소 배열(또는 배열 유사 유형)의 슈퍼타입입니다. SparseMatrixCSC, SparseVector 및 SuiteSparse.CHOLMOD.Sparse는 이의 하위 유형입니다.

구성 요소	설명
`L`	`LU`의 `L` (하삼각) 부분
`U`	`LU`의 `U` (상삼각) 부분
`p`	오른쪽 치환 `Vector`
`q`	왼쪽 치환 `Vector`
`Rs`	스케일링 계수의 `Vector`
`:`	`(L,U,p,q,Rs)` 구성 요소

구성 요소	설명
`F.L`	`LU`의 `L` (하삼각) 부분
`F.U`	`LU`의 `U` (상삼각) 부분
`F.p`	(오른쪽) 순열 `Vector`
`F.P`	(오른쪽) 순열 `Matrix`

지원 함수	`LU`	`LU{T,Tridiagonal{T}}`
`/`	✓
`\`	✓	✓
`inv`	✓	✓
`det`	✓	✓
`logdet`	✓	✓
`logabsdet`	✓	✓
`size`	✓	✓