Function: bnfinit
Section: number_fields
C-Name: bnfinit0
Prototype: GD0,L,DGp
Help: bnfinit(P,{flag=0},{tech=[]}): compute the necessary data for future
 use in ideal and unit group computations, including fundamental units if
 they are not too large. flag and tech are both optional. flag can be any of
 0: default, 1: include all data in algebraic form (compact units).
 See manual for details about tech.
Description:
 (gen):bnf:prec           Buchall($1, 0, $prec)
 (gen, 0):bnf:prec        Buchall($1, 0, $prec)
 (gen, 1):bnf:prec        Buchall($1, nf_FORCE, $prec)
 (gen, ?small, ?gen):bnf:prec        bnfinit0($1, $2, $3, $prec)
Doc: initializes a \kbd{bnf} structure used in programs such as
 \kbd{bnfisprincipal}, \kbd{bnfisunit}. The result is
 conditional on the GRH, hence any output from functions requiring a
 \var{bnf} may be wrong. The output \var{bnf} may be certified using
 \kbd{bnfcertify}, thereby certifying all later uses of the resulting
 \var{bnf}. Unconditionally, the only guarantee is that the computed units
 generate a subgroup of finite index in the full unit group.

 This implements \idx{Buchmann}'s sub-exponential algorithm for computing the
 class group, the regulator and a system of \idx{fundamental units} of the
 general algebraic number field $K$ defined by the monic irreducible
 polynomial $P$ with integer coefficients.

 The meaning of $\fl$ is as follows:

 \item $\fl = 0$ (default). This is the historical behavior, kept for
 compatibility reasons and speed. It has severe drawbacks but is likely to be
 a little faster than the alternative, twice faster say, so only use it if
 speed is paramount, you obtain a useful speed gain for the fields
 under consideration, and you are only interested in the field invariants
 such as the classgroup structure or its regulator. The computations involve
 exact algebraic numbers which are replaced by floating point embeddings for
 the sake of speed. If the precision is insufficient, \kbd{gp} may not be able
 to compute fundamental units, nor to solve some discrete logarithm problems.
 It \emph{may} be possible to increase the precision of the \kbd{bnf}
 structure using \kbd{nfnewprec} but this may fail, in particular when
 fundamental units are large. In short, the resulting \kbd{bnf}
 structure is correct and contains useful information but later
 function calls to \kbd{bnfisprincpal} or \kbd{bnrclassfield} may fail.

 When $\fl=1$, we keep an exact algebraic version of all floating point data
 and this allows to guarantee that functions using the structure will always
 succeed, as well as to compute the fundamental units exactly. The units are
 computed in compact form, as a product of small $S$-units, possibly with
 huge exponents. This flag also allows \kbd{bnfisprincipal} to compute
 generators of principal ideals in factored form as well. Be warned that
 expanding such products explicitly can take a very long time, but they can
 easily be mapped to floating point or $\ell$-adic embeddings of bounded
 accuracy, or to $K^{*}/(K^{*})^{\ell}$, and this is enough for applications. In
 short, this flag should be used by default, unless you have a very good
 reason for it, for instance building massive tables of class numbers, and
 you do not care about units or the effect large units would have on your
 computation.

 \misctitle{The \var{tech} argument (technical)}

 This argument is better left omitted unless default tuning turns out to be
 inadequate and it looks like the algorithm made little progress over
 a few hours (or days). This can be diagnosed interactively using
 \kbd{setdebug(bnf,1)} or higher debugging levels. Careful use of this
 parameter may then speed up your computations. Assuming GRH, the correction
 of \kbd{bnfinit} output does not depend on the chosen parameters.

 Its format is
 $$[c_{1}, c_{2}, \var{nrpid}, \var{max\_fact}, \var{idex}, \var{usethr}],$$
 You do not need to supply all values. However,
 should you choose to modify a subset, they \emph{must} be given in the
 given order, where a $0$ encodes ``the default value''. For example,
 to specify $\var{nrpid} = 20$ without affecting $c_{1}$ and $c_{2}$, you can
 provide $[0,0,20]$. Their meaning is as follows

 \item $0 \leq c_{1} \leq c_{2}$ are real numbers. For $i =
 1,2$, let $B_{i} = c_{i}(\log |d_{K}|)^{2}$, and denote by $S(B)$ the set of
 maximal ideals of $K$ whose norm is less than $B$. We want $S(B_{1})$ to
 generate $\Cl(K)$ and hope that $S(B_{2})$ can be \emph{proven} to generate
 $\Cl(K)$.

 More precisely, $S(B_{1})$ is a factorbase used to compute a tentative
 $\Cl(K)$ by generators and relations. We then check, using essentially
 \kbd{bnfisprincipal}, that the elements of $S(B_{2})$ belong to the
 span of $S(B_{1})$. Under the assumption that $S(B_{2})$ generates $\Cl(K)$,
 we are done.

 When $c_{1}$ is unspecified (equal to $0$) the algorithm takes it equal to
 $c_{2}$. User-supplied $c_{i}$ are only used to compute initial guesses for
 the bounds $B_{i}$, and the algorithm increases them until one can
 \emph{prove} under GRH that $S(B_{2})$ generates $\Cl(K)$. A uniform result
 of Greni\'e and Molteni says
 that $c_{2} = 4$ is always suitable, but this bound is pessimistic and a
 direct algorithm due to Belabas-Diaz-Friedman, improved by Greni\'e and
 Molteni, is used to check the condition, assuming GRH.

 If the algorithm does not find enough relations, you may
 want to increase $c_{1}$ and $c_{2}$ to be larger than the so-called
 \emph{Bach constant} displayed by \kbd{setdebug("bnf",1)}, at the cost of
 increased memory usage and linear algebra time. It is quite possible to
 take $c_{2} > 4$ but using an unconditional bound and dividing it by
 $(\log |d_{K}|)^2$ is not a great idea: the complexity becomes exponential
 while the result remains conditional (we only know for sure that the true
 class group is a quotient of the computed one).

 \item $\var{nrpid}$ is the maximal number of small norm relations attached
 to each ideal in the factor base. Set it to $-1$ to disable the search for
 small norm relations. Reasonable values are between 4 and 20. The default is
 4 (which is also used if \var{nrpid} is zero). Increasing this value has
 seldom much effect, but setting it to $-1$ can have a large positive or
 negative effect on the running time.

 \item $\var{max\_fact}$ is the maximal number of trial factorizations to
 perform per ideal. There is an inherent trade-off between testing more
 ideals or testing more elements per ideals. The default is 500 (which is also
 used if \var{max\_fact} is zero).  If the algorithm does not find enough
 small norm relations, increase this value. Reasonable values are between 100
 and 10000. When using parallelism (see below) it can be reasonable to
 increase it up to about $10^{6}$.

 \item $\var{idex}$ is the power of the ideal to use. Reasonable values are
 between 1 and 12. The default is 0, which lets the algorithm picks a small
 power of the ideal depending on its norm.

 \item $\var{usethr}$ decides whether to use parallelism when searching for
 relations. The possible values are 0: no parallelism (default), 1: use
 \kbd{default(nbthreads)} threads, and $n > 1$: use $n$ threads. Parallelism
 requires to omit early-abort strategies when looking for relations which
 slows down the algorithm in easy cases. This setting does not affect the
 linear algebra part of the algorithm (which may use parallelism on its own).

 A good strategy is to first try to change $\var{idex}$,
 then increase $\var{max\_fact}$. If this is not sufficient, try to
 increase $c_{1}$ and $c_{2}$. If this causes the search to be too slow, try
 parallelism.

 \smallskip

 The components of a \var{bnf} are technical.
 In fact: \emph{never access a component directly, always use
 a proper member function.} However, for the sake of completeness and internal
 documentation, their description is as follows. We use the notations
 explained in the book by H. Cohen, \emph{A Course in Computational Algebraic
 Number Theory}, Graduate Texts in Maths \key{138}, Springer-Verlag, 1993,
 Section 6.5, and subsection 6.5.5 in particular.

 $\var{bnf}[1]$ contains the matrix $W$, i.e.~the matrix in Hermite normal
 form giving relations for the class group on prime ideal generators
 $(\goth{p}_{i})_{1\le i\le r}$.

 $\var{bnf}[2]$ contains the matrix $B$, i.e.~the matrix containing the
 expressions of the prime ideal factorbase in terms of the $\goth{p}_{i}$.
 It is an $r\times c$ matrix.

 $\var{bnf}[3]$ contains the complex logarithmic embeddings of the system of
 fundamental units which has been found. It is an
 $(r_{1}+r_{2})\times(r_{1}+r_{2}-1)$ matrix.

 $\var{bnf}[4]$ contains the matrix $M''_{C}$ of Archimedean components of the
 relations of the matrix $(W|B)$.

 $\var{bnf}[5]$ contains the prime factor base, i.e.~the list of prime
 ideals used in finding the relations.

 $\var{bnf}[6]$ contains a dummy $0$.

 $\var{bnf}[7]$ or \kbd{\var{bnf}.nf} is equal to the number field data
 $\var{nf}$ as would be given by \kbd{nfinit}.

 $\var{bnf}[8]$ is a vector containing the classgroup \kbd{\var{bnf}.clgp}
 as a finite abelian group, the regulator \kbd{\var{bnf}.reg},
 the number of roots of unity and a generator \kbd{\var{bnf}.tu}, the
 fundamental units \emph{in expanded form} \kbd{\var{bnf}.fu}. If the
 fundamental units were omitted in the \var{bnf}, \kbd{\var{bnf}.fu} returns
 the sentinel value $0$. If $\fl = 1$, this vector contain also algebraic
 data corresponding to the fundamental units and to the discrete logarithm
 problem (see \kbd{bnfisprincipal}). In particular, if $\fl = 1$ we may
 \emph{only} know the units in factored form: the first call to
 \kbd{\var{bnf}.fu} expands them, which may be very costly, then caches the
 result.

 $\var{bnf}[9]$ is a vector used in \tet{bnfisprincipal} only
 and obtained as follows. Let $D = U W V$ obtained by applying the
 \idx{Smith normal form} algorithm to the matrix $W$ (= $\var{bnf}[1]$) and
 let $U_{r}$ be the reduction of $U$ modulo $D$. The first elements of the
 factorbase are given (in terms of \kbd{bnf.gen}) by the columns of $U_{r}$,
 with Archimedean component $g_{a}$; let also $GD_{a}$ be the Archimedean
 components of the generators of the (principal) ideals defined by the
 \kbd{bnf.gen[i]\pow bnf.cyc[i]}. Then $\var{bnf}[9]=[U_{r}, g_{a}, GD_{a}]$,
 followed by technical exact components which allow to recompute $g_{a}$ and
 $GD_{a}$ to higher accuracy.

 $\var{bnf}[10]$ is by default unused and set equal to 0. This field is used
 to store further information about the field as it becomes available, which
 is rarely needed, hence would be too expensive to compute during the initial
 \kbd{bnfinit} call. For instance, the generators of the principal ideals
 \kbd{bnf.gen[i]\pow bnf.cyc[i]} (during a call to \tet{bnrisprincipal}), or
 those corresponding to the relations in $W$ and $B$ (when the \kbd{bnf}
 internal precision needs to be increased).
Variant:
 Also available is \fun{GEN}{Buchall}{GEN P, long flag, long prec},
 corresponding to \kbd{tech = NULL}, where
 $\fl$ is either $0$ (default) or \tet{nf_FORCE} (include all data in
 algebraic form). The function
 \fun{GEN}{Buchall_param}{GEN P, double c1, double c2, long nrpid, long flag, long prec} gives direct access to the technical parameters.

Function: _bnfinit_FP_worker
C-Name: bnfinit_FP_worker
Prototype: GGGLGLLU
Section: programming/internals
Help: worker for bnfinit
