Karim BELABAS on Mon, 10 Mar 2003 22:41:09 +0100 (MET)


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: rnflllgram() regression


On Fri, 7 Mar 2003, Igor Schein wrote:
> On Mon, Mar 03, 2003 at 12:48:04PM +0100, Karim BELABAS wrote:
>> On Sun, 2 Mar 2003, Igor Schein wrote:
>>> ? nf=nfinit(y^9-10*y^8-y^7+7*y^6+y^5-y^4+5*y^2+9*y+4);
>>> ? pol=x^9-10*x^8-10*x^7+6*x^6-4*x^5+7*x^4+7*x^3+8*x^2-1;
>>> ? rnflllgram(nf,pol,rnfpseudobasis(nf,pol));
>>>   ***   not a definite matrix in lllgram
>>>
>>> It was broken some time between 2.2.4 and 2.2.5
>>
>> Precision loss. It occured in 2.2.4 also, but was slightly less acute
>> (different internal nf format), hence was hidden / disregarded [ and the
>> result was incorrect: not LLL reduced ].
>>
>> At \p50 it works.
>
> Any way to have precision insufficiency detected?  I mean, the error
> seems pretty arbitrary, even I didn't think to try higher precision,
> and I should definitely know by now :)

Basically, the algorithm doesn't work [ doesn't really reduce as much as
desired ]. But you're right, it's no reason to be numerically unstable on top
of that.

I have fixed the numerical instability (not the algorithm). It also fixes an
old TODO item:

  4  rnfpolred is numerically unstable:
     ? rnfpolred(nfinit(quadpoly(904,y)),quadray(904,1))
       ***   division by zero in gdiv, gdivgs or ginv

Cheers,

    Karim.
-- 
Karim Belabas                     Tel: (+33) (0)1 69 15 57 48
Dép. de Mathématiques, Bât. 425   Fax: (+33) (0)1 69 15 60 19
Université Paris-Sud              http://www.math.u-psud.fr/~belabas/
F-91405 Orsay (France)            http://www.parigp-home.de/  [PARI/GP]