Next: 2. Normalisation Up: 4. Some global algorithms Previous: 4. Some global algorithms   Contents

## 1. primary decomposition

Any ideal in a Noetherian ring can be written as with primary ideals (that is, and implies or for some ).

This generalises the unique factorisation (valid in factorial rings) with irreducible, from elements to ideals. In we have both, unique factorisation and primary decomposition and any algorithm for primary decomposition needs factorisation (because a primary decomposition of a principal ideal is equivalent to a factorisation of ).

In contrast to factorisation, primary decomposition is, in general, not unique, even if we consider minimal decompositions, that is, the associated primes are all distinct and none of the can be omitted in the intersection. However, the minimal (or isolated) primes, that is, the minimal elements of Ass with regard to inclusion, are uniquely determined. The minimal primes are the only geometrically visible'' primes in the sense that

is the decomposition of into irreducible components. A non-minimal associated prime    minAss is called embedded, because there exists a    minAss. This means geometrically , that is, the irreducible component of corresponding to is embedded in some bigger irreducible component.

As an example we compute the primary decomposition of the ideal in SINGULAR, the output being slightly changed in order to save space.


LIB "primdec.lib";              //calling library for primary decomposition
ring R  = 0,(x,y,z),dp;
ideal I = x2y3-x3yz,y2z-xz2;
primdecGTZ(I);
==> [1]: [1]:               [2]: [1]:               [3]: [1]:
_[1]=-y2+xz              _[1]=z2                 _[1]=z
[2]:                       _[2]=y                  _[2]=x2
_[1]=-y2+xz           [2]:                    [2]:
_[1]=z                  _[1]=z
_[2]=y                  _[2]=x

The result is a list of three pairs of ideals (for each pair, the first ideal is the primary component, the second ideal the corresponding prime component). The second prime component [2] : [2] is embedded in the first [1] : [2]. The first primary component [1] : [1] is already prime, the other two are not.

Hence, and we obtain:

All known algorithms for primary decompositions in are quite involved and use many different sub-algorithms from various parts of computer algebra, in particular Gröbner bases, resp. characteristic sets, and multivariate polynomial factorisation over some (algebraic or transcendental) extension of the field . For an efficient implementation which can treat examples of interest in algebraic geometry, a lot of extra small additional algorithms have to be used. In particular one should use easy'' splitting as soon and as often as possible, see DGP.

In SINGULAR the algorithms of GTZ (which was the first practical and general primary decomposition algorithm), the recent algorithm of SY and some of the homological algebra algorithms for primary decomposition of EHV have been implemented. For detailed and improved versions of these algorithms, together with extensive comparisons, see DGP.

Here are some major ingredients for primary decomposition:

1. Reduction to zero-dimensional primary decomposition (GTZ);

maximal independent sets;
ideal quotient, saturation, intersection.

2. Zero-dimensional primary decomposition (GTZ);

lexicographical Gröbner basis;
factorisation of multivariate polynomials;
generic change of variables;
primitive element computation.

Related algorithms:

square-free part of univariate polynomials;
find (random) regular sequences (EHV).

2. Computation of the equidimensional part (EHV);

Ext-annihilators;
ideal quotients, saturation and intersection.

To see how homological algebra comes into play, let us compute the equidimensional part of , that is, the union of all maximal dimensional components of , or, algebraically, the intersection of all minimal primes. Following EHV, we can calculate the equidimensional part of a variety via Ext-groups:

If    codim, then the equidimensional part of is the annihilator ideal of the module Ext by EHV.

For example, the equidimensional part of is given by the ideal    annExt.

Using SINGULAR, we obtain this via:


LIB "homolog.lib";
ring  r  = 0,(x,y,z),dp;
ideal I  = xz, yz;
module M = Ext_R(1,I);
quotient(M,freemodule(nrows(M)));
==> _[1] =z


Note that module M = Ext_R(i,I) computes a presentation matrix of Ext. Hence, identifying a matrix with its column space in the free module of rank equal to the number of rows, Ext with freemodule(nrows(M)) and, therefore, AnnExt quotient(M,freemodule(nrows(M))).

Above, we used the procedure Ext_R(-,-) from homolog.lib. Below we show that the Ext groups can easily be computed directly in a system which offers free resolutions, respectively syzygies, transposition of matrices and presentations of sub-quotients of a free module (modulo in SINGULAR). Indeed, the Ext-annihilator can be computed more directly (and faster) without computing the Ext group itself:

Take a free resolution of :

Then consider the dual sequence:

Hom   Hom

Ext   KerIm    and    AnnExt   Im   Ker.

The corresponding SINGULAR commands are:


int i = 1;
resolution L = res(I,i+1);
module Im    = transpose(L[i]);
module Ker   = syz(transpose(L[i+1]));
module ext   = modulo(Ker,Im);           //the Ext group
ideal ann    = quotient(Im,Ker);         //the Ext-annihilator


Since the resolution can be computed by iterated syzygy computation, this is a beautiful example of geometric use of syzygies. However, the algorithm is not at all obvious, but based on the non-trivial theorem of Eisenbud, Huneke and Vasconcelos.

Next: 2. Normalisation Up: 4. Some global algorithms Previous: 4. Some global algorithms   Contents
| ZCA Home | Reports |