Igor Schein on Thu, 13 Mar 2003 14:53:32 -0500 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: rnflllgram() regression |
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