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
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
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
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
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
Since V2.11, factorization of bivariate polynomials over all supported rings is accomplished by a new algorithm which extends van Hoeij's knapsack ideas for Z[x] to solve the hard combination problem for GF(q)[x,y]. 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 a new 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
Gröbner Walk algorithm for converting the Gröbner basis of an ideal over a field from one monomial order to another order
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
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.
On a Athlon 2800+ XP machine, Magma computes the lex order Gröbner basis for the Katsura-5 problem in 0.3 seconds and the lex order Gröbner basis for the cyclic 6-th roots problem in 0.07 seconds. Taking a more difficult example, Magma computes the grevlex order Gröbner basis for the Cyclic-7 roots ideal in 2.2 seconds and transforms this to the lex order Gröbner basis in a further 23 seconds (using the p-adic FGLM algorithm). These examples are from the POSSO polynomial systems library (ftp posso.dm.unipi.it).
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
Normalisation of the affine quotient algebra of an ideal
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
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
Construction of degree-d (truncated) Gröbner bases (respecting the grading of the polynomial ring)
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.
Creation of an affine algebra
Arithmetic with elements
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
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) form a special category in Magma. Multivariate polynomial 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. This method is much more efficient than introducing new variables to represent the columns since the number of columns does not affect the total number of variables.
Construction of modules with TOP ("term over position") or POT ("position over term") module orders
Construction of graded modules with weights on the columns (determining homogeneity)
Arithmetic with elements
Construction of Gröbner bases of modules
Row and column operations on elements