稀疏数组

    在Julia中，稀疏矩阵是按照压缩稀疏列(CSC)格式存储的。Julia稀疏矩阵具有类型，其中Tv是存储值的类型，Ti是存储列指针和行索引的整型类型。SparseMatrixCSC的内部表示如下所示：

    压缩稀疏列存储格式使得访问稀疏矩阵的列元素非常简单快速，而访问稀疏矩阵的行会非常缓慢。在CSC稀疏矩阵中执行类似插入新元素的操作也会非常慢。这是由于在稀疏矩阵中插入新元素时，在插入点之后的所有元素都要向后移动一位。

    All operations on sparse matrices are carefully implemented to exploit the CSC data structure for performance, and to avoid expensive operations.

    If you have data in CSC format from a different application or library, and wish to import it in Julia, make sure that you use 1-based indexing. The row indices in every column need to be sorted. If your SparseMatrixCSC object contains unsorted row indices, one quick way to sort them is by doing a double transpose.

    In some applications, it is convenient to store explicit zero values in a SparseMatrixCSC. These are accepted by functions in Base (but there is no guarantee that they will be preserved in mutating operations). Such explicitly stored zeros are treated as structural nonzeros by many routines. The nnz function returns the number of elements explicitly stored in the sparse data structure, including structural nonzeros. In order to count the exact number of numerical nonzeros, use , which inspects every stored element of a sparse matrix. dropzeros, and the in-place , can be used to remove stored zeros from the sparse matrix.

    1. julia> A = sparse([1, 2, 3], [1, 2, 3], [0, 2, 0])
    2. 3×3 SparseMatrixCSC{Int64,Int64} with 3 stored entries:
    3.   [1, 1]  =  0
    4.   [2, 2]  =  2
    5.   [3, 3]  =  0
    7. julia> dropzeros(A)
    8. 3×3 SparseMatrixCSC{Int64,Int64} with 1 stored entry:
    9.   [2, 2]  =  2

    Sparse vectors are stored in a close analog to compressed sparse column format for sparse matrices. In Julia, sparse vectors have the type SparseVector{Tv,Ti} where Tv is the type of the stored values and Ti the integer type for the indices. The internal representation is as follows:

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

    As for , the SparseVector type can also contain explicitly stored zeros. (See Sparse Matrix Storage.).

    The simplest way to create a sparse array is to use a function equivalent to the function that Julia provides for working with dense arrays. To produce a sparse array instead, you can use the same name with an sp prefix:

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

    The sparse function is often a handy way to construct sparse arrays. For example, to construct a sparse matrix we can input a vector I of row indices, a vector J of column indices, and a vector V of stored values (this is also known as the ). sparse(I,J,V) then constructs a sparse matrix such that S[I[k], J[k]] = V[k]. The equivalent sparse vector constructor is sparsevec, which takes the (row) index vector I and the vector V with the stored values and constructs a sparse vector R such that R[I[k]] = V[k].

    1. julia> I = [1, 4, 3, 5]; J = [4, 7, 18, 9]; V = [1, 2, -5, 3];
    3. julia> S = sparse(I,J,V)
    4. 5×18 SparseMatrixCSC{Int64,Int64} with 4 stored entries:
    5.   [1 ,  4]  =  1
    6.   [4 ,  7]  =  2
    7.   [5 ,  9]  =  3
    8.   [3 , 18]  =  -5
    10. julia> R = sparsevec(I,V)
    11. 5-element SparseVector{Int64,Int64} with 4 stored entries:
    12.   [1]  =  1
    13.   [3]  =  -5
    14.   [4]  =  2
    15.   [5]  =  3

    The inverse of the and sparsevec functions is , which retrieves the inputs used to create the sparse array. findall(!iszero, x) returns the cartesian indices of non-zero entries in x (including stored entries equal to zero).

    1. julia> findnz(S)
    2. ([1, 4, 5, 3], [4, 7, 9, 18], [1, 2, 3, -5])
    4. julia> findall(!iszero, S)
    5. 4-element Array{CartesianIndex{2},1}:
    6.  CartesianIndex(1, 4)
    7.  CartesianIndex(4, 7)
    8.  CartesianIndex(5, 9)
    9.  CartesianIndex(3, 18)
    11. julia> findnz(R)
    12. ([1, 3, 4, 5], [1, -5, 2, 3])
    14. julia> findall(!iszero, R)
    15. 4-element Array{Int64,1}:
    16.  1
    17.  3
    18.  4
    19.  5

    Another way to create a sparse array is to convert a dense array into a sparse array using the function:

    1. julia> sparse(Matrix(1.0I, 5, 5))
    2. 5×5 SparseMatrixCSC{Float64,Int64} with 5 stored entries:
    3.   [1, 1]  =  1.0
    4.   [2, 2]  =  1.0
    5.   [3, 3]  =  1.0
    6.   [4, 4]  =  1.0
    7.   [5, 5]  =  1.0
    9. julia> sparse([1.0, 0.0, 1.0])
    10. 3-element SparseVector{Float64,Int64} with 2 stored entries:
    11.   [1]  =  1.0
    12.   [3]  =  1.0

    You can go in the other direction using the Array constructor. The function can be used to query if a matrix is sparse.

    1. julia> issparse(spzeros(5))
    2. true

    Arithmetic operations on sparse matrices also work as they do on dense matrices. Indexing of, assignment into, and concatenation of sparse matrices work in the same way as dense matrices. Indexing operations, especially assignment, are expensive, when carried out one element at a time. In many cases it may be better to convert the sparse matrix into (I,J,V) format using findnz, manipulate the values or the structure in the dense vectors (I,J,V), and then reconstruct the sparse matrix.

    The following table gives a correspondence between built-in methods on sparse matrices and their corresponding methods on dense matrix types. In general, methods that generate sparse matrices differ from their dense counterparts in that the resulting matrix follows the same sparsity pattern as a given sparse matrix S, or that the resulting sparse matrix has density d, i.e. each matrix element has a probability d of being non-zero.

    Details can be found in the section of the standard library reference.

    Sparse Arrays

    SparseArrays.SparseVector — Type

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

    Vector type for storing sparse vectors.

    — Type

    1. SparseMatrixCSC{Tv,Ti<:Integer} <: AbstractSparseMatrix{Tv,Ti}

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

    — Function

    1. sparse(A)

    Convert an AbstractMatrix A into a sparse matrix.

    Examples

    1. julia> A = Matrix(1.0I, 3, 3)
    2. 3×3 Array{Float64,2}:
    3.  1.0  0.0  0.0
    4.  0.0  1.0  0.0
    5.  0.0  0.0  1.0
    7. julia> sparse(A)
    8. 3×3 SparseMatrixCSC{Float64,Int64} with 3 stored entries:
    9.   [1, 1]  =  1.0
    10.   [2, 2]  =  1.0
    11.   [3, 3]  =  1.0
    1. sparse(I, J, 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!.

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

    Examples

    1. julia> Is = [1; 2; 3];
    3. julia> Js = [1; 2; 3];
    5. julia> Vs = [1; 2; 3];
    7. julia> sparse(Is, Js, Vs)
    8. 3×3 SparseMatrixCSC{Int64,Int64} with 3 stored entries:
    9.   [1, 1]  =  1
    10.   [3, 3]  =  3

    — Function

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

    1. julia> II = [1, 3, 3, 5]; V = [0.1, 0.2, 0.3, 0.2];
    3. julia> sparsevec(II, V)
    4. 5-element SparseVector{Float64,Int64} with 3 stored entries:
    5.   [1]  =  0.1
    6.   [3]  =  0.5
    7.   [5]  =  0.2
    9. julia> sparsevec(II, V, 8, -)
    10. 8-element SparseVector{Float64,Int64} with 3 stored entries:
    11.   [1]  =  0.1
    12.   [3]  =  -0.1
    13.   [5]  =  0.2
    15. julia> sparsevec([1, 3, 1, 2, 2], [true, true, false, false, false])
    16. 3-element SparseVector{Bool,Int64} with 3 stored entries:
    17.   [1]  =  1
    18.   [2]  =  0
    19.   [3]  =  1
    1. sparsevec(d::Dict, [m])

    Examples

    1. sparsevec(A)

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

    Examples

    1. julia> sparsevec([1.0, 2.0, 0.0, 0.0, 3.0, 0.0])
    2. 6-element SparseVector{Float64,Int64} with 3 stored entries:
    3.   [1]  =  1.0
    4.   [2]  =  2.0
    5.   [5]  =  3.0

    SparseArrays.issparse — Function

    1. issparse(S)

    Returns true if S is sparse, and false otherwise.

    Examples

    1. julia> sv = sparsevec([1, 4], [2.3, 2.2], 10)
    2. 10-element SparseVector{Float64,Int64} with 2 stored entries:
    3.   [1 ]  =  2.3
    4.   [4 ]  =  2.2
    6. julia> issparse(sv)
    7. true
    9. julia> issparse(Array(sv))
    10. false

    — Function

    1. nnz(A)

    Returns the number of stored (filled) elements in a sparse array.

    Examples

    1. julia> A = sparse(2I, 3, 3)
    2. 3×3 SparseMatrixCSC{Int64,Int64} with 3 stored entries:
    3.   [1, 1]  =  2
    4.   [2, 2]  =  2
    5.   [3, 3]  =  2
    7. julia> nnz(A)
    8. 3

    SparseArrays.findnz — Function

    1. findnz(A)

    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.

    Examples

    1. julia> A = sparse([1 2 0; 0 0 3; 0 4 0])
    2. 3×3 SparseMatrixCSC{Int64,Int64} with 4 stored entries:
    3.   [1, 1]  =  1
    4.   [1, 2]  =  2
    5.   [3, 2]  =  4
    6.   [2, 3]  =  3
    8. julia> findnz(A)
    9. ([1, 1, 3, 2], [1, 2, 2, 3], [1, 2, 4, 3])

    — Function

    1. 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. No storage will be allocated for nonzero values during construction. The type defaults to Float64 if not specified.

    Examples

    1. julia> spzeros(3, 3)
    2. 3×3 SparseMatrixCSC{Float64,Int64} with 0 stored entries
    4. julia> spzeros(Float32, 4)
    5. 4-element SparseVector{Float32,Int64} with 0 stored entries

    — Function

    1. spdiagm(kv::Pair{<:Integer,<:AbstractVector}...)
    2. spdiagm(m::Integer, n::Ingeger, 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 (if size=nothing), 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

    1. julia> spdiagm(-1 => [1,2,3,4], 1 => [4,3,2,1])
    2. 5×5 SparseMatrixCSC{Int64,Int64} with 8 stored entries:
    3.   [2, 1]  =  1
    4.   [1, 2]  =  4
    5.   [3, 2]  =  2
    6.   [2, 3]  =  3
    7.   [4, 3]  =  3
    8.   [3, 4]  =  2
    9.   [5, 4]  =  4
    10.   [4, 5]  =  1

    SparseArrays.blockdiag — Function

    1. blockdiag(A...)

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

    Examples

    1. julia> blockdiag(sparse(2I, 3, 3), sparse(4I, 2, 2))
    2. 5×5 SparseMatrixCSC{Int64,Int64} with 5 stored entries:
    3.   [1, 1]  =  2
    4.   [2, 2]  =  2
    5.   [3, 3]  =  2
    6.   [4, 4]  =  4
    7.   [5, 5]  =  4

    — Function

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

    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). Nonzero values are sampled from the distribution specified by rfn and have the type type. The uniform distribution is used in case rfn is not specified. The optional rng argument specifies a random number generator, see Random Numbers.

    Examples

    1. julia> sprand(Bool, 2, 2, 0.5)
    2. 2×2 SparseMatrixCSC{Bool,Int64} with 1 stored entry:
    3.   [2, 2]  =  1
    5. julia> sprand(Float64, 3, 0.75)
    6. 3-element SparseVector{Float64,Int64} with 1 stored entry:
    7.   [3]  =  0.298614

    — Function

    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.

    1. julia> sprandn(2, 2, 0.75)
    2. 2×2 SparseMatrixCSC{Float64,Int64} with 2 stored entries:
    3.   [2, 2]  =  0.297336

    — Function

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

    Examples

    1. julia> A = sparse(2I, 3, 3)
    2. 3×3 SparseMatrixCSC{Int64,Int64} with 3 stored entries:
    3.   [1, 1]  =  2
    4.   [2, 2]  =  2
    5.   [3, 3]  =  2
    8. 3-element Array{Int64,1}:
    9.  2
    10.  2
    11.  2

    SparseArrays.rowvals — Function

    1. rowvals(A::SparseMatrixCSC)

    Return a vector of the row indices of 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 and nzrange.

    Examples

    1. julia> A = sparse(2I, 3, 3)
    2. 3×3 SparseMatrixCSC{Int64,Int64} with 3 stored entries:
    3.   [1, 1]  =  2
    4.   [2, 2]  =  2
    5.   [3, 3]  =  2
    7. julia> rowvals(A)
    8. 3-element Array{Int64,1}:
    9.  1
    10.  2
    11.  3

    — Function

    1. nzrange(A::SparseMatrixCSC, col::Integer)

    Return the range of indices to the structural nonzero values of a sparse matrix column. In conjunction with nonzeros and , this allows for convenient iterating over a sparse matrix :

    1. A = sparse(I,J,V)
    2. rows = rowvals(A)
    3. vals = nonzeros(A)
    4. m, n = size(A)
    5. for j = 1:n
    6.    for i in nzrange(A, j)
    7.       row = rows[i]
    8.       val = vals[i]
    9.       # perform sparse wizardry...
    10.    end
    11. end

    SparseArrays.dropzeros! — Function

    1. dropzeros!(A::SparseMatrixCSC; trim::Bool = true)

    Removes stored numerical zeros from A, optionally trimming resulting excess space from A.rowval and A.nzval when trim is true.

    For an out-of-place version, see . For algorithmic information, see fkeep!.

    1. dropzeros!(x::SparseVector; trim::Bool = true)

    Removes stored numerical zeros from x, optionally trimming resulting excess space from x.nzind and x.nzval when trim is true.

    For an out-of-place version, see dropzeros. For algorithmic information, see fkeep!.

    — Function

    1. dropzeros(A::SparseMatrixCSC; trim::Bool = true)

    Generates a copy of A and removes stored numerical zeros from that copy, optionally trimming excess space from the result’s rowval and nzval arrays when trim is true.

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

    Examples

    1. julia> A = sparse([1, 2, 3], [1, 2, 3], [1.0, 0.0, 1.0])
    2. 3×3 SparseMatrixCSC{Float64,Int64} with 3 stored entries:
    3.   [1, 1]  =  1.0
    4.   [2, 2]  =  0.0
    5.   [3, 3]  =  1.0
    7. julia> dropzeros(A)
    8. 3×3 SparseMatrixCSC{Float64,Int64} with 2 stored entries:
    9.   [1, 1]  =  1.0
    10.   [3, 3]  =  1.0
    1. dropzeros(x::SparseVector; trim::Bool = true)

    Generates a copy of x and removes numerical zeros from that copy, optionally trimming excess space from the result’s nzind and nzval arrays when trim is true.

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

    Examples

    1. julia> A = sparsevec([1, 2, 3], [1.0, 0.0, 1.0])
    2. 3-element SparseVector{Float64,Int64} with 3 stored entries:
    3.   [1]  =  1.0
    4.   [2]  =  0.0
    5.   [3]  =  1.0
    7. julia> dropzeros(A)
    8. 3-element SparseVector{Float64,Int64} with 2 stored entries:
    9.   [1]  =  1.0
    10.   [3]  =  1.0

    SparseArrays.permute — Function

    1. permute(A::SparseMatrixCSC{Tv,Ti}, p::AbstractVector{<:Integer},
    2.         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) == A.n). Row-permutation p‘s length must match A‘s row count (length(p) == A.m).

    For expert drivers and additional information, see .

    Examples

    1. julia> A = spdiagm(0 => [1, 2, 3, 4], 1 => [5, 6, 7])
    2. 4×4 SparseMatrixCSC{Int64,Int64} with 7 stored entries:
    3.   [1, 1]  =  1
    4.   [1, 2]  =  5
    5.   [2, 2]  =  2
    6.   [2, 3]  =  6
    7.   [3, 3]  =  3
    8.   [3, 4]  =  7
    9.   [4, 4]  =  4
    11. julia> permute(A, [4, 3, 2, 1], [1, 2, 3, 4])
    12. 4×4 SparseMatrixCSC{Int64,Int64} with 7 stored entries:
    13.   [4, 1]  =  1
    14.   [3, 2]  =  2
    15.   [4, 2]  =  5
    16.   [2, 3]  =  3
    17.   [3, 3]  =  6
    18.   [1, 4]  =  4
    19.   [2, 4]  =  7
    21. julia> permute(A, [1, 2, 3, 4], [4, 3, 2, 1])
    22. 4×4 SparseMatrixCSC{Int64,Int64} with 7 stored entries:
    23.   [3, 1]  =  7
    24.   [4, 1]  =  4
    25.   [2, 2]  =  6
    26.   [3, 2]  =  3
    27.   [1, 3]  =  5
    28.   [2, 3]  =  2
    29.   [1, 4]  =  1

    Base.permute! — Method

    1. permute!(X::SparseMatrixCSC{Tv,Ti}, A::SparseMatrixCSC{Tv,Ti},
    2.          p::AbstractVector{<:Integer}, q::AbstractVector{<:Integer},

    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:

    X‘s dimensions must match those of A (X.m == A.m and X.n == A.n), and X must have enough storage to accommodate all allocated entries in A (length(X.rowval) >= nnz(A) and length(X.nzval) >= nnz(A)). Column-permutation q‘s length must match A‘s column count (length(q) == A.n). Row-permutation p‘s length must match A‘s row count (length(p) == A.m).

    C‘s dimensions must match those of transpose(A) (C.m == A.n and C.n == A.m), and C must have enough storage to accommodate all allocated entries in A (length(C.rowval) >= nnz(A) and length(C.nzval) >= nnz(A)).

    See also: .