Matrix extensions

AbstractSparseMatrixExtension

ExtendableSparse.AbstractSparseMatrixExtension — Type
abstract type AbstractSparseMatrixExtension{Tv, Ti} <: AbstractSparseMatrix{Tv, Ti} end

Abstract type for sparse matrix extension.

Subtypes T_ext must implement:

  • Constructor T_ext(m,n)
  • SparseArrays.nnz(ext::T_ext)
  • Base.size(ext::T_ext)
  • Base.sum(extmatrices::Vector{T_ext}, csx): add csr or csc matrix and extension matrices (one per partition) and return csx matrix
  • Base.+(ext::T_ext, csx) (optional) - Add extension matrix and csc/csr matrix, return csx matrix
  • rawupdateindex!(ext::Text, op, v, i, j, tid) where {Tv, Ti}: Set ext[i,j]op=v, possibly insert new entry into matrix. tid is a task or partition id
source

SparseMatrixLNK

ExtendableSparse.SparseMatrixLNK — Type
mutable struct SparseMatrixLNK{Tv, Ti<:Integer} <: ExtendableSparse.AbstractSparseMatrixExtension{Tv, Ti<:Integer}

AbstractSparseMatrixExtension where entries are organized in the linked list sparse matrix format. This was the standard structure in ExtendableSparse v1.x.

Modeled after the linked list sparse matrix format described in the whitepaper and the SPARSEKIT2 source code by Y. Saad. He writes "This is one of the oldest data structures used for sparse matrix computations."

The relevant source formats.f is also available in the debian/science gitlab.

The advantage of the linked list structure is the fact that upon insertion of a new entry, the arrays describing the structure can grow at their respective ends and can be conveniently updated via push!. No copying of existing data is necessary.

Via the type aliases STExtendableSparseMatrixCSC, ExtendableSparseMatrixCSC, and ExtendableSparseMatrix this extension is used as default for handling scalar assembly.

  • m::Integer: Number of rows
  • n::Integer: Number of columns
  • nnz::Integer: Number of nonzeros
  • nentries::Integer: Length of arrays

  • colptr::Vector{Ti} where Ti<:Integer: Linked list of column entries. Initial length is n, it grows with each new entry.

    colptr[index] contains the next index in the list or zero, in the later case terminating the list which starts at index 1<=j<=n for each column j.

  • rowval::Vector{Ti} where Ti<:Integer: Row numbers. For each index it contains the zero (initial state) or the row numbers corresponding to the column entry list in colptr.

    Initial length is n, it grows with each new entry.

  • nzval::Vector: Nonzero entry values corresponding to each pair (colptr[index],rowval[index])

    Initial length is n, it grows with each new entry.

source
Base.:+ — Method
+(
    lnk::ExtendableSparse.SparseMatrixLNK{Tv, Ti<:Integer},
    csc::SparseMatrixCSC
) -> SparseMatrixCSC

Add SparseMatrixCSC matrix and SparseMatrixLNK lnk, returning a SparseMatrixCSC

source
Base.getindex — Method
getindex(
    lnk::ExtendableSparse.SparseMatrixLNK{Tv, Ti},
    i,
    j
) -> Any

Return value stored for entry or zero if not found

source
Base.setindex! — Method
setindex!(
    lnk::ExtendableSparse.SparseMatrixLNK,
    v,
    i,
    j
) -> ExtendableSparse.SparseMatrixLNK

Update value of existing entry, otherwise extend matrix if v is nonzero.

source
Base.size — Method
size(
    lnk::ExtendableSparse.SparseMatrixLNK
) -> Tuple{Integer, Integer}

Return tuple containing size of the matrix.

source
ExtendableSparse.rawupdateindex! — Method
rawupdateindex!(
    lnk::ExtendableSparse.SparseMatrixLNK{Tv, Ti},
    op,
    v,
    i,
    j
) -> ExtendableSparse.SparseMatrixLNK{Tv, Ti} where {Tv, Ti}

Update element of the matrix with operation op. It assumes that op(0,0)==0. If v is zero a new entry is created nevertheless.

source
ExtendableSparse.updateindex! — Method
updateindex!(
    lnk::ExtendableSparse.SparseMatrixLNK{Tv, Ti},
    op,
    v,
    i,
    j
) -> ExtendableSparse.SparseMatrixLNK{Tv, Ti} where {Tv, Ti}

Update element of the matrix with operation op. It assumes that op(0,0)==0. If v is zero, no new entry is created.

source
SparseArrays.nnz — Method
nnz(lnk::ExtendableSparse.SparseMatrixLNK) -> Integer

Return number of nonzero entries.

source

SparseMatrixDILNKC

ExtendableSparse.SparseMatrixDILNKC — Type
mutable struct SparseMatrixDILNKC{Tv, Ti<:Integer} <: ExtendableSparse.AbstractSparseMatrixExtension{Tv, Ti<:Integer}

AbstractSparseMatrixExtension where entries are stored as linked list, but where – in difference to SparseMatrixLNK – the pointer to first index of column j is stored in a dictionary.

Thus this format – similar to SparseMatrixDict – avoids to store a vector of the length of unknowns indicating the first column indices, avoiding storage overhead during parallel assembly.

Via the type alias MTExtendableSparseMatrixCSC, this extension is used as default for handling parallel assembly.

  • m::Integer: Number of rows
  • n::Integer: Number of columns
  • nnz::Integer: Number of nonzeros
  • nentries::Integer: Length of arrays

  • colptr::Vector{Ti} where Ti<:Integer: Linked list of column entries. Initial length is n, it grows with each new entry.

    colptr[index] contains the next index in the list or zero, in the later case terminating the list which starts at index 1<=j<=n for each column j.

  • colstart::Dict{Ti, Ti} where Ti<:Integer: Dictionary to store start indices of columns
  • rowval::Vector{Ti} where Ti<:Integer: Row numbers. For each index it contains the zero (initial state) or the row numbers corresponding to the column entry list in colptr.
  • nzval::Vector: Nonzero entry values corresponding to each pair (colptr[index],rowval[index])
source
SparseArrays.SparseMatrixCSC — Method
SparseMatrixCSC(
    lnk::ExtendableSparse.SparseMatrixDILNKC
) -> SparseMatrixCSC{Float64, Int64}

Constructor from SparseMatrixDILNKC.

source
Base.getindex — Method
getindex(
    lnk::ExtendableSparse.SparseMatrixDILNKC{Tv, Ti},
    i,
    j
) -> Any

Return value stored for entry or zero if not found

source
Base.setindex! — Method
setindex!(
    lnk::ExtendableSparse.SparseMatrixDILNKC,
    v,
    i,
    j
) -> ExtendableSparse.SparseMatrixDILNKC

Update value of existing entry, otherwise extend matrix if v is nonzero.

source
Base.size — Method
size(
    lnk::ExtendableSparse.SparseMatrixDILNKC
) -> Tuple{Integer, Integer}

Return tuple containing size of the matrix.

source
ExtendableSparse.add_directly — Method
add_directly(
    lnk::ExtendableSparse.SparseMatrixDILNKC{Tv, Ti<:Integer},
    csc::SparseMatrixCSC
) -> SparseMatrixCSC

Add lnk and csc without creation of intermediate data. (to be fixed)

source
ExtendableSparse.add_via_COO — Method
add_via_COO(
    lnk::ExtendableSparse.SparseMatrixDILNKC{Tv, Ti<:Integer},
    csc::SparseMatrixCSC
) -> SparseMatrixCSC

Add lnk and csc via interim COO (coordinate) format, i.e. arrays I,J,V.

source
ExtendableSparse.findindex — Method
findindex(
    lnk::ExtendableSparse.SparseMatrixDILNKC,
    i,
    j
) -> Union{Tuple{Int64, Integer}, Tuple{Integer, Int64}}

Find index in matrix.

source
ExtendableSparse.rawupdateindex! — Method
rawupdateindex!(
    lnk::ExtendableSparse.SparseMatrixDILNKC{Tv, Ti},
    op,
    v,
    i,
    j
) -> ExtendableSparse.SparseMatrixDILNKC

Update element of the matrix with operation op. It assumes that op(0,0)==0. If v is zero a new entry is created nevertheless.

source
ExtendableSparse.updateindex! — Method
updateindex!(
    lnk::ExtendableSparse.SparseMatrixDILNKC{Tv, Ti},
    op,
    v,
    i,
    j
) -> ExtendableSparse.SparseMatrixDILNKC

Update element of the matrix with operation op. It assumes that op(0,0)==0. If v is zero, no new entry is created.

source
SparseArrays.nnz — Method
nnz(lnk::ExtendableSparse.SparseMatrixDILNKC) -> Integer

Return number of nonzero entries.

source

SparseMatrixDict

ExtendableSparse.SparseMatrixDict — Type
mutable struct SparseMatrixDict{Tv, Ti} <: ExtendableSparse.AbstractSparseMatrixExtension{Tv, Ti}

AbstractSparseMatrixExtension extension where entries are organized as dictionary. This is meant as an example implementation to show how a sparse matrix extension could be implemented. As dictionary access tends to be slow, it is not meant for general use.

An advantage of this format is the fact that it avoids to store a vector of the length of unknowns indicating the first column indices, avoiding storage overhead during parallel assembly.

  • m::Any: Number of rows
  • n::Any: Number of columns
  • values::Dict{Pair{Ti, Ti}, Tv} where {Tv, Ti}: Dictionary with pairs of integers as keys containing values
source
ExtendableSparse.SparseMatrixDict — Method
SparseMatrixDict(
    valuetype::Type{Tv},
    indextype::Type{Ti<:Integer},
    m,
    n
) -> ExtendableSparse.SparseMatrixDict{Tv, Ti} where {Tv, Ti<:Integer}
source
Base.:+ — Method
+(
    dictmatrix::ExtendableSparse.SparseMatrixDict{Tv, Ti},
    cscmatrix::SparseMatrixCSC{Tv, Ti}
) -> SparseMatrixCSC{Tv, Ti} where {Tv, Ti}
source
Base.getindex — Method
getindex(
    m::ExtendableSparse.SparseMatrixDict{Tv},
    i,
    j
) -> Any
source
Base.size — Method
size(
    m::ExtendableSparse.SparseMatrixDict
) -> Tuple{Any, Any}
source
Base.sum — Method
sum(
    dictmatrices::Array{ExtendableSparse.SparseMatrixDict{Tv, Ti}, 1},
    cscmatrix::SparseMatrixCSC{Tv, Ti}
) -> SparseMatrixCSC{Tv, Ti} where {Tv, Ti}
source