Sparse linear algebra

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 \texttt{SRow}. More precisely, the type is of parametrized form 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$. For example, SRow{fmpz} 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 \in R^{\mathbb{N}} \mid x_i = 0 \text{ for almost all }i\}$. In particular any two sparse rows over the same base ring can be added.

Creation

Hecke.sparse_row — Method.
sparse_row(R::Ring, J::Vector{Tuple{Int, T}}) -> SRow{T}

Constructs the sparse row $(a_i)_i$ with $a_{i_j} = x_j$, where $J = (i_j, x_j)_j$. The elements $x_i$ must belong to the ring $R$.

Hecke.sparse_row — Method.
sparse_row(R::Ring, J::Vector{Tuple{Int, T}}) -> SRow{T}

Constructs the sparse row $(a_i)_i$ with $a_{i_j} = x_j$, where $J = (i_j, x_j)_j$. The elements $x_i$ must belong to the ring $R$.

sparse_row(R::Ring, J::Vector{Tuple{Int, Int}}) -> SRow

Constructs the sparse row $(a_i)_i$ over $R$ with $a_{i_j} = x_j$, where $J = (i_j, x_j)_j$.

Hecke.sparse_row — Method.
sparse_row(R::Ring, J::Vector{Int}, V::Vector{T}) -> SRow{T}

Constructs the sparse row $(a_i)_i$ over $R$ with $a_{i_j} = x_j$, where $J = (i_j)_j$ and $V = (x_j)_j$.

Basic operations

Base.:== — Method.
==(x::SRow, y::SRow)

Checks whether $x$ and $y$ are the same sparse row, that is, whether $x$ and $y$ have the same non-zero entries.

Base.:+ — Method.
+(A::SRow, B::SRow) -> SRow

Returns the sum of $A$ and $B$.

Base.getindex — Method.
getindex(A::SRow, j::Int) -> RingElem

Given a sparse row $(a_i)_{i}$ and an index $j$ return $a_j$.

Base.:* — Method.
*(b::T, A::SRow{T}) -> SRow

Return the sparse row obtained by multiplying all elements of $A$ by $b$.

Base.div — Method.
div(A::SRow{T}, b::T) -> SRow

Return the sparse row obtained by dividing all elements of $A$ by $b$ using div.

AbstractAlgebra.Generic.divexact — Method.
divexact(A::SRow{T}, b::T) -> SRow

Return the sparse row obtained by dividing all elements of $A$ by $b$ using divexact.

Hecke.add_scaled_row — Method.
add_scaled_row(A::SRow{T}, B::SRow{T}, c::T) -> SRow{T}

Returns the row $c A + B$.

Change of base ring

Hecke.change_ring — Method.
change_ring(A::SRow, R::Ring) -> SRow

Create a new sparse row by coercing all elements into the ring $R$.

Maximum, minimum and 2-norm

Base.maximum — Method.
maximum(A::SRow{T}) -> T

Returns the largest entry of $A$.

Base.minimum — Method.
minimum(A::NfAbsOrdIdl) -> fmpz

Returns the smallest nonnegative element in $A \cap \mathbf Z$.

minimum(A::SRow{T}) -> T

Returns the smallest entry of $A$.

  minimum(A::NfRelOrdIdl) -> NfOrdIdl
  minimum(A::NfRelOrdIdl) -> NfRelOrdIdl

Returns the ideal $A \cap O$ where $O$ is the maximal order of the coefficient ideals of $A$.

Hecke.norm2 — Method.
norm2(A::SRow{T} -> T

Returns $A \cdot A^t$.

Functionality for integral sparse rows

Nemo.lift — Method.
lift(A::SRow{nmod}) -> SRow{fmpz}

Return the sparse row obtained by lifting all entries in $A$.

Hecke.mod! — Method.
mod!(A::SRow{fmpz}, n::fmpz) -> SRow{fmpz}

Inplace reduction of all entries of $A$ modulo $n$ to the positive residue system.

Hecke.mod_sym! — Method.
mod_sym!(A::SRow{fmpz}, n::fmpz) -> SRow{fmpz}

Inplace reduction of all entries of $A$ modulo $n$ to the symmetric residue system.

Base.maximum — Method.
maximum(abs, A::SRow{fmpz}) -> fmpz

Returns the largest, in absolute value, entry of $A$.

Sparse matrices

Let $R$ be a commutative ring. Sparse matrices with base ring $R$ are modlled 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{fmpz} is the type for sparse matrices over the integers.

In constrast to sparse rows, sparse matrices have a fixed number of rows and columns, that is, they represent elements of the matrices space $\mathrm{Mat}_{n\times 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.

Construction