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é [NS09] 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.