A finitely-presented algebra (FPA) is a quotient of a free associative K<x1,…,xn> algebra by an ideal of relations, where K is a field. To compute with such ideals and quotients, one constructs noncommutative Gröbner bases (GBs), which have many parallels with the standard commutative GBs. At the heart of the theory is a noncommutative version of the Buchberger algorithm which computes a GB of an ideal of an algebra starting from an arbitrary generating set of the ideal. One significant difference with the commutative case is that a noncommutative GB may not be finite for a finitely-generated ideal, but in such cases it may still be useful to construct a truncated GB up to a certain degree d.
Magma contains a powerful suite of algorithms for computing with noncommutative GBs and FPAs. Ideals can be defined to be left-, right-, or two-sided and a GB can be computed for each type of ideal. Besides the standard Buchberger algorithm, Magma includes a noncommutative generalisation by A. Steel (2005) of the Faugere F4 algorithm for GBs, which is based on sparse linear algebra techniques. As for the commutative case, this uses optimal packed representations for small finite fields and modular algorithms for fields of characteristic zero and so this algorithm typically runs dramatically faster than the Buchberger algorithm.
For example, here are some standard benchmarks taken from a paper [V. Levandovskyy, G. Studzinski, B. Schnitzler, Enhanced computations of Groebner bases in free algebras as a new application of the letterplace paradigm, Proc. ISSAC 2013] in which the authors compare their algorithm to compute noncommutative GBs in Singular with Magma. Let F be the free algebra ℚ<x,y,z> and let I be the two-sided ideal generated by the following braid relations:
As another example, let F be the free algebra ℚ<f1,f2,f3,f4> and let I be the two-sided ideal generated by the following Serre relations (related to Cartan matrices of Lie algebras):
For ideals of free algebras and their quotients, Magma supports analogues of all the basic operations for the commutative case when applicable. Let A be the FPA K<x1,…,xn> / I, where I may be a left-, right-, or two-sided ideal. If the GB of I is finite and has been computed, then it is easy to determine whether A has finite dimension or not. If the dimension d is finite, then Magma can easily compute d and a representation of A as a matrix algebra or a structure constant algebra, together with the isomorphism, assuming d is not too large (since this involves constructing d×d matrices over K). Using this matrix representation, one can also compute properties of elements of A such as minimal polynomial and also structural properties of A such as the centre or Jacobson radical, with the results involving elements of A explicitly (i.e., as words in the free generators, reduced modulo I). The advantage of the FPA representation of an algebra is that is often sparse: one can construct algebras with dimensions in the tens of thousands or more which have compact presentations as FPAs but would require matrices which are too large in practice with the matrix or structure constant algebra types.
Magma also has special support for exterior algebras. Such an algebra is skew-commutative and is a quotient of the free algebra K<x1,…, xn> by the relations xi2 = 0 and xi xj = -xj xi for 1 ≤ i,j ≤ n, i ≠ j. Because of these relations, elements of the algebra can be written in terms of commutative monomials in the variables (via a collection algorithm), and the associated algorithms are much more efficient than for the general noncommutative case. Also, a Gröbner basis of an ideal of an exterior algebra is always finite and another special extension of the Faugere F4 algorithm enables Magma to compute this GB of an ideal very rapidly. One can also construct modules over exterior algebras and construct free resolutions and perform operations similar to those for modules over commutative polynomial rings. As an example of an application in algebraic geometry, free resolutions over exterior algebras are heavily used in the Decker–Eisenbud–Fløystad–Schreyer algorithm to compute the cohomology of coherent sheaves.