Re: LatticeReduce extension
- To: mathgroup at smc.vnet.net
- Subject: [mg42481] Re: [mg42450] LatticeReduce extension
- From: Dr Bob <majort at cox-internet.com>
- Date: Thu, 10 Jul 2003 03:37:06 -0400 (EDT)
- References: <200307091224.IAA27114@smc.vnet.net>
- Reply-to: majort at cox-internet.com
- Sender: owner-wri-mathgroup at wolfram.com
Maybe this will help.
MatrixForm[b = {{1, 0, 0, 100000}, {0, 1, 0, 100010}, {0, 0, 1, 100100}}]
MatrixForm[lr = LatticeReduce[b]]
ps = PseudoInverse[b];
lr.ps // MatrixForm
lr.ps.b // MatrixForm
lr.ps is a matrix of coordinates for the reduced basis in terms of the
original vectors.
If the original vectors aren't independent, the resulting coordinates
aren't unique, of course, and the integer version of those coordinates may
not be the one derived this way.
For instance:
MatrixForm[b = {{1, 0,
0, 100000}, {0, 1, 0, 100010}, {0, 0, 1, 100100}, {1, 0, 0, 100000} +
{0, 1, 0, 100010} - {0, 0, 1, 100100}}]
MatrixForm[lr = LatticeReduce[b]]
ps = PseudoInverse[b];
lr.ps // MatrixForm
lr.ps.b // MatrixForm
But the following should always work. (Assume b is the original matrix of
interest.)
MatrixForm[b = {{1, 0,
0, 100000}, {0, 1, 0, 100010}, {0, 0, 1, 100100}, {1, 0, 0, 100000} +
{0, 1, 0, 100010} - {0, 0, 1, 100100}}]
(bb = AppendRows[IdentityMatrix@Length@b, b]) // MatrixForm
MatrixForm[lr = LatticeReduce[bb]]
ps = PseudoInverse[bb];
lr.ps // MatrixForm
lr.ps.b // MatrixForm
lr.ps gives the integer coordinates now. Your original example began with
an identity matrix, so the coordinates showed up both in the original lr
matrix and in lr.ps. But if b doesn't begin with an identity matrix,
simply insert one! It changes the reduced basis, but that's not unique
anyway.
Bobby
On Wed, 9 Jul 2003 08:24:25 -0400 (EDT), <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.
>
>
>
>
--
majort at cox-internet.com
Bobby R. Treat
- References:
- LatticeReduce extension
- From: davidmma@freemail.hu
- LatticeReduce extension