Re: LatticeReduce

*To*: mathgroup at yoda.physics.unc.edu*Subject*: Re: LatticeReduce*From*: keiper*Date*: Tue, 10 Mar 92 13:05:01 CST

>From dan at uiucmath.math.uiuc.edu Tue Mar 10 10:29:20 1992 >Date: Tue, 10 Mar 92 10:28:24 cst >From: dan at uiucmath.math.uiuc.edu (Daniel R. Grayson) >To: keiper at wri.com, sgupta at wcu.bitnet >In-Reply-To: keiper at wri.com's message of Tue, 10 Mar 92 09:49:35 CST <9203101549.AA09390 at spider.wri.com> >Subject: user question I am constructing an integer lattice of rank d as the span of n integer vectors in R^d with n > d . I want to use the LLL algorithm to reduce to a basis (of size d). Unfortunately, LatticeReduce in Mathematica seems to require n=d. I need to use LLL in order to find short vectors in the lattice. What should I do ? Don't use LatticeReduce unless you really want to get SHORT vectors. The problem of getting a basis of a lattice is a linear algebra problem, and can be solved without LatticeReduce. Do it by row reduction over the integers (but RowReduce doesn't work over the integers, too bad.) Think of the vectors as rows in a matrix, and use elementary row operations with integer entries on that matrix to put it in triangular form: * * * * * 0 * * * * 0 0 * * * 0 0 0 * * 0 0 0 0 * 0 0 0 0 0 0 0 0 0 0 The pivot in column 1 is the gcd of the integers we started with in that column. We ignored row 1 and reduced the remaining entries in column 2 to get their gcd into row 2, with zeroes below, and so on. These new rows are vectors which span the same lattice, and we can discard the rows which are zero.