Sparse linear algebra
Introduction
This chapter deals with sparse linear algebra over commutative rings and fields.
Sparse linear algebra, that is, linear algebra with sparse matrices, plays an important role in various algorithms in algebraic number theory. For example, it is one of the key ingredients in the computation of class groups and discrete logarithms using index calculus methods.
Sparse rows
Building blocks for sparse matrices are sparse rows, which are modelled by objects of type SRow
. More precisely, the type is of parametrized form SRow{T}
, where T
is the element type of the base ring SRow{ZZRingElem}
is the type for sparse rows over the integers.
It is important to note that sparse rows do not have a fixed number of columns, that is, they represent elements of
Creation
sparse_row(R::Ring, J::Vector{Tuple{Int, T}}) -> SRow{T}
Constructs the sparse row
sparse_row(R::Ring, J::Vector{Tuple{Int, T}}) -> SRow{T}
Constructs the sparse row
sparse_row(R::Ring, J::Vector{Tuple{Int, Int}}) -> SRow
Constructs the sparse row
sparse_row(R::Ring, J::Vector{Int}, V::Vector{T}) -> SRow{T}
Constructs the sparse row
Basic operations
Rows support the usual operations:
+
,-
,==
multiplication by scalars
div
,divexact
getindex(A::SRow, j::Int) -> RingElem
Given a sparse row
add_scaled_row(A::SRow{T}, B::SRow{T}, c::T) -> SRow{T}
Returns the row
add_scaled_row(A::SRow{T}, B::SRow{T}, c::T) -> SRow{T}
Returns the row
transform_row(A::SRow{T}, B::SRow{T}, i::Int, j::Int, a::T, b::T, c::T, d::T)
Returns the tuple
Change of base ring
change_base_ring(R::Ring, A::SRow) -> SRow
Create a new sparse row by coercing all elements into the ring
Maximum, minimum and 2-norm
minimum(A::SRow{T}) -> T
Returns the smallest entry of
minimum(A::RelNumFieldOrderIdeal) -> AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}
minimum(A::RelNumFieldOrderIdeal) -> RelNumFieldOrderIdeal
Returns the ideal
Functionality for integral sparse rows
lift(A::SRow{zzModRingElem}) -> SRow{ZZRingElem}
Return the sparse row obtained by lifting all entries in
mod!(A::SRow{ZZRingElem}, n::ZZRingElem) -> SRow{ZZRingElem}
Inplace reduction of all entries of
mod_sym!(A::SRow{ZZRingElem}, n::ZZRingElem) -> SRow{ZZRingElem}
Inplace reduction of all entries of
mod_sym!(A::SRow{ZZRingElem}, n::Integer) -> SRow{ZZRingElem}
Inplace reduction of all entries of
maximum(abs, A::SRow{ZZRingElem}) -> ZZRingElem
Returns the largest, in absolute value, entry of
Conversion to/from julia and AbstractAlgebra types
Vector(a::SMat{T}, n::Int) -> Vector{T}
The first n
entries of a
, as a julia vector.
sparse_row(A::MatElem)
Convert A
to a sparse row. nrows(A) == 1
must hold.
dense_row(r::SRow, n::Int)
Convert r[1:n]
to a dense row, that is an AbstractAlgebra matrix.
Sparse matrices
Let SMat
. More precisely, the type is of parametrized form SRow{T}
, where T
is the element type of the base ring. For example, SMat{ZZRingElem}
is the type for sparse matrices over the integers.
In contrast to sparse rows, sparse matrices have a fixed number of rows and columns, that is, they represent elements of the matrices space
Construction
sparse_matrix(R::Ring) -> SMat
Return an empty sparse matrix with base ring
sparse_matrix(R::Ring, n::Int, m::Int) -> SMat
Return a sparse
Sparse matrices can also be created from dense matrices as well as from julia arrays:
sparse_matrix(A::MatElem; keepzrows::Bool = true)
Constructs the sparse matrix corresponding to the dense matrix keepzrows
is false, then the constructor will drop any zero row of
sparse_matrix(R::Ring, A::Matrix{T}) -> SMat
Constructs the sparse matrix over
sparse_matrix(R::Ring, A::Matrix{T}) -> SMat
Constructs the sparse matrix over
The normal way however, is to add rows:
Sparse matrices can also be concatenated to form larger ones:
vcat!(A::SMat, B::SMat) -> SMat
Vertically joins
hcat!(A::SMat, B::SMat) -> SMat
Horizontally concatenates
(Normal julia
There are special constructors:
identity_matrix(::Type{SMat}, R::Ring, n::Int)
Return a sparse
zero_matrix(::Type{SMat}, R::Ring, n::Int)
Return a sparse
zero_matrix(::Type{SMat}, R::Ring, n::Int, m::Int)
Return a sparse
block_diagonal_matrix(xs::Vector{SMat})
Return the block diagonal matrix with the matrices in xs
on the diagonal. Requires all blocks to have the same base ring.
Slices:
sub(A::SMat, r::AbstractUnitRange, c::AbstractUnitRange) -> SMat
Return the submatrix of
Transpose:
Elementary Properties
sparsity(A::SMat) -> Float64
Return the sparsity of A
, that is, the number of zero-valued elements divided by the number of all elements.
density(A::SMat) -> Float64
Return the density of A
, that is, the number of nonzero-valued elements divided by the number of all elements.
number_of_columns(A::SMat) -> Int
Return the number of columns of
is_upper_triangular(A::SMat)
Returns true if and only if
maximum(abs, A::SMat{ZZRingElem}) -> ZZRingElem
Finds the largest, in absolute value, entry of
elementary_divisors(A::SMat{ZZRingElem}) -> Vector{ZZRingElem}
The elementary divisors of
solve_dixon_sf(A::SMat{ZZRingElem}, b::SRow{ZZRingElem}, is_int::Bool = false) -> SRow{ZZRingElem}, ZZRingElem
solve_dixon_sf(A::SMat{ZZRingElem}, B::SMat{ZZRingElem}, is_int::Bool = false) -> SMat{ZZRingElem}, ZZRingElem
For a sparse square matrix
hadamard_bound2(A::SMat{T}) -> T
The square of the product of the norms of the rows of
echelon_with_transform(A::SMat{zzModRingElem}) -> SMat, SMat
Find a unimodular matrix
reduce_full(A::SMat{ZZRingElem}, g::SRow{ZZRingElem},
trafo = Val{false}) -> SRow{ZZRingElem}, Vector{Int}
Reduces
The second return value is the array of pivot elements of
If trafo
is set to Val{true}
, then additionally an array of transformations is returned.
hnf!(A::SMat{ZZRingElem})
Inplace transform of
hnf(A::SMat{ZZRingElem}) -> SMat{ZZRingElem}
Return the upper right Hermite normal form of
hnf_extend!(A::SMat{ZZRingElem}, b::SMat{ZZRingElem}, offset::Int = 0) -> SMat{ZZRingElem}
Given a matrix
is_diagonal(A::SMat) -> Bool
True iff only the i-th entry in the i-th row is non-zero.
det(A::SMat{ZZRingElem})
The determinant of
det_mc(A::SMat{ZZRingElem})
Computes the determinant of
valence_mc{T}(A::SMat{T}; extra_prime = 2, trans = Vector{SMatSLP_add_row{T}}()) -> T
Uses a Monte-Carlo algorithm to compute the valence of
The valence is computed modulo various primes until the computation stabilises for extra_prime
many.
trans
, if given, is a SLP (straight-line-program) in GL(n, Z). Then the valence of trans
*
saturate(A::SMat{ZZRingElem}) -> SMat{ZZRingElem}
Computes the saturation of
Equivalently, return
hnf_kannan_bachem(A::SMat{ZZRingElem}) -> SMat{ZZRingElem}
Compute the Hermite normal form of
diagonal_form(A::SMat{ZZRingElem}) -> SMat{ZZRingElem}
A matrix
Manipulation/ Access
getindex(A::SMat, i::Int, j::Int)
Given a sparse matrix
getindex(A::SMat, i::Int) -> SRow
Given a sparse matrix
setindex!(A::SMat, b::SRow, i::Int)
Given a sparse matrix
swap_rows!(A::SMat{T}, i::Int, j::Int)
Swap the
swap_cols!(A::SMat, i::Int, j::Int)
Swap the
add_scaled_col!(A::SMat{T}, i::Int, j::Int, c::T)
Add
add_scaled_row!(A::SMat{T}, i::Int, j::Int, c::T)
Add
transform_row!(A::SMat{T}, i::Int, j::Int, a::T, b::T, c::T, d::T)
Applies the transformation
mod_sym!(A::SMat{ZZRingElem}, n::ZZRingElem)
Inplace reduction of all entries of
find_row_starting_with(A::SMat, p::Int) -> Int
Tries to find the index
reduce(A::SMat{ZZRingElem}, g::SRow{ZZRingElem}, m::ZZRingElem) -> SRow{ZZRingElem}
Given an upper triangular matrix
reduce(A::SMat{ZZRingElem}, g::SRow{ZZRingElem}) -> SRow{ZZRingElem}
Given an upper triangular matrix
reduce(A::SMat{T}, g::SRow{T}) -> SRow{T}
Given an upper triangular matrix
Changing of the ring:
map_entries(f, A::SMat) -> SMat
Given a sparse matrix
change_base_ring(R::Ring, A::SMat)
Create a new sparse matrix by coercing all elements into the ring
Arithmetic
Matrices support the usual operations as well
+
,-
,==
div
,divexact
by scalarsmultiplication by scalars
Various products:
*(A::SMat{T}, b::AbstractVector{T}) -> Vector{T}
Return the product
*(A::SMat{T}, b::AbstractMatrix{T}) -> Matrix{T}
Return the product
dot(x::SRow{T}, A::SMat{T}, y::SRow{T}) where T -> T
Return the generalized dot product dot(x, A*y)
.
dot(x::MatrixElem{T}, A::SMat{T}, y::MatrixElem{T}) where T -> T
Return the generalized dot product dot(x, A*y)
.
dot(x::AbstractVector{T}, A::SMat{T}, y::AbstractVector{T}) where T -> T
Return the generalized dot product dot(x, A*y)
.
Other:
sparse(A::SMat) -> SparseMatrixCSC
The same matrix, but as a sparse matrix of julia type SparseMatrixCSC
.
ZZMatrix(A::SMat{T}) where {T <: Integer}
The same matrix ZZMatrix
. Requires a conversion from the base ring of
Array(A::SMat{T}) -> Matrix{T}
The same matrix, but as a two-dimensional julia array.