Sparse Arrays

The SparseArrays stdlib module provides sparse vectors and sparse matrices: arrays with enough zeros that storing only the other entries saves space and time compared to dense arrays.

Sparse Vectors and Matrices
Specialized Sparse Arrays
- User-defined element types
- Sparse arrays with a fixed pattern
SparseArrays API
Noteworthy External Sparse Packages

Sparse Vectors and Matrices

Compressed Sparse Column (CSC) Sparse Matrix Storage

In Julia, sparse matrices are stored in the Compressed Sparse Column (CSC) format. Julia sparse matrices have the type SparseMatrixCSC{Tv,Ti}, where Tv is the type of the stored values, and Ti is the integer type for storing column pointers and row indices. The internal representation of SparseMatrixCSC is as follows:

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 storage makes access to the entries of a column fast, and access by row considerably slower. Inserting previously unstored entries one at a time is slow as well, because every entry beyond the point of insertion has to be moved one place over. See Performance tips.

A SparseMatrixCSC may store explicit zeros. nnz counts the stored entries, including stored zeros, and count(!iszero, x) counts the numerical nonzeros. dropzeros, and the in-place dropzeros!, remove stored zeros.

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

Arrays in CSC format from another application or library can be wrapped, without copying, with SparseMatrixCSC(m, n, colptr, rowval, nzval). Within each column the row indices must be sorted and unique, which the constructor does not check; the SparseMatrixCSC docstring lists the invariants. Arrays from a 0-based source, such as C or SciPy, need 1 added to colptr and rowval. To sort the row indices of a matrix A wrapped this way, transpose it twice, copy(transpose(copy(transpose(A)))).

The arrays of an m × n matrix in compressed sparse row (CSR) format are the CSC arrays of its transpose, so build the n × m matrix from them and transpose it:

julia> rowptr = [1, 3, 4]; colval = [1, 3, 2]; nzval = [1.0, 2.0, 3.0];  # 2 × 3 CSR

julia> copy(transpose(SparseMatrixCSC(3, 2, rowptr, colval, nzval)))
2×3 SparseMatrixCSC{Float64, Int64} with 3 stored entries:
 1.0   ⋅   2.0
  ⋅   3.0   ⋅

Sparse Vector Storage

Sparse vectors are stored in a close analog of the CSC format. They have the type SparseVector{Tv,Ti}, where Tv is the type of the stored values and Ti the integer type of the indices. The internal representation is as follows:

struct SparseVector{Tv,Ti<:Integer} <: AbstractSparseVector{Tv,Ti}
    n::Ti               # Length of the sparse vector
    nzind::Vector{Ti}   # Indices of stored values
    nzval::Vector{Tv}   # Stored values, typically nonzeros
end

Like a SparseMatrixCSC, a SparseVector can store explicit zeros. Its length is stored in the index type, so length(x) is a Ti rather than an Int.

Sparse Vector and Matrix Constructors

The simplest way to create a sparse array is spzeros, the equivalent of zeros for dense arrays:

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

sparse builds a sparse matrix from a vector I of row indices, a vector J of column indices and a vector V of stored values, known as the COO (coordinate) format: sparse(I,J,V) returns S such that S[I[k], J[k]] = V[k]. Its vector equivalent sparsevec takes the index vector I and the values V, and returns R such that R[I[k]] = V[k]. Values given for the same position are added.

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:
 ⋅  ⋅  ⋅  1  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅   ⋅
 ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅   ⋅
 ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  -5
 ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  2  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅   ⋅
 ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  3  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅   ⋅

julia> R = sparsevec(I,V)
5-element SparseVector{Int64, Int64} with 4 stored entries:
  [1]  =  1
  [3]  =  -5
  [4]  =  2
  [5]  =  3

findnz is the inverse of sparse and sparsevec: it returns the indices and values of the stored entries, including stored zeros. findall(!iszero, x) returns the indices of the nonzero entries of x, excluding stored zeros, and sparse also accepts the positions as such a vector of CartesianIndexes.

julia> findnz(S)
([1, 4, 5, 3], [4, 7, 9, 18], [1, 2, 3, -5])

julia> findnz(R)
([1, 3, 4, 5], [1, -5, 2, 3])

julia> sparse(findall(!iszero, S), [1, 2, 3, -5]) == S
true

sparse also converts a dense array to a sparse one, the Array constructor converts back, and issparse tells whether an array is sparse.

julia> sparse([1.0, 0.0, 1.0])
3-element SparseVector{Float64, Int64} with 2 stored entries:
  [1]  =  1.0
  [3]  =  1.0

julia> issparse(spzeros(5))
true

Other constructors build common matrices directly. sparse(I, n, n) is the identity, spdiagm places vectors on diagonals, and blockdiag puts matrices along the diagonal of a larger one. sprand and sprandn return a random vector or matrix in which each entry is stored with probability d, with uniformly or normally distributed values.

julia> spdiagm(0 => [1, 2, 3], 1 => [4, 5])
3×3 SparseMatrixCSC{Int64, Int64} with 5 stored entries:
 1  4  ⋅
 ⋅  2  5
 ⋅  ⋅  3

julia> blockdiag(sparse(2I, 2, 2), sparse([3 4])) == [2 0 0 0; 0 2 0 0; 0 0 3 4]
true

Sparse matrix operations

Sparse arrays support the operations of dense arrays, and a result is sparse unless it would store every entry. The subsections below give the rules for each kind of operation. indtype returns the index type Ti of a sparse array.

Arithmetic

Operation	Result
`A + B`, `A - B` of sparse arrays, or with a `Diagonal` or `I`	sparse, without the zeros it computes
`A + D`, `A - D` with a dense array `D`	dense
`-A`, `2A`, `A / 2`	sparse, with the stored entries of `A`
`A / 0`	sparse with every entry stored, as `0 / 0` is `NaN`

Elementwise operations written with dot syntax, such as A .* B or A .+ 1, follow the rules of Broadcasting and map.

Indexing and assignment

Indexing with ranges, vectors, colons or a logical mask returns a sparse array: A[I, J] is a SparseMatrixCSC, and A[:, j], A[i, :], A[:] and A[mask] are SparseVectors. A scalar index returns the element, which is zero when it is not stored.

Assigning to a stored entry overwrites its value, even with zero: the entry stays stored until dropzeros! removes it. Assigning zero to an entry that is not stored changes nothing, and assigning any other value inserts the entry, which moves every stored entry after it. Indexing, and especially assignment, is therefore expensive one element at a time; see Performance tips.

Concatenation

[A B], [A; B] and [A B; C D] return a sparse array when at least one argument is sparse. A dense argument contributes its nonzeros, and a Diagonal or I its diagonal. sparse_hcat, sparse_vcat and sparse_hvcat return a sparse array even when no argument is sparse.

Reductions

sum(A) and the other reductions over all entries visit the stored entries only. Along a dimension, as in sum(A; dims = 2), the result is dense. With sparse = true, such as sum(A; dims = 2, sparse = true), it is sparse instead: it stores an entry only for the rows of A that store one, and its cost is proportional to the number of stored entries. prod, maximum, minimum, count, any, all and mapreduce accept the keyword too.

Broadcasting and `map`

broadcast (including dot syntax such as A .* B) and map over sparse arrays return a sparse result when the function maps zeros to zero. To decide, the function is evaluated once on the zeros of the arguments' element types:

Arguments	`f(0, 0, ...)` is zero	`f(0, 0, ...)` is not zero
one sparse array	sparse, with the stored entries of the argument	`Array`
several sparse arrays	sparse, storing only the nonzero results	`Array`
sparse arrays and a scalar	the scalar is folded into `f`; then as above	sparse with every entry stored; `Array` if `f` is made only of `+` and `-`

So 2 .* A, abs.(A) and Float64.(A) keep the stored zeros of A, just as 2A, -A and float(A) do, while a combination of several sparse arrays drops the zeros it computes:

julia> A = sparse([1, 1, 2, 3], [1, 2, 2, 3], [1, 0, -2, 3])
3×3 SparseMatrixCSC{Int64, Int64} with 4 stored entries:
 1   0  ⋅
 ⋅  -2  ⋅
 ⋅   ⋅  3

julia> B = sparse([1, 1, 3], [1, 3, 3], [1, 5, -3]);

julia> A .+ B
3×3 SparseMatrixCSC{Int64, Int64} with 3 stored entries:
 2   ⋅  5
 ⋅  -2  ⋅
 ⋅   ⋅  ⋅

julia> iszero.(A)
3×3 BitMatrix:
 0  1  1
 1  0  1
 1  1  0

julia> A .+ 2
3×3 Matrix{Int64}:
 3  2  2
 2  0  2
 2  2  5

A result such as 2 .* A .+ 1 or A .^ 0, sparse with every entry stored, needs more memory than the equivalent Array; convert to dense first when that is what is meant.

Arguments that are not sparse arrays are handled as follows:

Argument	Treatment
a `Vector` or `Matrix`, or its adjoint or transpose	converted to sparse, so `A .* D` is sparse; a broadcast made only of `+` and `-` returns an `Array`, as `A + D` does
a `Diagonal`, `Bidiagonal`, `Tridiagonal` or `SymTridiagonal` matrix	converted to sparse
a view of whole columns of a sparse matrix, or of a range of a sparse vector	treated as a sparse array
anything else: a tuple, a range, a triangular or `Symmetric` wrapper, a view of some rows, an array of more than two dimensions	the generic broadcast, which visits every element and returns an `Array`

julia> A .* Diagonal([1, 2, 3])
3×3 SparseMatrixCSC{Int64, Int64} with 3 stored entries:
 1   ⋅  ⋅
 ⋅  -4  ⋅
 ⋅   ⋅  9

julia> typeof(A .* (1:3))
Matrix{Int64} (alias for Array{Int64, 2})

Whether a result is sparse depends on the value f(0, 0, ...), so its type is inferred only when the compiler can evaluate f there, as it does for the standard number types. A broadcast made only of +, - and * is always inferable.

map over sparse arrays always returns a sparse array, with every entry stored when f(0, 0, ...) is not zero. It requires all arguments to have the same shape, whereas broadcast expands singleton dimensions, with a sparse vector behaving as a one-column matrix.

broadcast!, map! and .= with a sparse destination overwrite its stored pattern with that of the result. The destination may also be one of the arguments, as in C .= C .+ C'. One exception: C .= 0 calls fill!, which keeps the pattern of C and sets the stored values to zero.

To apply a function to the stored values only, leaving the pattern untouched whatever the function returns for zero, broadcast over nonzeros instead:

julia> C = A .* B;

julia> nonzeros(C) .= nonzeros(C) .+ 9;

julia> C
3×3 SparseMatrixCSC{Int64, Int64} with 2 stored entries:
 10  ⋅  ⋅
  ⋅  ⋅  ⋅
  ⋅  ⋅  0

Products

The functions of LinearAlgebra have methods for sparse arrays. Products, dot, kron and the norms are implemented in this package, and the docstrings of those that behave differently for sparse arrays are listed under Linear algebra. The factorizations, and the solves that use them, call SuiteSparse and are described on the Sparse Linear Solvers page.

The result of * follows the other factor:

Product of a sparse matrix with	Result
a `Vector` or a `Matrix`	dense
a sparse vector	`SparseVector`
a sparse matrix	`SparseMatrixCSC`
a `Diagonal`, `Bidiagonal`, `Tridiagonal` or `SymTridiagonal` matrix	`SparseMatrixCSC`

mul!(y, A, x) writes the product into y, and mul!(y, A, x, α, β) computes A*x*α + y*β in place. A sparse destination is supported only for scaling by a Diagonal or a number. Products with A' and transpose(A) do not materialize the transpose when the other factor is dense or a sparse vector: see Lazy transpose and adjoint.

dot(x, y) of sparse or dense vectors and matrices visits the stored entries only, and dot(x, A, y) computes x' * A * y without forming A * y.
kron of two sparse arrays, or of a sparse array and a dense or Diagonal matrix, is sparse.

julia> A = sparse([2.0 1 0; 0 3 1; 1 0 4]); x = [1.0, 2.0, 3.0];

julia> y = similar(x); mul!(y, A, x)
3-element Vector{Float64}:
  4.0
  9.0
 13.0

julia> dot(x, A, x)
61.0

Norms and condition numbers

norm(A, p) treats A as a vector of its entries, so norm(A) is the Frobenius norm. opnorm(A, p) is the operator norm for p equal to 1, 2 or Inf; for p = 2 it is an iterative estimate.
cond(A, p) for p equal to 1 or Inf estimates the norm of the inverse from a factorization. The 2-norm condition number is not available; use cond(Array(A)) for a matrix small enough.
inv(A) throws, since the inverse is usually dense: solve with A \ B instead.

julia> norm(A, 1), opnorm(A, 1), opnorm(A, Inf)
(12.0, 5.0, 5.0)

Diagonals, triangles and permutations

tr(A) sums the diagonal, and diag(A, k) returns the kth diagonal as a SparseVector of the entries stored on it.
triu(A, k) and tril(A, k) return a new SparseMatrixCSC with the stored entries of a triangle, stored zeros included. triu! and tril! remove the other entries from A in place, changing its sparsity pattern.
permute applies a row and a column permutation in one pass.

Performance tips

Sparse code is fast when its cost is proportional to the number of stored entries, and the CSC layout determines which operations have that property.

Iterate over stored entries by column

The stored entries of column j are located at the positions nzrange(A, j) of rowvals(A) and nonzeros(A). Looping over the columns, and over that range within each column, visits every stored entry once and in memory order, without searching. For example, a matrix-vector product can be written as:

julia> A = sparse([1, 1, 2, 3], [1, 3, 2, 3], [1.0, 2.0, 3.0, 4.0]);

julia> function mymul(A::SparseMatrixCSC, x::Vector)
           y = zeros(promote_type(eltype(A), eltype(x)), size(A, 1))
           rows, vals = rowvals(A), nonzeros(A)
           for j in axes(A, 2), k in nzrange(A, j)
               y[rows[k]] += vals[k] * x[j]
           end
           return y
       end;

julia> mymul(A, [1.0, 10.0, 100.0]) == A * [1.0, 10.0, 100.0]
true

The same three accessors work on a SparseVector, which is treated as a single column, and on a view of whole columns such as @view A[:, j] or @view A[:, 2:3]. They are not defined for a triangular, Symmetric or Hermitian wrapper; work on its parent. getcolptr, getrowval and getnzval return the three storage vectors of a matrix themselves.

In contrast, scalar indexing A[i, j] has to do a binary search of column j for row i. A loop over all (i, j) of an m-by-n matrix therefore performs m * n searches, however few entries are stored.

Build a matrix from its entries in one call

Storing a value at a position that has no stored entry yet moves all the later entries, so filling spzeros(m, n) one element at a time takes time proportional to nnz(A) for each insertion. sizehint! avoids reallocating, but not moving the entries. Instead, collect the row indices, column indices and values in three vectors and call sparse once. Entries with the same position are added together, or combined with the function passed as the last argument, as in sparse(I, J, V, m, n, max).

To change many entries of an existing matrix, convert it to that form with findnz, work on the three vectors, and rebuild it.

Slice columns, not rows

A[:, j] copies one contiguous range of the stored entries. A[i, :] has to search every column for row i, so its cost grows with the number of columns even when the row is empty. When an algorithm works row by row, transpose the matrix once and work on the columns of the result. permutedims(A) and copy(transpose(A)) build the transposed matrix in time proportional to nnz(A).

julia> At = permutedims(A);

julia> At[:, 1] == A[1, :]
true

Choose a smaller index type

The index type Ti is used for the column pointers and for one row index per stored entry. With Float64 values, Int32 indices reduce the memory per stored entry from 16 to 12 bytes. Ti is taken from the index vectors given to sparse, can be given to spzeros, and an existing matrix is converted with the type constructor. Both dimensions have to be at most typemax(Ti), and the number of stored entries has to be less than typemax(Ti). Operations between matrices with different index types promote to the wider one, so use one index type consistently.

julia> A32 = SparseMatrixCSC{Float64,Int32}(A)
3×3 SparseMatrixCSC{Float64, Int32} with 4 stored entries:
 1.0   ⋅   2.0
  ⋅   3.0   ⋅
  ⋅    ⋅   4.0

julia> spzeros(Float64, Int8, 200, 200)
ERROR: ArgumentError: number of rows (m = 200) does not fit in Ti = Int8
[...]

Lazy `transpose` and `adjoint`

transpose(A) and A' do not copy; they return Transpose and Adjoint wrappers around A. What happens to a wrapper depends on the function:

Products with dense vectors and matrices (including mul!) and with sparse vectors, \, ==, and A'[i, :], which is a column slice of A, work on the wrapper without materializing the transpose.
Products with another sparse matrix, broadcasting (which includes + and -), map, concatenation, kron and findnz first copy the wrapper into a new SparseMatrixCSC, in time proportional to nnz(A), on every call.
Other functions, such as sum, norm and indexing other than by row, reach generic AbstractMatrix methods that visit the wrapper element by element.

When a transposed matrix is used more than once, or is passed to code outside the first group, materialize it with copy, or with sparse when the argument may or may not be a wrapper.

julia> A' * [1.0, 10.0, 100.0]
3-element Vector{Float64}:
   1.0
  30.0
 402.0

julia> copy(A')
3×3 SparseMatrixCSC{Float64, Int64} with 4 stored entries:
 1.0   ⋅    ⋅
  ⋅   3.0   ⋅
 2.0   ⋅   4.0

Keep results free of stored zeros

Assigning zero to a stored entry, and cancellation in a matrix product, leave explicitly stored zeros behind. They are harmless for correctness but are visited by every kernel. dropzeros! removes them, droptol! removes entries of small magnitude, and fkeep! keeps the entries for which a predicate of (i, j, v) is true, all in place.

julia> B = copy(A); B[1, 1] = 0; nnz(B)
4

julia> nnz(dropzeros!(B))
3

julia> fkeep!((i, j, v) -> i == j, B)
3×3 SparseMatrixCSC{Float64, Int64} with 2 stored entries:
 ⋅   ⋅    ⋅
 ⋅  3.0   ⋅
 ⋅   ⋅   4.0

Specialized Sparse Arrays

User-defined element types

A sparse array can store values of any type T. Building one from indices and values, copying, slicing, concatenating and permuting it, and reading a stored entry call nothing on the elements. Everything else rests on three things:

zero(T) is the value of an entry that is not stored. It is called on the type, not on a value, by whatever has to produce such an entry: indexing, setindex!, Matrix(A), a product with a dense array or a sparse vector, A + B, map, broadcasting and the reductions.
iszero(x) decides whether a value has to be stored. sparse of a dense array, dropzeros!, A + B, map and broadcasting call it. It falls back to x == zero(x).
The arithmetic of the operation itself: + and * for a product, isless for maximum, minimum and sort, and so on. sum adds the n entries that are not stored in one step, as zero(T) * n, so it also needs the product of an element with an integer.

The sparse kernels skip the entries that are not stored, so they assume that zero(T) behaves as a zero: x + zero(T) == x, and a product with zero(T) is zero. A type that defines zero, + and * is enough for most of the package, and every Number qualifies. For other element types:

Multiplying two sparse matrices needs only * and +, not zero(T). So a matrix of elements that have no zero(T), such as Matrix{Float64}, can be stored and multiplied by another, but not indexed at an entry that is not stored.
c * A, A * c and A / c are defined for a scalar c that is a Number. For any other element type, use map or broadcasting.
The sparse factorizations work in real and complex floating point. A matrix of integers or rationals is converted to Float64 first; a matrix of another element type, such as BigFloat, is rejected.

Sparse arrays with a fixed pattern

Experimental

fixed, FixedSparseCSC and FixedSparseVector are experimental and not exported.

Writing into a SparseMatrixCSC can change which entries it stores. W .= M .- γ .* J drops an entry of W wherever the difference is zero, and W[i, j] = v inserts one. Code that has derived something from the pattern of W, such as a symbolic factorization or the positions of its entries in nonzeros(W), is then silently out of date.

A fixed sparse array rules that out. It is a destination whose sparsity pattern never changes: the stored values can be overwritten, and no entry can be added or removed. SparseArrays.fixed makes one, with the arguments of sparse or from a sparse array, which it copies. Three rules describe everything a fixed array does; the SparseArrays.FixedSparseCSC docstring lists the functions each one covers.

A write lands inside the pattern or throws. A write, such as W .= ..., copyto!, mul! or W[i, j] = v, stores a value at each stored entry, a zero included, and leaves the pattern alone. What is written need not fill the pattern: the stored entries it leaves out become zero. A write that needs an entry where the pattern has none throws an ArgumentError, and the kernels of this package check for that before they change any value. Writing through nonzeros(W) is always allowed.

julia> J = sparse([1.0 2 0; 0 3 0; 4 0 5]); M = sparse(1.0I, 3, 3);

julia> nnz(M .- J)   # the entry at (1, 1) cancels and is not stored
4

julia> W = SparseArrays.fixed(M + J);

julia> W .= M .- J
3×3 SparseArrays.FixedSparseCSC{Float64, Int64} with 5 stored entries:
  0.0  -2.0    ⋅
   ⋅   -2.0    ⋅
 -4.0    ⋅   -4.0

julia> W[1, 3] = 1.0
ERROR: ArgumentError: cannot store a new entry at (1, 3) in a FixedSparseCSC, its sparsity pattern is read-only
[...]

A function that exists to change the pattern throws. dropzeros!, droptol!, fkeep!, tril!, sort!, permute! and the like refuse a fixed array as the argument they change. Their out-of-place forms work, because of the next rule.

julia> dropzeros!(W)
ERROR: ArgumentError: cannot `dropzeros!` a FixedSparseCSC: it would change the sparsity pattern, which is read-only; apply it to a writable copy, `SparseMatrixCSC(A)`
[...]

Reading a fixed array gives an ordinary result. As an operand, a fixed array behaves as the SparseMatrixCSC or SparseVector with the same entries, and what comes back is what that array would give. Being fixed is a property of one array, not of its values, so it does not carry over to indexing, arithmetic, broadcasting, concatenation or similar. Only copy(W) is fixed, and shares the pattern of W; SparseArrays.fixed(A) fixes any other result, and SparseMatrixCSC(W) gives a writable copy.

julia> typeof(2W), typeof(similar(W))
(SparseMatrixCSC{Float64, Int64}, SparseMatrixCSC{Float64, Int64})

julia> V = copy(W); rowvals(V) === rowvals(W)
true

The factorizations accept a fixed matrix, which is what makes reusing a symbolic factorization safe: see "Reusing a factorization" on the Sparse Linear Solvers page.

SparseArrays API

SparseArrays — Module

Sparse vectors and matrices: SparseVector and SparseMatrixCSC, which store only some of their entries and treat the others as zero. Build them with sparse, sparsevec and spzeros; the functions of Base and LinearAlgebra, including \ and the factorizations, have methods for them.

Types

SparseArrays.AbstractSparseArray — Type

AbstractSparseArray{Tv,Ti,N}

Supertype for N-dimensional sparse arrays (or array-like types) with elements of type Tv and index type Ti. SparseMatrixCSC, SparseVector and SparseArrays.CHOLMOD.Sparse are subtypes of this.

SparseArrays.AbstractSparseVector — Type

AbstractSparseVector{Tv,Ti}

Supertype for one-dimensional sparse arrays (or array-like types) with elements of type Tv and index type Ti. Alias for AbstractSparseArray{Tv,Ti,1}.

SparseArrays.AbstractSparseMatrix — Type

AbstractSparseMatrix{Tv,Ti}

Supertype for two-dimensional sparse arrays (or array-like types) with elements of type Tv and index type Ti. Alias for AbstractSparseArray{Tv,Ti,2}.

SparseArrays.AbstractSparseMatrixCSC — Type

AbstractSparseMatrixCSC{Tv,Ti<:Integer} <: AbstractSparseMatrix{Tv,Ti}

Supertype for matrices stored in compressed sparse column (CSC) format with element type Tv and index type Ti. SparseMatrixCSC is the concrete type; packages define their own subtypes to reuse the CSC kernels on other storage.

A subtype must define size and the three storage accessors getcolptr, getrowval and getnzval, which are the only accessors the methods of this package call on it. They return vectors that alias the matrix and satisfy the invariants documented for the SparseMatrixCSC constructor: getcolptr(S) has length size(S, 2) + 1, starts at 1 and is nondecreasing; getrowval(S) and getnzval(S) have length getcolptr(S)[end] - 1; and within each column the row indices are sorted, unique and in 1:size(S, 1). Everything else, such as nnz, nzrange, indexing, copy, similar and the sparse linear algebra, is derived from these. rowvals and nonzeros are not defined for such a subtype.

Subtypes written while rowvals and nonzeros were the only exported accessors implement those in place of getrowval and getnzval, which fall back to them. This remains supported, but is planned to stop being supported in SparseArrays 2.0.

SparseArrays.SparseVector — Type

SparseVector{Tv,Ti<:Integer} <: AbstractSparseVector{Tv,Ti}

A sparse vector, with stored values of type Tv at indices of type Ti. SparseVector(n, nzind, nzval) wraps, without copying, a vector nzind of indices, which must be sorted and unique, and the vector nzval of the values at those indices, as a vector of length n. sparsevec builds one from unsorted indices, and sparse from a dense vector.

The length is stored as a Ti, so length(x) and size(x) return values of type Ti rather than Int. A vector can then be longer than typemax(Int) when Ti is BigInt, but arithmetic on the length of a vector with a small index type can overflow; convert it with Int(length(x)) first.

Examples

julia> x = SparseVector(4, [1, 2, 4], [5, 6, 7])
4-element SparseVector{Int64, Int64} with 3 stored entries:
  [1]  =  5
  [2]  =  6
  [4]  =  7

julia> x == sparse([5, 6, 0, 7])
true

SparseArrays.SparseMatrixCSC — Type

SparseMatrixCSC{Tv,Ti<:Integer} <: AbstractSparseMatrixCSC{Tv,Ti}

Matrix type for storing sparse matrices in the Compressed Sparse Column format. The standard way of constructing SparseMatrixCSC is through the sparse function. See also spzeros, spdiagm and sprand.

SparseMatrixCSC(m::Integer, n::Integer, colptr::Vector, rowval::Vector, nzval::Vector)

Wrap existing CSC arrays as an m × n matrix without copying them. Column j holds the entries nzval[k] in rows rowval[k] for k in colptr[j]:(colptr[j+1] - 1).

Only colptr and the lengths of rowval and nzval are checked. The row indices are not inspected, and must be strictly increasing within each column and lie in 1:m. The kernels in this package rely on that. A matrix with unsorted, repeated or out-of-range row indices is constructed silently and then gives inconsistent results. To construct a matrix from repeated indices, use sparse, which adds up their values. See the manual for how to repair such arrays.

Examples

julia> SparseMatrixCSC(3, 2, [1, 3, 4], [1, 3, 2], [1.0, 2.0, 3.0])
3×2 SparseMatrixCSC{Float64, Int64} with 3 stored entries:
 1.0   ⋅
  ⋅   3.0
 2.0   ⋅

Constructors

SparseArrays.sparse — Function

sparse(A::Union{AbstractVector, AbstractMatrix})

Convert a vector or matrix A into a sparse array. Numerical zeros in A are turned into structural zeros.

Examples

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

julia> [1.0, 0.0, 1.0]
3-element Vector{Float64}:
 1.0
 0.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

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

Create a sparse matrix S of dimensions m x n such that S[I[k], J[k]] = V[k]. The combine function is used to combine duplicates. If m and n are not specified, they are set to maximum(I) and maximum(J) respectively. If the combine function is not supplied, combine defaults to + unless the elements of V are Booleans in which case combine defaults to |. All elements of I must satisfy 1 <= I[k] <= m, and all elements of J must satisfy 1 <= J[k] <= n. Numerical zeros in (I, J, V) are retained as structural nonzeros; to drop numerical zeros, use dropzeros!.

The positions may also be given as one vector IJ of two-dimensional CartesianIndexes, such that S[IJ[k]] = V[k].

For additional documentation and an expert driver, see SparseArrays.sparse!.

Julia 1.14

Passing the positions as a vector of CartesianIndexes requires at least Julia 1.14.

Examples

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

julia> sparse([CartesianIndex(1, 2), CartesianIndex(3, 1)], [10, 20], 3, 3)
3×3 SparseMatrixCSC{Int64, Int64} with 2 stored entries:
  ⋅  10  ⋅
  ⋅   ⋅  ⋅
 20   ⋅  ⋅

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}

Parent of and expert driver for sparse; see sparse for basic usage. This method allows the user to provide preallocated storage for sparse's intermediate objects and result as described below. This capability enables more efficient successive construction of SparseMatrixCSCs from coordinate representations, and also enables extraction of an unsorted-column representation of the result's transpose at no additional cost.

This method consists of three major steps: (1) Counting-sort the provided coordinate representation into an unsorted-row CSR form including repeated entries. (2) Sweep through the CSR form, simultaneously calculating the desired CSC form's column-pointer array, detecting repeated entries, and repacking the CSR form with repeated entries combined; this stage yields an unsorted-row CSR form with no repeated entries. (3) Counting-sort the preceding CSR form into a fully-sorted CSC form with no repeated entries.

Input arrays csrrowptr, csrcolval, and csrnzval constitute storage for the intermediate CSR forms and require length(csrrowptr) >= m + 1, length(csrcolval) >= length(I), and length(csrnzval >= length(I)). Input array klasttouch, workspace for the second stage, requires length(klasttouch) >= n. Optional input arrays csccolptr, cscrowval, and cscnzval constitute storage for the returned CSC form S. If necessary, these are resized automatically to satisfy length(csccolptr) = n + 1, length(cscrowval) = nnz(S) and length(cscnzval) = nnz(S); hence, if nnz(S) is unknown at the outset, passing in empty vectors of the appropriate type (Vector{Ti}() and Vector{Tv}() respectively) suffices, or calling the sparse! method neglecting cscrowval and cscnzval.

On return, csrrowptr, csrcolval, and csrnzval contain an unsorted-column representation of the result's transpose.

You may reuse the input arrays' storage (I, J, V) for the output arrays (csccolptr, cscrowval, cscnzval). For example, you may call sparse!(I, J, V, csrrowptr, csrcolval, csrnzval, I, J, V). Note that they will be resized to satisfy the conditions above.

For the sake of efficiency, this method performs no argument checking beyond 1 <= I[k] <= m and 1 <= J[k] <= n. Use with care. Testing with --check-bounds=yes is wise.

This method runs in O(m, n, length(I)) time. The HALFPERM algorithm described in F. Gustavson, "Two fast algorithms for sparse matrices: multiplication and permuted transposition," ACM TOMS 4(3), 250-269 (1978) inspired this method's use of a pair of counting sorts.

SparseArrays.sparse!(I, J, V, [m, n, combine]) -> SparseMatrixCSC

Variant of sparse! that re-uses the input vectors (I, J, V) for the final matrix storage. After construction the input vectors will alias the matrix buffers; S.colptr === I, S.rowval === J, and S.nzval === V holds, and they will be resize!d as necessary.

Note that some work buffers will still be allocated. Specifically, this method is a convenience wrapper around sparse!(I, J, V, m, n, combine, klasttouch, csrrowptr, csrcolval, csrnzval, csccolptr, cscrowval, cscnzval) where this method allocates klasttouch, csrrowptr, csrcolval, and csrnzval of appropriate size, but reuses I, J, and V for csccolptr, cscrowval, and cscnzval.

Arguments m, n, and combine defaults to maximum(I), maximum(J), and +, respectively.

Julia 1.10

This method requires Julia version 1.10 or later.

SparseArrays.sparsevec — Function

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

Create a sparse vector S of length m such that S[I[k]] = V[k]. Duplicates are combined using the combine function, which defaults to + if no combine argument is provided, unless the elements of V are Booleans in which case combine defaults to |.

Examples

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(d::Dict, [m])

Create a sparse vector of length m where the nonzero indices are keys from the dictionary, and the nonzero values are the values from the dictionary.

Examples

julia> sparsevec(Dict(1 => 3, 2 => 2))
2-element SparseVector{Int64, Int64} with 2 stored entries:
  [1]  =  3
  [2]  =  2

sparsevec(A)

Convert a vector A into a sparse vector of length m. Numerical zeros in A are turned into structural zeros.

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

SparseArrays.spzeros — Function

spzeros([type,]m[,n])

Create a sparse vector of length m or sparse matrix of size m x n. This sparse array will not contain any nonzero values, and no storage is allocated for them. The type defaults to Float64 if not specified.

This does not make the call allocation-free: the empty index and value buffers are still allocated, and a matrix additionally allocates a column pointer of n + 1 entries, so an m x n matrix uses memory proportional to n.

Examples

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

spzeros([type], I::AbstractVector, J::AbstractVector, [m, n])

Create a sparse matrix S of dimensions m x n with structural zeros at S[I[k], J[k]].

This method can be used to construct the sparsity pattern of the matrix, and is more efficient than using e.g. sparse(I, J, zeros(length(I))).

For additional documentation and an expert driver, see SparseArrays.spzeros!.

Julia 1.10

This methods requires Julia version 1.10 or later.

SparseArrays.spzeros! — Function

spzeros!(::Type{Tv}, I::AbstractVector{Ti}, J::AbstractVector{Ti}, m::Integer, n::Integer,
         klasttouch::Vector{Ti}, csrrowptr::Vector{Ti}, csrcolval::Vector{Ti},
         [csccolptr::Vector{Ti}], [cscrowval::Vector{Ti}, cscnzval::Vector{Tv}]) where {Tv,Ti<:Integer}

Parent of and expert driver for spzeros(I, J) allowing user to provide preallocated storage for intermediate objects. This method is to spzeros what SparseArrays.sparse! is to sparse. See documentation for SparseArrays.sparse! for details and required buffer lengths.

Julia 1.10

This methods requires Julia version 1.10 or later.

SparseArrays.spzeros!(::Type{Tv}, I, J, [m, n]) -> SparseMatrixCSC{Tv}

Variant of spzeros! that re-uses the input vectors I and J for the final matrix storage. After construction the input vectors will alias the matrix buffers; S.colptr === I and S.rowval === J holds, and they will be resize!d as necessary.

Note that some work buffers will still be allocated. Specifically, this method is a convenience wrapper around spzeros!(Tv, I, J, m, n, klasttouch, csrrowptr, csrcolval, csccolptr, cscrowval) where this method allocates klasttouch, csrrowptr, and csrcolval of appropriate size, but reuses I and J for csccolptr and cscrowval.

Arguments m and n defaults to maximum(I) and maximum(J).

Julia 1.10

This method requires Julia version 1.10 or later.

SparseArrays.spdiagm — Function

spdiagm(kv::Pair{<:Integer,<:AbstractVector}...)
spdiagm(m::Integer, n::Integer, kv::Pair{<:Integer,<:AbstractVector}...)

Construct a sparse diagonal matrix from Pairs of vectors and diagonals. Each vector kv.second will be placed on the kv.first diagonal. By default, the matrix is square and its size is inferred from kv, but a non-square size m×n (padded with zeros as needed) can be specified by passing m,n as the first arguments.

Examples

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)

Construct a sparse matrix with elements of the vector as diagonal elements. By default (no given m and n), the matrix is square and its size is given by length(v), but a non-square size m×n can be specified by passing m and n as the first arguments.

Julia 1.6

These functions require at least Julia 1.6.

Examples

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.blockdiag — Function

blockdiag(A...)

Concatenate matrices block-diagonally. Currently only implemented for sparse matrices.

Examples

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],[T::Type],m,[n],p::AbstractFloat)
sprand([rng],m,[n],p::AbstractFloat,[rfn=rand])

Create a random length m sparse vector or m by n sparse matrix, in which the probability of any element being nonzero is independently given by p (and hence the mean density of nonzeros is also exactly p). The optional rng argument specifies a random number generator, see Random Numbers. The optional T argument specifies the element type, which defaults to Float64.

By default, nonzero values are sampled from a uniform distribution using the rand function, i.e. by rand(T), or rand(rng, T) if rng is supplied; for the default T=Float64, this corresponds to nonzero values sampled uniformly in [0,1).

You can sample nonzero values from a different distribution by passing a custom rfn function instead of rand. This should be a function rfn(k) that returns an array of k random numbers sampled from the desired distribution; alternatively, if rng is supplied, it should instead be a function rfn(rng, k).

Examples

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)

Create a random sparse vector of length m or sparse matrix of size m by n with the specified (independent) probability p of any entry being nonzero, where nonzero values are sampled from the normal distribution. The optional rng argument specifies a random number generator, see Random Numbers.

Julia 1.1

Specifying the output element type Type requires at least Julia 1.1.

Examples

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

Base.similar — Method

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

Create a SparseMatrixCSC with the given element type, index type and size, based on A. Each of them defaults to that of A.

When no size is given, the result stores the same entries as A, with uninitialized values. When a size is given, the result stores no entries, and has room for as many as A stores.

The result is a writable SparseMatrixCSC also when A is a FixedSparseCSC; copy keeps a fixed pattern.

Examples

julia> A = sparse([1, 2], [1, 2], [1.5, 2.5]);

julia> B = similar(A, Int);

julia> rowvals(B) == rowvals(A), eltype(B)
(true, Int64)

julia> similar(A, 3, 4)
3×4 SparseMatrixCSC{Float64, Int64} with 0 stored entries:
 ⋅  ⋅  ⋅  ⋅
 ⋅  ⋅  ⋅  ⋅
 ⋅  ⋅  ⋅  ⋅

Stored entries

SparseArrays.issparse — Function

issparse(S)

Returns true if S is sparse or wraps a sparse array, and false otherwise.

issparse is a classification predicate. A true result does not guarantee support for a particular SparseArrays operation (such as nnz, nonzeros, or findnz), a particular sparse storage format, or that sparse(S) is an identity or efficient operation. Likewise, false means that S is not recognized as sparse by SparseArrays, not that it is dense: an array type that does not subtype AbstractSparseArray or wrap one yields false regardless of its storage. Code requiring a particular sparse interface should dispatch on the relevant abstract type or operation instead of branching on issparse.

Examples

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)

Returns the number of stored (filled) elements in a sparse array. For a column view or a triangular, Symmetric or Hermitian wrapper of a sparse matrix, it is the number of the parent's stored entries that belong to the view or wrapper (for a symmetric or Hermitian wrapper, those of the stored triangle).

Examples

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)

Return a tuple (I, J, V) where I and J are the row and column indices of the stored ("structurally non-zero") values in sparse matrix A, and V is a vector of the values. A may also be the adjoint or transpose of a sparse matrix or vector, in which case the values in V are correspondingly adjointed or transposed.

Examples

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.nonzeros — Function

nonzeros(A)

Return a vector of the structural nonzero values in sparse array A. This includes zeros that are explicitly stored in the sparse array. The returned vector points directly to the internal nonzero storage of A, and any modifications to the returned vector will mutate A as well. See rowvals and nzrange.

For a view of all rows and some columns of a sparse matrix, nonzeros returns a view of the parent's storage holding the entries of A only, so length(nonzeros(A)) is nnz(A) and writes to it mutate the parent. For a view of a range of columns the view is contiguous; for another column subset it gathers the positions of the stored entries, which takes time proportional to nnz(A).

nonzeros, rowvals and nzrange are not defined for a triangular, Symmetric or Hermitian wrapper of a sparse matrix, whose entries are not a compressed column structure of their own. Convert the wrapper with sparse, or work on parent(A).

Examples

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

julia> nonzeros(view(A, :, 2:3))
2-element view(::Vector{Int64}, 2:3) with eltype Int64:
 2
 2

SparseArrays.rowvals — Function

rowvals(A)

Return a vector of the row indices of sparse array A. Any modifications to the returned vector will mutate A as well. Providing access to how the row indices are stored internally can be useful in conjunction with iterating over structural nonzero values. See also nonzeros and nzrange.

Examples

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

For a view of all rows and some columns of a sparse matrix, rowvals returns a view of the parent's vector holding the row indices of the entries of A only, matching nonzeros. For a sparse vector or a column view of a sparse matrix, rowvals returns the indices of the stored entries:

julia> rowvals(sparsevec([2, 5], [1.5, 2.5], 6))
2-element Vector{Int64}:
 2
 5

SparseArrays.nzrange — Function

nzrange(A, col::Integer)

Return the range of positions of the stored entries of column col of the sparse matrix A in rowvals(A) and nonzeros(A). Looping over the columns and over this range visits every stored entry once, in storage order.

Examples

julia> A = sparse([1, 3, 2], [1, 1, 3], [10, 30, 20]);

julia> rows, vals = rowvals(A), nonzeros(A);

julia> [(rows[k], j, vals[k]) for j in axes(A, 2) for k in nzrange(A, j)]
3-element Vector{Tuple{Int64, Int64, Int64}}:
 (1, 1, 10)
 (3, 1, 30)
 (2, 3, 20)

The same loop works on a view of all rows and some columns of A, whose nzrange indexes the rowvals and nonzeros of the view. For a view of a range of columns each call is O(1); for another column subset nzrange(A, col) sums the lengths of the preceding columns, so it is O(col).

Warning

Adding or removing a stored entry invalidates the range, so do not change the pattern of the matrix while iterating.

nzrange(x::SparseVectorOrView, col)

Return the range of positions of the stored entries of the sparse vector x in rowvals(x) and nonzeros(x). A vector is treated as a single column, and col is ignored.

Examples

julia> x = sparsevec([2, 5], [1.5, 2.5], 6);

julia> [(rowvals(x)[k], nonzeros(x)[k]) for k in nzrange(x, 1)]
2-element Vector{Tuple{Int64, Float64}}:
 (2, 1.5)
 (5, 2.5)

SparseArrays.getcolptr — Function

getcolptr(S)

Return the vector of column start indices of an AbstractSparseMatrixCSC pointing into rowvals and nonzeros: column j is stored at positions getcolptr(S)[j]:(getcolptr(S)[j+1] - 1). The returned vector aliases S, but implementations with fixed sparsity may make it read-only. When it is writable, modifications to it mutate S. See also getrowval, getnzval and nzrange.

getcolptr is not defined for a SparseVector, which has no column pointers; use nzrange(x, 1) instead.

Examples

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

julia> getcolptr(A)
4-element Vector{Int64}:
 1
 2
 3
 4

SparseArrays.getrowval — Function

getrowval(A)

Return the vector of row indices of the structural nonzeros of sparse array A. For a SparseMatrixCSC this is the rowval field; for a SparseVector it is the nzind field. Any modifications to the returned vector will mutate A as well. Providing access to how the row indices are stored internally can be useful in conjunction with iterating over structural nonzero values. See also getnzval and nzrange.

For a SparseMatrixCSC or a SparseVector, getrowval is equivalent to rowvals. For a view of all rows and some columns of a sparse matrix it returns the parent's vector, of which rowvals(A) is the part belonging to A. It is not defined for a triangular, Symmetric or Hermitian wrapper of a sparse matrix; use getrowval(parent(A)), which also holds the entries outside the wrapper's triangle.

Examples

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

julia> getrowval(A)
3-element Vector{Int64}:
 1
 2
 3

julia> getrowval(sparsevec([2, 5], [3.0, 4.0]))
2-element Vector{Int64}:
 2
 5

SparseArrays.getnzval — Function

getnzval(A)

Return the vector of structural nonzero values of sparse array A, i.e. the nzval field of a SparseMatrixCSC or SparseVector. This includes zeros that are explicitly stored in the sparse array. The returned vector points directly to the internal nonzero storage of A, and any modifications to the returned vector will mutate A as well. See also getrowval and nzrange.

For a SparseMatrixCSC or a SparseVector, getnzval is equivalent to nonzeros. For a view of all rows and some columns of a sparse matrix it returns the parent's vector, of which nonzeros(A) is the part belonging to A. It is not defined for a triangular, Symmetric or Hermitian wrapper of a sparse matrix; use getnzval(parent(A)), which also holds the entries outside the wrapper's triangle.

Examples

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

julia> getnzval(A)
3-element Vector{Int64}:
 2
 2
 2

julia> getnzval(sparsevec([2, 5], [3.0, 4.0]))
2-element Vector{Float64}:
 3.0
 4.0

SparseArrays.indtype — Function

indtype(S)

Return the integer type in which sparse array S stores its indices: the Ti in SparseMatrixCSC{Tv,Ti} and SparseVector{Tv,Ti}. It is the index-type counterpart of eltype.

Examples

julia> indtype(sparse(Int32[1, 2], Int32[1, 2], [1.0, 2.0]))
Int32

julia> indtype(sparsevec(Int8[2, 5], [3.0, 4.0]))
Int8

julia> indtype(sparse([1, 2], [1, 2], [1.0, 2.0])')
Int64

Removing stored entries

SparseArrays.dropzeros — Function

dropzeros(A::AbstractSparseMatrixCSC;)

Generates a copy of A and removes stored numerical zeros from that copy.

For an in-place version and algorithmic information, see dropzeros!.

Examples

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)

Generates a copy of x and removes numerical zeros from that copy.

For an in-place version and algorithmic information, see dropzeros!.

Examples

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.dropzeros! — Function

dropzeros!(A::AbstractSparseMatrixCSC)

Remove the stored zeros from A, in place, and return A.

See also dropzeros, which returns a copy, and droptol!.

dropzeros!(x::AbstractCompressedVector)

Remove the stored zeros from x, in place, and return x.

See also dropzeros, which returns a copy, and droptol!.

SparseArrays.droptol! — Function

droptol!(A::AbstractSparseMatrixCSC, tol)

Remove from A, in place, the stored values whose absolute value is less than or equal to tol, and return A.

Examples

julia> A = sparse([1, 2, 3], [1, 2, 3], [1.0, 1e-9, -2.0]);

julia> droptol!(A, 1e-6)
3×3 SparseMatrixCSC{Float64, Int64} with 2 stored entries:
 1.0  ⋅    ⋅
  ⋅   ⋅    ⋅
  ⋅   ⋅  -2.0

droptol!(x::AbstractCompressedVector, tol)

Remove from x, in place, the stored values whose absolute value is less than or equal to tol, and return x.

SparseArrays.fkeep! — Function

fkeep!(f, A::AbstractSparseArray)

Keep elements of A for which test f returns true. f's signature should be

f(i::Integer, [j::Integer,] x) -> Bool

where i and j are an element's row and column indices and x is the element's value. This method makes a single sweep through A, requiring O(size(A, 2), nnz(A))-time for matrices and O(nnz(A))-time for vectors and no space beyond that passed in.

Examples

julia> A = sparse(Diagonal([1, 2, 3, 4]))
4×4 SparseMatrixCSC{Int64, Int64} with 4 stored entries:
 1  ⋅  ⋅  ⋅
 ⋅  2  ⋅  ⋅
 ⋅  ⋅  3  ⋅
 ⋅  ⋅  ⋅  4

julia> SparseArrays.fkeep!((i, j, v) -> isodd(v), A)
4×4 SparseMatrixCSC{Int64, Int64} with 2 stored entries:
 1  ⋅  ⋅  ⋅
 ⋅  ⋅  ⋅  ⋅
 ⋅  ⋅  3  ⋅
 ⋅  ⋅  ⋅  ⋅

Permuting, transposing and sorting

SparseArrays.permute — Function

permute(A::AbstractSparseMatrixCSC{Tv,Ti}, p::AbstractVector{<:Integer},
        q::AbstractVector{<:Integer}) where {Tv,Ti}

Bilaterally permute A, returning PAQ (A[p,q]). Column-permutation q's length must match A's column count (length(q) == size(A, 2)). Row-permutation p's length must match A's row count (length(p) == size(A, 1)).

For expert drivers and additional information, see permute!.

Examples

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}

Bilaterally permute A, storing result PAQ (A[p,q]) in X. Stores intermediate result (AQ)^T (transpose(A[:,q])) in optional argument C if present. Requires that none of X, A, and, if present, C alias each other; to store result PAQ back into A, use the following method lacking X:

permute!(A::AbstractSparseMatrixCSC{Tv,Ti}, p::AbstractVector{<:Integer},
         q::AbstractVector{<:Integer}[, C::AbstractSparseMatrixCSC{Tv,Ti},
         [workcolptr::Vector{Ti}]]) where {Tv,Ti}

X's dimensions must match those of A (size(X, 1) == size(A, 1) and size(X, 2) == size(A, 2)), and X must have enough storage to accommodate all allocated entries in A (length(rowvals(X)) >= nnz(A) and length(nonzeros(X)) >= nnz(A)). Column-permutation q's length must match A's column count (length(q) == size(A, 2)). Row-permutation p's length must match A's row count (length(p) == size(A, 1)).

C's dimensions must match those of transpose(A) (size(C, 1) == size(A, 2) and size(C, 2) == size(A, 1)), and C must have enough storage to accommodate all allocated entries in A (length(rowvals(C)) >= nnz(A) and length(nonzeros(C)) >= nnz(A)).

Concatenation

SparseArrays.sparse_hcat — Function

sparse_hcat(A...)

Concatenate along dimension 2. Return a SparseMatrixCSC object.

Julia 1.8

This method was added in Julia 1.8. It mimics previous concatenation behavior, where the concatenation with specialized "sparse" matrix types from LinearAlgebra.jl automatically yielded sparse output even in the absence of any SparseArray argument.

SparseArrays.sparse_vcat — Function

sparse_vcat(A...)

Concatenate along dimension 1. Return a SparseMatrixCSC object.

Julia 1.8

SparseArrays.sparse_hvcat — Function

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

Sparse horizontal and vertical concatenation in one call. This function is called for block matrix syntax. The first argument specifies the number of arguments to concatenate in each block row.

Julia 1.8

Fixed pattern (experimental)

SparseArrays.fixed — Function

fixed(x...)

Experimental. Like sparse but returns a sparse array whose sparsity pattern is read-only: stored entries can change value, but none can be added or removed.

fixed(A) of a writable sparse array A copies it, so the result shares no memory with A. Use SparseArrays.move_fixed to reuse the buffers of A instead. fixed(F) of a fixed array is copy(F): it copies the values and shares the pattern.

A write into the result keeps every stored entry and throws an ArgumentError, before changing anything, when it needs an entry outside the pattern. A function whose purpose is to change the pattern, such as dropzeros! or tril!, throws. Operations that read the result return ordinary arrays: of the out-of-place functions only copy returns a fixed array, sharing the pattern. See Sparse arrays with a fixed pattern.

Examples

julia> W = SparseArrays.fixed(sparse([1.0 2; 0 3]));

julia> W .= 0 .* W
2×2 SparseArrays.FixedSparseCSC{Float64, Int64} with 3 stored entries:
 0.0  0.0
  ⋅   0.0

julia> W[2, 1] = 1.0
ERROR: ArgumentError: cannot store a new entry at (2, 1) in a FixedSparseCSC, its sparsity pattern is read-only
[...]

julia> typeof(W + W)
SparseMatrixCSC{Float64, Int64}

SparseArrays.FixedSparseCSC — Type

FixedSparseCSC{Tv,Ti<:Integer} <: AbstractSparseMatrixCSC{Tv,Ti}

Experimental. A sparse matrix in CSC format whose sparsity pattern is read-only: stored values can be overwritten, but no entry can be added or removed.

A FixedSparseCSC is a destination for in-place writes. As an operand it behaves as the SparseMatrixCSC with the same entries, and results are not fixed; only copy returns a FixedSparseCSC, which shares the pattern. See Sparse arrays with a fixed pattern.

A write stores a value at each stored entry, a zero included, and throws an ArgumentError when it needs an entry that the pattern does not have. That holds for W .= ..., map!, copyto!, mul!, fill!, rmul!, lmul!, rdiv!, scalar and block setindex!, assignment through a column view, and for a result written into a fixed destination by transpose!, permute! or circshift!. The kernels of this package check before they change any value. Where the package has no method for a sparse destination, Julia's generic one writes one entry at a time: a broadcast into a view, a dense source as in W .= D or copyto!(W, D), axpy!(a, A, W), or mul! with a dense factor. Such a write stops at the first entry outside the pattern, with the entries before it already written. Writing through nonzeros(W) is always allowed.

A function whose purpose is to change the pattern throws for a fixed argument: dropzeros!, droptol!, fkeep!, tril!, triu!, dropstored!, sort!, permute!, invpermute!, reverse!, circshift!, swaprows! and swapcols!. Their out-of-place forms work, and return an ordinary array.

SparseArrays.FixedSparseVector — Type

FixedSparseVector{Tv,Ti<:Integer} <: AbstractCompressedVector{Tv,Ti}

Experimental. A sparse vector whose sparsity pattern is read-only: stored values can be overwritten, but no entry can be added or removed.

It follows the rules of SparseArrays.FixedSparseCSC: a destination for in-place writes, an ordinary SparseVector as an operand.

Linear algebra

Base.:* — Method

*(A::AbstractSparseMatrixCSC, B::AbstractSparseMatrixCSC)

Product of two sparse matrices, a SparseMatrixCSC whose index type is the promotion of those of A and B.

The cost is proportional to the number of products of stored entries, not to the size of the result. An entry is stored wherever such a product contributes, even when the contributions cancel or a factor holds a stored zero; dropzeros! removes them.

The kind of array returned follows the other factor: a sparse matrix times a dense Vector or Matrix is dense, and times a sparse vector or a Diagonal, Bidiagonal, Tridiagonal or SymTridiagonal matrix it is sparse. The adjoint or transpose of a sparse factor is read in place when the other factor is dense, and materialized, at a cost proportional to its number of stored entries, when the other factor is sparse too.

Examples

julia> A = sparse([1.0 1.0; 0.0 1.0]); B = sparse([1.0 0.0; -1.0 1.0]);

julia> A * B
2×2 SparseMatrixCSC{Float64, Int64} with 4 stored entries:
  0.0  1.0
 -1.0  1.0

LinearAlgebra.mul! — Method

mul!(C::AbstractSparseMatrixCSC, A::AbstractSparseMatrixCSC, D::Diagonal, α, β)
mul!(C::AbstractSparseMatrixCSC, D::Diagonal, A::AbstractSparseMatrixCSC, α, β)

Store A*D*α + C*β, or D*A*α + C*β, in the sparse matrix C, and return C: the columns, or the rows, of A scaled by the diagonal of D.

Unlike a dense destination, C takes a new sparsity pattern: that of A when β is zero, and otherwise the union of the patterns of A and C. A fixed-pattern C keeps its pattern instead, and mul! throws, with C unchanged, if a nonzero of the result falls outside it.

A sparse destination is supported for scaling only, by a Diagonal here or by a number with mul!(C, A, b). Form other products of sparse matrices with *. With a dense destination, mul!(C, A, B, α, β) takes a sparse A and a dense B, or the other way round, and reads the adjoint or transpose of a sparse factor in place.

Base.kron — Method

kron(A::AbstractSparseMatrixCSC, B::AbstractSparseMatrixCSC)

Kronecker product of two sparse matrices, a SparseMatrixCSC with nnz(A) * nnz(B) stored entries, stored zeros included.

With a dense or Diagonal matrix, a dense vector or a number as the other factor, the result is sparse too; a dense factor is first converted with sparse, which stores only its nonzeros. The Kronecker product of two sparse vectors is a SparseVector, and that of a sparse vector with the adjoint or transpose of one is a SparseMatrixCSC.

Examples

julia> kron(sparse([1 0; 0 2]), [1 2; 0 3])
4×4 SparseMatrixCSC{Int64, Int64} with 6 stored entries:
 1  2  ⋅  ⋅
 ⋅  3  ⋅  ⋅
 ⋅  ⋅  2  4
 ⋅  ⋅  ⋅  6

Base.kron! — Method

kron!(C::SparseMatrixCSC, A::AbstractSparseMatrixCSC, B::AbstractSparseMatrixCSC)

Store the Kronecker product of A and B in C, replacing its sparsity pattern, and return C. C must have size (size(A, 1) * size(B, 1), size(A, 2) * size(B, 2)), and its buffers are resized to hold nnz(A) * nnz(B) entries, so a C from an earlier call with operands of the same number of stored entries is reused without growing.

C must be a SparseMatrixCSC, and a SparseVector for two sparse vectors. A fixed-pattern destination is not accepted, since the pattern of C is replaced. The other factors accepted by kron are accepted here too.

LinearAlgebra.diag — Method

diag(A::AbstractSparseMatrixCSC, k::Integer=0)

The kth diagonal of the sparse matrix A, as a SparseVector with the index type of A that holds the entries stored on that diagonal, stored zeros included. A dense matrix gives a Vector instead.

Examples

julia> diag(sparse([1, 3], [1, 3], [5.0, 0.0]))
3-element SparseVector{Float64, Int64} with 2 stored entries:
  [1]  =  5.0
  [3]  =  0.0

LinearAlgebra.tril! — Method

tril!(M, k::Integer)

Return the lower triangle of M starting from the kth superdiagonal, overwriting M in the process.

Examples

julia> M = [1 2 3 4 5; 1 2 3 4 5; 1 2 3 4 5; 1 2 3 4 5; 1 2 3 4 5]
5×5 Matrix{Int64}:
 1  2  3  4  5
 1  2  3  4  5
 1  2  3  4  5
 1  2  3  4  5
 1  2  3  4  5

julia> tril!(M, 2)
5×5 Matrix{Int64}:
 1  2  3  0  0
 1  2  3  4  0
 1  2  3  4  5
 1  2  3  4  5
 1  2  3  4  5

tril!(A::AbstractSparseMatrixCSC, k::Integer=0)

Remove from A, in place, the stored entries above its kth diagonal, and return A. Stored zeros on and below that diagonal are kept.

A dense matrix has those entries set to zero; a sparse one drops them, which changes its sparsity pattern, so a fixed-pattern matrix throws an ArgumentError. tril(A, k) returns a new SparseMatrixCSC instead.

LinearAlgebra.triu! — Method

triu!(M, k::Integer)

Return the upper triangle of M starting from the kth superdiagonal, overwriting M in the process.

Examples

julia> M = [1 2 3 4 5; 1 2 3 4 5; 1 2 3 4 5; 1 2 3 4 5; 1 2 3 4 5]
5×5 Matrix{Int64}:
 1  2  3  4  5
 1  2  3  4  5
 1  2  3  4  5
 1  2  3  4  5
 1  2  3  4  5

julia> triu!(M, 1)
5×5 Matrix{Int64}:
 0  2  3  4  5
 0  0  3  4  5
 0  0  0  4  5
 0  0  0  0  5
 0  0  0  0  0

triu!(A::AbstractSparseMatrixCSC, k::Integer=0)

Remove from A, in place, the stored entries below its kth diagonal, and return A. Stored zeros on and above that diagonal are kept.

A dense matrix has those entries set to zero; a sparse one drops them, which changes its sparsity pattern, so a fixed-pattern matrix throws an ArgumentError. triu(A, k) returns a new SparseMatrixCSC instead.

LinearAlgebra.opnorm — Method

opnorm(A::AbstractMatrix, p::Real=2)

Compute the operator norm (or matrix norm) induced by the vector p-norm, where valid values of p are 1, 2, or Inf. (Note that for sparse matrices, p=2 is currently not implemented.) Use norm to compute the Frobenius norm.

When p=1, the operator norm is the maximum absolute column sum of A:

\[\|A\|_1 = \max_{1 ≤ j ≤ n} \sum_{i=1}^m | a_{ij} |\]

with $a_{ij}$ the entries of $A$, and $m$ and $n$ its dimensions.

When p=2, the operator norm is the spectral norm, equal to the largest singular value of A.

When p=Inf, the operator norm is the maximum absolute row sum of A:

\[\|A\|_\infty = \max_{1 ≤ i ≤ m} \sum _{j=1}^n | a_{ij} |\]

Examples

julia> A = [1 -2 -3; 2 3 -1]
2×3 Matrix{Int64}:
 1  -2  -3
 2   3  -1

julia> opnorm(A, Inf)
6.0

julia> opnorm(A, 1)
5.0

opnorm(A::AbstractSparseMatrixCSC, p::Real=2)

Operator p-norm of the sparse matrix A, for p equal to 1, 2 or Inf.

For p = 2 the norm is an iterative estimate from Lanczos bidiagonalization rather than a full singular value decomposition. It approaches the norm from below, to a relative accuracy of about 1e-10, and is computed in Float64 arithmetic even when the element type is wider. Each iteration costs a product with A and one with A'. Matrices whose largest singular values are tightly clustered may need a number of iterations comparable to their size; use opnorm(Array(A)) when such a matrix is small enough.

LinearAlgebra.cond — Method

cond(M, p::Real=2)

Condition number of the matrix M, computed using the operator p-norm. Valid values for p are 1, 2 (default), or Inf.

cond(A::AbstractSparseMatrixCSC, p::Real=2)

Condition number of the sparse matrix A in the operator p-norm, for p equal to 1 or Inf.

The norm of A is exact, and that of its inverse is estimated with the block 1-norm estimator of Higham and Tisseur, from a factorization of A by factorize and without forming the inverse, so the result can fall below the exact condition number. p = 2, the default, throws an ArgumentError, so cond(A) does too: use cond(Array(A)) for a matrix small enough to store dense.

Base.inv — Method

inv(A::AbstractSparseMatrixCSC)

Throw an error rather than invert a sparse matrix: the inverse is usually dense, even when A has few stored entries, and can exhaust memory. Solve with A \ B instead, which factorizes A without forming its inverse, or use inv(Matrix(A)) for a matrix small enough to store dense.

Noteworthy External Sparse Packages

Other Julia packages provide further sparse formats and operations:

SuiteSparseGraphBLAS.jl is a wrapper over the fast, multithreaded SuiteSparse:GraphBLAS C library.
CUDA.jl exposes the CUSPARSE library for GPU sparse matrix operations.
SparseMatricesCSR.jl provides a Julia native implementation of the Compressed Sparse Rows (CSR) format.
MKLSparse.jl accelerates SparseArrays sparse-dense matrix operations using Intel's MKL library.
SparseArrayKit.jl provides multidimensional sparse arrays.
LuxurySparse.jl provides static sparse array formats, as well as a coordinate format.
ExtendableSparse.jl enables fast insertion into sparse matrices using a lazy approach to new stored indices.
Finch.jl supports extensive multidimensional sparse array formats and operations through a mini tensor language and compiler, all in native Julia. Support for COO, CSF, CSR, CSC and more, as well as operations like broadcast, reduce, etc. and custom operations.

External packages providing sparse direct solvers:

External packages providing solvers for iterative solution of eigensystems and singular value decompositions:

External packages for working with graphs:

Graphs.jl