|
[____]
Lattices play an important role in various areas, e.g., representation
theory, coding theory, geometry and algebraic number theory.
A lattice in Magma is a free Z-module contained in Qn or
Rn, together with a positive definite inner product having image
in Q or R.
The information specifying a lattice is a basis, given by a sequence
of elements in Qn or Rn, and a bilinear product (., .),
given by (v, w) = v M wtr for a positive definite matrix M.
Central to the lattice machinery in Magma is a fast implementation of the
Lenstra-Lenstra-Lovász lattice reduction algorithm [LLL82].
The Lenstra-Lenstra-Lovász algorithm (LLL for short)
takes a basis of a lattice and returns a new basis of the
lattice which is LLL-reduced
which usually means that the vectors of the new basis have small norms.
The Magma algorithm is based on both the floating-point LLL algorithm
of Nguyen and Stehlé [NS09a]
and the exact integral algorithm as described by de Weger in [dW87],
but includes many optimisations, with
particular attention to different kinds of input matrices. The
algorithm can operate on either a basis matrix or a Gram matrix
and can be controlled by many parameters (selection of methods,
LLL reduction constants, step and time limits, etc.).
For each lattice, a LLL-reduced basis for the
lattice is computed and stored internally when necessary and
subsequently used for many operations. This gives maximum efficiency
for the operations, yet all the operations are presented using the
external ("user") basis of the lattice.
Lattices are thus a more efficient alternative to R-spaces where R
is the integer ring Z since lattices use a LLL-reduced form of the basis
matrix extensively instead of the Hermite form of a basis matrix used
by R-spaces which may have very large entries.
Another important component of the lattice machinery is a very efficient
algorithm for enumerating all vectors of a lattice with norms in a
given range. This algorithm is used for computing the minimum, the shortest
vectors, vectors up to a chosen length, and vectors close to or closest
to a given vector (possibly) outside a lattice.
Several interesting lattices are directly accessible inside Magma
using standard constructions (e.g., root lattices and preimages of
linear codes).
Additionally, an interface has been provided to convert lattices in
the database of G. Nebe and N.J.A. Sloane [NS01a]
into Magma format.
[Next][Prev] [Right] [____] [Up] [Index] [Root]
|