Karim BELABAS on Fri, 15 Nov 2002 14:31:13 +0100 (MET) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: Bug rnfconductor |
On 1 Oct 2002, I wrote: > P.S: conductor() uses a highly inefficient algorithm, via > orderofquotient() , computing many full bnr for different moduli, and many > bnrisprincipal for each bnr, where the only question is whether all x = 1 > mod^* (f / v), (x, f) = 1 [ v a place in the support of the divisor f ] > belong to the congruence subgroup or not [ and if so, incrementally for f / > v^2, ... ]. > > This can be checked trivially in (O_K / f)^* for the original f, since > (O_K/f)^* / (O_K/(f/v))^* is cyclic with "obvious" generator. This was wrong. Not always cyclic (only if v archimedean, or v^2 does not divide f, or f has degree 1), but with obvious generators, yes. > Using the general formalism for exact sequence of abelian groups from > Cohen's (second) book is a real waste in this case. > > This code is copy-pasted in discrayrelall() and should be fixed here as > well. I'll do it one of these days -- once I'm done checking late bug > reports:-( I've implemented these changes in both conductor() and discrayrelall(). This affects [bnr|rnf]conductor(), bnrdisc(), and by extension most class field routines [ it's a major change: the unified diff has ~ 1500 lines ]. The change makes it possible to use bnrconductor() [provided flag <= 0] and bnrdisc() with a 'bnr' computed without generators: this was previously required, although undocumented (I've also fixed the documentation). ? bnr = bnrinit(pol, f); bnrconductor(bnr) *** please apply bnrinit(,,1) and not bnrinit(,). The conductor() routine is now about 20 times faster for trivial examples, and much more for complicated ones. Unfortunately, there are still bottlenecks related to the bnr generators¹. I shall try a second batch of patches in order to implement this second step, but it's an even more complicated change. Anything broken so far ? Igor ? Karim. ¹: or more exactly, to the use of bnr.gen: we could bypass them completely (define them only abstractly), and have lightning fast bnrisprincipal(bnr2, bnr.gen[i]). which is a basic operation in class field theoretic routines, without ever needing to compute the generators [which is now very cheap, contrary to what the doc implies]. But, more importantly, which have a completely inadequate format for the above operation (and in fact for any operation besides perhaps screen printing): they are naturally given in factored form, and fully expanded in bnrinit() [ or idealstar() ]; using the expansion requires costly transformations (basically recovering the factorization) _each time_ we use a bnr for whatever purpose... -- 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 Email: Karim.Belabas@math.u-psud.fr F-91405 Orsay (France) http://www.math.u-psud.fr/~belabas/ -- PARI/GP Home Page: http://www.parigp-home.de/