Re: LatticeReduce extension
- To: mathgroup at smc.vnet.net
- Subject: [mg42469] Re: [mg42450] LatticeReduce extension
- From: Daniel Lichtblau <danl at wolfram.com>
- Date: Thu, 10 Jul 2003 03:36:53 -0400 (EDT)
- References: <200307091224.IAA27114@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
davidmma at freemail.hu wrote:
>
> Dear MathGroup,
>
> I would like to use the LLL algorithm to get the reduce basis for a given
> set of vectors, but I also need the coordinates of the basis vectors in
> the original system.
>
> LatticeReduce doesn't have this functionality, and when I tried to
> implement such an extension, I've found it very slow, although it
> shouldn't be. I would be glad if somebody who had faced with this
> problem earlier could help me. I don't post the code here, because it is
> awful, long and seems to be uncorrectable. :(
>
> Thank you in advance.
Strangely enough I was asked about this yesterday by someone else. I can
offer two possibilities.
First, if your lattice has full row rank, you can get the multipler
matrix by linear algebra. I illustrate below with a simple example. I am
assuming you want something like
U . initial_lattice == reduced_lattice
where we solve for unimodular matrix U.
In[36]:= latmat = { {1,2,3,4}, {4,5,6,7}, {6,-2,1,3} };
In[37]:= redlat = LatticeReduce[latmat]
Out[37]= {{2, 1, 0, -1}, {1, 2, 3, 4}, {3, -5, -2, 0}}
In[38]:= unimodmultmat = redlat . Transpose[latmat] .
Inverse[latmat.Transpose[latmat]]
Out[38]= {{-2, 1, 0}, {1, 0, 0}, {1, -1, 1}}
We check the result.
In[39]:= unimodmultmat . latmat - redlat
Out[39]= {{0, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}}
In the case where the original matrix does not have full row rank, one
can do something along the above lines by computing the Hermite normal
form (via Developer`HermiteNormalForm), using the conversion matrix this
provides, then taking the part of the normal form that has full rank,
that is the rows that are not all zeros, reducing them and finding the
conversion matrix as above, then figuring out how to string these
conversion matrices together given that they have incompatible
dimensions (in essence, the second one will need to be augmented, I
suspect by an identity matrix on the main diagonal).
An alternative is to use a MathSource package by Wilberd van Kallen
called "Extended lattice reduce algorithm". It may be found at:
http://library.wolfram.com/infocenter/MathSource/681/
This will compute both the reduced lattice and the conversion matrix,
regardless of row rank.
Daniel Lichtblau
Wolfram Research
- References:
- LatticeReduce extension
- From: davidmma@freemail.hu
- LatticeReduce extension