|
|
D.4.22 nfmodstd_lib
- Library:
- nfmodstd.lib
- Purpose:
- Groebner bases of ideals in polynomial rings
over algebraic number fields
- Authors:
- D.K. Boku boku@mathematik.uni-kl.de
W. Decker decker@mathematik.uni-kl.de
C. Fieker fieker@mathematik.uni-kl.de
- Overview:
- A library for computing the Groebner basis of an ideal in the polynomial
ring over an algebraic number field Q(t) using the modular methods, where t is
algebraic over the field of rational numbers Q. For the case Q(t) = Q, the
procedure is inspired by Arnold [1]. This idea is then extended to the case
t not in Q using factorization as follows:
Let f be the minimal polynomial of t.
For I, I' ideals in Q(t)[X], Q[X,t]/<f> respectively, we map I to I' via the
map sending t to t + <f>. We first choose a prime p such that f has at least
two factors in characteristic p and add each factor f_i to I' to obtain the
ideal J'_i = I' + <f_i>. We then compute a standard basis G'_i of J'_i for each
i and combine the G'_i to G_p (a standard basis of I'_p) using chinese remaindering
for polynomials. The procedure is repeated for many primes p, where we compute the
G_p in parallel until the number of primes is sufficiently large to recover the
correct standard basis G' of I'. Finally, by mapping G' back to Q(t)[X], a standard
basis G of I is obtained.
The procedure also works if the input is a module. For this, we consider the
rings A = Q(t)[X] and A' = (Q[t]/<f>)[X]. For submodules I, I' in A^m, A'^m,
respectively, we map I to I' via the map sending t to t + <f>. As above, we first
choose a prime p such that f has at least two factors in characteristic p. For each
factor f_{i,p} of f_p := (f mod p), we set I'_{i,p} := (I'_p mod f_{i,p}). We then
compute a standard basis G'_i of I'_{i,p} over F_p[t]/<f_{i,p}> for each i and
combine the G'_i to G_p (a standard basis of I'_p) using chinese remaindering for
polynomials. The procedure is repeated for many primes p as described above and we
finally obtain a standard basis of I.
- References:
- [1] E. A. Arnold: Modular algorithms for computing Groebner bases.
J. Symb. Comp. 35, 403-419 (2003).
Procedures:
|
