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.
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 R R R . For example, 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 { ( x i ) i ∈ R N ∣ x i = 0 for almost all i } \{ (x_i)_i \in R^{\mathbb{N}} \mid x_i = 0 \text{ for almost all }i\} {( x i ) i ∈ R N ∣ x i = 0 for almost all i } . In particular any two sparse rows over the same base ring can be added.
sparse_row(R::Ring, J::Vector {Tuple {Int , T}}) -> SRow{T}
Constructs the sparse row ( a i ) i (a_i)_i ( a i ) i with a i j = x j a_{i_j} = x_j a i j = x j , where J = ( i j , x j ) j J = (i_j, x_j)_j J = ( i j , x j ) j . The elements x i x_i x i must belong to the ring R R R .
source sparse_row(R::Ring, J::Vector {Tuple {Int , Int }}) -> SRow
Constructs the sparse row ( a i ) i (a_i)_i ( a i ) i over R R R with a i j = x j a_{i_j} = x_j a i j = x j , where J = ( i j , x j ) j J = (i_j, x_j)_j J = ( i j , x j ) j .
source sparse_row(R::NCRing, J::Vector {Int }, V::Vector {T}) -> SRow{T}
Constructs the sparse row ( a i ) i (a_i)_i ( a i ) i over R R R with a i j = x j a_{i_j} = x_j a i j = x j , where J = ( i j ) j J = (i_j)_j J = ( i j ) j and V = ( x j ) j V = (x_j)_j V = ( x j ) j .
source Rows support the usual operations:
+
, -
, ==
multiplication by scalars div
, divexact
getindex(A::SRow, j::Int ) -> RingElem
Given a sparse row ( a i ) i (a_i)_{i} ( a i ) i and an index j j j return a j a_j a j .
source add_scaled_row(A::SRow{T}, B::SRow{T}, c::T) -> SRow{T}
Returns the row c A + B c A + B c A + B .
source add_scaled_row(A::SRow{T}, B::SRow{T}, c::T) -> SRow{T}
Returns the row c A + B c A + B c A + B .
source transform_row(A::SRow{T}, B::SRow{T}, i::Int , j::Int , a::T, b::T, c::T, d::T)
Returns the tuple ( a A + b B , c A + d B ) (aA + bB, cA + dB) ( a A + b B , c A + d B ) .
source length(A::SRow)
Returns the number of nonzero entries of A A A .
source change_base_ring(R::Ring, A::SRow) -> SRow
Create a new sparse row by coercing all elements into the ring R R R .
source maximum(A::SRow{T}) -> T
Returns the largest entry of A A A .
source maximum(A::SRow{T}) -> T
Returns the largest entry of A A A .
source minimum(A::SRow{T}) -> T
Returns the smallest entry of A A A .
source minimum(A::RelNumFieldOrderIdeal) -> AbsNumFieldOrderIdeal{AbsSimpleNumField, AbsSimpleNumFieldElem}
minimum(A::RelNumFieldOrderIdeal) -> RelNumFieldOrderIdeal
Returns the ideal A ∩ O A \cap O A ∩ O where O O O is the maximal order of the coefficient ideals of A A A .
source minimum(A::SRow{T}) -> T
Returns the smallest entry of A A A .
source norm2(A::SRow{T} -> T
Returns A ⋅ A t A \cdot A^t A ⋅ A t .
source lift(A::SRow{zzModRingElem}) -> SRow{ZZRingElem}
Return the sparse row obtained by lifting all entries in A A A .
source mod!(A::SRow{ZZRingElem}, n::ZZRingElem) -> SRow{ZZRingElem}
Inplace reduction of all entries of A A A modulo n n n to the positive residue system.
source mod_sym!(A::SRow{ZZRingElem}, n::ZZRingElem) -> SRow{ZZRingElem}
Inplace reduction of all entries of A A A modulo n n n to the symmetric residue system.
source mod_sym!(A::SRow{ZZRingElem}, n::Integer ) -> SRow{ZZRingElem}
Inplace reduction of all entries of A A A modulo n n n to the symmetric residue system.
source maximum(abs, A::SRow{ZZRingElem}) -> ZZRingElem
Returns the largest, in absolute value, entry of A A A .
source Vector (a::SMat{T}, n::Int ) -> Vector {T}
The first n
entries of a
, as a julia vector.
source sparse_row(A::MatElem)
Convert A
to a sparse row. nrows(A) == 1
must hold.
source dense_row(r::SRow, n::Int )
Convert r[1:n]
to a dense row, that is an AbstractAlgebra matrix.
source Let R R R be a commutative ring. Sparse matrices with base ring R R R are modelled by objects of type 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 M a t n × m ( R ) \mathrm{Mat}_{n\times m}(R) Mat n × m ( R ) . Internally, sparse matrices are implemented as an array of sparse rows. As a consequence, unlike their dense counterparts, sparse matrices have a mutable number of rows and it is very performant to add additional rows.
sparse_matrix(R::Ring) -> SMat
Return an empty sparse matrix with base ring R R R .
source sparse_matrix(R::Ring, n::Int , m::Int ) -> SMat
Return a sparse n n n times m m m zero matrix over R R R .
source 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 A A A . If keepzrows
is false, then the constructor will drop any zero row of A A A .
source sparse_matrix(R::Ring, A::Matrix {T}) -> SMat
Constructs the sparse matrix over R R R corresponding to A A A .
source sparse_matrix(R::Ring, A::Matrix {T}) -> SMat
Constructs the sparse matrix over R R R corresponding to A A A .
source The normal way however, is to add rows:
push!(A::SMat{T}, B::SRow{T}) where T
Appends the sparse row B
to A
.
source Sparse matrices can also be concatenated to form larger ones:
vcat!(A::SMat, B::SMat) -> SMat
Vertically joins A A A and B B B inplace, that is, the rows of B B B are appended to A A A .
source vcat(A::SMat, B::SMat) -> SMat
Vertically joins A A A and B B B .
source hcat!(A::SMat, B::SMat) -> SMat
Horizontally concatenates A A A and B B B , inplace, changing A A A .
source hcat(A::SMat, B::SMat) -> SMat
Horizontally concatenates A A A and B B B .
source (Normal julia c a t cat c a t is also supported)
There are special constructors:
identity_matrix(::Type {SMat}, R::Ring, n::Int )
Return a sparse n n n times n n n identity matrix over R R R .
source zero_matrix(::Type {SMat}, R::Ring, n::Int )
Return a sparse n n n times n n n zero matrix over R R R .
source zero_matrix(::Type {SMat}, R::Ring, n::Int , m::Int )
Return a sparse n n n times m m m zero matrix over R R R .
source 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.
source Slices:
sub(A::SMat, r::AbstractUnitRange , c::AbstractUnitRange ) -> SMat
Return the submatrix of A A A , where the rows correspond to r r r and the columns correspond to c c c .
source Transpose:
transpose(A::SMat) -> SMat
Returns the transpose of A A A .
source sparsity(A::SMat) -> Float64
Return the sparsity of A
, that is, the number of zero-valued elements divided by the number of all elements.
source density(A::SMat) -> Float64
Return the density of A
, that is, the number of nonzero-valued elements divided by the number of all elements.
source nnz(A::SMat) -> Int
Return the number of non-zero entries of A A A .
source number_of_rows(A::SMat) -> Int
Return the number of rows of A A A .
source number_of_columns(A::SMat) -> Int
Return the number of columns of A A A .
source isone(A::SMat)
Tests if A A A is an identity matrix.
source iszero(A::SMat)
Tests if A A A is a zero matrix.
source is_upper_triangular(A::SMat)
Returns true if and only if A A A is upper (right) triangular.
source maximum(A::SMat{T}) -> T
Finds the largest entry of A A A .
source minimum(A::SMat{T}) -> T
Finds the smallest entry of A A A .
source maximum(abs, A::SMat{ZZRingElem}) -> ZZRingElem
Finds the largest, in absolute value, entry of A A A .
source elementary_divisors(A::SMat{ZZRingElem}) -> Vector {ZZRingElem}
The elementary divisors of A A A , i.e. the diagonal elements of the Smith normal form of A A A .
source 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 A A A of full rank and a sparse matrix (row), find a sparse matrix (row) x x x and an integer d d d s.th. x A = b d x A = bd x A = b d holds. The algorithm is a Dixon-based linear p-adic lifting method. If \code{is_int} is given, then d d d is assumed to be 1 1 1 . In this case rational reconstruction is avoided.
source hadamard_bound2(A::SMat{T}) -> T
The square of the product of the norms of the rows of A A A .
source echelon_with_transform(A::SMat{zzModRingElem}) -> SMat, SMat
Find a unimodular matrix T T T and an upper-triangular E E E s.th. T A = E TA = E T A = E holds.
source reduce_full(A::SMat{ZZRingElem}, g::SRow{ZZRingElem},
with_transform = Val (false )) -> SRow{ZZRingElem}, Vector {Int }
Reduces g g g modulo A A A and assumes that A A A is upper triangular.
The second return value is the array of pivot elements of A A A that changed.
If with_transform
is set to Val(true)
, then additionally an array of transformations is returned.
source hnf!(A::SMat{ZZRingElem})
Inplace transform of A A A into upper right Hermite normal form.
source hnf(A::SMat{ZZRingElem}) -> SMat{ZZRingElem}
Return the upper right Hermite normal form of A A A .
t r u n c a t e truncate t r u n c a t e
indicates if zero rows should be returned or disgarded, when f u l l h n f full_hnf f u l l h n f is set to f a l s e false f a l se only an upper triangular matrix is computed, ie. the upwards reduction is not performed.
a u t o auto a u t o
if set to true selects a different elemination strategy - here the upwards reduction is temporarily switched off.
l i m i t limit l imi t
marks the last column where size reduction happens, so calling h n f hnf hn f on h c a t ( A , i d e n t i t y m a t r i x ( S M a t , Z Z , n r o w s ( A ) ) ) hcat(A, identity_matrix(SMat, ZZ, nrows(A))) h c a t ( A , i d e n t i t y m a t r i x ( SM a t , ZZ , n ro w s ( A ))) with l i m i t limit l imi t set to n c o l s ( A ) ncols(A) n co l s ( A ) should produce a non-reduced transformation matrix in the right. If l i m i t limit l imi t is not set, the transformation matrix will also be partly triangular.
source snf(A::SMat{ZZRingElem})
The Smith normal form (snf) of A A A .
source hnf_extend!(A::SMat{ZZRingElem}, b::SMat{ZZRingElem}, offset::Int = 0 ) -> SMat{ZZRingElem}
Given a matrix A A A in HNF, extend this to get the HNF of the concatenation with b b b .
source is_diagonal(A::SMat) -> Bool
True iff only the i-th entry in the i-th row is non-zero.
source det(A::SMat{ZZRingElem})
The determinant of A A A using a modular algorithm. Uses the dense (zzModMatrix) determinant on A A A for various primes p p p .
source det_mc(A::SMat{ZZRingElem})
Computes the determinant of A A A using a LasVegas style algorithm, i.e. the result is not proven to be correct. Uses the dense (zzModMatrix) determinant on A A A for various primes p p p .
source 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 A A A . The valence is the valence of the minimal polynomial f f f of t r a n s p o s e ( A ) ∗ A transpose(A)*A t r an s p ose ( A ) ∗ A , thus the last non-zero coefficient, typically f ( 0 ) f(0) f ( 0 ) .
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
* A A A is computed instead.
source saturate(A::SMat{ZZRingElem}) -> SMat{ZZRingElem}
Computes the saturation of A A A , that is, a basis for Q ⊗ M ∩ Z n \mathbf{Q}\otimes M \cap \mathbf{Z}^n Q ⊗ M ∩ Z n , where M M M is the row span of A A A and n n n the number of rows of A A A .
Equivalently, return T A TA T A for an invertible rational matrix T T T , such that T A TA T A is integral and the elementary divisors of T A TA T A are all trivial.
source hnf_kannan_bachem(A::SMat{ZZRingElem}) -> SMat{ZZRingElem}
Compute the Hermite normal form of A A A using the Kannan-Bachem algorithm.
source diagonal_form(A::SMat{ZZRingElem}) -> SMat{ZZRingElem}
A matrix D D D that is diagonal and obtained via unimodular row and column operations. Like a snf without the divisibility condition.
source getindex(A::SMat, i::Int , j::Int )
Given a sparse matrix A = ( a i j ) i , j A = (a_{ij})_{i, j} A = ( a ij ) i , j , return the entry a i j a_{ij} a ij .
source getindex(A::SMat, i::Int ) -> SRow
Given a sparse matrix A A A and an index i i i , return the i i i -th row of A A A .
source setindex!(A::SMat, b::SRow, i::Int )
Given a sparse matrix A A A , a sparse row b b b and an index i i i , set the i i i -th row of A A A equal to b b b .
source swap_rows!(A::SMat{T}, i::Int , j::Int )
Swap the i i i -th and j j j -th row of A A A inplace.
source swap_cols!(A::SMat, i::Int , j::Int )
Swap the i i i -th and j j j -th column of A A A inplace.
source scale_row!(A::SMat{T}, i::Int , c::T)
Multiply the i i i -th row of A A A by c c c inplace.
source add_scaled_col!(A::SMat{T}, i::Int , j::Int , c::T)
Add c c c times the i i i -th column to the j j j -th column of A A A inplace, that is, A j → A j + c ⋅ A i A_j \rightarrow A_j + c \cdot A_i A j → A j + c ⋅ A i , where ( A i ) i (A_i)_i ( A i ) i denote the columns of A A A .
source add_scaled_row!(A::SMat{T}, i::Int , j::Int , c::T)
Add c c c times the i i i -th row to the j j j -th row of A A A inplace, that is, A j → A j + c ⋅ A i A_j \rightarrow A_j + c \cdot A_i A j → A j + c ⋅ A i , where ( A i ) i (A_i)_i ( A i ) i denote the rows of A A A .
source transform_row!(A::SMat{T}, i::Int , j::Int , a::T, b::T, c::T, d::T)
Applies the transformation ( A i , A j ) → ( a A i + b A j , c A i + d A j ) (A_i, A_j) \rightarrow (aA_i + bA_j, cA_i + dA_j) ( A i , A j ) → ( a A i + b A j , c A i + d A j ) to A A A , where ( A i ) i (A_i)_i ( A i ) i are the rows of A A A .
source diagonal(A::SMat) -> ZZRingElem[]
The diagonal elements of A A A in an array.
source reverse_rows!(A::SMat)
Inplace inversion of the rows of A A A .
source mod_sym!(A::SMat{ZZRingElem}, n::ZZRingElem)
Inplace reduction of all entries of A A A modulo n n n to the symmetric residue system.
source find_row_starting_with(A::SMat, p::Int ) -> Int
Tries to find the index i i i such that A i , p ≠ 0 A_{i,p} \neq 0 A i , p = 0 and A i , p − j = 0 A_{i, p-j} = 0 A i , p − j = 0 for all j > 1 j > 1 j > 1 . It is assumed that A A A is upper triangular. If such an index does not exist, find the smallest index larger.
source reduce(A::SMat{T}, g::SRow{T}, m::T) -> SRow{T}
Given an upper triangular matrix A A A over the integers, a sparse row g g g and an integer m m m , this function reduces g g g modulo A A A and returns g g g modulo m m m with respect to the symmetric residue system.
source reduce(A::SMat{T}, g::SRow{T}) -> SRow{T}
Given an upper triangular matrix A A A over a field and a sparse row g g g , this function reduces g g g modulo A A A .
source reduce(A::SMat{T}, g::SRow{T}) -> SRow{T}
Given an upper triangular matrix A A A over a field and a sparse row g g g , this function reduces g g g modulo A A A .
source rand_row(A::SMat) -> SRow
Return a random row of the sparse matrix A A A .
source Changing of the ring:
map_entries(f, A::SMat) -> SMat
Given a sparse matrix A A A and a callable object f f f , this function will construct a new sparse matrix by applying f f f to all elements of A A A .
source change_base_ring(R::Ring, A::SMat)
Create a new sparse matrix by coercing all elements into the ring R R R .
source 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 ⋅ b A \cdot b A ⋅ b as a dense vector.
source *(A::SMat{T}, b::AbstractMatrix {T}) -> Matrix {T}
Return the product A ⋅ b A \cdot b A ⋅ b as a dense matrix.
source *(A::SMat{T}, b::MatElem{T}) -> MatElem
Return the product A ⋅ b A \cdot b A ⋅ b as a dense matrix.
source *(A::SRow, B::SMat) -> SRow
Return the product A ⋅ B A\cdot B A ⋅ B as a sparse row.
source mul_sparse(A::SMat{T}, B::SMat{T}) -> SMat{T}
Return the product A ⋅ B A\cdot B A ⋅ B as a sparse matrix.
The product of two sparse matrices is, in general, not sparse, so depending on the context, it might be more efficient to use mul_dense(::SMat{T}, ::SMat{T}) where {T}
instead.
source mul_dense(A::SMat{T}, B::SMat{T}) -> MatElem{T}
Return the product A ⋅ B A\cdot B A ⋅ B as a dense matrix.
source dot(x::SRow{T}, A::SMat{T}, y::SRow{T}) where T -> T
Return the generalized dot product dot(x, A*y)
.
source dot(x::MatrixElem{T}, A::SMat{T}, y::MatrixElem{T}) where T -> T
Return the generalized dot product dot(x, A*y)
.
source dot(x::AbstractVector {T}, A::SMat{T}, y::AbstractVector {T}) where T -> T
Return the generalized dot product dot(x, A*y)
.
source Other:
sparse(A::SMat) -> SparseMatrixCSC
The same matrix, but as a sparse matrix of julia type SparseMatrixCSC
.
source ZZMatrix(A::SMat{ZZRingElem})
The same matrix A A A , but as an ZZMatrix
.
source ZZMatrix(A::SMat{T}) where {T <: Integer }
The same matrix A A A , but as an ZZMatrix
. Requires a conversion from the base ring of A A A to Z Z \mathbb ZZ Z Z .
source Matrix (A::SMat{T}) -> Matrix {T}
The same matrix, but as a julia matrix.
source Array (A::SMat{T}) -> Matrix {T}
The same matrix, but as a two-dimensional julia array.
source