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.