Sparse Matrix Functions

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

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

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

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

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

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

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

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.

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

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

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

Get the ci-th column of the sparse matrix.

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.

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.

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

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

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

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

sparse_size(matrix::SparseMatrix)

Return the size of a sparse matrix.

The function returns a tuple which contains the number of rows and the number of columns of the given matrix.

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

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

sparse_is_zero(sm::SparseMatrix)

Test whether the sparse matrix sm is the zero matrix.

sparse_is_identity(A::SparseMatrix)

Test whether the sparse matrix A is the identity matrix.

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.

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.

sparse_is_rref(A::SparseMatrix)

Check whether a matrix is in reduced row Echelon format.

This function determines whether a given matrix is in reduced row Echelon format. It returns the appropriate boolean value.

bool = sparse_is_sut(sm::SparseMatrix)

Check whether the sparse matrix is strictly upper triangular.

sparse_fullness(sm::SparseMatrix)

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

sparse_sparsity(sm::SparseMatrix)

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

sparse_nz_count(sm::SparseMatrix)

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

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!

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

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.

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

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

Display the sparse matrix sm when hitting return in REPL.

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

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 equal to zero, then the return matrix has rational type.

sparse_from_full(vec::Vector{Int}; [p::Int=2])

Create sparse column matrix from a full integer vector. 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 equal to zero, then the return matrix has rational type.

full_from_sparse(sm::SparseMatrix)

Create full matrix from sparse matrix.

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.

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.

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

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

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

Create a sparse zero matrix with nr rows and nc 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).

sparse_diagonal(nr::Int, nc::Int, d::Vector{<:Real};
                p::Int=2, offset::Int=0)

Create sparse diagonal matrix.

The function creates a sparse matrix with nr rows and nc columns, over a field with characteristic p. Without additional arguments, the matrix has the entries in the vector d along the main diagonal. If the optional argument offset is given and positive, then the diagonal is placed offset positions above the main diagonal, if it is negative, then it indicates how many positions below the diagonal it is placed. The function places as many entries from d as possible, i.e., if the length of d is too short, the remaining diagonal entries are zero, if it is too long, then the later entries are ignored. The function tries to convert the entries in d to the correct format based on p. Errors are raised if this is not possible.

sparse_hcat(A::SparseMatrix, B::SparseMatrix)

Concatenate two sparse matrices horizontally.

Exceptions are raised if the matrices are not defined over the same field, or if they have different numbers of rows.

sparse_hcat(S1, S2, S3, ...)

Concatenate several sparse matrices horizontally.

This method of sparse_hcat allows for any number of arguments. If you want to concatenate a vector vec of sparse matrices, use the call sparse_hcat(vec...).

Exceptions are raised if the matrices are not defined over the same field, or if they have different numbers of rows.

sparse_vcat(A::SparseMatrix, B::SparseMatrix)

Concatenate two sparse matrices vertically.

Exceptions are raised if the matrices are not defined over the same field, or if they have different numbers of columns.

sparse_vcat(S1, S2, S3, ...)

Concatenate several sparse matrices vertically.

This method of sparse_vcat allows for any number of arguments. If you want to concatenate a vector vec of sparse matrices, use the call sparse_vcat(vec...).

Exceptions are raised if the matrices are not defined over the same field, or if they have different numbers of columns.

sparse_hvcat(rblocks::Tuple{Vararg{Int}}, A::SparseMatrix...)

Arrange sparse matrices in rectangular form.

The fist argument has to be a tuple which specifies how many blocks have to be combined in each row. This means that the total number of sparse matrices has to be equal to the sum of the entries in rblocks. Exceptions are raised if the dimensions of the matrices are not compatible, or if the matrices are not defined over the same field.

sparse_hvcat(rblocks::Int, A::SparseMatrix...)

Arrange sparse matrices in rectangular form.

The fist argument specifies how many blocks are contained in each row. Thus, the number of sparse matrices in Avec has to be divisible by rblocks. Exceptions are raised if the dimensions of the matrices are not compatible, or if the matrices are not defined over the same field.

sparse_hvncat(dims::Tuple{Int,Int}, rowfirst::Bool, A::SparseMatrix...)

Arrange sparse matrices in rectangular form.

The function expects dimensions (d1,d2), as well as d1*d2 sparse matrices. The boolean argument rowfirst indicates whether the sparse matrices are arranged row-first or column-first. The matrices are then arranged in an d1 x d2-times rectangular array to create a new sparse matrix. Exceptions are raised if the dimensions of the matrices are not compatible, or if the matrices are not defined over the same field.

sparse_cat(A::SparseMatrix...; dims=1)

Concatenate sparse matrices along a dimension.

The integer dims specifies along which dimension the sparse matrices are combined. In other words, dims=1 reduces to vcat, while dims=2 reduces to hcat. In addition, this function accepts the argument dims=(1,2). In this case, the sparse matrices are placed as blocks along the diagonal of a large sparse block matrix, with all remaining blocks being zero.

Base.hcat(::SparseMatrix...)

Concatenate several sparse matrices horizontally.

This method allows one to use the shortform [S1 S2 S3...] for the horizontal concatenation, just like in the matrix case.

Base.vcat(::SparseMatrix...)

Concatenate several sparse matrices vertically.

This method allows one to use the shortform [S1; S2; S3; ...] for the vertical concatenation, just like in the matrix case.

Base.hvcat(::Tuple{Vararg{Int}}, ::SparseMatrix...)

Arrange sparse matrices in rectangular form.

This method allows one to use the shortform [S1 S2; S3 S4 S5] etc for the concatenation, just like in the matrix case. It is based on the function sparse_hvcat. For more information, refer to its documentation. The number of blocks in each row can vary, as long as the dimensions are overall compatible.

Base.hvcat(::Int, ::SparseMatrix...)

Arrange sparse matrices in rectangular form.

This method allows one to use the shortform [S1 S2; S3 S4] etc for the concatenation, just like in the matrix case. It is based on the function sparse_hvcat. For more information, refer to its documentation.

Base.hvncat(::Tuple{Int,Int}, ::Bool, ::SparseMatrix...)

Arrange sparse matrices in rectangular form.

This method allows one to use the shortform [S1; S2;; S3; S4] etc for the concatenation, just like in the matrix case. It is based on the function sparse_hvncat. For more information, refer to its documentation. This form does require that the same number of blocks are used in each row and each column. For varying numbers please use the functions hvcat or sparse_hvcat.

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

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

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.

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

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

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.

sparse_rref!(A::SparseMatrix)

Compute the reduced row Echelon form of the given matrix.

This function computes the reduced row Echelon form of a sparse matrix in place. The input matrix will be altered!

Example

julia> Afull = [1 0 1 2 4 3 2; 3 4 6 2 3 4 2; 2 0 2 4 1 1 1];

julia> A = sparse_from_full(Afull, p=7);

julia> sparse_rref!(A)

julia> sparse_show(A)
 1 . 1 2 4 . 3
 . 1 6 6 3 . 5
 . . . . . 1 2

sparse_rref(A::SparseMatrix)

Compute the reduced row Echelon form of the given matrix.

This function computes and returns the reduced row Echelon form of a sparse matrix. The argument A is not altered.

Example

julia> Afull = [1 0 1 2 4 3 2; 3 4 6 2 3 4 2; 2 0 2 4 1 1 1];

julia> A = sparse_from_full(Afull, p=2);

julia> sparse_show(A)
 1 . 1 . . 1 .
 1 . . . 1 . .
 . . . . 1 1 1

julia> sparse_show(sparse_rref(A))
 1 . . . . 1 1
 . . 1 . . . 1
 . . . . 1 1 1

sparse_solve(A::SparseMatrix, b::SparseMatrix)

Find a solution of a sparse linear system.

This function computes a solution of the sparse linear system Ax = b. It is expected that A and b are sparse matrices over the same field, and that both have the same number of rows. Usually, this function is used with a column vector b. However, if b is a matrix, then the respective matrix equation is solved. The function returns a particular solution of the system, if one exists. Otherwise it returns nothing.

In order to obtain all solutions of the system, one has to add an arbitrary linear combination of the basis vectors determined via sparse_basis_kernel(A).

Example

julia> Afull = [1 0 1 2 4 3 2; 3 4 6 2 3 4 2; 2 0 2 4 1 1 1];

julia> A = sparse_from_full(Afull, p=7);

julia> bfull = [1 2 5 3; 3 6 6 4; 2 4 2 1];

julia> b = sparse_from_full(bfull, p=7);

julia> sparse_show(A)
 1 . 1 2 4 3 2
 3 4 6 2 3 4 2
 2 . 2 4 1 1 1

julia> sparse_show(b)
 1 2 5 3
 3 6 6 4
 2 4 2 1

julia> x = sparse_solve(A, b);

julia> sparse_show(x)
 1 2 3 .
 . . 5 .
 . . . .
 . . . .
 . . . .
 . . 3 1
 . . . .

julia> A*x == b
true

sparse_basis_kernel(A::SparseMatrix)

Compute a kernel basis for a sparse matrix.

This function determines a basis for the kernel of the given matrix A. The result is returned as a vector of sparse matrices. The latter are column vectors which span the kernel.

Example

julia> Afull = [1 0 1 2 4 3 2; 3 4 6 2 3 4 2; 2 0 2 4 1 1 1];

julia> A = sparse_from_full(Afull, p=7);

julia> sparse_rref!(A)

julia> sparse_show(A)
 1 . 1 2 4 . 3
 . 1 6 6 3 . 5
 . . . . . 1 2

julia> kbasis = sparse_basis_kernel(A);

julia> length(kbasis)
4

julia> sparse_show(sparse_transpose(kbasis[1]))
 6 1 1 . . . .

julia> sparse_show(sparse_transpose(kbasis[2]))
 5 1 . 1 . . .

julia> sparse_show(sparse_transpose(kbasis[3]))
 3 4 . . 1 . .

julia> sparse_show(sparse_transpose(kbasis[4]))
 4 2 . . . 5 1

sparse_basis_range(A::SparseMatrix)

Compute a basis for the range of a sparse matrix.

This function determines a basis for the range of the given matrix A. The result is returned as a vector of sparse matrices. The latter are column vectors which span the range, also known as column space.

Example

julia> Afull = [1 0 1 2 4 3 2; 3 4 6 2 3 4 2; 2 0 2 4 1 1 1];

julia> A = sparse_from_full(Afull, p=7);

julia> sparse_show(A)
 1 . 1 2 4 3 2
 3 4 6 2 3 4 2
 2 . 2 4 1 1 1

julia> rbasis = sparse_basis_range(A);

julia> length(rbasis)
3

julia> sparse_show(sparse_transpose(rbasis[1]))
 1 3 2

julia> sparse_show(sparse_transpose(rbasis[2]))
 . 4 .

julia> sparse_show(sparse_transpose(rbasis[3]))
 3 4 1

julia> sparse_show(sparse_rref(A))
 1 . 1 2 4 . 3
 . 1 6 6 3 . 5
 . . . . . 1 2

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.

sparse_transpose(A::SparseMatrix)

Create the transpose of a sparse matrix.

This does seem pretty self-explanatory, doesn't it?

Base.adjoint(A::SparseMatrix)

Create the transpose of a sparse matrix.

This method allows one to use A' for the computation of the transpose matrix.

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.

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

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

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.

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.

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.

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.

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.

sparse_scale(sfac, A::SparseMatrix)

Scale a sparse matrix by a scalar.

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

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.

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.

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.

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.

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.

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.

scalar_inverse(s, p::Int)

Compute the inverse of a scalar.

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

Compute the inverse of a scalar.

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

scalar_multiply(s1, s2, p::Int)

Compute the product of two scalars.

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.

scalar_add(s1, s2, p::Int)

Compute the sum of two scalars.

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.