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
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
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.
Pedagogy: OGB is written to educate both students and academics
who are not mathematicians but use mathematics (scientists, engineers,...)
is as efficient as other competitors (the only other
online Gröbner Basis software we are aware of is at
http://www.geocities.com/CapeCanaveral/Hall/3131/groebner_applet.html.
This uses JAVA, and runs on the clients machine; it will
hence give different run-times for different users.)
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)x17x35x632REDUCED 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
Only lexicographical ordering is available
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.
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.