Debian Codegraph @

doc/gb-book.html

raw
1 <?xml version="1.0" encoding="iso-8859-1"?>
2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
3 "DTD/xhtml1-transitional.dtd">
4 <html xmlns="http://www.w3.org/1999/xhtml">
5 <head>
6 <link rel="stylesheet" type="text/css" href="html.css" />
7 <title>JAS - Gr&ouml;bner bases book</title>
8 </head>
9 <body class="main">
10 <h1>Gr&ouml;bner bases book algorithms and JAS methods</h1>
11
12 <p>
13 Summary of algorithms from the
14 <a href="http://www.springer.com/mathematics/book/978-0-387-97971-7" target="gbb">Gr&ouml;bner bases</a>
15 book and corresponding JAS classes and methods.
16 </p>
17
18
19 <h2>Gr&ouml;bner bases book algorithms</h2>
20
21 <p>
22 The JAS base package <code>edu.jas</code> name is omitted in the
23 following table.
24 JAS also contains improved versions of the algorithms which may be located through the links.
25 A short explanation of code organization with interfaces and several implementing classes
26 can be found in the <a href="design.html">API guide</a>.
27 </p>
28
29 <table border="1" cellpadding="3" summary="GB book to JAS summary" >
30 <tr>
31 <td>GB book algorithm</td>
32 <td>JAS interfaces, classes and methods</td>
33 <td>remarks</td>
34 </tr>
35
36 <tr>
37 <td>0.1&nbsp;<code>DIVINT</code></td>
38 <td><a href="api/edu/jas/arith/BigInteger.html#divideAndRemainder(edu.jas.arith.BigInteger)" target="classFrame"><code>arith.BigInteger.divideAndRemainder</code></a>
39 </td>
40 <td>adapter for <code>java.math.BigInteger.divideAndRemainder</code>
41 </td>
42 </tr>
43
44 <tr>
45 <td colspan="3">&nbsp;</td>
46 </tr>
47
48 <tr>
49 <td>2.1&nbsp;<code>DIV</code></td>
50 <td><a href="api/edu/jas/structure/MonoidElem.html#divide(C)" target="classFrame"><code>structure.MonoidElem.divide</code></a>
51 and
52 <a href="api/edu/jas/structure/MonoidElem.html#remainder(C)" target="classFrame"><code>structure.MonoidElem.remainder</code></a>
53 </td>
54 <td>all classes which implement this interface
55 </td>
56 </tr>
57
58 <tr>
59 <td>2.2&nbsp;<code>DIVPOL</code></td>
60 <td><a href="api/edu/jas/poly/GenPolynomial.html#divideAndRemainder(edu.jas.poly.GenPolynomial)" target="classFrame"><code>poly.GenPolynomial.</code> <code>divideAndRemainder</code></a>
61 </td>
62 <td>for univariate polynomials over fields
63 </td>
64 </tr>
65
66 <tr>
67 <td>2.3&nbsp;<code>EXTEUC</code></td>
68 <td><a href="api/edu/jas/poly/GenPolynomial.html#egcd(edu.jas.poly.GenPolynomial)" target="classFrame"><code>poly.GenPolynomial.egcd</code></a>
69 </td>
70 <td>for univariate polynomials over fields
71 </td>
72 </tr>
73
74 <tr>
75 <td colspan="3">&nbsp;</td>
76 </tr>
77
78 <tr>
79 <td>3.1&nbsp;<code>LINDEP</code></td>
80 <td><a href="" target="classFrame"><code></code></a>
81 not implemented
82 </td>
83 <td>
84 But see
85 <a href="api/edu/jas/vector/LinAlg.html#rowEchelonForm(edu.jas.vector.GenMatrix)" target="classFrame"
86 ><code>vector.LinAlg.</code> <code>rowEchelonForm</code></a> and other classes
87 in the <code>vector</code> package.
88 </td>
89 </tr>
90
91 <tr>
92 <td>3.2&nbsp;<code>EXCHANGE</code></td>
93 <td><a href="" target="classFrame"><code></code></a>
94 not implemented
95 </td>
96 <td>
97 </td>
98 </tr>
99
100 <tr>
101 <td colspan="3">&nbsp;</td>
102 </tr>
103
104 <tr>
105 <td>4.1&nbsp;<code>EQUIV</code></td>
106 <td><a href="api/edu/jas/structure/Residue.html#equals(java.lang.Object)" target="classFrame"><code>structure.Residue.equals</code></a>
107 or
108 <a href="api/edu/jas/application/Residue.html#equals(java.lang.Object)" target="classFrame"><code>application.Residue.equals</code></a>
109 </td>
110 <td>arbitrary residue class rings and residue class rings modulo polynomial ideals
111 </td>
112 </tr>
113
114 <tr>
115 <td colspan="3">&nbsp;</td>
116 </tr>
117
118 <tr>
119 <td>5.1&nbsp;<code>REDPOL</code></td>
120 <td><a href="api/edu/jas/gb/Reduction.html#normalform(java.util.List,%20edu.jas.poly.GenPolynomial)" target="classFrame"><code>gb.Reduction.normalform</code></a>,
121 <a href="api/edu/jas/gb/ReductionAbstract.html#normalform(java.util.List,%20java.util.List)" target="classFrame"><code>gb.ReductionAbstract.normalform</code></a>,
122 <a href="api/edu/jas/gb/ReductionSeq.html#normalform(java.util.List,%20java.util.List,%20edu.jas.poly.GenPolynomial)" target="classFrame"><code>gb.ReductionSeq.normalform</code></a>
123 </td>
124 <td>interface and sequential computation class, the method exists also for
125 polynomial lists and with a reduction recording matrix (this is exactly
126 <code>REDPOL</code>)
127 </td>
128 </tr>
129
130 <tr>
131 <td>5.2&nbsp;<code>REDUCTION</code></td>
132 <td><a href="api/edu/jas/gb/Reduction.html#irreducibleSet(java.util.List)" target="classFrame"><code>gb.Reduction.irreducibleSet</code></a>
133 </td>
134 <td>
135 </td>
136 </tr>
137
138 <tr>
139 <td>5.3&nbsp;<code>GR&Ouml;BNERTEST</code></td>
140 <td><a href="api/edu/jas/gb/GroebnerBase.html#isGB(java.util.List)" target="classFrame"><code>gb.GroebnerBase.isGB</code></a>
141 </td>
142 <td>provided by all classes which implement this interface
143 </td>
144 </tr>
145
146 <tr>
147 <td>5.4&nbsp;<code>GR&Ouml;BNER</code></td>
148 <td>not implemented
149 </td>
150 <td>
151 </td>
152 </tr>
153
154 <tr>
155 <td>5.5&nbsp;<code>REDGR&Ouml;BNER</code></td>
156 <td><a href="api/edu/jas/gb/GroebnerBase.html#GB(java.util.List)"
157 target="classFrame"><code>gb.GroebnerBase.GB</code></a>
158 with
159 <a href="api/edu/jas/gb/OrderedMinPairlist.html"
160 target="classFrame"><code>gb.OrderedMinPairlist</code></a>
161 </td>
162 <td>provided by all classes which implement the interface and
163 allow the selection of the pair-list in a constructor
164 </td>
165 </tr>
166
167 <tr>
168 <td>5.6&nbsp;<code>GR&Ouml;BNERNEW1</code></td>
169 <td><a href="api/edu/jas/gb/GroebnerBase.html#GB(java.util.List)"
170 target="classFrame"><code>gb.GroebnerBase.GB</code></a>
171 with
172 <a href="api/edu/jas/gb/OrderedPairlist.html"
173 target="classFrame"><code>gb.OrderedPairlist</code></a>
174 </td>
175 <td>provided by all classes which implement the interface and
176 allow the selection of the pair-list in a constructor
177 </td>
178 </tr>
179
180 <tr>
181 <td>5.7&nbsp;<code>UPDATE</code>, 5.8&nbsp;<code>GR&Ouml;BNERNEW2</code></td>
182 <td><a href="api/edu/jas/gb/GroebnerBase.html#GB(java.util.List)"
183 target="classFrame"><code>gb.GroebnerBase.GB</code></a>
184 with
185 <a href="api/edu/jas/gb/OrderedSyzPairlist.html"
186 target="classFrame"><code>gb.OrderedSyzPairlist</code></a>
187 </td>
188 <td>provided by all classes which implement the interface and
189 allow the selection of the pair-list in a constructor
190 </td>
191 </tr>
192
193 <tr>
194 <td>5.9&nbsp;<code>EXTGR&Ouml;BNER</code></td>
195 <td><a href="api/edu/jas/gb/GroebnerBase.html#extGB(java.util.List)" target="classFrame"><code>gb.GroebnerBase.extGB</code></a>
196 </td>
197 <td>provided by some classes which implement the interface
198 </td>
199 </tr>
200
201 <tr>
202 <td colspan="3">&nbsp;</td>
203 </tr>
204
205 <tr>
206 <td>6.1&nbsp;<code>ELIMINATION</code></td>
207 <td><a href="api/edu/jas/application/Ideal.html#eliminate(edu.jas.poly.GenPolynomialRing)" target="classFrame"><code>application.Ideal.eliminate</code></a>
208 </td>
209 <td>the version with the <code>String[]</code> parameter computes a Gr&ouml;bner base wrt. the
210 corresponding elimination order
211 </td>
212 </tr>
213
214 <tr>
215 <td>6.2&nbsp;<code>PROPER</code></td>
216 <td><a href="api/edu/jas/application/Ideal.html#isONE()" target="classFrame"><code>application.Ideal.isONE</code></a>
217 </td>
218 <td>proper ideal test is <code>! id.isONE()</code>
219 </td>
220 </tr>
221
222 <tr>
223 <td>6.3&nbsp;<code>INTERSECTION</code></td>
224 <td><a href="api/edu/jas/application/Ideal.html#intersect(java.util.List)" target="classFrame"><code>application.Ideal.intersect</code></a>
225 </td>
226 <td>for lists of ideals a simple iterative algorithm is used and
227 for a pair of ideals it is the same algorithm
228 </td>
229 </tr>
230
231 <tr>
232 <td>6.4&nbsp;<code>CRT</code></td>
233 <td><a href="api/edu/jas/gbufd/PolyGBUtil.html#chineseRemainderTheorem(java.util.List,%20java.util.List)" target="classFrame"><code>gbufd.PolyGBUtil.chineseRemainderTheorem</code></a>
234 </td>
235 <td>
236 </td>
237 </tr>
238
239 <tr>
240 <td>6.5&nbsp;<code>IDEALDIV1</code></td>
241 <td><a href="api/edu/jas/application/Ideal.html#quotient(edu.jas.application.Ideal)" target="classFrame"><code>application.Ideal.quotient</code></a>
242 </td>
243 <td>for an ideal a simple iterative algorithm is used and
244 for one polynomial it is an algorithm without computing syzygies
245 </td>
246 </tr>
247
248 <tr>
249 <td>6.6&nbsp;<code>IDEALDIV2</code></td>
250 <td><a href="api/edu/jas/application/Ideal.html#infiniteQuotientRab(edu.jas.poly.GenPolynomial)" target="classFrame"><code>application.Ideal.</code> <code>infiniteQuotientRab</code></a>
251 and
252 <a href="api/edu/jas/application/Ideal.html#infiniteQuotientExponent(edu.jas.poly.GenPolynomial)" target="classFrame"><code>application.Ideal.</code> <code>infiniteQuotientExponent</code></a>
253 </td>
254 <td>the exponent is computed in a separate step at the moment
255 </td>
256 </tr>
257
258 <tr>
259 <td>6.7&nbsp;<code>RADICALMEMTEST</code></td>
260 <td><a href="api/edu/jas/application/Ideal.html#isRadicalMember(edu.jas.poly.GenPolynomial)" target="classFrame"><code>application.Ideal.isRadicalMember</code></a>
261 </td>
262 <td>the exponent is not computed
263 </td>
264 </tr>
265
266 <tr>
267 <td>6.8&nbsp;<code>SUBRINGMEMTEST</code></td>
268 <td><a href="api/edu/jas/gbufd/PolyGBUtil.html#subRingAndMember(java.util.List,%20edu.jas.poly.GenPolynomial)" target="classFrame"><code>gbufd.PolyGBUtil.subRingAndMember</code></a>
269 </td>
270 <td>
271 </td>
272 </tr>
273
274 <tr>
275 <td colspan="3">&nbsp;</td>
276 </tr>
277
278 <tr>
279 <td>8.1&nbsp;<code>PREDEC</code></td>
280 <td><a href="api/edu/jas/application/Ideal.html#zeroDimDecomposition()" target="classFrame"><code>application.Ideal.</code> <code>zeroDimDecomposition</code></a>
281 </td>
282 <td>univariate polynomials of minimal degree in the ideal are irreducible
283 and not a power of an irreducible polynomial as specified in <code>PREDEC</code>
284 </td>
285 </tr>
286
287 <tr>
288 <td>8.2&nbsp;<code>ZRADICALTEST</code></td>
289 <td><a href="api/edu/jas/application/Ideal.html#isZeroDimRadical()" target="classFrame"><code>application.Ideal.isZeroDimRadical</code></a>
290 </td>
291 <td>will also work in characteritsic p &gt; 0
292 </td>
293 </tr>
294
295 <tr>
296 <td>8.3&nbsp;<code>ZRADICAL</code></td>
297 <td><a href="api/edu/jas/application/Ideal.html#radical()" target="classFrame"><code>application.Ideal.radical</code></a>
298 </td>
299 <td><code>ZRADICAL</code> is containted as special case,
300 see also <a href="api/edu/jas/application/Ideal.html#zeroDimRadicalDecomposition()" target="classFrame"><code>application.Ideal.</code> <code>zeroDimRadicalDecomposition</code></a>
301 </td>
302 </tr>
303
304 <tr>
305 <td>8.4&nbsp;<code>NORMPRIMDEC</code></td>
306 <td><a href="api/edu/jas/application/Ideal.html#zeroDimPrimaryDecomposition()" target="classFrame"><code>application.Ideal.</code> <code>zeroDimPrimaryDecomposition</code></a>
307 </td>
308 <td>contains all preprocessing steps, see <code>ZPRIMDEC</code>
309 </td>
310 </tr>
311
312 <tr>
313 <td>8.5&nbsp;<code>NORMPOS</code></td>
314 <td><a href="api/edu/jas/application/Ideal.html#normalPositionFor(int,%20int,%20java.util.List)" target="classFrame"><code>application.Ideal.normalPositionFor</code></a>
315 </td>
316 <td>one step of <code>NORMPOS</code> as explained for the modified algorithm on page 383ff
317 </td>
318 </tr>
319
320 <tr>
321 <td>8.6&nbsp;<code>ZPRIMDEC</code></td>
322 <td><a href="api/edu/jas/application/Ideal.html#zeroDimPrimaryDecomposition()" target="classFrame"><code>application.Ideal.</code> <code>zeroDimPrimaryDecomposition</code></a>
323 </td>
324 <td>returns a list of <code>PrimaryComponent</code> containers
325 </td>
326 </tr>
327
328 <tr>
329 <td>8.7&nbsp;<code>CONT</code></td>
330 <td><a href="api/edu/jas/application/Ideal.html#contraction(edu.jas.application.IdealWithUniv)" target="classFrame"><code>application.Ideal.contraction</code></a>
331 </td>
332 <td>more complicated since the permutation of variables must be considered also,
333 see <a href="api/edu/jas/application/Ideal.html#permContraction(edu.jas.application.IdealWithUniv)" target="classFrame"><code>application.Ideal.permContraction</code></a>,
334 the polynomial <code>f</code> is returned in the <code>IdealWithUniv</code> container
335 </td>
336 </tr>
337
338 <tr>
339 <td>8.8&nbsp;<code>EXTCONT</code></td>
340 <td><a href="api/edu/jas/application/Ideal.html#extension(java.lang.String[])" target="classFrame"><code>application.Ideal.extension</code></a>
341 </td>
342 <td>only <code>EXT</code>, the combination <code>EXTCONT</code> is not implemented explicitly,
343 the polynomial <code>f</code> is returned in the <code>IdealWithUniv</code> container
344 </td>
345 </tr>
346
347 <tr>
348 <td>8.9&nbsp;<code>RADICAL</code></td>
349 <td><a href="api/edu/jas/application/Ideal.html#radical()" target="classFrame"><code>application.Ideal.radical</code></a>
350 </td>
351 <td>for ideals with arbitrary dimension
352 </td>
353 </tr>
354
355 <tr>
356 <td>8.10&nbsp;<code>PRIMDEC</code></td>
357 <td><a href="api/edu/jas/application/Ideal.html#primaryDecomposition()" target="classFrame"><code>application.Ideal.</code> <code>primaryDecomposition</code></a>
358 </td>
359 <td>for ideals with arbitrary dimension
360 </td>
361 </tr>
362
363 <tr>
364 <td colspan="3"></td>
365 </tr>
366
367 <tr>
368 <td>8.11&nbsp;<code>VARSIGN</code></td>
369 <td><a href="api/edu/jas/root/RootUtil.html#signVar(java.util.List)" target="classFrame"><code>root.RootUtil.signVar</code></a>
370 </td>
371 <td>
372 </td>
373 </tr>
374
375 <tr>
376 <td>8.12&nbsp;<code>STURMSEQ</code></td>
377 <td><a href="api/edu/jas/root/RealRootsSturm.html#sturmSequence(edu.jas.poly.GenPolynomial)" target="classFrame"><code>root.RealRootsSturm.sturmSequence</code></a>
378 </td>
379 <td>
380 </td>
381 </tr>
382
383 <tr>
384 <td>8.13&nbsp;<code>ISOLATE</code></td>
385 <td>
386 <a href="api/edu/jas/root/RealRoots.html#realRoots(edu.jas.poly.GenPolynomial)" target="classFrame"><code>root.RealRoots.realRoots</code></a>
387 </td>
388 <td>could also be used for real root isolations not using Sturm sequences
389 </td>
390 </tr>
391
392 <tr>
393 <td>8.14&nbsp;<code>ISOREC</code></td>
394 <td>
395 <a href="api/edu/jas/root/RealRootsSturm.html#realRoots(edu.jas.root.Interval,%20java.util.List)" target="classFrame"><code>root.RealRootsSturm.realRoots</code></a>
396 </td>
397 <td>interval bi-section until a root is isolated
398 </td>
399 </tr>
400
401 <tr>
402 <td>8.15&nbsp;<code>ISOREFINE</code></td>
403 <td>
404 <a href="api/edu/jas/root/RealRoots.html#refineInterval(edu.jas.root.Interval,%20edu.jas.poly.GenPolynomial,%20C)" target="classFrame"><code>root.RealRoots.refineInterval</code></a>
405 </td>
406 <td>also for real root isolations not using Sturm sequences
407 </td>
408 </tr>
409
410 <tr>
411 <td>8.16&nbsp;<code>SQUEEZE</code></td>
412 <td><a href="api/edu/jas/root/RealRoots.html#invariantMagnitudeInterval(edu.jas.root.Interval,%20edu.jas.poly.GenPolynomial,%20edu.jas.poly.GenPolynomial,%20C)" target="classFrame"><code>root.RealRoots.</code> <code>invariantMagnitudeInterval</code></a>
413 </td>
414 <td>see also
415 <a href="api/edu/jas/root/RealRoots.html#realMagnitude(edu.jas.root.Interval,%20edu.jas.poly.GenPolynomial,%20edu.jas.poly.GenPolynomial,%20C)" target="classFrame"><code>root.RealRoots.</code> <code>realMagnitude</code></a>
416 </td>
417 </tr>
418
419 <tr>
420 <td>8.17&nbsp;<code>REALZEROS</code></td>
421 <td><a href="api/edu/jas/application/PolyUtilApp.html#realAlgebraicRoots(edu.jas.application.Ideal)" target="classFrame"><code>application.PolyUtilApp.</code> <code>realAlgebraicRoots</code></a>
422 </td>
423 <td>different algorithm and different result data structure with <code>RealAlgebraicNumbers</code>
424 </td>
425 </tr>
426
427 <tr>
428 <td colspan="3">&nbsp;</td>
429 </tr>
430
431 <tr>
432 <td>9.1&nbsp;<code>REDTERMS</code></td>
433 <td><a href="api/edu/jas/gbufd/GroebnerBaseFGLM.html#redTerms(java.util.List)" target="classFrame"><code>gbufd.GroebnerBaseFGLM.redTerms</code></a>
434 </td>
435 <td>
436 </td>
437 </tr>
438
439 <tr>
440 <td>9.2&nbsp;<code>UNIVPOL</code></td>
441 <td><a href="api/edu/jas/application/Ideal.html#constructUnivariate(int)" target="classFrame"><code>application.Ideal.</code> <code>constructUnivariate</code></a>
442 </td>
443 <td>
444 </td>
445 </tr>
446
447 <tr>
448 <td>9.3&nbsp;<code>CONVGR&Ouml;BNER</code></td>
449 <td><a href="api/edu/jas/gbufd/GroebnerBaseFGLM.html#convGroebnerToLex(java.util.List)" target="classFrame"><code>gbufd.GroebnerBaseFGLM.</code> <code>convGroebnerToLex</code></a>
450 </td>
451 <td>
452 See also <a href="api/edu/jas/gbufd/GroebnerBaseFGLM.html#GB(int, java.util.List)" target="classFrame"><code>gbufd.GroebnerBaseFGLM.GB</code></a>. It computes a Gr&ouml;bner base with respect to a graded term order and then uses FGLM to convert to a lexicographic term order.
453
454 See also <a href="api/edu/jas/gbufd/GroebnerBaseWalk.html#GB(int, java.util.List)" target="classFrame"><code>gbufd.GroebnerBaseWalk.GB</code></a>. It computes a Gr&ouml;bner base with respect to a term order <code>t1</code> and then uses Gr&ouml;bner Walk to convert to a GB with term order <code>t2</code>.
455 </td>
456 </tr>
457
458 <tr>
459 <td>9.4&nbsp;<code>LMINTERM</code></td>
460 <td><a href="api/edu/jas/gbufd/GroebnerBaseFGLM.html#lMinterm(java.util.List, edu.jas.poly.GenPolynomial)" target="classFrame"><code>gbufd.GroebnerBaseFGLM.lMinterm</code></a>
461 </td>
462 <td>
463 </td>
464 </tr>
465
466 <tr>
467 <td>9.5&nbsp;<code>STRCONST</code></td>
468 <td><a href="" target="classFrame"><code></code></a>
469 not implemented
470 </td>
471 <td>
472 </td>
473 </tr>
474
475 <tr>
476 <td>9.6&nbsp;<code>DIMENSION</code></td>
477 <td><a href="api/edu/jas/application/Ideal.html#dimension()" target="classFrame"><code>application.Ideal.dimension</code></a>
478 </td>
479 <td>
480 </td>
481 </tr>
482
483 <tr>
484 <td colspan="3">&nbsp;</td>
485 </tr>
486
487 <tr>
488 <td>10.1&nbsp;<code>D-GR&Ouml;BNER</code></td>
489 <td><a href="api/edu/jas/gb/DGroebnerBaseSeq.html#GB(int,%20java.util.List)" target="classFrame"><code>gb.DGroebnerBaseSeq.GB</code></a>
490 and
491 <a href="api/edu/jas/gb/EGroebnerBaseSeq.html#GB(int,%20java.util.List)" target="classFrame"><code>gb.EGroebnerBaseSeq.GB</code></a>
492 </td>
493 <td>
494 </td>
495 </tr>
496
497 </table>
498
499 <p>
500 </p>
501
502
503 <!--
504 <code></code>
505 <p>
506 </p>
507 <p>
508 </p>
509 <pre>
510 </pre>
511 -->
512
513 <p><!--a href="README" target="readme" >README</a-->
514 <!--a href="" target="classFrame"><code></code></a-->
515 </p>
516
517 <hr />
518 <address><a href="mailto:kredel at rz.uni-mannheim.de">Heinz Kredel</a></address>
519 <p>
520 <!-- Created: Sun May 23 13:14:59 CEST 2010 -->
521 <!-- hhmts start -->
522 Last modified: Thu Jul 8 17:47:59 CEST 2021
523 <!-- hhmts end -->
524 </p>
525 <!--p align="right" >
526 $Id$
527 </p-->
528 </body>
529 </html>