Karim BELABAS on Thu, 13 Mar 2003 18:22:31 +0100 (MET)


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

Re: rnflllgram() regression


On Mon, 10 Mar 2003, Igor Schein wrote:

> On Mon, Mar 10, 2003 at 10:41:09PM +0100, Karim BELABAS wrote:
> > 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
>
> This got broken though:
>
> ? rnfpolred(nfinit(quadpoly(1129,y)),quadray(1129,1))
>   ***   the PARI stack overflows !
>   current stack size: 64000000 (61.035 Mbytes)
>   [hint] you can increase GP stack with allocatemem()
>
> Didn't need more than a default stack before.

Did it ? The stable release yields

  ***   division by zero in gdiv, gdivgs or ginv

at default precision.

It's still a precision problem but at a higher level: the base nf is not
computed to a sufficient accuracy. The natural solution (which I've
implemented in CVS) is to increase that accuracy and go on.

Since the relative LLL algorithm (even implemented with exact computations)
doesn't really work, this produces worse results than immediately using the
right accuracy [ in regular LLL, going astray due to accuracy problems
is quickly corrected in the following iterations. Here, not at all ].

    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]