Primary decomposition of zero-dimensional ideals

This page describes the Magma implementation of the algorithms described in [2]. Also included is an implementation of algorithm ZPDF in [1].

The implementation is available here: primarydecomposition.tgz.

To use the algorithm, after starting magma, type

> Attach("primarydecomposition.magma");

This provides three methods: radical (Algorithm 4.8 in [2]), primaryDecompositionInfinite (Algorithm 5.16 in [2]), and primaryDecomposition (Algorithm 6.5 in [2]).

To use the algorithm ZPDF, after starting magma, type

> Attach("primarydecomposition.magma");
> Attach("gtz.magma");

This provides the additional method primaryDecompositionGTZ (an implementation of Algorithm ZPDF in [1]).

All four methods take as argument a zero-dimensional ideal I with computed Gröbner basis. The method radical computes the radical of I, and the other methods compute the primary decomposition of I.

Example

> R< x, y > := PolynomialRing(Rationals(), 2, "grevlex");
> I := ideal< R | (x^2 + 1)^2, y^2 + 1 >;
> Groebner(I);
> radical(I);
Ideal of Polynomial ring of rank 2 over Rational Field
Order: Graded Reverse Lexicographical
Variables: x, y
Inhomogeneous, Dimension 0
Groebner basis:
[
    x^2 + 1,
    y^2 + 1
]
> primaryDecomposition(I);
[
    Ideal of Polynomial ring of rank 2 over Rational Field
    Order: Graded Reverse Lexicographical
    Variables: x, y
    Inhomogeneous, Dimension 0
    Groebner basis:
    [
        x^2 - 2*x*y - 1,
        y^2 + 1
    ],
    Ideal of Polynomial ring of rank 2 over Rational Field
    Order: Graded Reverse Lexicographical
    Variables: x, y
    Inhomogeneous, Dimension 0
    Groebner basis:
    [
        x^2 + 2*x*y - 1,
        y^2 + 1
    ]
]
> primaryDecompositionInfinite(I);
[
    Ideal of Polynomial ring of rank 2 over Rational Field
    Order: Graded Reverse Lexicographical
    Variables: x, y
    Inhomogeneous, Dimension 0
    Groebner basis:
    [
        x^2 + 2*x*y - 1,
        y^2 + 1
    ],
    Ideal of Polynomial ring of rank 2 over Rational Field
    Order: Graded Reverse Lexicographical
    Variables: x, y
    Inhomogeneous, Dimension 0
    Groebner basis:
    [
        x^2 - 2*x*y - 1,
        y^2 + 1
    ]
]
> primaryDecompositionGTZ(I);
[
    Ideal of Polynomial ring of rank 2 over Rational Field
    Order: Graded Reverse Lexicographical
    Variables: x, y
    Inhomogeneous, Dimension 0
    Groebner basis:
    [
        x^2 + 2*x*y - 1,
        y^2 + 1
    ],
    Ideal of Polynomial ring of rank 2 over Rational Field
    Order: Graded Reverse Lexicographical
    Variables: x, y
    Inhomogeneous, Dimension 0
    Groebner basis:
    [
        x^2 - 2*x*y - 1,
        y^2 + 1
    ]
]

Benchmarks

The paper includes benchmarks using nine examples. These examples are included in the package, contained in the files

finite1_ilias13.magma
finite2_Reimer_5a.magma
finite3_Steidel_1.magma
rationals1.magma
rationals2.magma
rationals3.magma
functionfield1.magma
functionfield2.magma
functionfield3.magma

After attaching the packages primarydecomposition.magma and gtz.magma as described above, the benchmarks can be run as follows.

> load "finite1_ilias13.magma";
Loading "finite1_ilias13.magma"
> time pd := primaryDecomposition(I);
Time: 2.160
> time pdgtz := primaryDecompositionGTZ(I);
Time: 3.400

Verbose printing

Use SetVerbose("PrimaryDecomposition", d) to set the verbose printing for the algorithms, where d is a value between 0 and 3.

References

[1]	P. Gianni, B. Trager, and G. Zacharias Gröbner bases and primary decomposition of polynomial ideals J. Symbolic Comput. 6 (1988), no. 2-3, 139-167.
[2]	S. Jambor Primary decomposition of zero-dimensional ideals over arbitrary fields Preprint (2014).