Разреженные массивы

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

Внешние пакеты, которые реализуют различные типы для хранения разреженных данных, многомерные разреженные массивы и т. п., приведены в разделе Важные внешние пакеты для хранения разреженных данных

Хранение разреженных матриц в формате сжатых разреженных столбцов (CSC)

В Julia разреженные матрицы хранятся в формате сжатых разреженных столбцов (CSC). Разреженные матрицы в Julia имеют тип SparseMatrixCSC{Tv,Ti}, где Tv — это тип хранимых значений, а Ti — целочисленный тип для хранения указателей столбцов и индексов строк. Внутреннее представление SparseMatrixCSC имеет следующий вид:

struct SparseMatrixCSC{Tv,Ti<:Integer} <: AbstractSparseMatrixCSC{Tv,Ti}
    m::Int                  # Количество строк
    n::Int                  # Количество столбцов
    colptr::Vector{Ti}      # Столбец j находится в colptr[j]:(colptr[j+1]-1)
    rowval::Vector{Ti}      # Индексы строк хранимых значений
    nzval::Vector{Tv}       # Хранимые значения, обычно ненулевые
end

Хранение разреженных столбцов в сжатом виде позволяет легко и быстро получать доступ к элементам столбца разреженной матрицы, в то время как доступ к разреженной матрице по строкам происходит гораздо медленнее. Такие операции, как вставка новых элементов по одному, в структуре CSC обычно осуществляются медленно. Причина в том, что все элементы разреженной матрицы после точки вставки необходимо переместить на одну позицию.

Все операции с разреженными матрицами были тщательно продуманы для обеспечения высокой производительности и экономии ресурсов при работе со структурой данных CSC.

Если вы хотите импортировать в Julia данные в формате CSC из другого приложения или библиотеки, используйте индексирование от единицы. Индексы строк в каждом столбце должны быть отсортированы. В противном случае матрица будет отображаться неправильно. Если объект 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  ⋅
 ⋅  ⋅  ⋅

Хранение разреженных векторов

Разреженные векторы хранятся в формате, который очень похож на формат сжатых разреженных столбцов для разреженных матриц. Разреженные векторы в Julia имеют тип SparseVector{Tv,Ti}, где Tv — это тип хранимых значений, а Ti — целочисленный тип для индексов. Внутреннее представление имеет следующий вид:

struct SparseVector{Tv,Ti<:Integer} <: AbstractSparseVector{Tv,Ti}
    n::Int              # Длина разреженного вектора
    nzind::Vector{Ti}   # Индексы хранимых значений
    nzval::Vector{Tv}   # Хранимые значения, обычно ненулевые
end

Так же как и SparseMatrixCSC, тип SparseVector может содержать явно сохраненные нулевые значения. (См. раздел Хранение разреженных матриц.)

Конструкторы разреженных векторов и матриц

Самый простой способ создать разреженный массив — воспользоваться функцией, которая эквивалентна функции zeros, используемой в Julia для работы с плотными массивами. Чтобы получить разреженный массив, можно использовать то же имя, но с префиксом sp:

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

Для создания разреженных массивов часто бывает удобна функция sparse. Например, чтобы создать разреженную матрицу, можно передать вектор I индексов строк, вектор J индексов столбцов и вектор V хранимых значений (такой формат также называется COO (координированным)). В результате 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

Операции с разреженными матрицами

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

Соответствие плотных и разреженных методов

В следующей таблице сопоставляются встроенные методы для работы с разреженными матрицами и соответствующие методы для работы с матрицами плотных типов. В целом методы, создающие разреженные матрицы, отличаются от аналогов для плотных матриц тем, что итоговая матрица имеет то же расположение ненулевых элементов, что и разреженная матрица S, или тем, что итоговая разреженная матрица имеет плотность d, то есть каждый элемент матрицы является ненулевым с вероятностью d.

Подробные сведения см. в разделе Разреженные векторы и матрицы справки по стандартной библиотеке.

Разреженная Плотная Описание

Разреженная	Плотная	Описание
`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), которая содержит ненулевые значения, независимо, одинаково и равномерно распределенные в полуинтервале .
`sprandn(m,n,d)`	`randn(m,n)`	Создает случайную матрицу размером m на n (с плотностью d), которая содержит ненулевые значения, независимо и одинаково распределенные согласно стандартному нормальному распределению (распределению Гаусса).
`sprandn(rng,m,n,d)`	`randn(rng,m,n)`	Создает случайную матрицу размером m на n (с плотностью d), которая содержит независимо и одинаково распределенные ненулевые значения, созданные генератором случайных чисел `rng`.

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), которая содержит ненулевые значения, независимо, одинаково и равномерно распределенные в полуинтервале .

sprandn(m,n,d)

randn(m,n)

Создает случайную матрицу размером m на n (с плотностью d), которая содержит ненулевые значения, независимо и одинаково распределенные согласно стандартному нормальному распределению (распределению Гаусса).

sprandn(rng,m,n,d)

randn(rng,m,n)

Создает случайную матрицу размером m на n (с плотностью d), которая содержит независимо и одинаково распределенные ненулевые значения, созданные генератором случайных чисел rng.

API SparseArrays

# SparseArrays.AbstractSparseArray — Type

AbstractSparseArray{Tv,Ti,N}

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

# SparseArrays.AbstractSparseVector — Type

AbstractSparseVector{Tv,Ti}

Супертип для одномерных разреженных массивов (или массивоподобных типов) с элементами типа Tv и типом индекса Ti. Псевдоним для AbstractSparseArray{Tv,Ti,1}.

# SparseArrays.AbstractSparseMatrix — Type

AbstractSparseMatrix{Tv,Ti}

Супертип для двумерных разреженных массивов (или массивоподобных типов) с элементами типа Tv и типом индекса Ti. Псевдоним для 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}

Матричный тип для хранения разреженных матриц в формате сжатых разреженных столбцов. Стандартный способ создания SparseMatrixCSC — с помощью функции sparse. См. также spzeros, spdiagm и sprand.

# SparseArrays.sparse — Function

sparse(A)

Преобразовывает объект AbstractMatrix A в разреженную матрицу.

Примеры

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

sparse(I, J, V,[ m, n, combine])

Создает разреженную матрицу S размером m x n такую, что S[I[k], J[k]] = V[k]. Поиск combine используется для объединения дубликатов. Если m и n не указаны, им присваиваются значения maximum(I) и maximum(J) соответственно. Если функция combine не предоставлена, в качестве combine по умолчанию используется +, если только элементы V не являются логическими значениями. В этом случае по умолчанию в качестве combine используется |. Все элементы I должны отвечать условию 1 <= I[k] <= m, а все элементы J — условию 1 <= J[k] <= n. Числовые нули в (I, J, V) сохраняются как структурные ненулевые значения; для удаления числовых нулей используйте dropzeros!.

Дополнительную документацию и рекомендации см. в описании функции SparseArrays.sparse!.

Примеры

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  ⋅
 ⋅  ⋅  3

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

Данный метод выполняется в три основных этапа: 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)). Ввод массив 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}() соответственно) или вызвать метод sparse!, игнорируя cscrowval и cscnzval.

При возврате управления 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)). На использование в этом методе двух сортировок подсчетом вдохновил алгоритм HALFPERM, описанный в работе Ф. Густавсона (F. Gustavson) Two fast algorithms for sparse matrices: multiplication and permuted transposition, ACM TOMS 4(3), 250-269 (1978).

# SparseArrays.sparsevec — Function

sparsevec(I, V, [m, combine])

Создает разреженный вектор S длиной m такой, что S[I[k]] = V[k]. Дубликаты объединяются с помощью функции combine, в качестве которой по умолчанию используется +, если аргумент combine не указан. Исключением является случай, когда элементы V представляют собой логические значения. В таком случае в качестве combine по умолчанию используется |.

Примеры

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]  =  1

sparsevec(A)

Преобразовывает вектор A в разреженный вектор длиной m.

Примеры

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.0

sparsevec(A)

Convert a vector A into a sparse vector of length m.

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.0

# Base.similar — Method

similar(A::AbstractSparseMatrixCSC{Tv,Ti}, [::Type{TvNew}, ::Type{TiNew}, m::Integer, n::Integer]) where {Tv,Ti}

Создает неинициализированный изменяемый массив с заданным типом элементов, типом индексов и размером на основе заданного исходного SparseMatrixCSC. Новая разреженная матрица сохраняет структуру исходной разреженной матрицы, за исключением случая, когда измерения выходной матрицы отличаются от выходных данных.

Выходная матрица имеет нули в тех же расположениях, что и входная, но имеет неинициализированные значения в ненулевых расположениях.

# SparseArrays.issparse — Function

issparse(S)

Возвращает true, если S является разреженным, и false в противном случае.

Примеры

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))
false

# SparseArrays.nnz — Function

nnz(A)

Возвращает количество хранимых (добавленных) элементов в разреженном массиве.

Примеры

julia> A = sparse(2I, 3, 3)
3×3 SparseMatrixCSC{Int64, Int64} with 3 stored entries:
 2  ⋅  ⋅
 ⋅  2  ⋅
 ⋅  ⋅  2

julia> nnz(A)
3

# SparseArrays.findnz — Function

findnz(A::SparseMatrixCSC)

Возвращает кортеж (I, J, V), где I и J — это индексы строк и столбцов хранимых («структурных ненулевых») значений в разреженной матрице A, а V — вектор значений.

Примеры

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, если тип не указан.

Примеры

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 entries

# 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 в качестве первых аргументов.

Примеры

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 в качестве первых аргументов.

Совместимость: Julia 1.6

Для этих функций требуется версия Julia не ниже 1.6.

Примеры

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  ⋅  ⋅
 ⋅  ⋅  ⋅
 ⋅  ⋅  3

# SparseArrays.sparse_hcat — Function

sparse_hcat(A...)

Выполняет конкатенацию в измерении 2. Возвращает объект SparseMatrixCSC.

Совместимость: Julia 1.8

Этот метод был добавлен в Julia 1.8. Он воспроизводит предыдущее поведение конкатенации, которое заключалось в том, что конкатенация со специализированными «разреженными» типами матриц из LinearAlgebra.jl автоматически давала разреженный результат даже при отсутствии аргумента SparseArray.

# SparseArrays.sparse_vcat — Function

sparse_vcat(A...)

Выполняет конкатенацию в измерении 1. Возвращает объект SparseMatrixCSC.

Совместимость: Julia 1.8

# SparseArrays.sparse_hvcat — Function

sparse_hvcat(rows::Tuple{Vararg{Int}}, values...)

Разреженная горизонтальная и вертикальная конкатенация в одном вызове. Эта функция вызывается для синтаксиса блочной матрицы. Первый аргумент задает количество аргументов для конкатенации в каждой строке блока.

Совместимость: Julia 1.8

# SparseArrays.blockdiag — Function

blockdiag(A...)

Выполняет конкатенацию матриц поблочно по диагонали. В настоящее время реализовано только для разреженных матриц.

Примеры

julia> blockdiag(sparse(2I, 3, 3), sparse(4I, 2, 2))
5×5 SparseMatrixCSC{Int64, Int64} with 5 stored entries:
 2  ⋅  ⋅  ⋅  ⋅
 ⋅  2  ⋅  ⋅  ⋅
 ⋅  ⋅  2  ⋅  ⋅
 ⋅  ⋅  ⋅  4  ⋅
 ⋅  ⋅  ⋅  ⋅  4

# SparseArrays.sprand — Function

sprand([rng],[type],m,[n],p::AbstractFloat,[rfn])

Создает разреженный вектор случайной длины m или разреженную матрицу размером m на n, в которых вероятность того, что любой элемент является ненулевым, задается независимо с помощью p (и поэтому средняя плотность ненулевых значений всегда равна p). Ненулевые значения выбираются из распределения, указанного в rfn, и имеют тип type. Если аргумент rfn не указан, применяется равномерное распределение. Необязательный rng указывается генератор случайных чисел; см. раздел Случайные числа.

Примеры

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.49425

# SparseArrays.sprandn — Function

sprandn([rng][,Type],m[,n],p::AbstractFloat)

Создает случайный разреженный вектор длиной m или разреженную матрицу размером m на n, в которой каждый элемент является ненулевым с указанной (независимой) вероятностью p, а ненулевые значения выбираются из нормального распределения. Необязательный rng указывается генератор случайных чисел; см. раздел Случайные числа.

Совместимость: Julia 1.1

Для указания типа выходных элементов Type требуется версия не ниже Julia 1.1.

Примеры

julia> sprandn(2, 2, 0.75)
2×2 SparseMatrixCSC{Float64, Int64} with 3 stored entries:
 -1.20577     ⋅
  0.311817  -0.234641

# SparseArrays.nonzeros — Function

nonzeros(A)

Возвращает вектор структурных ненулевых значений в разреженном массиве A. Эта включаются нули, сохраненные в разреженном массиве явным образом. Возвращаемый вектор указывает непосредственно на внутреннее ненулевое хранилище A, а любое изменение возвращаемого вектора приводит также к изменению A. Дополнительные сведения rowvals и nzrange.

Примеры

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
 2

# SparseArrays.rowvals — Function

rowvals(A::AbstractSparseMatrixCSC)

Возвращает вектор индексов строк A. Любое изменение возвращаемого вектора приводит также к изменению A. Доступ к внутренней информации о том, как хранятся индексы строк, может быть полезен в связи с итерацией по структурным ненулевым значениям. См. также описание nonzeros и nzrange.

Примеры

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
 3

# SparseArrays.nzrange — Function

nzrange(A::AbstractSparseMatrixCSC, col::Integer)

Возвращает диапазон индексов структурных ненулевых значений в столбце разреженной матрицы. В сочетании с 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]
      # операции с разреженной матрицей...
   end
end

nzrange(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!, которая является версией данной функции, выполняемой на месте.

Примеры

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.0

dropzeros(x::AbstractCompressedVector)

Создает копию x и удаляет из нее числовые нули.

Примеры

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.0

# SparseArrays.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!.

Примеры

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, сохраняя результат PAQ (A[p,q]) в X. Сохраняет промежуточный результат (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, одновременно применяя f к каждому элементу A и сохраняя результат (f(A)Q)^T (map(f, transpose(A[:,q]))) в X.

Тип элементов Tv матрицы X должен соответствовать f(::TvA), где TvA — это тип элементов матрицы A. Измерения матрицы 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[!]).

Этот метод реализует алгоритм HALFPERM, описанный в работе Ф. Густавсона (F. Gustavson) Two fast algorithms for sparse matrices: multiplication and permuted transposition, ACM TOMS 4(3), 250-269 (1978). Алгоритм выполняется за время 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 и сохраняет ее в X, одновременно применяя функцию f к ненулевым элементам. Нулевые элементы, создаваемые функцией f, не удаляются. size(X) должно быть равно size(transpose(A)). Дополнительная память, помимо изменения размера rowval и nzval для X (если это необходимо), не выделяется.

Дополнительные сведения см. в описании halfperm!.

Важные внешние пакеты для хранения разреженных данных

Следует упомянуть еще ряд пакетов Julia, реализующих разреженные матрицы:

SuiteSparseGraphBLAS.jl — это оболочка вокруг быстрой многопоточной библиотеки C SuiteSparse:GraphBLAS. При выполнении на ЦП она обычно показывает наиболее высокое быстродействие, зачастую значительно превосходя MKLSparse.
CUDA.jl предоставляет библиотеку CUSPARSE для операций с разреженными матрицами на GPU.
SparseMatricesCSR.jl предоставляет собственную реализацию формата CSR (Compressed Sparse Rows, сжатые разреженные строки) в Julia.
MKLSparse.jl ускоряет операции с разреженно-плотными матрицами SparseArrays посредством библиотеки MKL от Intel.
SparseArrayKit.jl реализует многомерные разреженные массивы.
LuxurySparse.jl предоставляет форматы статических разреженных массивов, а также формат координат.
ExtendableSparse.jl обеспечивает быструю вставку в разреженные матрицы посредством отложенного подхода к новых сохраняемым индексам.
Finch.jl поддерживает расширенные форматы многомерных разреженных массивов и операции с ними посредством простого языка тензоров и компилятора, реализованных на Julia. Поддерживаются форматы COO, CSF, CSR, CSC и другие, а также такие операции, как трансляция, сокращение и т. д., и пользовательские операции.