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

bool = sparse_is_sut(sm::SparseMatrix)

Check whether the sparse matrix is strictly upper triangular.

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

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

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_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 the sparse matrix sm.

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_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_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_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.:*(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.

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.

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.

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.