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 Z-module contained in R^n with some additional structure, in particular an inner product. The basic information for a lattice is a basis, given by a sequence of vectors in R^n, and an inner product (., .) given by a positive definite matrix M such that (v, w) = v M w^(tr).
Central to the lattice machinery in Magma is a fast implementation of the LLL lattice reduction [A.K. Lenstra, H.W. Lenstra and L. Lov'{a]sz, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), pp. 515--534.} algorithm. The LLL algorithm 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 FP-LLL algorithm of Schnorr and Euchner [C.P. Schnorr and M. Euchner, Lattice Basis Reduction: Improved Practical Algorithms and Solving Subset Sum Problems, Proc. Fundamentals of Computation Theory, LNCS 529, 1991, pp. 68--85.] and the exact integral algorithm of de Weger [B.M.M. de Weger, Solving exponential Diophantine equations using lattice basis reduction, J. Number Theory 26 (1987), pp. 325--367.], but includes many optimizations, 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, delta constant, 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.
The computation of the automorphism group of a lattice and the testing of lattices for isometry is performed within Magma by the AUTO and ISOM programs of Bernd Souvignier [W. Plesken, B. Souvignier, Computing Isometries of Lattices, J. Symb. Comp. 24 (1997), pp. 327--334.].
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 (http://www.research.att.com/ { njas/lattices}) into Magma format.
[Next] [Prev] [Right] [____] [Up] [Index] [Root]