Re: Re: LatticeReduce
- To: mathgroup at smc.vnet.net
- Subject: [mg93600] Re: [mg93580] Re: LatticeReduce
- From: danl at wolfram.com
- Date: Mon, 17 Nov 2008 06:18:03 -0500 (EST)
- References: <200811151103.GAA16591@smc.vnet.net> <491F2366.3040401@csl.pl>
> P.S.
> And for the case:
> {a1, a2, a3} = {1, 3^4,
> 5^4}; a = {{1, 0, 0, -a1}, {0, 1, 0, -a2}, {0, 0, 1, -a3}}; b =
> LatticeReduce[a]
>
> Out1:*{{1, 0, 0, -1}, {12, -8, 1, 11}, {-6, -23, 3, -6}}
>
> Mathematica should be return 2 solutions:
>
> 23 - 8*3^4 + 5^4=0
> 12 + 23*3^4 - 3*5^4=0
>
> **After good LatticeReduce should begin from : {{23,-8,1,0}, {12,
> 23,-3,0}, {c, c1,c2, c3}}
>
> What is wrong in LatticeReduce or what I'm doing wrong ?
>
> Artur
You are misunderstanding what lattice reduction means. It has no
underlying understanding of any equations to solve, it simply reduces
lattices. As far as I can tell, it is doing just that in your examples.
If you want to get solutions to your equations, there are various
approaches. One is to use Reduce or FindInstance (you will need
restrictions to avoid the zero solution for that latter, since the
equation is homogeneous). You might use Minimize, imposing an objective
function, as below.
{a0, a1, a2} = {1, 2^15, -3^8};
In[32]:= Minimize[{x + y + z, {x, y, z}.{a0, a1, a2} == 0, x >= 1,
y >= 1, z >= 1}, {x, y, z}, Integers]
Out[32]= {43, {x -> 37, y -> 1, z -> 5}}
(Or just minimize x, maybe.)
In[42]:= Minimize[{x, {x, y, z}.{a0, a1, a2} == 0, x >= 1, y >= 1,
z >= 1}, {x, y, z}, Integers]
Out[42]= {1, {x -> 1, y -> 7093, z -> 35425}}
If you seek reasonably small solutions, you might use LatticeReduce as
follows. Weight your lattice in such a way as to push the last column
coordinates toward zero, in the hope of getting solutions. Here is an
example.
{a1, a2, a3} = 10*{1, 3^4, 5^4};
a = {{1, 0, 0, -a1}, {0, 1, 0, -a2}, {0, 0, 1, -a3}};
b = LatticeReduce[a]
{{1, 0, 0, -10}, {23, -8, 1, 0}, {-12, -23, 3, 0}}
Now you see those "small" solutions that generate the full solution set.
There are other approaches, using ExtendedGCD, HermiteDecomposition, or
LinearSolve. Which are desireable would depend on what specifically you
seek (generating set? small solutions?...).
Daniel Lichtblau
Wolfram Research
> Artur pisze:
>> Dear Mathematica Gurus,
>> I want to find such inetegrs x,y,z that
>> x + y*2^15 + z*3^8 = 0
>> I'm reading in manual that I can use LatticeReduce
>>
>> {a0, a1, a2} = {1,
>> 2^15, -3^8}; a = {{1, 0, 0, -a0}, {0, 1, 0, -a1}, {0, 0,
>> 1, -a2}}; b = LatticeReduce[a]
>>
>> Out1:{{1, 0, 0, -1}, {18, 1, 5, 19}, {117, -171, -854, 117}}
>>
>> That mean that computer don't find such solution (solution is finded
>> when last number in one of rows should be 0)
>>
>> If I run again:
>> {a0, a1, a2} = {37,
>> 2^15, -3^8}; a = {{1, 0, 0, -a0}, {0, 1, 0, -a1}, {0, 0,
>> 1, -a2}}; b = LatticeReduce[a]
>>
>> Out2:{{1, 1, 5, 0}, {1, 0, 0, -37}, {170, -7, -34, 12}}
>>
>> Now solution is finded by Mathematica OK!
>> k = Transpose[{{37, 2^15, -3^8, anything}}]; b[[1]].k
>>
>> Out3: {0}
>>
>> Is OK!
>>
>> Is another method finding coefficients x, y, z as LatticeReduce and
>> why Mathematica don't reduced
>> {a0, a1, a2} = {1, 2^15, -3^8}; a = {{1, 0, 0, -a0}, {0, 1, 0, -a1},
>> {0, 0, 1, -a2}}; b = LatticeReduce[a]
>>
>>
>> Best wishes
>> Artur
>>
>
- References:
- Basic programming
- From: BionikBlue <frankflip@hotmail.com>
- Basic programming