23- nf components

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

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/