Re: bnfinit perhaps getting stuck?

[Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr>]

* Phil Carmody [2008-05-14 22:16]:
> --- On Wed, 5/14/08, Bill Allombert <Bill.Allombert@math.u-bordeaux1.fr> wrote:
> > You are using the stable version. Due to several improvement (in
> > particular 2.4.0F4 and the new LLL code) I would suggest
> > you try the SVN version but actually, I should rather suggest you
> > to give up because I do not think this can finish.
> 
> I'm up for still hacking away at it if it's still needed [task requestor bcc:d]
> I don't have SVN, but can grab 
> Development version: pari-2.4.2.alpha.tar.gz,  2183 KBy, Dec 23 00:58:07 2007 
> from the website.

Rather a development snapshot:

  http://pari.math.u-bordeaux.fr/cgi-bin/viewcvs.cgi/trunk.tar.gz?root=pari&view=tar

(current svn differs significantly from 2.4.2)

> > Using \g1 is generally sufficient and keep the logs readable.
> > You can try
> > grep cglob <your log> 
> > or if this is too verbose
> > grep needed <your log>
> > to get a measure of progress.
> 
> Ah, that's very useful to know. It appears that I was making steady progress:
> """
> (more relations needed: 171)
> ++++ cglob = 2452: new relation (need 2622)
> ++++ cglob = 2453: new relation (need 2622)
> ...
> ++++ cglob = 2470: new relation (need 2622)
> ++++ cglob = 2471: new relation (need 2622)
> ^C
> """
> 
> Extrapolating how long I ran that most recent verbose run, and how long I ran the original, I would have expected to have found 171 relations. Is the hard and non-deterministic work all done after the requisite number of relations is found?

Unfortunately no, almost all the work is concentrated in this non-deterministic
search for relations [ unless the field is really "simple" ], and it's not 
that simple.

The (more relations needed: ...) is likely to appear many
more times [ each time we incorporate a batch of random relations ]. In short,
you need:

* decreasing xxx in (need xxx)  [ --> 0 ]
* decreasing yyy in (more relations needed: yyy) [ --> go on with xxx = yyy ]
* decreasing zzz in "check = ..."  [ when this is 1, we are done ]

Try out "trivial" fields like bnfinit(x^4 - 2) to get the hang of it.
Or bnfinit(x^17-17) for a more "realistic" example [ still a few seconds ]

Cheers,

    K.B.
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux.fr/~belabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]
`