\sffamily \Large Online Gr\"obner Basis [OGB]

Online Gröbner Basis [OGB]


Michael Mc Gettrick

Department of Information Technology, The National University of Ireland, Galway, Ireland
michael.mcgettrick@nuigalway.ie

Software name:
OGB [Online Gröbner Basis]
Short description:
OGB calculates a (reduced, minimal) Gröbner Basis over the Rationals. Latest version (which we hope to demonstrate) allows maple syntax and calculates using any admissible term ordering following the classification of Robbiano[1]. The technologies (software) used are GMP[2], PHP1 and HTML. Features include
  • Sparse representation of polynomials

  • Implementation of Buchberger's criteria[3] to speed up calculation

  • Gröbner Bases are calculated over Q (the rationals) using arbitrary precision arithmetic (GMP[2] library)

  • Software is run remotely from a web page on the server machine[4], and so uses none (or little) of the client's CPU and requires no installation!

  • As far as we are aware, this is the only free software for calculating Gröbner Bases that uses none of the client's CPU!

  • Since, in general, the Buchberger algorithm is not efficient, the web interface allows the user to limit time for execution

Public access:
Remote access through web interface at http://grobner.nuigalway.ie/

Abstract
What OGB does
OGB calculates in the polynomical ring Q[x1, x2, ... , xn], i.e the set of all polynomials in n variables with rational coefficients. It does all Gröbner Basis calculations using lexicographical ordering, defined as follows: A given term T1 = c1x1a1x2a2...xnan is lexicographically greater than another term T2 = c2x1b1x2b2...xnbn (and so we write T1 > T2) iff the first non-zero term in the vector (a1-b1, a2-b2,...,an-bn) is positive. Here cj is in Q, i.e. cj=m/n with m, n in Z. OGB calculates the Gröbner Basis, the minimal Gröbner Basis (with the property that the leading monomial in polynomial i is not a factor of the leading monomial in polynomial j for j different from i), or the reduced Gröbner Basis (with the property that the leading monomial in polynomial i is not a factor of any monomial in polynomial j for j different from i).

...yet another Gröbner Basis calculator???
This software implements known algorithms that have been implemented many other places. However the focus of OGB is on
  1. Applicability to solving systems of equations: This is why the lexicographic ordering is chosen, and the reduced basis is calculated. It is known that if there are a sufficient number of equations, and if the system is solvable, the reduced basis under lexicographical ordering is always triangular and moreover the last polynomial is univariate.

  2. Pedagogy: OGB is written to educate both students and academics who are not mathematicians but use mathematics (scientists, engineers,...)

  3. Ease of use: OGB
Interface and Examples
In designing software there is often a trade off between different types of interface: At one extreme we would "walk" the user through a series of web pages. The first might ask the number of polynomials, the second the number of terms in each polynomial, etc. This interface is clearer, but it is harder for the user to do repeated calculations. It suits the new user rather than the regular one. On the other hand we could present just one "box" into which the user enters all the polynomials, and the calculation is carried out immediately. This suits the repeated user, but not the beginner. A decision was made to construct the second type of interface. All monomials are represented sparsely: this means that for a term such as x13x47 = x13x20x30x47 we do not store variables with zero exponent (in this case we do not store x2 or x3)
EXAMPLE 1:
Suppose we wish to calculate with the single monomial -13x17x35x632/14. Enter -13,14,1,7,3,5,6,32. OGB will echo in the output (in HTML) both the polynomial(s) you have entered and the reduced Gröbner Basis. In this case it gives: INPUT: -(13/14)x17x35x632 REDUCED GRÖBNER BASIS: x17x35x632. Note that even when the coefficient is an integer (e.g. if it were -13 instead of -13/14) we must enter a numerator and a denominator (which will be 1 in the case of -13).
EXAMPLE 2:
Suppose we want to solve the two equations [-3/7]x2y2+xy3+3=0 and xy3+[ 4/13]y2=0. Enter -3,7,1,2,2,2;1,1,1,1,2,3;3,1| 1,1,1,1,2,3;4,13,2,2. Note here that a semicolon (;) separates terms and a vertical bar (|) separates polynomials. OGB gives x22 - (3501/364) and x1+(112/3501)x2 from which we can easily solve the system.

Limitations
  1. Only lexicographical ordering is available

  2. Only works over Q (the rationals). Note however this is not a limitation in many real-world examples. We can represent an arbitrary (but finite) number of digits in a real number using rationals, e.g. write 3.572 as [ 3572/1000].

References

[1]
L. Robbiano (1985), Term orderings on the polynomial ring, LNCS 204, pp. 513-517.
[2]
GNU Multiple Precision. This library is available free at http://www.swox.com/gmp/
[3]
B. Buchberger (1985), Gröbner bases: an algorithmic method in polynomial ideal theory, in Multidimensional Systems Theory, edited by N. K. Bose, D. Reidel Publishing Company, 184-232.
[4]
Home page for Online Gröbner Bases (OGB) is at http://grobner.nuigalway.ie/
[5]
S. Hughes & A. Zmievski (2001), PHP Developer's Cookbook, Sams Publishing (2nd. edition).

Footnotes:

1a server-side scripting language, whose recursive acronym stands for PHP Hypertext Preprocessor[5]


File translated from TEX by TTH, version 3.39.
On 6 Jun 2003, 15:46.