MathGroup Archive 1992

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: LatticeReduce

  • To: mathgroup at
  • Subject: Re: LatticeReduce
  • From: keiper
  • Date: Tue, 10 Mar 92 13:05:01 CST

>From dan at Tue Mar 10 10:29:20 1992
>Date: Tue, 10 Mar 92 10:28:24 cst
>From: dan at (Daniel R. Grayson)
>To: keiper at, sgupta at wcu.bitnet
>In-Reply-To: keiper at's message of Tue, 10 Mar 92 09:49:35 CST <9203101549.AA09390 at>
>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.

  • Prev by Date: Re: Partial Fraction Decomposition with imaginary coeff.
  • Next by Date: Elliptic integral trouble in Mathematica...
  • Previous by thread: LatticeReduce
  • Next by thread: Re: LatticeReduce