Re: Running time of bnfinit()

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

* Jeroen Demeyer [2018-07-26 09:38]:
> do you happen to have a rule-of-thumb to estimate the running time of a
> bnfinit() call, say in terms of the degree and discriminant?

Not really. An average estimate, possibly, but with *huge* deviations...
Basically, [assuming GRH] 
(not the defining polynomial!), a discriminant < 10^40 should be fine
[between a few seconds and a few minutes] but there will be bad exceptions.
Compare the following "random" fields with roughly the same discriminants,
around 10^40-ish:
- bnfinit(polcyclo(31)) : trivial (0.1 s, although degree 30!),
- bnfinit(x^2 - nextprime(10^40)) : "easy" (3 minutes)
- bnfinit(x^2 - nextprime(10^44)) : "tougher" (40 minutes)

Conversely a few fields of degree ~100 have been "easily" computed in
about 10-20 hours, but don't expect to succeed every time...

> For Sage, we want to have a heuristic of when it's "easy" to compute
> bnfinit().

I don't know how to guarantee that it'll be easy. In any case, you
should never compute a bnfinit when it's not absolutely necessary.
[ I.e. you should do it on the fly when the extra structure is a
prerequisite for a specific function call. ]

Cheers,

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