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.

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.