Julia's Extended Sparse Array Interface

The following ArrayInterface functions extend Julia's Base LinearAlgebra interface to improve the ability to do sparse linear algebra.

Sparse Indexing

These routines allow for improving sparse iteration and indexing.

ArrayInterface.isstructured — Function

isstructured(::Type{T}) -> Bool

Query whether a type is a representation of a structured matrix.

source

ArrayInterface.findstructralnz — Function

findstructralnz(x::AbstractArray)

Return: (I,J) #indexable objects Find sparsity pattern of special matrices, the same as the first two elements of findnz(::SparseMatrixCSC).

source

ArrayInterface.has_sparsestruct — Function

has_sparsestruct(x::AbstractArray) -> Bool

Determine whether findstructralnz accepts the parameter x.

source

ArrayInterface.same_sparsity_structure — Function

same_sparsity_structure(A, B) -> Bool

Return true when A and B store their nonzeros in exactly the same structural positions, i.e. they share an identical sparsity pattern (and shape). This is the condition under which values may be written into B reusing A's stored layout (or a cached symbolic factorization of A reused for B) without rebuilding the structure.

Semantics by category:

Dense arrays store every position, so two of them share a structure exactly when they have the same shape.
Structured (Diagonal, Bidiagonal, Tridiagonal, SymTridiagonal) and sparse (SparseMatrixCSC, GPU CSC/CSR) matrices compare by their pattern — shape (plus uplo/format) or the stored index arrays (e.g. colptr/rowval for CSC).
Two arrays whose base types differ (e.g. a structured matrix and a dense one, or two different structured types) return false: a layout is not reused across categories, so they are treated as "not the same structure".
Two arrays of the same base type with no specialized method are unknown, not false: rather than fabricate an answer, a MethodError is thrown so the type can define its own method. (has_sparsestruct can be used to check applicability first.)

Unlike findstructralnz, this performs no allocation on its fast paths, so it is suitable for use in hot loops (for example, deciding per Jacobian evaluation whether a sparse jac_prototype's structure needs rebuilding).

source

Matrix Coloring

Many routines require calculating the coloring of a matrix, such as for sparse differentation. The matrix_colors function is the high level function which returns a color vector Vector{Int} with the column colors. This function is overloaded for many special matrix types with analytical solutions for the matrix colors.

ArrayInterface.fast_matrix_colors — Function

fast_matrix_colors(A)

Query whether a matrix has a fast algorithm for getting the structural colors of the matrix.

source

ArrayInterface.matrix_colors — Function

matrix_colors(A::Union{Array,UpperTriangular,LowerTriangular})

The color vector for dense matrix and triangular matrix is simply [1,2,3,..., Base.size(A,2)].

source

General Matrix Colors

For the general dispatch of matrix_colors, see SparseDiffTools.jl for a full graph-based coloring algorithm which extends ArrayInterface.

Addtional Sparse Array Interface Tools

If dealing with general sparse arrays, consider:

SparseDiffTools.jl: A general set of tools for extending calculus libraries for sparse optimizations.
LinearSolve.jl: An extended linear solving library with support for generic sparse arrays.