1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
|
% Copyright The Numerical Algorithms Group Limited 1992-94. All rights reserved.
% !! DO NOT MODIFY THIS FILE BY HAND !! Created by ht.awk.
\newcommand{\GroebnerFactorizationPackageXmpTitle}{GroebnerFactorizationPackage}
\newcommand{\GroebnerFactorizationPackageXmpNumber}{9.31}
%
% =====================================================================
\begin{page}{GroebnerFactorizationPackageXmpPage}{9.31 GroebnerFactorizationPackage}
% =====================================================================
\beginscroll
%%
%% GBF
%%
%% GroebnerFactorizationPackage
%%
%% J. Grabmeier 26 04 91
Solving systems of polynomial equations with the
\texht{Gr\"{o}bner}{Groebner}
%-% \HDindex{Groebner basis@{Gr\protect\"{o}bner basis}}{GroebnerFactorizationPackageXmpPage}{9.31}{GroebnerFactorizationPackage}
basis algorithm can often be very time consuming because, in general,
%-% \HDindex{basis!Groebner@{Gr\protect\"{o}bner}}{GroebnerFactorizationPackageXmpPage}{9.31}{GroebnerFactorizationPackage}
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
\texht{Gr\"{o}bner}{Groebner} calculations are reducible.
Since \Language{} has an excellent polynomial factorization algorithm, it is
very natural to combine the
\texht{Gr\"{o}bner}{Groebner} and factorization algorithms.
\spadtype{GroebnerFactorizationPackage} exports the
\axiomFunFrom{groebnerFactorize}{GroebnerFactorizationPackage}
operation which implements a modified
\texht{Gr\"{o}bner}{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 \texht{$p_1, \ldots,p_n.$}{\spad{p1, ..., pn.}}
In the branches corresponding to \texht{$p_2,
\ldots,p_n,$}{\spad{p2, ..., pn,}} the factor
\texht{$p_1$}{\spad{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
\texht{Gr\"{o}bner}{Groebner} basis.
Here is an example from chemistry.
%-% \HDindex{chemistry}{GroebnerFactorizationPackageXmpPage}{9.31}{GroebnerFactorizationPackage}
In a theoretical model of the cyclohexan \texht{${\rm C}_6{\rm H}_{12}$}{C6H12},
the six carbon atoms each sit in the center of gravity of a
%-% \HDindex{cyclohexan}{GroebnerFactorizationPackageXmpPage}{9.31}{GroebnerFactorizationPackage}
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
\smath{x}, \smath{y} and \smath{z}.
\texht{A.~Dress}{A. Dress} developed a theory to decide whether a set of points
%% reference?
and distances between them can be realized in an \smath{n}-dimensional space.
Here, of course, we have \smath{n = 3}.
\xtc{
}{
\spadpaste{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]] \bound{mfzn}}
}
\xtc{
For the cyclohexan, the distances have to satisfy this equation.
}{
\spadpaste{eq := determinant mfzn \free{mfzn}\bound{eq}}
}
\xtc{
They also must satisfy the equations
given by cyclic shifts of the indeterminates.
}{
\spadpaste{groebnerFactorize [eq, eval(eq, [x,y,z], [y,z,x]), eval(eq, [x,y,z], [z,x,y])] \free{eq}}
}
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 \smath{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.''
\axiomFunFrom{groebnerFactorize}{GroebnerFactorizationPackage}
has an optional \axiomType{Boolean}-valued second argument.
When it is \spad{true} partial results are displayed, since it may happen that the
calculation does not terminate in a reasonable time.
See the source code for \spadtype{GroebnerFactorizationPackage}
in {\bf groebf\spadFileExt{}} for more details about the algorithms
used.
\endscroll
\autobuttons
\end{page}
%
|
