Solving systems of polynomial equations with the Groebner basis algorithm can often be very time consuming because, in general, the algorithm has exponential run-time. These systems, which often come from concrete applications, frequently have symmetries which are not taken advantage of by the algorithm. However, it often happens in this case that the polynomials which occur during the Groebner calculations are reducible. Since FriCAS has an excellent polynomial factorization algorithm, it is very natural to combine the Groebner and factorization algorithms.
GroebnerFactorizationPackage exports the groebnerFactorize operation which implements a modified Groebner basis algorithm. In this algorithm, each polynomial that is to be put into the partial list of the basis is first factored. The remaining calculation is split into as many parts as there are irreducible factors. Call these factors p1,...,pN. In the branches corresponding to p2,...,pN, the factor p1 can be divided out, and so on. This package also contains operations that allow you to specify the polynomials that are not zero on the common roots of the final Groebner basis.
Here is an example from chemistry. In a theoretical model of the cyclohexan C6H12, the six carbon atoms each sit in the center of gravity of a tetrahedron that has two hydrogen atoms and two carbon atoms at its corners. We first normalize and set the length of each edge to 1. Hence, the distances of one fixed carbon atom to each of its immediate neighbours is 1. We will denote the distances to the other three carbon atoms by x, y and z.
A. Dress developed a theory to decide whether a set of points and distances between them can be realized in an n-dimensional space. Here, of course, we have n = 3.
mfzn : SQMATRIX(6,DMP([x,y,z],Fraction INT)) := _
[ [0,1,1,1,1,1], [1,0,1,8/3,x,8/3], [1,1,0,1,8/3,y], _
[1,8/3,1,0,1,8/3], [1,x,8/3,1,0,1], [1,8/3,y,8/3,1,0] ]
+0 1 1 1 1 1+
| |
| 8 8|
|1 0 1 - x -|
| 3 3|
| |
| 8 |
|1 1 0 1 - y|
| 3 |
| |
| 8 8|
|1 - 1 0 1 -|
| 3 3|
| |
| 8 |
|1 x - 1 0 1|
| 3 |
| |
| 8 8 |
|1 - y - 1 0|
+ 3 3 +
Type: SquareMatrix(6,DistributedMultivariatePolynomial([x,y,z],
Fraction Integer))
For the cyclohexan, the distances have to satisfy this equation.
eq := determinant mfzn
2 2 22 2 25 2 22 2 388 250 25 2 250 14575
- x y + -- x y - -- x + -- x y - --- x y - --- x - -- y - --- y + -----
3 9 3 9 27 9 27 81
Type: DistributedMultivariatePolynomial([x,y,z],Fraction Integer)
They also must satisfy the equations given by cyclic shifts of the indeterminates.
groebnerFactorize [eq,eval(eq, [x,y,z],[y,z,x]), eval(eq,[x,y,z],[z,x,y])]
[
22 22 22 121
[x y + x z - -- x + y z - -- y - -- z + ---,
3 3 3 3
2 22 25 2 22 25 22 2 388 250
x z - -- x z + -- x + y z - -- y z + -- y - -- z + --- z + ---,
3 9 3 9 3 9 27
2 2 22 2 25 2 22 2 388 250 25 2 250 14575
y z - -- y z + -- y - -- y z + --- y z + --- y + -- z + --- z - -----]
3 9 3 9 27 9 27 81
,
21994 2 21994 4427 463
[x + y - -----,y - ----- y + ----,z - ---],
5625 5625 675 87
2 1 11 5 265 2 38 265
[x - - x z - -- x - - z + ---,y - z,z - -- z + ---],
2 2 6 18 3 9
25 11 11 11 11 11 5 5 5
[x - --,y - --,z - --], [x - --,y - --,z - --], [x + -,y + -,z + -],
9 3 3 3 3 3 3 3 3
19 5 5
[x - --,y + -,z + -]]
3 3 3
Type: List List DistributedMultivariatePolynomial([x,y,z],Fraction Integer)
The union of the solutions of this list is the solution of our original problem. If we impose positivity conditions, we get two relevant ideals. One ideal is zero-dimensional, namely x = y = z =11/3, and this determines the “boat” form of the cyclohexan. The other ideal is one-dimensional, which means that we have a solution space given by one parameter. This gives the “chair” form of the cyclohexan. The parameter describes the angle of the “back of the chair.”
groebnerFactorize has an optional Boolean-valued second argument. When it is true partial results are displayed, since it may happen that the calculation does not terminate in a reasonable time. See the source code for GroebnerFactorizationPackage in groebf.spad.pamphlet for more details about the algorithms used.
See Also: