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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
|
<?xml version="1.0" encoding="UTF-8" ?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1 plus MathML 2.0//EN"
"http://www.w3.org/TR/MathML2/dtd/xhtml-math11-f.dtd" [
<!ENTITY mathml "http://www.w3.org/1998/Math/MathML">
]>
<html xmlns="http://www.w3.org/1999/xhtml"
xmlns:xlink="http://www.w3.org/1999/xlink" >
<head>
<title>Section9.31</title>
<link rel="stylesheet" type="text/css" href="graphicstyle.css" />
<script type="text/javascript" src="bookax1.js" />
</head>
<body>
<a href="book-contents.xhtml" style="margin-right: 10px;">Book Contents</a><a href="section-9.30.xhtml" style="margin-right: 10px;">Previous Section 9.30 GeneralSparseTable</a><a href="section-9.32.xhtml" style="margin-right: 10px;">Next Section 9.32 Heap</a>
<a href="book-index.xhtml">Book Index</a><div class="section" id="sec-9.31">
<h2 class="sectiontitle">9.31 GroebnerFactorizationPackage</h2>
<a name="GroebnerFactorizationPackageXmpPage" class="label"/>
<p>Solving systems of polynomial equations with the Gröbner 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 Gröbner
calculations are reducible. Since Axiom has an excellent polynomial
factorization algorithm, it is very natural to combine the Gröbner
and factorization algorithms.
</p>
<p><span class="teletype">GroebnerFactorizationPackage</span> exports the
<span class="spadfunFrom" >groebnerFactorize</span><span class="index">groebnerFactorize</span><a name="chapter-9-50"/><span class="index">GroebnerFactorizationPackage</span><a name="chapter-9-51"/>
operation which implements a modified Gröbner 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 <math xmlns="&mathml;" mathsize="big"><mstyle><mrow><msub><mi>p</mi><mn>1</mn></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>p</mi><mi>n</mi></msub><mo>.</mo></mrow></mstyle></math> In the branches corresponding to <math xmlns="&mathml;" mathsize="big"><mstyle><mrow><msub><mi>p</mi><mn>2</mn></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>p</mi><mi>n</mi></msub><mo>,</mo></mrow></mstyle></math> the factor <math xmlns="&mathml;" mathsize="big"><mstyle><mrow><msub><mi>p</mi><mn>1</mn></msub></mrow></mstyle></math> 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
Gröbner basis.
</p>
<p>Here is an example from chemistry. In a theoretical model of
cyclohexane, <math xmlns="&mathml;" mathsize="big"><mstyle><mrow><msub><mrow><mtext>C</mtext></mrow><mn>6</mn></msub><msub><mrow><mtext>H</mtext></mrow><mn>12</mn></msub></mrow></mstyle></math>, 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 <math xmlns="&mathml;" mathsize="big"><mstyle><mi>x</mi></mstyle></math>, <math xmlns="&mathml;" mathsize="big"><mstyle><mi>y</mi></mstyle></math> and <math xmlns="&mathml;" mathsize="big"><mstyle><mi>z</mi></mstyle></math>.
</p>
<p>A. Dress developed a theory to decide whether a set of points
and distances between them can be realized in an <math xmlns="&mathml;" mathsize="big"><mstyle><mi>n</mi></mstyle></math>-dimensional space.
Here, of course, we have <math xmlns="&mathml;" mathsize="big"><mstyle><mrow><mi>n</mi><mo>=</mo><mn>3</mn></mrow></mstyle></math>.
</p>
<div id="spadComm9-73" class="spadComm" >
<form id="formComm9-73" action="javascript:makeRequest('9-73');" >
<input id="comm9-73" type="text" class="command" style="width: 105em;" value="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] ] " />
</form>
<span id="commSav9-73" class="commSav" >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] ] </span>
<div id="mathAns9-73" ></div>
</div>
<div class="math">
<table>
<tr><td>
<math xmlns="&mathml;" mathsize="big" display="block"><mstyle><mrow><mo>[</mo><mtable><mtr><mtd><mn>0</mn></mtd><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd></mtr><mtr><mtd><mn>1</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>1</mn></mtd><mtd><mfrac><mn>8</mn><mn>3</mn></mfrac></mtd><mtd><mi>x</mi></mtd><mtd><mfrac><mn>8</mn><mn>3</mn></mfrac></mtd></mtr><mtr><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>1</mn></mtd><mtd><mfrac><mn>8</mn><mn>3</mn></mfrac></mtd><mtd><mi>y</mi></mtd></mtr><mtr><mtd><mn>1</mn></mtd><mtd><mfrac><mn>8</mn><mn>3</mn></mfrac></mtd><mtd><mn>1</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>1</mn></mtd><mtd><mfrac><mn>8</mn><mn>3</mn></mfrac></mtd></mtr><mtr><mtd><mn>1</mn></mtd><mtd><mi>x</mi></mtd><mtd><mfrac><mn>8</mn><mn>3</mn></mfrac></mtd><mtd><mn>1</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>1</mn></mtd></mtr><mtr><mtd><mn>1</mn></mtd><mtd><mfrac><mn>8</mn><mn>3</mn></mfrac></mtd><mtd><mi>y</mi></mtd><mtd><mfrac><mn>8</mn><mn>3</mn></mfrac></mtd><mtd><mn>1</mn></mtd><mtd><mn>0</mn></mtd></mtr></mtable><mo>]</mo></mrow></mstyle></math>
</td></tr>
</table>
</div>
<div class="returnType">
Type: SquareMatrix(6,DistributedMultivariatePolynomial([x,y,z],Fraction Integer))
</div>
<p>For cyclohexane the distances have to satisfy this equation.
</p>
<div id="spadComm9-74" class="spadComm" >
<form id="formComm9-74" action="javascript:makeRequest('9-74');" >
<input id="comm9-74" type="text" class="command" style="width: 16em;" value="eq := determinant mfzn " />
</form>
<span id="commSav9-74" class="commSav" >eq := determinant mfzn </span>
<div id="mathAns9-74" ></div>
</div>
<div class="math">
<table>
<tr><td>
<math xmlns="&mathml;" mathsize="big" display="block"><mstyle><mrow><mtable><mtr><mtd><mo>-</mo><mrow><mrow><msup><mi>x</mi><mn>2</mn></msup></mrow><mspace width="0.5 em" /><mrow><msup><mi>y</mi><mn>2</mn></msup></mrow></mrow><mo>+</mo><mrow><mfrac><mn>22</mn><mn>3</mn></mfrac><mspace width="0.5 em" /><mrow><msup><mi>x</mi><mn>2</mn></msup></mrow><mspace width="0.5 em" /><mi>y</mi></mrow><mo>-</mo><mrow><mfrac><mn>25</mn><mn>9</mn></mfrac><mspace width="0.5 em" /><mrow><msup><mi>x</mi><mn>2</mn></msup></mrow></mrow><mo>+</mo><mrow><mfrac><mn>22</mn><mn>3</mn></mfrac><mspace width="0.5 em" /><mi>x</mi><mspace width="0.5 em" /><mrow><msup><mi>y</mi><mn>2</mn></msup></mrow></mrow><mo>-</mo><mrow><mfrac><mn>388</mn><mn>9</mn></mfrac><mspace width="0.5 em" /><mi>x</mi><mspace width="0.5 em" /><mi>y</mi></mrow><mo>-</mo></mtd></mtr><mtr><mtd></mtd></mtr><mtr><mtd><mrow><mfrac><mn>250</mn><mn>27</mn></mfrac><mspace width="0.5 em" /><mi>x</mi></mrow><mo>-</mo><mrow><mfrac><mn>25</mn><mn>9</mn></mfrac><mspace width="0.5 em" /><mrow><msup><mi>y</mi><mn>2</mn></msup></mrow></mrow><mo>-</mo><mrow><mfrac><mn>250</mn><mn>27</mn></mfrac><mspace width="0.5 em" /><mi>y</mi></mrow><mo>+</mo><mfrac><mn>14575</mn><mn>81</mn></mfrac></mtd></mtr></mtable></mrow></mstyle></math>
</td></tr>
</table>
</div>
<div class="returnType">
Type: DistributedMultivariatePolynomial([x,y,z],Fraction Integer)
</div>
<p>They also must satisfy the equations
given by cyclic shifts of the indeterminates.
</p>
<div id="spadComm9-75" class="spadComm" >
<form id="formComm9-75" action="javascript:makeRequest('9-75');" >
<input id="comm9-75" type="text" class="command" style="width: 53em;" value="groebnerFactorize [eq, eval(eq, [x,y,z], [y,z,x]), eval(eq, [x,y,z], [z,x,y])] " />
</form>
<span id="commSav9-75" class="commSav" >groebnerFactorize [eq, eval(eq, [x,y,z], [y,z,x]), eval(eq, [x,y,z], [z,x,y])] </span>
<div id="mathAns9-75" ></div>
</div>
<div class="math">
<table>
<tr><td>
<math xmlns="&mathml;" mathsize="big" display="block"><mstyle><mrow><mo>[</mo><mrow><mo>[</mo><mrow><mrow><mi>x</mi><mspace width="0.5 em" /><mi>y</mi></mrow><mo>+</mo><mrow><mi>x</mi><mspace width="0.5 em" /><mi>z</mi></mrow><mo>-</mo><mrow><mfrac><mn>22</mn><mn>3</mn></mfrac><mspace width="0.5 em" /><mi>x</mi></mrow><mo>+</mo><mrow><mi>y</mi><mspace width="0.5 em" /><mi>z</mi></mrow><mo>-</mo><mrow><mfrac><mn>22</mn><mn>3</mn></mfrac><mspace width="0.5 em" /><mi>y</mi></mrow><mo>-</mo><mrow><mfrac><mn>22</mn><mn>3</mn></mfrac><mspace width="0.5 em" /><mi>z</mi></mrow><mo>+</mo><mfrac><mn>121</mn><mn>3</mn></mfrac></mrow><mo>,</mo><mspace width="0.5 em" /><mrow><mrow><mi>x</mi><mspace width="0.5 em" /><mrow><msup><mi>z</mi><mn>2</mn></msup></mrow></mrow><mo>-</mo><mrow><mfrac><mn>22</mn><mn>3</mn></mfrac><mspace width="0.5 em" /><mi>x</mi><mspace width="0.5 em" /><mi>z</mi></mrow><mo>+</mo><mrow><mfrac><mn>25</mn><mn>9</mn></mfrac><mspace width="0.5 em" /><mi>x</mi></mrow><mo>+</mo><mrow><mi>y</mi><mspace width="0.5 em" /><mrow><msup><mi>z</mi><mn>2</mn></msup></mrow></mrow><mo>-</mo><mrow><mfrac><mn>22</mn><mn>3</mn></mfrac><mspace width="0.5 em" /><mi>y</mi><mspace width="0.5 em" /><mi>z</mi></mrow><mo>+</mo><mrow><mfrac><mn>25</mn><mn>9</mn></mfrac><mspace width="0.5 em" /><mi>y</mi></mrow><mo>-</mo><mrow><mfrac><mn>22</mn><mn>3</mn></mfrac><mspace width="0.5 em" /><mrow><msup><mi>z</mi><mn>2</mn></msup></mrow></mrow><mo>+</mo><mrow><mfrac><mn>388</mn><mn>9</mn></mfrac><mspace width="0.5 em" /><mi>z</mi></mrow><mo>+</mo><mfrac><mn>250</mn><mn>27</mn></mfrac></mrow><mo>,</mo><mspace width="0.5 em" /><mrow><mrow><mrow><msup><mi>y</mi><mn>2</mn></msup></mrow><mspace width="0.5 em" /><mrow><msup><mi>z</mi><mn>2</mn></msup></mrow></mrow><mo>-</mo><mrow><mfrac><mn>22</mn><mn>3</mn></mfrac><mspace width="0.5 em" /><mrow><msup><mi>y</mi><mn>2</mn></msup></mrow><mspace width="0.5 em" /><mi>z</mi></mrow><mo>+</mo><mrow><mfrac><mn>25</mn><mn>9</mn></mfrac><mspace width="0.5 em" /><mrow><msup><mi>y</mi><mn>2</mn></msup></mrow></mrow><mo>-</mo><mrow><mfrac><mn>22</mn><mn>3</mn></mfrac><mspace width="0.5 em" /><mi>y</mi><mspace width="0.5 em" /><mrow><msup><mi>z</mi><mn>2</mn></msup></mrow></mrow><mo>+</mo><mrow><mfrac><mn>388</mn><mn>9</mn></mfrac><mspace width="0.5 em" /><mi>y</mi><mspace width="0.5 em" /><mi>z</mi></mrow><mo>+</mo><mrow><mfrac><mn>250</mn><mn>27</mn></mfrac><mspace width="0.5 em" /><mi>y</mi></mrow><mo>+</mo><mrow><mfrac><mn>25</mn><mn>9</mn></mfrac><mspace width="0.5 em" /><mrow><msup><mi>z</mi><mn>2</mn></msup></mrow></mrow><mo>+</mo><mrow><mfrac><mn>250</mn><mn>27</mn></mfrac><mspace width="0.5 em" /><mi>z</mi></mrow><mo>-</mo><mfrac><mn>14575</mn><mn>81</mn></mfrac></mrow><mo>]</mo></mrow><mo>,</mo><mspace width="0.5 em" /><mrow><mo>[</mo><mrow><mi>x</mi><mo>+</mo><mi>y</mi><mo>-</mo><mfrac><mn>21994</mn><mn>5625</mn></mfrac></mrow><mo>,</mo><mspace width="0.5 em" /><mrow><mrow><msup><mi>y</mi><mn>2</mn></msup></mrow><mo>-</mo><mrow><mfrac><mn>21994</mn><mn>5625</mn></mfrac><mspace width="0.5 em" /><mi>y</mi></mrow><mo>+</mo><mfrac><mn>4427</mn><mn>675</mn></mfrac></mrow><mo>,</mo><mspace width="0.5 em" /><mrow><mi>z</mi><mo>-</mo><mfrac><mn>463</mn><mn>87</mn></mfrac></mrow><mo>]</mo></mrow><mo>,</mo><mspace width="0.5 em" /><mrow><mo>[</mo><mrow><mrow><msup><mi>x</mi><mn>2</mn></msup></mrow><mo>-</mo><mrow><mfrac><mn>1</mn><mn>2</mn></mfrac><mspace width="0.5 em" /><mi>x</mi><mspace width="0.5 em" /><mi>z</mi></mrow><mo>-</mo><mrow><mfrac><mn>11</mn><mn>2</mn></mfrac><mspace width="0.5 em" /><mi>x</mi></mrow><mo>-</mo><mrow><mfrac><mn>5</mn><mn>6</mn></mfrac><mspace width="0.5 em" /><mi>z</mi></mrow><mo>+</mo><mfrac><mn>265</mn><mn>18</mn></mfrac></mrow><mo>,</mo><mspace width="0.5 em" /><mrow><mi>y</mi><mo>-</mo><mi>z</mi></mrow><mo>,</mo><mspace width="0.5 em" /><mrow><mrow><msup><mi>z</mi><mn>2</mn></msup></mrow><mo>-</mo><mrow><mfrac><mn>38</mn><mn>3</mn></mfrac><mspace width="0.5 em" /><mi>z</mi></mrow><mo>+</mo><mfrac><mn>265</mn><mn>9</mn></mfrac></mrow><mo>]</mo></mrow><mo>,</mo><mspace width="0.5 em" /><mrow><mo>[</mo><mrow><mi>x</mi><mo>-</mo><mfrac><mn>25</mn><mn>9</mn></mfrac></mrow><mo>,</mo><mspace width="0.5 em" /><mrow><mi>y</mi><mo>-</mo><mfrac><mn>11</mn><mn>3</mn></mfrac></mrow><mo>,</mo><mspace width="0.5 em" /><mrow><mi>z</mi><mo>-</mo><mfrac><mn>11</mn><mn>3</mn></mfrac></mrow><mo>]</mo></mrow><mo>,</mo><mspace width="0.5 em" /><mrow><mo>[</mo><mrow><mi>x</mi><mo>-</mo><mfrac><mn>11</mn><mn>3</mn></mfrac></mrow><mo>,</mo><mspace width="0.5 em" /><mrow><mi>y</mi><mo>-</mo><mfrac><mn>11</mn><mn>3</mn></mfrac></mrow><mo>,</mo><mspace width="0.5 em" /><mrow><mi>z</mi><mo>-</mo><mfrac><mn>11</mn><mn>3</mn></mfrac></mrow><mo>]</mo></mrow><mo>,</mo><mspace width="0.5 em" /><mrow><mo>[</mo><mrow><mi>x</mi><mo>+</mo><mfrac><mn>5</mn><mn>3</mn></mfrac></mrow><mo>,</mo><mspace width="0.5 em" /><mrow><mi>y</mi><mo>+</mo><mfrac><mn>5</mn><mn>3</mn></mfrac></mrow><mo>,</mo><mspace width="0.5 em" /><mrow><mi>z</mi><mo>+</mo><mfrac><mn>5</mn><mn>3</mn></mfrac></mrow><mo>]</mo></mrow><mo>,</mo><mspace width="0.5 em" /><mrow><mo>[</mo><mrow><mi>x</mi><mo>-</mo><mfrac><mn>19</mn><mn>3</mn></mfrac></mrow><mo>,</mo><mspace width="0.5 em" /><mrow><mi>y</mi><mo>+</mo><mfrac><mn>5</mn><mn>3</mn></mfrac></mrow><mo>,</mo><mspace width="0.5 em" /><mrow><mi>z</mi><mo>+</mo><mfrac><mn>5</mn><mn>3</mn></mfrac></mrow><mo>]</mo></mrow><mo>]</mo></mrow></mstyle></math>
</td></tr>
</table>
</div>
<div class="returnType">
Type: List List
DistributedMultivariatePolynomial([x,y,z],Fraction Integer)
</div>
<p>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 <math xmlns="&mathml;" mathsize="big"><mstyle><mrow><mi>x</mi><mo>=</mo><mi>y</mi><mo>=</mo><mi>z</mi><mo>=</mo><mn>11</mn><mo>/</mo><mn>3</mn></mrow></mstyle></math>,
and this determines the ``boat'' form of cyclohexane. The
other ideal is one-dimensional, which means that we have a solution
space given by one parameter. This gives the ``chair'' form of
cyclohexane. The parameter describes the angle of the ``back of the
chair.''
</p>
<p><span class="spadfunFrom" >groebnerFactorize</span><span class="index">groebnerFactorize</span><a name="chapter-9-52"/><span class="index">GroebnerFactorizationPackage</span><a name="chapter-9-53"/> has an
optional <span class="teletype">Boolean</span>-valued second argument. When it is <span class="teletype">true</span>
partial results are displayed, since it may happen that the
calculation does not terminate in a reasonable time. See the source
code for <span class="teletype">GroebnerFactorizationPackage</span> in <span style="font-weight: bold;"> groebf.input</span>
for more details about the algorithms used.
</p>
</div><a href="book-contents.xhtml" style="margin-right: 10px;">Book Contents</a>
<a href="section-9.30.xhtml" style="margin-right: 10px;">Previous Section 9.30 GeneralSparseTable</a><a href="section-9.32.xhtml" style="margin-right: 10px;">Next Section 9.32 Heap</a>
<a href="book-index.xhtml">Book Index</a></body>
</html>
|
