Sparse Arrays

Julia поддерживает разреженные векторы и sparse matrices в стандартной библиотеке модуля SparseArrays. Разреженные массивы — это массивы, которые содержат достаточно нулей, чтобы хранение их в специальной структуре данных приводило к экономии места и времени выполнения по сравнению с плотными массивами.

Внешние пакеты, которые реализуют различные типы разреженного хранения, многомерные разреженные массивы и многое другое, можно найти в 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 из другого приложения или библиотеки и вы хотите импортировать их в 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

Самый простой способ создать разреженный массив — использовать функцию, эквивалентную функции zeros, которую предоставляет Julia для работы с плотными массивами. Чтобы получить разреженный массив, вы можете использовать то же имя с префиксом 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

Арифметические операции над разреженными матрицами работают так же, как и над плотными матрицами. Индексация, присваивание и конкатенация разреженных матриц работают так же, как и плотные матрицы. Операции индексации, особенно присваивание, являются дорогими, когда выполняются по одному элементу за раз. Во многих случаях может быть лучше преобразовать разреженную матрицу в формат (I,J,V) с использованием findnz, манипулировать значениями или структурой в плотных векторах (I,J,V), а затем восстановить разреженную матрицу.

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

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}

Супертип для N-мерных разреженных массивов (или типов, подобных массивам) с элементами типа Tv и типом индекса Ti. SparseMatrixCSC, SparseVector и SuiteSparse.CHOLMOD.Sparse являются подтипами этого.

Компонент	Описание
`L`	`L` (нижняя треугольная) часть `LU`
`U`	`U` (верхняя треугольная) часть `LU`
`p`	правая перестановка `Vector`
`q`	левая перестановка `Vector`
`Rs`	`Vector` коэффициентов масштабирования
`:`	компоненты `(L,U,p,q,Rs)`

Компонент	Описание
`F.L`	`L` (нижняя треугольная) часть `LU`
`F.U`	`U` (верхняя треугольная) часть `LU`
`F.p`	(правое) перестановка `Vector`
`F.P`	(правое) перестановка `Matrix`

Поддерживаемая функция	`LU`	`LU{T,Tridiagonal{T}}`
`/`	✓
`\`	✓	✓
`inv`	✓	✓
`det`	✓	✓
`logdet`	✓	✓
`logabsdet`	✓	✓
`size`	✓	✓