Karim BELABAS on Mon, 10 Jun 2002 00:03:13 +0200 (MEST) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
23- nf components |
On Sun, 9 Jun 2002, Karim BELABAS wrote: > 23- INCOMPATIBILITY: nf.zk is now T2-LLL-reduced > 29- INCOMPATIBILITY: the internal components of nf[5] have changed (MC and > T2 not needed anymore) An old entry in TODO (with maximal priority) read 5 don't assume that nf.zk is HNF. Allow using LLL-T2-reduced bases (with first element 1) --> huge improvement to all idealred computations (esp. bnfisprincipal, bnfinit) I've implemented just that. More precisely, in nfinit(), the integral basis computed by Round4 is LLL-reduced (with "LLL quality parameter" 99/100). The reduction does not depend on the current 'realprecision' (a conservative precision is worked out internally). The major gain is that an nf element which is small when expressed on our chosen basis nf.zk also has small embeddings, which makes basic operations like multiplication or ideal reduction much faster (both could be even faster, no time for that yet), also it drastically improves general numerical stability when making floating point computations (taking embeddings, etc). This also helped removing unnecessary requirements from the source code. Note: nfields bench is faster; from the cvs sources, on my machine (PIII 1GHz, Linux), I get pari-2.1.4: (stable) * Testing nfields for gp-sta..TIME=1720 for gp-dyn..TIME=1730 pari-2.2.3: (unstable) * Testing nfields for gp-sta..TIME=1040 for gp-dyn..TIME=1040 Tough examples should be even faster [ this is also due to the new modular algorithms, and to a lesser extent to the new floating point LLL ]. Major problems: 1) programs using explicit coordinates for nf elements or ideals (HNF or primedec form) have to be corrected. I've written routines to change between the two bases (HNF basis <---> fixed LLL-reduced base), currently called nftohnfbasis / nffromhnfbasis, but they're not directly available from GP (need to install()) and neither are they documented. Also they only work when given the actual LLL-reduced base, so they can't be used to automatically upgrade a script, they need to do some actual computations. The inputs to the bench suite had to be updated. 2) matrix components of nf (nf[5]) have changed, breaking compatibility: MC (nf[5][2]) has been replaced by a matrix G such that G~ * G = T2, T2 (nf[5][3] = nf.t2) has been removed (currently set to 0). The member function nf.t2 still gives the expected matrix (internally computes G~ * G), but I'd like to remove it since it's completely useless. 3) I'd like to modify further the nf structure, and I can't do that without breaking compatibility further. Possibly it's better to do it all at once. Possibly it's better to wait until t_TAG and missing member functions are implemented, and explicit access to nf components via vector coordinated ( nf[1] ) disappear. Current minor problems: 1) we may need to compute the roots and the embeddings to a higher accuracy than 'realprecision'. Currently, some of that information is lost when nfinit() returns since the matrix components of nf are truncated to the requested 'realprecision' (the roots themselves nf.roots, are still known to a higher accuracy). Can easily be changed. 2) the chosen integral basis nf.zk is no more canonical (the HNF representation on the power basis for the given polynomial nf.pol was not really canonical either, but a bit more so). 3) computing a nfinit() just to get the discriminant or maximal order is quite a bit slower than before. So use nfdisc() / nfbasis() for that, only use nfinit() when you actually intend to work with the field. Karim. -- 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/