Sparse Matrix Functions

Internal Sparse Matrix Representation

ConleyDynamics.SparseMatrix — Type

SparseMatrix{T}

Composite data type for a sparse matrix with entries of type T.

The struct has the following fields:

const nrow::Int: Number of rows
const ncol::Int: Number of columns
const char::Int: Characteristic of type T
const zero::T: Number 0 of type T
const one::T: Number 1 of type T
entries::Vector{Vector{T}}: Matrix entries corresponding to columns
columns::Vector{Vector{Int}}: columns[k] points to nonzero entries in column k
rows::Vector{Vector{Int}}: rows[k] points to nonzero entries in the k-th row

source

Access Functions

ConleyDynamics.sparse_get_entry — Function

sparse_get_entry(matrix::SparseMatrix, ri::Int, ci::Int)

Get the sparse matrix entry at location (ri,ci).

source

Base.getindex — Method

Base.getindex(matrix::SparseMatrix, ri::Int, ci::Int)

Get the sparse matrix entry at location (ri,ci).

source

ConleyDynamics.sparse_set_entry! — Function

sparse_set_entry!(matrix::SparseMatrix, ri::Int, ci::Int, val)

Set the sparse matrix entry at location (ri,ci) to val.

source

sparse_set_entry!(matrix::SparseMatrix{Int}, ri::Int, ci::Int, val)

Set the sparse matrix entry at location (ri,ci) to val.

This method assumes that the sparse matrix is over the integers, which means that it is interpreted over a finite field. Thus, the new entry is automatically reduced via modular arithmetic.

source

Base.setindex! — Method

Base.setindex!(matrix::SparseMatrix, val, ri::Int, ci::Int)

Set the sparse matrix entry at location (ri,ci) to val.

source

ConleyDynamics.sparse_get_column — Function

sparse_get_column(matrix::SparseMatrix, ci::Int)

Get the ci-th column of the sparse matrix.

source

ConleyDynamics.sparse_get_nz_column — Function

sparse_get_nz_column(matrix::SparseMatrix, ci::Int)

Get the row indices for the nonzero entries in the ci-th column of the sparse matrix.

source

ConleyDynamics.sparse_get_nz_row — Function

sparse_get_nz_row(matrix::SparseMatrix, ri::Int)

Get the column indices for the nonzero entries in the ri-th row of the sparse matrix.

source

ConleyDynamics.sparse_minor — Function

smp = sparse_minor(sm::SparseMatrix, rvec::Vector{Int}, cvec::Vector{Int})

Create sparse submatrix by specifying the desired row and column indices.

source

Basic Functions

ConleyDynamics.sparse_size — Function

sparse_size(matrix::SparseMatrix, dim::Int)

Number of rows (dim=1) or columns (dim=2) of a sparse matrix.

source

ConleyDynamics.sparse_low — Function

sparse_low(matrix::SparseMatrix, col::Int)

Row index of the lowest nonzero matrix entry in column col.

source

ConleyDynamics.sparse_is_zero — Function

sparse_is_zero(sm::SparseMatrix)

Test whether the sparse matrix sm is the zero matrix.

source

ConleyDynamics.sparse_is_identity — Function

sparse_is_identity(A::SparseMatrix)

Test whether the sparse matrix A is the identity matrix.

source

ConleyDynamics.sparse_is_equal — Function

sparse_is_equal(A::SparseMatrix, B::SparseMatrix)

Test whether the sparse matrices A and B are equal.

For equality, the two sparse matrices not only have to have the same size and the same entries, they also have to be of the same type and be defined over the same field.

source

Base.:(==) — Method

Base.:(==)(A::SparseMatrix,B::SparseMatrix)

Test whether the sparse matrices A and B are equal.

For equality, the two sparse matrices not only have to have the same size and the same entries, they also have to be of the same type and be defined over the same field.

source

ConleyDynamics.sparse_is_sut — Function

bool = sparse_is_sut(sm::SparseMatrix)

Check whether the sparse matrix is strictly upper triangular.

source

ConleyDynamics.sparse_identity — Function

sparse_identity(n::Int; p::Int=0)

Create a sparse identity matrix with n rows and columns.

The optional argument p specifies the field characteristic. If p=0 then the sparse matrix is over the rationals, while if p>0 is a prime, then the matrix is an integer matrix whose entries are interpreted in GF(p).

source

ConleyDynamics.sparse_zero — Function

sparse_zero(nr::Int, nc::Int; p::Int=0)

Create a sparse zero matrix with nr rows and nc columns.

source

ConleyDynamics.sparse_fullness — Function

sparse_fullness(sm::SparseMatrix)

Return the fullness of the sparse matrix sm, which equals the percentage of nonzero elements.

source

ConleyDynamics.sparse_sparsity — Function

sparse_sparsity(sm::SparseMatrix)

Return the sparsity of the sparse matrix sm, which equals the percentage of zero entries.

source

ConleyDynamics.sparse_nz_count — Function

sparse_nz_count(sm::SparseMatrix)

Return the number of nonzero entries of the sparse matrix sm.

source

ConleyDynamics.sparse_show — Function

sparse_show(sm::SparseMatrix)

Display a sparse matrix in readable format.

This function will print the complete matrix, so be careful with sparse matrices of large size!

source

sparse_show(sm::SparseMatrix, rlabels::Vector{String}, clabels::Vector{String})

Display a sparse matrix in readable format, with labels.

The input parameter clabels contains the labels for the columns, while rlabels give the row labels.

Examples

julia> lc, mvf = example_forman1d();

julia> cm = connection_matrix(lc, mvf, algorithm="DHL");

julia> sparse_show(cm.matrix, cm.labels, cm.labels)
  ┆  A CD  F BF DE
--┆---------------
 A┆  .  .  .  .  1
CD┆  .  .  .  .  .
 F┆  .  .  .  .  1
BF┆  .  .  .  .  .
DE┆  .  .  .  .  .

source

sparse_show(sm::SparseMatrix, labels::Vector{String})

Display a sparse matrix in readable format, with labels.

This function assumes that the matrix is square, and that the labels are the same for rows and columns. They are provided in labels.

source

sparse_show(cm::ConleyMorseCM)

Display the connection matrix with labels.

This function displays the (sparse) connection matrix including its labels. It uses sparse_show(cm.matrix, cm.labels, cm.labels).

Examples

julia> lc, mvf = example_forman1d();

julia> cm = connection_matrix(lc, mvf, algorithm="DHL");

julia> sparse_show(cm)
  ┆  A CD  F BF DE
--┆---------------
 A┆  .  .  .  .  1
CD┆  .  .  .  .  .
 F┆  .  .  .  .  1
BF┆  .  .  .  .  .
DE┆  .  .  .  .  .

source

Base.show — Method

Base.show(io::IO, ::MIME"text/plain", sm::SparseMatrix)

Display the sparse matrix sm when hitting return in REPL.

source

Elementary Matrix Operations

ConleyDynamics.sparse_add_column! — Function

sparse_add_column!(matrix::SparseMatrix, ci1::Int, ci2::Int, cn, cd)

Replace column[ci1] by column[ci1] + (cn/cd) * column[ci2].

source

sparse_add_column!(matrix::SparseMatrix{Int}, ci1::Int, ci2::Int,
                   cn::Int, cd::Int)

Replace column[ci1] by column[ci1] + (cn/cd) * column[ci2].

The computation is performed mod p, where the characteristic is taken from matrix.char. An error is thrown if matrix.char==0.

source

ConleyDynamics.sparse_add_row! — Function

sparse_add_row!(matrix::SparseMatrix, ri1::Int, ri2::Int, cn, cd)

Replace row[ri1] by row[ri1] + (cn/cd) * row[ri2].

source

sparse_add_row!(matrix::SparseMatrix{Int}, ri1::Int, ri2::Int,
                cn::Int, cd::Int)

Replace row[ri1] by row[ri1] + (cn/cd) * row[ri2].

The computation is performed mod p, where the characteristic is taken from matrix.char. An error is thrown if matrix.char==0.

source

ConleyDynamics.sparse_permute — Function

sparse_permute(sm::SparseMatrix, pr::Vector{Int}, pc::Vector{Int})

Create sparse matrix by permuting the row and column indices.

The vector pr describes the row permutation, and pc the column permutation.

source

ConleyDynamics.sparse_inverse — Function

sparse_inverse(matrix::SparseMatrix)

Compute the inverse of a sparse matrix.

The function automatically performs the computations over the underlying field of the sparse matrix.

source

ConleyDynamics.sparse_remove! — Function

sparse_remove!(matrix::SparseMatrix, ri::Int, ci::Int)

Remove the sparse matrix entry at location (ri,ci).

source

ConleyDynamics.sparse_add — Function

sparse_add(A::SparseMatrix, B::SparseMatrix)

Add two sparse matrices.

Exceptions are raised if the matrix sum is not defined or the entry types do not match.

source

ConleyDynamics.sparse_subtract — Function

sparse_subtract(A::SparseMatrix, B::SparseMatrix)

Subtract two sparse matrices.

The function returns A - B. Exceptions are raised if the matrix difference is not defined or the entry types do not match.

source

ConleyDynamics.sparse_multiply — Function

sparse_multiply(A::SparseMatrix, B::SparseMatrix)

Multiply two sparse matrices.

Exceptions are raised if the matrix product is not defined or the entry types do not match.

source

sparse_multiply(alpha::Int, A::SparseMatrix)

Multiply a scalar with a sparse matrix.

This method is for finite fields. An exception is raised if the sparse matrix is not defined over a finite field.

source

sparse_multiply(alpha::Rational{Int}, A::SparseMatrix)

Multiply a scalar with a sparse matrix.

This method is for the rational numbers. An exception is raised if the sparse matrix is not defined over field of rationals.

source

ConleyDynamics.sparse_scale — Function

sparse_scale(sfac, A::SparseMatrix)

Scale a sparse matrix by a scalar.

An exception is raised if the entry types do not match.

source

Base.:+ — Method

Base.:+(A::SparseMatrix, B::SparseMatrix)

Add two sparse matrices.

Exceptions are raised if the matrix sum is not defined or the entry types do not match.

source

Base.:- — Method

Base.:-(A::SparseMatrix, B::SparseMatrix)

Subtract two sparse matrices.

Exceptions are raised if the matrix difference is not defined or the entry types do not match.

source

Base.:* — Method

Base.:*(A::SparseMatrix, B::SparseMatrix)

Multiply two sparse matrices.

Exceptions are raised if the matrix product is not defined or the entry types do not match.

source

Base.:* — Method

Base.:*(alpha::Int, A::SparseMatrix)

Multiply a scalar with a sparse matrix.

This method is for finite fields. An exception is raised if the sparse matrix is not defined over a finite field.

source

Base.:* — Method

Base.:*(alpha::Rational{Int}, A::SparseMatrix)

Multiply a scalar with a sparse matrix.

This method is for the rational numbers. An exception is raised if the sparse matrix is not defined over field of rationals.

source

Base.:* — Method

Base.:*(sfac, A::SparseMatrix)

Compute the scalar product of sfac and the sparse matrix A.

An exception is raised if the scalar sfac does not have the same type as the matrix entries.

source

Conversion Functions

ConleyDynamics.sparse_from_full — Function

sparse_from_full(matrix::Matrix{Int}; [p::Int=0])

Create sparse matrix from full integer matrix. If the optional argument p is specified and positive, then the returned matrix is an integer matrix which is interpreted over GF(p). On the other hand, if p is omitted or equal to zero, then the return matrix has rational type.

source

ConleyDynamics.full_from_sparse — Function

full_from_sparse(sm::SparseMatrix)

Create full matrix from sparse matrix.

source

ConleyDynamics.sparse_from_lists — Function

sparse_from_lists(nr, nc, tchar, tzero, tone, r, c, v)

Create sparse matrix from lists describing the entries.

The vectors r, c, and v have to have the same length and the matrix has entry v[k] at (r[k],c[k]). Zero entries will be ignored, and multiple entries for the same matrix position raise an error.

The input arguments have the following meaning:

nr::Int: Number of rows
nc::Int: Number of columns
tchar: Field characteristic if T==Int
tzero::T: Number 0 of type T
tone::T: Number 1 of type T
r::Vector{Int}: Vector of row indices
c::Vector{Int}: Vector of column indices
v::Vector{T}: Vector of matrix entries

If tchar>0, then the entries in v are all replaced by their values mod tchar.

source

ConleyDynamics.lists_from_sparse — Function

nr, nc, tchar, tzero, tone, r, c, v = lists_from_sparse(sm::SparseMatrix)

Create list representation from sparse matrix.

The output variables are exactly what is needed to create a sparse matrix object using sparse_from_lists.

source

Sparse Helper Functions

ConleyDynamics.scalar_inverse — Function

scalar_inverse(s, p::Int)

Compute the inverse of a scalar.

source

scalar_inverse(s::Int, p::Int)

Compute the inverse of a scalar.

This function computes the inverse in modular arithmetic with base p.

source

ConleyDynamics.scalar_multiply — Function

scalar_multiply(s1, s2, p::Int)

Compute the product of two scalars.

source

scalar_multiply(s1::Int, s2::Int, p::Int)

Compute the product of two scalars.

This function computes the product in modular arithmetic with base p.

source

ConleyDynamics.scalar_add — Function

scalar_add(s1, s2, p::Int)

Compute the sum of two scalars.

source

scalar_add(s1::Int, s2::Int, p::Int)

Compute the sum of two scalars.

This function computes the sum in modular arithmetic with base p.

source