Re: rnflllgram() regression

[Igor Schein <igor@txc.com>]

On Thu, Mar 13, 2003 at 06:22:31PM +0100, Karim BELABAS wrote:
> 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.

Of course.  I was comparing with 2.2.5.

> 
> 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 ].

I guess by worse results you mean the following:

? rnfpolred(nfinit(quadpoly(1297,y)),quadray(1297,1));
  ***   the PARI stack overflows !
  current stack size: 512000000 (488.281 Mbytes)
  [hint] you can increase GP stack with allocatemem()

If I set \p163 though, it works fine at default stack.  

Precision increase is a tricky subject.  I tend to think it's good to
do it automatically only when there's no penalty.  In this case 500MB+
stack is a huge penalty, so I think it's better to gracefully detect
insufficient precision and let the user increase it, e.g.:

\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
                    GP/PARI CALCULATOR Version 2.2.5 (alpha)
                i686 running linux (ix86 kernel) 32-bit version
                (readline v4.3 enabled, extended help available)
? rnfpolred(nfinit(quadpoly(1297,y)),quadray(1297,1));
  ***   precision too low in mpent (precision loss in trucation).
? \p163
   realprecision = 163 significant digits
? rnfpolred(nfinit(quadpoly(1297,y)),quadray(1297,1));
time = 20,120 ms.
\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

BTW, at \p163 current CVS is 30% faster than 2.2.5 when running this
command, so it's a significant performance improvement.

Thanks

Igor