Sparse Arrays

Julia a un support pour les vecteurs creux et sparse matrices dans le module standard SparseArrays. Les tableaux creux sont des tableaux qui contiennent suffisamment de zéros pour que les stocker dans une structure de données spéciale entraîne des économies d'espace et de temps d'exécution, par rapport aux tableaux denses.

Des packages externes qui implémentent différents types de stockage sparse, des tableaux sparse multidimensionnels, et plus encore peuvent être trouvés dans Noteworthy External Sparse Packages

Compressed Sparse Column (CSC) Sparse Matrix Storage

En Julia, les matrices creuses sont stockées dans le Compressed Sparse Column (CSC) format. Les matrices creuses Julia ont le type SparseMatrixCSC{Tv,Ti}, où Tv est le type des valeurs stockées, et Ti est le type entier pour stocker les pointeurs de colonne et les indices de ligne. La représentation interne de SparseMatrixCSC est la suivante :

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

Le stockage en colonne éparse compressé facilite et accélère l'accès aux éléments de la colonne d'une matrice éparse, tandis que l'accès à la matrice éparse par lignes est considérablement plus lent. Des opérations telles que l'insertion d'entrées précédemment non stockées une à une dans la structure CSC tendent à être lentes. Cela est dû au fait que tous les éléments de la matrice éparse qui se trouvent au-delà du point d'insertion doivent être déplacés d'une place.

Toutes les opérations sur les matrices creuses sont soigneusement mises en œuvre pour tirer parti de la structure de données CSC pour des performances optimales et éviter des opérations coûteuses.

Si vous avez des données au format CSC provenant d'une autre application ou bibliothèque, et que vous souhaitez les importer dans Julia, assurez-vous d'utiliser un indexage basé sur 1. Les indices de ligne dans chaque colonne doivent être triés, et s'ils ne le sont pas, la matrice s'affichera incorrectement. Si votre objet SparseMatrixCSC contient des indices de ligne non triés, une façon rapide de les trier est de faire une double transposition. Étant donné que l'opération de transposition est paresseuse, faites une copie pour matérialiser chaque transposition.

Dans certaines applications, il est pratique de stocker des valeurs zéro explicites dans un SparseMatrixCSC. Celles-ci sont acceptées par les fonctions de Base (mais il n'y a aucune garantie qu'elles seront préservées lors des opérations de mutation). Ces zéros stockés explicitement sont traités comme des non-zéros structurels par de nombreuses routines. La fonction nnz renvoie le nombre d'éléments stockés explicitement dans la structure de données sparse, y compris les zéros non structurels. Pour compter le nombre exact de non-zéros numériques, utilisez count(!iszero, x), qui inspecte chaque élément stocké d'une matrice sparse. dropzeros, et le dropzeros! en place, peuvent être utilisés pour supprimer les zéros stockés de la matrice sparse.

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

Les vecteurs creux sont stockés dans un analogue proche du format de colonne creuse compressée pour les matrices creuses. En Julia, les vecteurs creux ont le type SparseVector{Tv,Ti} où Tv est le type des valeurs stockées et Ti le type entier pour les indices. La représentation interne est la suivante :

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

En ce qui concerne SparseMatrixCSC, le type SparseVector peut également contenir des zéros stockés explicitement. (Voir Sparse Matrix Storage.)

Sparse Vector and Matrix Constructors

La manière la plus simple de créer un tableau creux est d'utiliser une fonction équivalente à la fonction zeros que Julia fournit pour travailler avec des tableaux denses. Pour produire un tableau creux à la place, vous pouvez utiliser le même nom avec un préfixe sp :

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

La fonction sparse est souvent un moyen pratique de construire des tableaux creux. Par exemple, pour construire une matrice creuse, nous pouvons entrer un vecteur I d'indices de lignes, un vecteur J d'indices de colonnes et un vecteur V de valeurs stockées (ceci est également connu sous le nom de COO (coordinate) format). sparse(I,J,V) construit alors une matrice creuse telle que S[I[k], J[k]] = V[k]. Le constructeur de vecteur creux équivalent est sparsevec, qui prend le vecteur d'indices (de ligne) I et le vecteur V avec les valeurs stockées et construit un vecteur creux R tel que 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

L'inverse des fonctions sparse et sparsevec est findnz, qui récupère les entrées utilisées pour créer le tableau sparse (y compris les entrées stockées égales à zéro). findall(!iszero, x) renvoie les indices cartésiens des entrées non nulles dans x (sans inclure les entrées stockées égales à zéro).

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

Une autre façon de créer un tableau sparse est de convertir un tableau dense en un tableau sparse en utilisant la fonction 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

Vous pouvez aller dans l'autre direction en utilisant le constructeur Array. La fonction issparse peut être utilisée pour interroger si une matrice est éparse.

julia> issparse(spzeros(5))
true

Sparse matrix operations

Les opérations arithmétiques sur les matrices creuses fonctionnent également comme sur les matrices denses. L'indexation, l'assignation et la concaténation des matrices creuses fonctionnent de la même manière que pour les matrices denses. Les opérations d'indexation, en particulier l'assignation, sont coûteuses lorsqu'elles sont effectuées un élément à la fois. Dans de nombreux cas, il peut être préférable de convertir la matrice creuse en format (I,J,V) en utilisant findnz, de manipuler les valeurs ou la structure dans les vecteurs denses (I,J,V), puis de reconstruire la matrice creuse.

Correspondence of dense and sparse methods

Le tableau suivant donne une correspondance entre les méthodes intégrées sur les matrices creuses et leurs méthodes correspondantes sur les types de matrices denses. En général, les méthodes qui génèrent des matrices creuses diffèrent de leurs homologues denses en ce sens que la matrice résultante suit le même motif de parcimonie qu'une matrice creuse donnée S, ou que la matrice creuse résultante a une densité d, c'est-à-dire que chaque élément de la matrice a une probabilité d d'être non nul.

Les détails peuvent être trouvés dans la section Sparse Vectors and Matrices de la référence de la bibliothèque standard.

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

Les solveurs de matrices creuses appellent des fonctions de SuiteSparse. Les factorisations suivantes sont disponibles :

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

Ces factorizations sont décrites plus en détail dans le Sparse Linear Algebra API section :

SparseArrays API

SparseArrays.AbstractSparseArray — Type

AbstractSparseArray{Tv,Ti,N}

Supertype pour les tableaux (ou types similaires) creux de dimension N avec des éléments de type Tv et un type d'index Ti. SparseMatrixCSC, SparseVector et SuiteSparse.CHOLMOD.Sparse sont des sous-types de ceci.

Composant	Description
`L`	partie `L` (triangulaire inférieure) de `LU`
`U`	partie `U` (triangulaire supérieure) de `LU`
`p`	permutation à droite `Vector`
`q`	permutation à gauche `Vector`
`Rs`	`Vector` de facteurs d'échelle
`:`	composants `(L,U,p,q,Rs)`

Composant	Description
`F.L`	`L` (partie triangulaire inférieure) de `LU`
`F.U`	`U` (partie triangulaire supérieure) de `LU`
`F.p`	permutation `Vector` (droite)
`F.P`	permutation `Matrix` (droite)

Fonction prise en charge	`LU`	`LU{T,Tridiagonal{T}}`
`/`	✓
`\`	✓	✓
`inv`	✓	✓
`det`	✓	✓
`logdet`	✓	✓
`logabsdet`	✓	✓
`size`	✓	✓