Library 'groebner': Calculation of Gr"obner-bases for poly nomial ideals
Interface:
groebner::gbasis
groebner::spoly
groebner::normalf
The functions spoly computes the S-polynomial of two polynomials P1 and P2. The result will be computed with respect to the total degree ordering of the terms.
/ 2 2 2 \
poly \ 5 x + y + x y, [y, x] /
/ 3 2 \
poly \ - 2 y + 7 x y + 1 , [y, x] /
/ 2 4 2 2 3 2 \
poly \ - x - 2 y - 10 x y - 7 x y , [y, x] /
One may also use the lexicographical ordering.
/ 2 2 2 2 \
poly \ - 7 x y - 10 x y - 2 x y - 1 , [y, x] /
As an example consider the ideal P = {P1,P2} and the polynomial q to be reduced.
/ 3 2 2 \
poly \ 5 x - 3 x y + 3 x y + 2 x y , [y, x] /
Then the normal form of q with respect to the total degree ordering is given by:
/ 2 3 2 2 \
poly \- 5 x + 3 x y - 50 x + 15 x - 10 y + 10 x y + 1, [y, x]/
The reduced gröbner basis of a polynomial ideal is computed by the function gbasis. The ideal must be given as a list of polynomials.
-- / 2 3 2 \
| poly \y + 251 x + 175 x + 50 y - 5, [y, x]/, poly
--
/ 2 2 2 \ / 3 2 \ --
\5 x + y + x y, [y, x] /, poly \ 2 y - 7 x y - 1, [y, x]/ |
--
The gröbner basis may also be computed with respect to the lexicographical ordering. One may further allow the function gbasis to heuristically change the order of the unknowns to find a more efficient one.
-- / 3 4 5 6
| poly \175 x + 50 y - 4 y - 345 y + 49 y + 4 y + 1,
--
\ / 3 4 6 7 \ --
[x, y]/, poly \y - 20 y - 4 y + 69 y + 4 y + 5, [x, y]/ |
--
poly(x + y z - 2, [x, y, z])
poly(y + x z - 3, [x, y, z])
poly(z + x y - 5, [x, y, z])
Given a system of equations {P1=0, P2=0, P3=0}, does there exist a solution at all? How many solutions are there? Such questions may be answered given the gröbner basis of the ideal P:= {P1,P2,P3}.
It is well known that there exists a solution if the basis does not contain a constant polynomial (regardless of the ordering chosen).
So let us first compute the reduced basis with respect to the degree ordering.
-- 2 2
| x + y z - 2, y + x z - 3, - 3 y + 5 z + y - z , z + x
--
2 2 2 3 --
y - 5, - 2 x + 5 z + x - z , - 3 x - 2 y - z - 5 z + z + 11 |
--
One may further conclude that a system has only a finite number of solutions if for each indeterminate X there is a leading term in the gröbner basis which is of the form X^n for some n.
The leading terms of our basis B fulfill this criteria:
-- 2 2 3 --
| y z, x z, y , x y, x , z |
-- --
As another example consider the system {P1=0, P2=0, P3=0} with polynomials
/ 2 2 \
poly \ 4 y + x y - 17, [x, y] /
/ 3 \
poly \ 2 x y - 3 y + 8, [x, y] /
/ 2 \
poly \ - 5 x y + x y + 1 , [x, y] /
The system has no solution, irrespective of the term ordering used:
[1]
[1]