Karim BELABAS on Sat, 3 Aug 2002 16:42:52 +0200 (MEST) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: rnfkummer-induced bug |
On Fri, 26 Jul 2002, Igor Schein wrote: > ? setrand(1);rnfkummer(bnrinit(bnfinit(quadpoly(124,y)),11,1),Mat(5)) > *** impossible division in diviiexact. > > This is happening in 2.2.3 and latest CVS. I had decided to dump rnfkummer and wait for somebody to implement Claus Fieker's algorithm [ Xavier Roblot already volunteered for this]. But I changed my mind: for comparison/benching purposes, it will be useful to have a decent implementation of rnfkummer [which uses purely Hecke's theorem]. Also, I believe the complexity of all these algorithms should be dominated by the computation of bnfinit(polcompositum(nf, polcyclo(l))) So I implemented a few ideas I had some years ago, the most important of which was to do all computations formally [on formal products of "natural basis elements", mostly S-unit generators]. Since the final generator is defined modulo l-th powers, we are allowed to cancel arbitrary l-th powers and the elements obtained by reducing exponents mod l before the final 'factorback' are much, much smaller than they used to be. Another one was to extract further l-th powers from nf element x as follows: factor x = A^l R (as a product of prime ideals, this is easy since x has known support), such that valuation of R at any prime is less than l. Then LLL-reduce A --> we get 'a' of small height in A. Then replace x by x / a^l. [ LLL-reducing the logarithmic embedings of x modulo the logarithmic embedings of the u^l, for some S-unit generators u (for some small set S of finite places) was another idea, but it only marginally improves the situation at this point ] As a result rnfkummer should be a few orders of magnitude faster (esp. when the class group of the base field is large) AND give usable results, i.e relative equations that can actually be used. To double check the results, I added a "lazy reduction" flag to rnfpolredabs [analogous to the one already present in polredabs]. So rnfpolredabs(nf, x, 16) use lazy reduction, without factoring the discriminant. This is a huge and complicated patch [the resulting code is hopefully simpler though], there are certainly a few remaining bugs such as: On Fri, 2 Aug 2002, Igor Schein wrote: > in latest CVS > > ? setrand(1);bnr=bnrinit(bnfinit(y^4-y^3-2404*y^2+2404*y+1154401),5,1); > ? rnfkummer(bnr,matdiagonal([5,1])) > *** not an Abelian extension in rnfnormgroup. which Igor spotted before I could announce my changes ... and which I've fixed in the meantime. I ran preliminary regression tests without spotting further problems. Any feedback will be much appreciated. Karim. P.S: rnfkummer is still unable to handle extension of non-prime degree [this is a "feature" of the method], as well as extensions of degree larger than 5 [this is pure laziness]. -- Karim Belabas Tel: (+33) (0)1 69 15 57 48 Dép. de Mathematiques, Bat. 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/