The Magma facility for commutative rings allows the user to define any ring, starting from the ring of integers, by repeatedly applying the four basic constructions: transcendental extension, quotient by an ideal, localization, and completion. Rings derived from a polynomial ring will be considered in this section, while fields, their orders and valuation rings will be presented in the following section. The following rings and modules are considered here:
Multivariate polynomial rings
Ideal theory of multivariate polynomial rings
Affine algebras
Modules over affine algebras
Localization in an affine algebra
Boolean Polynomial Rings
The basic computational problems for commutative rings include:
A canonical form for elements
Efficient arithmetic
A canonical representation (i.e., standard basis) for ideals
Arithmetic with ideals
Formation of quotient rings
Localization at the origin
Ideal decomposition, i.e., primary decomposition
The study of modules over rings
The fundamental tools on which most machinery for computational (commutative) ring theory is based include factorization of elements in a UFD, the efficient construction of standard bases for ideals and the factorization of ideals.
Multivariate polynomial rings in any number of variables may be formed over any coefficient ring, including a polynomial ring. Multivariate polynomials are represented in distributive form, using ordered arrays of coefficient-monomial pairs. Different orderings are allowed on the monomials; these become significant in the construction of Gröbner bases of ideals. Computations with ideals are available (since V2.8) for ideals defined over general Euclidean rings as well as for ideals defined over fields.
Creation of a polynomial ring
Monomial orders: lexicographical, graded lexicographical, graded reverse lexicographical, block elimination, general weight vectors, etc.
Dynamic data structures for monomials providing optimal packing and rigorous detection of overflow
Base extend
Definition of a ring map
Kernel of a ring map
Properties of ring maps: Surjective, bijective
Since V2.7, the original linked-list representation of polynomials has been replaced with a more compact random-access array structure, resulting in less memory usage and faster access. A new fraction-free representation for polynomials at the lowest level gives very significant speedups for arithmetic over some fields (particularly the rational field and rational function fields). A new representation employing variable byte sizes for monomials is also introduced in V2.7, requiring less memory and providing greater speed. The maximum total degree of any monomial has been increased to 230 – 1 = 1073741823. Monomial overflow is rigorously detected.
Arithmetic with elements
Fast multiplication and divison using heap-based algorithms of Monagan and Pearce
Fast powering in characterstic p via Frobenius map
Recursive coefficient, monomial, term, and degree access
Differentiation, integration
Evaluation and interpolation
Properties: a unit, a zero-divisor, nilpotent
Greatest common divisor (sparse EEZ-GCD, fast GCD-HEU, evaluation-interpolation algorithms)
Newton polygon
Squarefree factorization
Bivariate factorization over GF(q), ℤ and ℚ (polynomial-time trace-based algorithm of Belabas et al., interpolation algorithms)
Multivariate factorization over GF(q), ℤ and ℚ (reducing to bivariate factorization to solve combination problem)
Factorization over arbitrary algebraic function fields (including inseparable field extensions)
Resultant (modular and sub-resultant algorithms), discriminant
Factorization of bivariate polynomials over all supported rings is accomplished by an algorithm which extends van Hoeij's knapsack ideas for Z[x] to solve the hard combination problem for GF(q)[x,y] [BHKS]. The new algorithm runs in polynomial time and performs extremely well in practice. General multivariate factorization is reduced to this new bivariate algorithm, so a combination problem never arises for any number of variables. Shoup's tree Hensel lifting algorithm has also been adapted for power series, making the lifting stages of all kinds of bivariate/multivariate factorization much faster than previously.
Factorization over general algebraic function fields of small characteristic is accomplished by an algorithm of Allan Steel [Insep]. This can handle extensions which are inseparable, and may have an arbitrary number of both algebraic and transcendental generators.
Resultants are computed using asymptotically-fast modular and evaluation/interpolation algorithms. Options are provided for Monte Carlo-style stopping on stability, which greatly speeds up the computation (since the bounds are usually very much worse than the required lifting level).
Construction of ideals and subrings
Gröbner bases of ideals over fields, with specialized algorithms for different coefficient fields (fraction-free methods for the rational field and rational function fields)
Gröbner bases of ideals over finite fields and rationals, using optimized Faugère F4 algorithm
Gröbner bases of ideals over general Euclidean rings, using an extension by Allan Steel of Faugère's F4 algorithm (includes integer ring ℤ, residue class rings ℤ/mℤ, K[x]/ < f(x) > [m,f arbitrary non-zero moduli] and Galois rings)
Gröbner Walk algorithm for converting the Gröbner basis of an ideal over a field from one monomial order to another order
Construction of ideals of boolean polynomial rings and Gröbner bases of such ideals
FGLM algorithm for converting the Gröbner basis of a zero-dimensional ideal over a field from one monomial order to a different order (a fast p-adic method is used in the case of the rational field)
Construction of degree-d (truncated) Gröbner bases
Construction of ideal via fixed basis (so as to determine coordinates of elements with respect to this basis)
Normal form of a polynomial with respect to an ideal
Reduction of ideal bases
S-polynomial of two polynomials
Since V2.11, an optimized implementation of Faugère's F4 algorithm (which uses sparse linear algebra) to compute Gröbner bases is available for ideals over finite fields and the rationals. See [SteelGB] for detailed timings.
The first HFE cryptosystem challenge of J. Patarin is solved by Magma 2.8 hours and 14GB on an 2.4GHz Intel Xeon64. This involves solving a system of 80 quadratic equations in 80 variables over GF(2) (each input polynomial has about 1600 terms). The challenge was first solved by J.-C. Faugère in 52 hours on an 1GHz Alpha in 2002 using his unpublished F5/2 algorithm (allowing for processor speed, Magma is about 3 times faster). At the time of writing, there is still no publically-available software besides Magma which can solve the challenge.
Sum, product, intersection, colon ideal,
Saturation of an ideal, leading monomial ideal
Elimination ideals
Determination of whether a polynomial is in an ideal or its radical
Properties of an ideal: Zero, principal, proper, zero-dimensional
Extension and contraction of ideals
Variable extension of ideals
Noether normalisation of ideals
Minimal bases for homogeneous ideals
Normalisation of the affine quotient algebra of an ideal
Maximal regular sequences in polynomial ideals
Rees ideal of an ideal in a polynomial ring or affine algebra
Milnor numbers and Tjurina numbers
Dimension and maximally independent sets
Hilbert series and Hilbert polynomial
Primary decomposition of an ideal
Triangular decomposition of a zero-dimensional ideal (algorithm of D. Lazard).
Probabilistic prime decomposition of the radical of an ideal
Equidimensional decomposition of an ideal
Radical of an ideal
Computation of the variety of a zero-dimensional ideal
Relation ideals (determination of algebraic relations between polynomials)
Syzygy modules
Construction of a minimal generating set of a polynomial subalgebra
Computations with polynomial generators of a submodule over a subalgebra in a polynomial ring
Primary decomposition of ideals over general algebraic function fields of small characteristic is handled by a new algorithm of Allan Steel [Insep].
Construction of graded polynomial rings with specific weights on the variables
Special efficient graded reverse lexicographical order with weights for optimal Gröbner basis of ideals in graded rings
All monomials of specific total or weighted degree
Homogeneous components of polynomials
Homogenization and dehomogenization of an ideal
Hilbert-driven Buchberger algorithm for fast computation of the Gröbner basis of a homogeneous ideal when the Hilbert series is known (using the F4 algorithm when possible)
Construction of degree-d (truncated) Gröbner bases (respecting the grading of the polynomial ring)
Boolean polynomial rings provide efficient Gröbner basis computations with ideals in polynomial rings over GF(2) for which one desires to solve the underlying system of equations over GF(2). The effect of computing with an ideal in such a ring is the automatic inclusion of the field polynomials xi2 + xi in the ideal. This saves time and memory because a compact bit vector representation is available for the monomials and conversion to and from this is not needed.
Construction of boolean polynomial rings with specific numbers of variables
Monomial orders: lexicographical, graded lexicographical, graded reverse lexicographical
Efficient construction of large polynomials in compact bit vector representation (via integers)
Gröbner bases using the bit vector representation
Varieties
Let K be a field, R = K[x1,…, xn] a polynomial ring over K and I an ideal of R. The quotient ring A = R/I is called an affine algebra.
Construction of ideals and subrings
Gröbner bases of ideals
Ideal arithmetic: addition, multiplication, powers, quotients, colon ideals, intersections
Membership test for ideals
Test equality and inclusion of ideals
Construction of Rees ideals
Affine algebras arise commonly in commutative algebra and algebraic geometry. They can also be viewed as generalizations of number fields and algebraic function fields.
If the ideal J of relations defining an affine algebra A = K[x1,…,xn]/J is maximal, then A is a field and may be used with any algorithms in Magma which work over fields. Factorization of polynomials over such affine algebras is also supported.
If an affine algebra has finite dimension considered as a vector space over the coefficient field, extra special operations are available on its elements.
Modules over a multivariate polynomial ring R[x1,…, xn] (R a Euclidean ring or field) and quotient rings of such (affine algebras) Magma has a special category for modules over three kinds of commutative multivariate rings:
Multivariate polynomial rings.
Localizations of Multivariate polynomial rings.
Affine Algebras.
Such rings are not principal ideal rings in general, so the standard matrix echelonization algorithms are not applicable. Magma allows computations in modules over such rings by adding a column field to each monomial of a polynomial and then by using the ideal machinery based on Gröbner bases.
Construction of modules with various module orders
Construction of graded modules with weights on the columns
Flexible choice of monomial orders (top-over-position, position-over-top, Schreyer order)
Arithmetic with elements
Construction of Gröbner bases of modules
Row and column operations on elements
Tensor products
Construction of submodules and quotient modules
Membership testing
Tensor product
Hilbert series of (homogeneous) modules
Multiplicity
Submodule sum, intersection, colon operation
Minimal bases for homogeneous modules
Multiplicity of a submodule
Syzygy modules
Construction of the image and kernel of a homomorphism
Hom(M,N), where M and N are modules
Free resolutions, minimal free resolutions (Hybrid La Scala/F4 algorithm, iterative syzygy algorithm)
Betti numbers, homological dimension
Fitting ideals
Homology of a complex
Ext and Tor of a complex
Dimension of cohomology groups of Serre twists of graded modules (Decker-Eisenbud-Floystad-Schreyer algorithm)
Fundamental to Homology computations is a fast algorithm for computing free resolutions. Magma contains a hybrid of the algorithm of La Scala and the Faugere F4 Gröbner basis algorithm. This hybrid algorithm is able to compute resolutions of many modules in much faster time than for previous methods.
Magma contains a substantial package for computing with invariant rings and fields of finite groups and algebraic groups, which been developed by Gregor Kemper and Allan Steel [KemSte98].
For finite groups, Magma supports computation in invariant rings over ground fields of arbitrary characteristic. Of particular interest is the modular case, i.e., the case where the characteristic of the ground field divides the order of the group. Magma includes an algorithm for computing primary invariants that guarantees that the degrees of the invariants constructed are optimal (with respect to their product and their sum) [Kemper99].
Beginning with V2.14, Magma also provides algorithms for finding invariants of linear algebraic groups. In particular, Derksen's algorithm [Derksen99] and the algorithm by Beth and Müller-Quade [MQB99] are included.
Permutation and matrix group actions on polynomials
Independent homogeneous invariants of a specific degree
Molien series
Primary invariants having optimal degrees (with respect to their product and then sum)
Secondary invariants of optimal degrees (using a new algorithm for the modular case)
For the 4-dimensional representation of A5 over F2, optimal primary invariants (of degrees 3, 5, 8 and 12) are found in 1.5 seconds. For the cyclic matrix group of order 8 generated by the 5-dimensional Jordan form over F2, optimal primary invariants (of degrees 1, 2, 2, 4 and 8) are found in 0.6 seconds and secondary invariants with respect to these (of degrees 0, 3, 3, 3, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 7, 8, 8, 9, 9, 10 and 11) are found 14.4 seconds. This last computation took many hours with algorithms prior to those implemented in Magma V2.2.
Efficient construction of fundamental invariants (direct and King algorithms)
Invariant ring as a graded module over the algebra generated by the primary invariants and explicit construction of the isomorphism
Invariant ring as a polynomial algebra
Determination of algebraic relations between secondary invariants
Module syzygies between secondary invariants
Algebraic relations between invariants
The algorithm of King for computing fundamental invariants is in general an order of magnitude faster than the previous direct method (which combined primaries and secondaries and reduces them to a minimal set). Using the King algorithm, fundamental invariants can be computed (each modulo a prime coprime with the group order) for all transitive groups of degree 7 in about 1 second total, and for all transitive groups of degree 8 in about 2 minutes total.
Hilbert series
Free resolution
Depth and homological dimension
Attribute control of invariant ring information
Determine whether an invariant ring is a polynomial ring or a Cohen-Macaulay ring
A linear algebraic group is an affine variety G together with morphisms giving G the structure of a group and is defined in Magma by simply giving polynomials defining G as an affine variety and a suitable G-module. The main tool with computing with invariants of linear algebraic groups is Derksen's algorithm, which successively computes homogeneous invariants of increaseing degree, and reduces these to a minimal set via syzygy computations in modules over the underlying polynomial ring.
Invariant ring of an algebraic group defined by multivariate polynomials describing an affine variety
Construction of binary forms
Computation of invariants of given degree
Computation of fundamental invariants (Derksen algorithm)
If G is a group acting on a polynomial ring K[x1,…,xn], it also acts on the rational function field K(x1,…,xn) by homomorphic extension. The invariants field K(x1,…,xn)G is the field consisting of all functions which are fixed by G. Magma allows the construction of the invariant field and elementary computations within it.
Construction of invariant fields of finite groups or algebraic groups
Computation of fundamental invariants (Müller-Quade/Beth algorithm)