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>