Re: Re: LatticeReduce
- To: mathgroup at smc.vnet.net
- Subject: [mg93601] Re: [mg93580] Re: LatticeReduce
- From: Artur <grafix at csl.pl>
- Date: Mon, 17 Nov 2008 06:18:13 -0500 (EST)
- References: <200811151103.GAA16591@smc.vnet.net> <491F2366.3040401@csl.pl> <200811161202.HAA04504@smc.vnet.net> <2086.98.212.148.221.1226852850.squirrel@webmail.wolfram.com>
- Reply-to: grafix at csl.pl
Dear Daniel,
Many thanks for explanations! That helps! I will be learning about
ExtendedGCD and HermiteDecomposition.
What do you mean LinearSolve ? Could you give me one equation exercise
(related to my) and solvng them by LinearSolve?
Best wishes
Artur
danl at wolfram.com pisze:
>> 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
>>>
>>>
>
>
>
> __________ Information from ESET NOD32 Antivirus, version of virus signature database 3615 (20081115) __________
>
> The message was checked by ESET NOD32 Antivirus.
>
> http://www.eset.com
>
>
>
>
- References:
- Basic programming
- From: BionikBlue <frankflip@hotmail.com>
- Re: LatticeReduce
- From: Artur <grafix@csl.pl>
- Basic programming