I - Groebner basis computation

Here are some theoretical data gathered from [1]:

An ideal V is the set of all polynomials g*f, g = any polynomial, f belonging to a family F of generator polynomials.

We consider the polynomials in the indeterminates x1,x2,...,xn. Let < be an ordering over the monomials that satisfies to the following conditions:
a) if a < b, then for every monomial c, we have ac < bc
b) for every monomials a and b with b!=1, we have a < ab

The lexicographical ordering satisfies to these conditions. It is defined as:

x1^a1*x2^a2*...*xn^an < x1^b1*x2^b2*...*xn^bn
aj = bj for j<i

The maximum monomial of a polynomial with respect to the ordering < is called its head monomial.

Let G be a set of polynomials. We say that a polynomial f is reduced against G if no head monomial of a polynomial of G divides the head monomial of f.

If f isn't reduced, we can subtract multiples of the elements of G from it. This process is called a reduction of f against G. It is finite, i.e. it ends up with a reduced polynomial.

A family of generators (a "basis") G of an ideal I is called a Groebner basis with respect to the ordering < if the reduction against G of every polynomial f of I always gives 0.

A system of polynomial equations has a finite number of solutions (it is "zero dimensional") if and only if every indeterminate appears alone in the head monomial of one polynomial of the corresponding Groebner basis with respect to any ordering satisfying to the conditions a) and b) above.

When the basis is computed with respect to an "elimination" ordering (for instance, lexicographical), this gives a method to compute every solution of the system by finding one indeterminate after the other. (This is one motivation for computing a Groebner basis).

To compute a Groebner basis, we can use Buchberger's algorithm:
We define the s-polynomial of two polynomials f and g as:

S(f,g)=(scm(hm(f),hm(g))/hm(f))*f - (scm(hm(f),hm(g))/hm(g))*g

where hm(f) (resp hm(g)) stands for the head monomial of f (resp g).

A basis G is a Groebner basis if and only if for every pair (f,g) of polynomials of G, the reduction of S(f,g) against G gives 0.

If some S(f,g) doesn't reduce to 0, we can add it to G (since it's a linear combination of polynomials of G, the ideal generated by G remains the same). S(f,g) then reduces to 0 against the new G. We can repeat this process for every S(f,g). Buchberger has proved that this process is finite, i.e. it ends up with a Groebner basis.

At each step, we must make the choice of a pair (f,g). This is where some optimization can take place. We can eliminate some possibilities using Buchberger's third criterion:

If there is an element h of G such that the head monomial of h divides the scm of the head monomials of two polynomials f and g, and if we already have considered S(f,h) and S(h,g), then we don't have to consider S(f,g) because it reduces to 0.

Even after applying this criterion, several possibilities may remain. According to Buchberger, the choice of a pair such that the scm of the head monomials is minimal in the current ordering is good. As an improvement, we chose the pair with the minimal "sugar" (see [3]).

II - Symbolic integration

The rational functions integration algorithm is taken from [4].

III - Number theory

There are good explanations in wikipedia which I used when implementing Euler's phi function and primitive roots.


[1] Davenport J., Siret Y., Tournier E., Calcul formel - systemes et algorithmes de manipulations algebriques, MASSON, 1993 ( http://staff.bath.ac.uk/masjhd/masternew.pdf )

[2] JC Faugere ( http://calfor.lip6.fr/~jcf/ )

[3] Alessandro Giovini, Teo Mora, Gianfranco Niesi, Lorenzo Robbiano and Carlo Traverso, "One sugar cube, please" or selection strategies in the Buchberger algorithm, Proceedings of the 1991 international symposium on Symbolic and algebraic computation July 15 - 17, 1991, Bonn West Germany

[4] Manuel Bronstein, Symbolic integration tutorial, ISSAC'98, Rostock, August 12, 1998 ( http://www-sop.inria.fr/cafe/Manuel.Bronstein/publications/issac98.ps.gz )

[5] Thom Mulders, A note on subresultants and a correction to the lazard/rioboo/trager formula in rational function integration, Journal of Symbolic Computation, 24(1):45-50, 1997

[6] F Mancini ( http://www.geocities.com/famancin/groebner_applet.html )

[7] Singular ( http://www.singular.uni-kl.de )

[8] David Hestenes, Oersted Medal Lecture 2002: Reforming the Mathematical Language of Physics ( http://modelingnts.la.asu.edu/pdf/OerstedMedalLecture.pdf )

[9] The Geobucket Data Structure for Polynomials, T Yan - JSC, 1998 ( http://historical.ncstrl.org/tr/ps/cornellcs/TR96-1607.ps )