Ideal Theory and Gröbner Bases, Affine Algebras [HB 49, 50]

Magma now contains the most powerful algorithms available for computing Gröbner bases. Further, in Magma GB computation is available for polynomial rings over all exact fields, for polynomial rings over euclidean rings, for finitely presented associative algebras and for finitely presented Lie algebras.

V2.11 includes a new highly optimized implementation of the Faugère F4 algorithm for computing Gröbner bases (GBs) over fields. The algorithm uses sparse linear algebra and has specialized vector representations for all types of finite fields, and an asympotically-fast modular algorithm for the rationals. Special techniques are also used for solving systems over GF(2).

As an example, the Cyclic-7 grevlex GB is computed in 2.2 seconds on an Athlon 2800+ XP PC. We have also computed the Cyclic-9 grevlex GB over the rationals in 7.5 days on a 750MHz Sunfire v880 (one sequential processor, 11GB memory used). As far as we are aware, no-one else has successfully computed this Gröbner basis except for J.-C. Faugère (in 18 sequential days on 4 processors). More timings can be found on the webpage http://magma.maths.usyd.edu.au/users/allan/gb/.

Removals and Changes:

• The function Ideal for multivariate polynomials has been renamed to IdealWithFixedBasis to remove confusion (used when specifying a sequence of polynomials with respect to which the Coordinates function will return its answer).

New Features:

• New Faugère F4 algorithm over fields and new parameters for the Groebner procedure.

• Intrinsics EquidimensionalDecomposition and FineEquidimensionalDecomposition have been added for ideals with no embedded primary components. These are generally faster than primary or radical decompositions.

• Intrinsic NoetherNormalization added to give a linear Noether normalization of the quotient algebra of an ideal.

• Intrinsic Normalization added to give the integral closure of the quotient algebra of an ideal in its total ring of fractions. For ideals in rank 2 polynomial rings, Magma's function field machinery is used. For higher rank rings, a general algorithm of de Jong is used. The base field of the polynomial ring must be perfect.