source: CGBLisp/latex-doc/manual/node2.html@ 1

Last change on this file since 1 was 1, checked in by Marek Rychlik, 15 years ago

First import of a version circa 1997.
File size: 63.9 KB
Line 
1<!--Converted with LaTeX2HTML 97.1 (release) (July 13th, 1997)
2 by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds
3* revised and updated by: Marcus Hennecke, Ross Moore, Herb Swan
4* with significant contributions from:
5 Jens Lippman, Marek Rouchal, Martin Wilck and others -->
6<HTML>
7<HEAD>
8<TITLE>The Gr&#246;bner Basis package</TITLE>
9<META NAME="description" CONTENT="The Gr&#246;bner Basis package">
10<META NAME="keywords" CONTENT="manual">
11<META NAME="resource-type" CONTENT="document">
12<META NAME="distribution" CONTENT="global">
13<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso_8859_1">
14<LINK REL="STYLESHEET" HREF="manual.css">
15<LINK REL="next" HREF="node3.html">
16<LINK REL="previous" HREF="node1.html">
17<LINK REL="up" HREF="manual.html">
18<LINK REL="next" HREF="node3.html">
19</HEAD>
20<BODY bgcolor="#ffffff">
21<!--Navigation Panel-->
22<A NAME="tex2html742"
23 HREF="node3.html">
24<IMG WIDTH="37" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="next" SRC="next_motif.gif"></A>
25<A NAME="tex2html739"
26 HREF="manual.html">
27<IMG WIDTH="26" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="up" SRC="up_motif.gif"></A>
28<A NAME="tex2html733"
29 HREF="node1.html">
30<IMG WIDTH="63" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="previous" SRC="previous_motif.gif"></A>
31<A NAME="tex2html741"
32 HREF="node1.html">
33<IMG WIDTH="65" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="contents" SRC="contents_motif.gif"></A>
34<BR>
35<B> Next:</B> <A NAME="tex2html743"
36 HREF="node3.html">The String Interface to</A>
37<B> Up:</B> <A NAME="tex2html740"
38 HREF="manual.html">CGBLisp User Guide and</A>
39<B> Previous:</B> <A NAME="tex2html734"
40 HREF="node1.html">Contents</A>
41<BR>
42<BR>
43<!--End of Navigation Panel-->
44<!--Table of Child-Links-->
45<A NAME="CHILD_LINKS"><strong>Subsections</strong></A>
46<UL>
47<LI><A NAME="tex2html744"
48 HREF="node2.html#SECTION00020010000000000000">
49<I>*grobner<MATH CLASS="INLINE">
50-
51</MATH>debug*</I></A>
52<LI><A NAME="tex2html745"
53 HREF="node2.html#SECTION00020020000000000000">
54<I>*buchberger<MATH CLASS="INLINE">
55-
56</MATH>merge<MATH CLASS="INLINE">
57-
58</MATH>pairs*</I></A>
59<LI><A NAME="tex2html746"
60 HREF="node2.html#SECTION00020030000000000000">
61<I>*gebauer<MATH CLASS="INLINE">
62-
63</MATH>moeller<MATH CLASS="INLINE">
64-
65</MATH>merge<MATH CLASS="INLINE">
66-
67</MATH>pairs*</I></A>
68<LI><A NAME="tex2html747"
69 HREF="node2.html#SECTION00020040000000000000">
70<I>*grobner<MATH CLASS="INLINE">
71-
72</MATH>function*</I></A>
73<LI><A NAME="tex2html748"
74 HREF="node2.html#SECTION00020050000000000000">
75<I>select<MATH CLASS="INLINE">
76-
77</MATH>grobner<MATH CLASS="INLINE">
78-
79</MATH>algorithm</I></A>
80<LI><A NAME="tex2html749"
81 HREF="node2.html#SECTION00020060000000000000">
82<I>grobner</I></A>
83<LI><A NAME="tex2html750"
84 HREF="node2.html#SECTION00020070000000000000">
85<I>debug<MATH CLASS="INLINE">
86-
87</MATH>cgb</I></A>
88<LI><A NAME="tex2html751"
89 HREF="node2.html#SECTION00020080000000000000">
90<I>spoly</I></A>
91<LI><A NAME="tex2html752"
92 HREF="node2.html#SECTION00020090000000000000">
93<I>grobner<MATH CLASS="INLINE">
94-
95</MATH>primitive<MATH CLASS="INLINE">
96-
97</MATH>part</I></A>
98<LI><A NAME="tex2html753"
99 HREF="node2.html#SECTION000200100000000000000">
100<I>grobner<MATH CLASS="INLINE">
101-
102</MATH>content</I></A>
103<LI><A NAME="tex2html754"
104 HREF="node2.html#SECTION000200110000000000000">
105<I>normal<MATH CLASS="INLINE">
106-
107</MATH>form</I></A>
108<LI><A NAME="tex2html755"
109 HREF="node2.html#SECTION000200120000000000000">
110<I>buchberger</I></A>
111<LI><A NAME="tex2html756"
112 HREF="node2.html#SECTION000200130000000000000">
113<I>grobner<MATH CLASS="INLINE">
114-
115</MATH>op</I></A>
116<LI><A NAME="tex2html757"
117 HREF="node2.html#SECTION000200140000000000000">
118<I>buchberger<MATH CLASS="INLINE">
119-
120</MATH>sort<MATH CLASS="INLINE">
121-
122</MATH>pairs</I></A>
123<LI><A NAME="tex2html758"
124 HREF="node2.html#SECTION000200150000000000000">
125<I>mock<MATH CLASS="INLINE">
126-
127</MATH>spoly</I></A>
128<LI><A NAME="tex2html759"
129 HREF="node2.html#SECTION000200160000000000000">
130<I>buchberger<MATH CLASS="INLINE">
131-
132</MATH>merge<MATH CLASS="INLINE">
133-
134</MATH>pairs<MATH CLASS="INLINE">
135-
136</MATH>use<MATH CLASS="INLINE">
137-
138</MATH>mock<MATH CLASS="INLINE">
139-
140</MATH>spoly</I></A>
141<LI><A NAME="tex2html760"
142 HREF="node2.html#SECTION000200170000000000000">
143<I>buchberger<MATH CLASS="INLINE">
144-
145</MATH>merge<MATH CLASS="INLINE">
146-
147</MATH>pairs<MATH CLASS="INLINE">
148-
149</MATH>smallest<MATH CLASS="INLINE">
150-
151</MATH>lcm</I></A>
152<LI><A NAME="tex2html761"
153 HREF="node2.html#SECTION000200180000000000000">
154<I>buchberger<MATH CLASS="INLINE">
155-
156</MATH>merge<MATH CLASS="INLINE">
157-
158</MATH>pairs<MATH CLASS="INLINE">
159-
160</MATH>use<MATH CLASS="INLINE">
161-
162</MATH>smallest<MATH CLASS="INLINE">
163-
164</MATH>degree</I></A>
165<LI><A NAME="tex2html762"
166 HREF="node2.html#SECTION000200190000000000000">
167<I>buchberger<MATH CLASS="INLINE">
168-
169</MATH>merge<MATH CLASS="INLINE">
170-
171</MATH>pairs<MATH CLASS="INLINE">
172-
173</MATH>use<MATH CLASS="INLINE">
174-
175</MATH>smallest<MATH CLASS="INLINE">
176-
177</MATH>length</I></A>
178<LI><A NAME="tex2html763"
179 HREF="node2.html#SECTION000200200000000000000">
180<I>buchberger<MATH CLASS="INLINE">
181-
182</MATH>merge<MATH CLASS="INLINE">
183-
184</MATH>pairs<MATH CLASS="INLINE">
185-
186</MATH>use<MATH CLASS="INLINE">
187-
188</MATH>smallest<MATH CLASS="INLINE">
189-
190</MATH>coefficient<MATH CLASS="INLINE">
191-
192</MATH>length</I></A>
193<LI><A NAME="tex2html764"
194 HREF="node2.html#SECTION000200210000000000000">
195<I>buchberger<MATH CLASS="INLINE">
196-
197</MATH>set<MATH CLASS="INLINE">
198-
199</MATH>pair<MATH CLASS="INLINE">
200-
201</MATH>heuristic</I></A>
202<LI><A NAME="tex2html765"
203 HREF="node2.html#SECTION000200220000000000000">
204<I>criterion<MATH CLASS="INLINE">
205-
206</MATH>1</I></A>
207<LI><A NAME="tex2html766"
208 HREF="node2.html#SECTION000200230000000000000">
209<I>criterion<MATH CLASS="INLINE">
210-
211</MATH>2</I></A>
212<LI><A NAME="tex2html767"
213 HREF="node2.html#SECTION000200240000000000000">
214<I>normalize<MATH CLASS="INLINE">
215-
216</MATH>poly</I></A>
217<LI><A NAME="tex2html768"
218 HREF="node2.html#SECTION000200250000000000000">
219<I>normalize<MATH CLASS="INLINE">
220-
221</MATH>basis</I></A>
222<LI><A NAME="tex2html769"
223 HREF="node2.html#SECTION000200260000000000000">
224<I>reduction</I></A>
225<LI><A NAME="tex2html770"
226 HREF="node2.html#SECTION000200270000000000000">
227<I>reduced<MATH CLASS="INLINE">
228-
229</MATH>grobner</I></A>
230<LI><A NAME="tex2html771"
231 HREF="node2.html#SECTION000200280000000000000">
232<I>monom<MATH CLASS="INLINE">
233-
234</MATH>depends<MATH CLASS="INLINE">
235-
236</MATH>p</I></A>
237<LI><A NAME="tex2html772"
238 HREF="node2.html#SECTION000200290000000000000">
239<I>term<MATH CLASS="INLINE">
240-
241</MATH>depends<MATH CLASS="INLINE">
242-
243</MATH>p</I></A>
244<LI><A NAME="tex2html773"
245 HREF="node2.html#SECTION000200300000000000000">
246<I>poly<MATH CLASS="INLINE">
247-
248</MATH>depends<MATH CLASS="INLINE">
249-
250</MATH>p</I></A>
251<LI><A NAME="tex2html774"
252 HREF="node2.html#SECTION000200310000000000000">
253<I>ring<MATH CLASS="INLINE">
254-
255</MATH>intersection</I></A>
256<LI><A NAME="tex2html775"
257 HREF="node2.html#SECTION000200320000000000000">
258<I>elimination<MATH CLASS="INLINE">
259-
260</MATH>ideal</I></A>
261<LI><A NAME="tex2html776"
262 HREF="node2.html#SECTION000200330000000000000">
263<I>ideal<MATH CLASS="INLINE">
264-
265</MATH>intersection</I></A>
266<LI><A NAME="tex2html777"
267 HREF="node2.html#SECTION000200340000000000000">
268<I>poly<MATH CLASS="INLINE">
269-
270</MATH>contract</I></A>
271<LI><A NAME="tex2html778"
272 HREF="node2.html#SECTION000200350000000000000">
273<I>poly<MATH CLASS="INLINE">
274-
275</MATH>lcm</I></A>
276<LI><A NAME="tex2html779"
277 HREF="node2.html#SECTION000200360000000000000">
278<I>grobner<MATH CLASS="INLINE">
279-
280</MATH>gcd</I></A>
281<LI><A NAME="tex2html780"
282 HREF="node2.html#SECTION000200370000000000000">
283<I>grobner<MATH CLASS="INLINE">
284-
285</MATH>equal</I></A>
286<LI><A NAME="tex2html781"
287 HREF="node2.html#SECTION000200380000000000000">
288<I>grobner<MATH CLASS="INLINE">
289-
290</MATH>subsetp</I></A>
291<LI><A NAME="tex2html782"
292 HREF="node2.html#SECTION000200390000000000000">
293<I>grobner<MATH CLASS="INLINE">
294-
295</MATH>member</I></A>
296<LI><A NAME="tex2html783"
297 HREF="node2.html#SECTION000200400000000000000">
298<I>ideal<MATH CLASS="INLINE">
299-
300</MATH>equal</I></A>
301<LI><A NAME="tex2html784"
302 HREF="node2.html#SECTION000200410000000000000">
303<I>ideal<MATH CLASS="INLINE">
304-
305</MATH>subsetp</I></A>
306<LI><A NAME="tex2html785"
307 HREF="node2.html#SECTION000200420000000000000">
308<I>ideal<MATH CLASS="INLINE">
309-
310</MATH>member</I></A>
311<LI><A NAME="tex2html786"
312 HREF="node2.html#SECTION000200430000000000000">
313<I>ideal<MATH CLASS="INLINE">
314-
315</MATH>saturation<MATH CLASS="INLINE">
316-
317</MATH>1</I></A>
318<LI><A NAME="tex2html787"
319 HREF="node2.html#SECTION000200440000000000000">
320<I>add<MATH CLASS="INLINE">
321-
322</MATH>variables</I></A>
323<LI><A NAME="tex2html788"
324 HREF="node2.html#SECTION000200450000000000000">
325<I>extend<MATH CLASS="INLINE">
326-
327</MATH>polynomials</I></A>
328<LI><A NAME="tex2html789"
329 HREF="node2.html#SECTION000200460000000000000">
330<I>saturation<MATH CLASS="INLINE">
331-
332</MATH>extension</I></A>
333<LI><A NAME="tex2html790"
334 HREF="node2.html#SECTION000200470000000000000">
335<I>polysaturation<MATH CLASS="INLINE">
336-
337</MATH>extension</I></A>
338<LI><A NAME="tex2html791"
339 HREF="node2.html#SECTION000200480000000000000">
340<I>saturation<MATH CLASS="INLINE">
341-
342</MATH>extension<MATH CLASS="INLINE">
343-
344</MATH>1</I></A>
345<LI><A NAME="tex2html792"
346 HREF="node2.html#SECTION000200490000000000000">
347<I>ideal<MATH CLASS="INLINE">
348-
349</MATH>polysaturation<MATH CLASS="INLINE">
350-
351</MATH>1</I></A>
352<LI><A NAME="tex2html793"
353 HREF="node2.html#SECTION000200500000000000000">
354<I>ideal<MATH CLASS="INLINE">
355-
356</MATH>saturation</I></A>
357<LI><A NAME="tex2html794"
358 HREF="node2.html#SECTION000200510000000000000">
359<I>ideal<MATH CLASS="INLINE">
360-
361</MATH>polysaturation</I></A>
362<LI><A NAME="tex2html795"
363 HREF="node2.html#SECTION000200520000000000000">
364<I>buchberger<MATH CLASS="INLINE">
365-
366</MATH>criterion</I></A>
367<LI><A NAME="tex2html796"
368 HREF="node2.html#SECTION000200530000000000000">
369<I>grobner<MATH CLASS="INLINE">
370-
371</MATH>test</I></A>
372<LI><A NAME="tex2html797"
373 HREF="node2.html#SECTION000200540000000000000">
374<I>minimization</I></A>
375<LI><A NAME="tex2html798"
376 HREF="node2.html#SECTION000200550000000000000">
377<I>add<MATH CLASS="INLINE">
378-
379</MATH>minimized</I></A>
380<LI><A NAME="tex2html799"
381 HREF="node2.html#SECTION000200560000000000000">
382<I>colon<MATH CLASS="INLINE">
383-
384</MATH>ideal</I></A>
385<LI><A NAME="tex2html800"
386 HREF="node2.html#SECTION000200570000000000000">
387<I>colon<MATH CLASS="INLINE">
388-
389</MATH>ideal<MATH CLASS="INLINE">
390-
391</MATH>1</I></A>
392<LI><A NAME="tex2html801"
393 HREF="node2.html#SECTION000200580000000000000">
394<I>pseudo<MATH CLASS="INLINE">
395-
396</MATH>divide</I></A>
397<LI><A NAME="tex2html802"
398 HREF="node2.html#SECTION000200590000000000000">
399<I>gebauer<MATH CLASS="INLINE">
400-
401</MATH>moeller</I></A>
402<LI><A NAME="tex2html803"
403 HREF="node2.html#SECTION000200600000000000000">
404<I>update</I></A>
405<LI><A NAME="tex2html804"
406 HREF="node2.html#SECTION000200610000000000000">
407<I>gebauer<MATH CLASS="INLINE">
408-
409</MATH>moeller<MATH CLASS="INLINE">
410-
411</MATH>merge<MATH CLASS="INLINE">
412-
413</MATH>pairs<MATH CLASS="INLINE">
414-
415</MATH>use<MATH CLASS="INLINE">
416-
417</MATH>mock<MATH CLASS="INLINE">
418-
419</MATH>spoly</I></A>
420<LI><A NAME="tex2html805"
421 HREF="node2.html#SECTION000200620000000000000">
422<I>gebauer<MATH CLASS="INLINE">
423-
424</MATH>moeller<MATH CLASS="INLINE">
425-
426</MATH>merge<MATH CLASS="INLINE">
427-
428</MATH>pairs<MATH CLASS="INLINE">
429-
430</MATH>smallest<MATH CLASS="INLINE">
431-
432</MATH>lcm</I></A>
433<LI><A NAME="tex2html806"
434 HREF="node2.html#SECTION000200630000000000000">
435<I>gebauer<MATH CLASS="INLINE">
436-
437</MATH>moeller<MATH CLASS="INLINE">
438-
439</MATH>merge<MATH CLASS="INLINE">
440-
441</MATH>pairs<MATH CLASS="INLINE">
442-
443</MATH>use<MATH CLASS="INLINE">
444-
445</MATH>smallest<MATH CLASS="INLINE">
446-
447</MATH>degree</I></A>
448<LI><A NAME="tex2html807"
449 HREF="node2.html#SECTION000200640000000000000">
450<I>gebauer<MATH CLASS="INLINE">
451-
452</MATH>moeller<MATH CLASS="INLINE">
453-
454</MATH>merge<MATH CLASS="INLINE">
455-
456</MATH>pairs<MATH CLASS="INLINE">
457-
458</MATH>use<MATH CLASS="INLINE">
459-
460</MATH>smallest<MATH CLASS="INLINE">
461-
462</MATH>length</I></A>
463<LI><A NAME="tex2html808"
464 HREF="node2.html#SECTION000200650000000000000">
465<I>gebauer<MATH CLASS="INLINE">
466-
467</MATH>moeller<MATH CLASS="INLINE">
468-
469</MATH>merge<MATH CLASS="INLINE">
470-
471</MATH>pairs<MATH CLASS="INLINE">
472-
473</MATH>use<MATH CLASS="INLINE">
474-
475</MATH>smallest<MATH CLASS="INLINE">
476-
477</MATH>coefficient<MATH CLASS="INLINE">
478-
479</MATH>length</I></A>
480<LI><A NAME="tex2html809"
481 HREF="node2.html#SECTION000200660000000000000">
482<I>gebauer<MATH CLASS="INLINE">
483-
484</MATH>moeller<MATH CLASS="INLINE">
485-
486</MATH>set<MATH CLASS="INLINE">
487-
488</MATH>pair<MATH CLASS="INLINE">
489-
490</MATH>heuristic</I></A>
491<LI><A NAME="tex2html810"
492 HREF="node2.html#SECTION000200670000000000000">
493<I>spoly<MATH CLASS="INLINE">
494-
495</MATH>sugar</I></A>
496<LI><A NAME="tex2html811"
497 HREF="node2.html#SECTION000200680000000000000">
498<I>spoly<MATH CLASS="INLINE">
499-
500</MATH>with<MATH CLASS="INLINE">
501-
502</MATH>sugar</I></A>
503<LI><A NAME="tex2html812"
504 HREF="node2.html#SECTION000200690000000000000">
505<I>normal<MATH CLASS="INLINE">
506-
507</MATH>form<MATH CLASS="INLINE">
508-
509</MATH>with<MATH CLASS="INLINE">
510-
511</MATH>sugar</I></A>
512<LI><A NAME="tex2html813"
513 HREF="node2.html#SECTION000200700000000000000">
514<I>buchberger<MATH CLASS="INLINE">
515-
516</MATH>with<MATH CLASS="INLINE">
517-
518</MATH>sugar</I></A>
519<LI><A NAME="tex2html814"
520 HREF="node2.html#SECTION000200710000000000000">
521<I>buchberger<MATH CLASS="INLINE">
522-
523</MATH>with<MATH CLASS="INLINE">
524-
525</MATH>sugar<MATH CLASS="INLINE">
526-
527</MATH>merge<MATH CLASS="INLINE">
528-
529</MATH>pairs</I></A>
530<LI><A NAME="tex2html815"
531 HREF="node2.html#SECTION000200720000000000000">
532<I>buchberger<MATH CLASS="INLINE">
533-
534</MATH>with<MATH CLASS="INLINE">
535-
536</MATH>sugar<MATH CLASS="INLINE">
537-
538</MATH>sort<MATH CLASS="INLINE">
539-
540</MATH>pairs</I></A>
541<LI><A NAME="tex2html816"
542 HREF="node2.html#SECTION000200730000000000000">
543<I>criterion<MATH CLASS="INLINE">
544-
545</MATH>1<MATH CLASS="INLINE">
546-
547</MATH>with<MATH CLASS="INLINE">
548-
549</MATH>sugar</I></A>
550<LI><A NAME="tex2html817"
551 HREF="node2.html#SECTION000200740000000000000">
552<I>criterion<MATH CLASS="INLINE">
553-
554</MATH>2<MATH CLASS="INLINE">
555-
556</MATH>with<MATH CLASS="INLINE">
557-
558</MATH>sugar</I></A>
559<LI><A NAME="tex2html818"
560 HREF="node2.html#SECTION000200750000000000000">
561<I>gebauer<MATH CLASS="INLINE">
562-
563</MATH>moeller<MATH CLASS="INLINE">
564-
565</MATH>with<MATH CLASS="INLINE">
566-
567</MATH>sugar</I></A>
568<LI><A NAME="tex2html819"
569 HREF="node2.html#SECTION000200760000000000000">
570<I>update<MATH CLASS="INLINE">
571-
572</MATH>with<MATH CLASS="INLINE">
573-
574</MATH>sugar</I></A>
575<LI><A NAME="tex2html820"
576 HREF="node2.html#SECTION000200770000000000000">
577<I>gebauer<MATH CLASS="INLINE">
578-
579</MATH>moeller<MATH CLASS="INLINE">
580-
581</MATH>with<MATH CLASS="INLINE">
582-
583</MATH>sugar<MATH CLASS="INLINE">
584-
585</MATH>merge<MATH CLASS="INLINE">
586-
587</MATH>pairs</I></A>
588<LI><A NAME="tex2html821"
589 HREF="node2.html#SECTION000200780000000000000">
590<I>grobner<MATH CLASS="INLINE">
591-
592</MATH>primitive<MATH CLASS="INLINE">
593-
594</MATH>part<MATH CLASS="INLINE">
595-
596</MATH>with<MATH CLASS="INLINE">
597-
598</MATH>sugar</I></A>
599</UL>
600<!--End of Table of Child-Links-->
601<HR>
602<H1><A NAME="SECTION00020000000000000000">
603The Gr&#246;bner Basis package</A>
604</H1>
605<H4><A NAME="SECTION00020010000000000000">
606<I>*grobner<MATH CLASS="INLINE">
607-
608</MATH>debug*</I></A>
609</H4>
610<P><IMG WIDTH="495" HEIGHT="27" ALIGN="MIDDLE" BORDER="0"
611 SRC="img1.gif"
612 ALT="$\textstyle\parbox{\pboxargslen}{\em nil \/}$"> [<EM>VARIABLE</EM>]
613<BLOCKQUOTE>
614If T, produce debugging and tracing output.</BLOCKQUOTE><H4><A NAME="SECTION00020020000000000000">
615<I>*buchberger<MATH CLASS="INLINE">
616-
617</MATH>merge<MATH CLASS="INLINE">
618-
619</MATH>pairs*</I></A>
620</H4>
621<P><IMG WIDTH="425" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
622 SRC="img2.gif"
623 ALT="$\textstyle\parbox{\pboxargslen}{\em 'buchberger$-$merge$-$pairs$-$smallest$-$lcm \/}$"> [<EM>VARIABLE</EM>]
624<BLOCKQUOTE>
625A variable holding the predicate used to sort critical pairs
626in the order of decreasing priority for the Buchberger algorithm.</BLOCKQUOTE><H4><A NAME="SECTION00020030000000000000">
627<I>*gebauer<MATH CLASS="INLINE">
628-
629</MATH>moeller<MATH CLASS="INLINE">
630-
631</MATH>merge<MATH CLASS="INLINE">
632-
633</MATH>pairs*</I></A>
634</H4>
635<P><IMG WIDTH="384" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
636 SRC="img3.gif"
637 ALT="$\textstyle\parbox{\pboxargslen}{\em 'gebauer$-$moeller$-$merge$-$pairs$-$use$-$mock$-$spoly \/}$"> [<EM>VARIABLE</EM>]
638<BLOCKQUOTE>
639A variable holding the predicate used to sort critical pairs
640in the order of decreasing priority for the Gebauer<MATH CLASS="INLINE">
641-
642</MATH>Moeller
643algorithm </BLOCKQUOTE><H4><A NAME="SECTION00020040000000000000">
644<I>*grobner<MATH CLASS="INLINE">
645-
646</MATH>function*</I></A>
647</H4>
648<P><IMG WIDTH="480" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
649 SRC="img4.gif"
650 ALT="$\textstyle\parbox{\pboxargslen}{\em 'buchberger \/}$"> [<EM>VARIABLE</EM>]
651<BLOCKQUOTE>
652The name of the function used to calculate Grobner basis</BLOCKQUOTE><H4><A NAME="SECTION00020050000000000000">
653<I>select<MATH CLASS="INLINE">
654-
655</MATH>grobner<MATH CLASS="INLINE">
656-
657</MATH>algorithm</I></A>
658</H4>
659<P><IMG WIDTH="429" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
660 SRC="img5.gif"
661 ALT="$\textstyle\parbox{\pboxargslen}{\em algorithm \/}$"> [<EM>FUNCTION</EM>]
662<BLOCKQUOTE>
663Select one of the several implementations of the Grobner basis
664algorithm.</BLOCKQUOTE><H4><A NAME="SECTION00020060000000000000">
665<I>grobner</I></A>
666</H4>
667<P><IMG WIDTH="559" HEIGHT="50" ALIGN="MIDDLE" BORDER="0"
668 SRC="img6.gif"
669 ALT="$\textstyle\parbox{\pboxargslen}{\em f {\sf \&optional} (pred \char93 'lex$\gt$) (start
670 0) (top$-$reduction$-$only
671 nil) (ring
672 *coefficient$-$ring*) \/}$"> [<EM>FUNCTION</EM>]
673<BLOCKQUOTE>
674Return Grobner basis of an ideal generated by polynomial list F.
675Assume that the monomials of each polynomial are ordered according to
676the admissible monomial order PRED. The result will be a list of
677polynomials ordered as well according to PRED. The polynomials from 0
678to START<MATH CLASS="INLINE">
679-
680</MATH>1 in the list F are assumed to be a Grobner basis, and
681thus certain critical pairs do not have to be calculated. If
682TOP<MATH CLASS="INLINE">
683-
684</MATH>REDUCTION<MATH CLASS="INLINE">
685-
686</MATH>ONLY is not NIL then only top reductions will be
687performed, instead of full division, and thus the returned Grobner
688basis will have its polynomials only top<MATH CLASS="INLINE">
689-
690</MATH>reduced with respect to
691the preceding polynomials. RING should be set to the RING structure
692(see COEFFICIENT<MATH CLASS="INLINE">
693-
694</MATH>RING package) corresponding to the coefficients of
695the polynomials in the list F. This function is currently just an
696interface to several algorithms which fine Grobner bases. Use
697SELECT<MATH CLASS="INLINE">
698-
699</MATH>GROBNER<MATH CLASS="INLINE">
700-
701</MATH>ALGORITHM in order to change the algorithm.</BLOCKQUOTE><H4><A NAME="SECTION00020070000000000000">
702<I>debug<MATH CLASS="INLINE">
703-
704</MATH>cgb</I></A>
705</H4>
706<P><IMG WIDTH="576" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
707 SRC="img7.gif"
708 ALT="$\textstyle\parbox{\pboxargslen}{\em {\sf \&rest} args \/}$"> [<EM>MACRO</EM>]
709<BLOCKQUOTE>
710This macro is used in printing debugging and tracing messages
711and its arguments are analogous to the FORMAT function, except
712that the stream argument is omitted. By default, the output is
713sent to *trace<MATH CLASS="INLINE">
714-
715</MATH>output*, which can be set to produce output
716in a file.</BLOCKQUOTE><H4><A NAME="SECTION00020080000000000000">
717<I>spoly</I></A>
718</H4>
719<P><IMG WIDTH="576" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
720 SRC="img8.gif"
721 ALT="$\textstyle\parbox{\pboxargslen}{\em f g pred ring \/}$"> [<EM>FUNCTION</EM>]
722<BLOCKQUOTE>
723Return the S<MATH CLASS="INLINE">
724-
725</MATH>polynomial of F and G, which should
726be two polynomials with terms ordered by PRED and
727coefficients in a ring whose operations are the slots
728of the RING structure.</BLOCKQUOTE><H4><A NAME="SECTION00020090000000000000">
729<I>grobner<MATH CLASS="INLINE">
730-
731</MATH>primitive<MATH CLASS="INLINE">
732-
733</MATH>part</I></A>
734</H4>
735<P><IMG WIDTH="446" HEIGHT="28" ALIGN="MIDDLE" BORDER="0"
736 SRC="img9.gif"
737 ALT="$\textstyle\parbox{\pboxargslen}{\em p ring \/}$"> [<EM>FUNCTION</EM>]
738<BLOCKQUOTE>
739Divide polynomial P with integer coefficients by gcd of its
740coefficients and return the result. Use the RING structure from the
741COEFFICIENT<MATH CLASS="INLINE">
742-
743</MATH>RING package to perform the operations on the
744coefficients.</BLOCKQUOTE><H4><A NAME="SECTION000200100000000000000">
745<I>grobner<MATH CLASS="INLINE">
746-
747</MATH>content</I></A>
748</H4>
749<P><IMG WIDTH="446" HEIGHT="28" ALIGN="MIDDLE" BORDER="0"
750 SRC="img9.gif"
751 ALT="$\textstyle\parbox{\pboxargslen}{\em p ring \/}$"> [<EM>FUNCTION</EM>]
752<BLOCKQUOTE>
753Greatest common divisor of the coefficients of the polynomial P. Use
754the RING structure to compute the greatest common divisor.</BLOCKQUOTE><H4><A NAME="SECTION000200110000000000000">
755<I>normal<MATH CLASS="INLINE">
756-
757</MATH>form</I></A>
758</H4>
759<P><IMG WIDTH="520" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
760 SRC="img10.gif"
761 ALT="$\textstyle\parbox{\pboxargslen}{\em f fl pred top$-$reduction$-$only ring \/}$"> [<EM>FUNCTION</EM>]
762<BLOCKQUOTE>
763Calculate the normal form of the polynomial F with respect to
764the polynomial list FL. Destructive to F; thus, copy<MATH CLASS="INLINE">
765-
766</MATH>tree should be
767used where F needs to be preserved. It returns multiple values.
768The first value is the polynomial R which is reduced (or
769top<MATH CLASS="INLINE">
770-
771</MATH>reduced if TOP<MATH CLASS="INLINE">
772-
773</MATH>REDUCTION<MATH CLASS="INLINE">
774-
775</MATH>ONLY is not NIL). The second value
776is an integer which is the number of reductions actually performed.
777The third value is the coefficient by which F needs to be multiplied
778in order to be able to perform the division without actually having
779to divide in the coefficient ring (a form of pseudo<MATH CLASS="INLINE">
780-
781</MATH>division is
782used). All operations on the coefficients are performed using the
783RING structure from the COEFFICIENT<MATH CLASS="INLINE">
784-
785</MATH>RING package.</BLOCKQUOTE><H4><A NAME="SECTION000200120000000000000">
786<I>buchberger</I></A>
787</H4>
788<P><IMG WIDTH="535" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"
789 SRC="img11.gif"
790 ALT="$\textstyle\parbox{\pboxargslen}{\em f pred start top$-$reduction$-$only ring {\sf \&aux} (s (1$-$\space (length f))) b m \/}$"> [<EM>FUNCTION</EM>]
791<BLOCKQUOTE>
792An implementation of the Buchberger algorithm. Return Grobner
793basis of the ideal generated by the polynomial list F.
794The terms of each polynomial are ordered by the admissible
795monomial order PRED. Polynomials 0 to START<MATH CLASS="INLINE">
796-
797</MATH>1 are assumed to
798be a Grobner basis already, so that certain critical pairs
799will not be examined. If TOP<MATH CLASS="INLINE">
800-
801</MATH>REDUCTION<MATH CLASS="INLINE">
802-
803</MATH>ONLY set, top reduction
804will be preformed. The RING structure is used to perform operations
805on coefficents (see COEFFICIENT<MATH CLASS="INLINE">
806-
807</MATH>RING package).</BLOCKQUOTE><H4><A NAME="SECTION000200130000000000000">
808<I>grobner<MATH CLASS="INLINE">
809-
810</MATH>op</I></A>
811</H4>
812<P><IMG WIDTH="529" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
813 SRC="img12.gif"
814 ALT="$\textstyle\parbox{\pboxargslen}{\em c1 c2 m a b pred ring {\sf \&aux} n a1 a2 \/}$"> [<EM>FUNCTION</EM>]
815<BLOCKQUOTE>
816Perform a calculation equivalent to
817(POLY<MATH CLASS="INLINE">
818-
819</MATH> (SCALAR<MATH CLASS="INLINE">
820-
821</MATH>TIMES<MATH CLASS="INLINE">
822-
823</MATH>POLY C2 A)
824 (SCALAR<MATH CLASS="INLINE">
825-
826</MATH>TIMES<MATH CLASS="INLINE">
827-
828</MATH>POLY C1 (MONOM<MATH CLASS="INLINE">
829-
830</MATH>TIMES<MATH CLASS="INLINE">
831-
832</MATH>POLY M B))
833 PRED)
834but more efficiently; it destructively modifies A and stores the
835result in it; A is returned.</BLOCKQUOTE><H4><A NAME="SECTION000200140000000000000">
836<I>buchberger<MATH CLASS="INLINE">
837-
838</MATH>sort<MATH CLASS="INLINE">
839-
840</MATH>pairs</I></A>
841</H4>
842<P><IMG WIDTH="451" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
843 SRC="img13.gif"
844 ALT="$\textstyle\parbox{\pboxargslen}{\em b g pred ring \/}$"> [<EM>FUNCTION</EM>]
845<BLOCKQUOTE>
846Sort critical pairs B by the function which is
847the value of the vairable *buchberger<MATH CLASS="INLINE">
848-
849</MATH>merge<MATH CLASS="INLINE">
850-
851</MATH>pairs*.
852G is the list of polynomials which the elemnts
853of B point into. PRED is the admissible monomial order.
854The RING structure holds operations on the coefficients
855as described in the COEFFICIENT<MATH CLASS="INLINE">
856-
857</MATH>RING package.</BLOCKQUOTE><H4><A NAME="SECTION000200150000000000000">
858<I>mock<MATH CLASS="INLINE">
859-
860</MATH>spoly</I></A>
861</H4>
862<P><IMG WIDTH="526" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
863 SRC="img14.gif"
864 ALT="$\textstyle\parbox{\pboxargslen}{\em f g pred \/}$"> [<EM>FUNCTION</EM>]
865<BLOCKQUOTE>
866Returns an upper<MATH CLASS="INLINE">
867-
868</MATH>bound on the leading
869monomial of the S<MATH CLASS="INLINE">
870-
871</MATH>polynomial of F and G, which are two polynomials
872sorted by the admissible monomial order PRED.</BLOCKQUOTE><H4><A NAME="SECTION000200160000000000000">
873<I>buchberger<MATH CLASS="INLINE">
874-
875</MATH>merge<MATH CLASS="INLINE">
876-
877</MATH>pairs<MATH CLASS="INLINE">
878-
879</MATH>use<MATH CLASS="INLINE">
880-
881</MATH>mock<MATH CLASS="INLINE">
882-
883</MATH>spoly</I></A>
884</H4>
885<P><IMG WIDTH="301" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
886 SRC="img15.gif"
887 ALT="$\textstyle\parbox{\pboxargslen}{\em b c g pred ring \/}$"> [<EM>FUNCTION</EM>]
888<BLOCKQUOTE>
889Merges lists of critical pairs B and C into one list.
890The pairs are assumed to be ordered according to the
891increasing value of MOCK<MATH CLASS="INLINE">
892-
893</MATH>SPOLY, as determined by the admissible
894monomial order PRED. G is the list of polynomials which the pairs
895of integers in B and C point into, and RING is the ring structure
896defined in the COEFFICIENT<MATH CLASS="INLINE">
897-
898</MATH>RING package.</BLOCKQUOTE><H4><A NAME="SECTION000200170000000000000">
899<I>buchberger<MATH CLASS="INLINE">
900-
901</MATH>merge<MATH CLASS="INLINE">
902-
903</MATH>pairs<MATH CLASS="INLINE">
904-
905</MATH>smallest<MATH CLASS="INLINE">
906-
907</MATH>lcm</I></A>
908</H4>
909<P><IMG WIDTH="301" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
910 SRC="img15.gif"
911 ALT="$\textstyle\parbox{\pboxargslen}{\em b c g pred ring \/}$"> [<EM>FUNCTION</EM>]
912<BLOCKQUOTE>
913Merges lists of critical pairs B and C into a single ordered
914list. Implements a strategy of ordering pairs according to the
915smallest lcm of the leading monomials of the two polynomials <MATH CLASS="INLINE">
916-
917</MATH> so
918called normal strategy.</BLOCKQUOTE><H4><A NAME="SECTION000200180000000000000">
919<I>buchberger<MATH CLASS="INLINE">
920-
921</MATH>merge<MATH CLASS="INLINE">
922-
923</MATH>pairs<MATH CLASS="INLINE">
924-
925</MATH>use<MATH CLASS="INLINE">
926-
927</MATH>smallest<MATH CLASS="INLINE">
928-
929</MATH>degree</I></A>
930</H4>
931<P><IMG WIDTH="301" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
932 SRC="img15.gif"
933 ALT="$\textstyle\parbox{\pboxargslen}{\em b c g pred ring \/}$"> [<EM>FUNCTION</EM>]
934<BLOCKQUOTE>
935Mergest lists B and C of critical pairs. This strategy is based on
936ordering the pairs according to the smallest degree of the lcm of
937the leading monomials of the two polynomials.</BLOCKQUOTE><H4><A NAME="SECTION000200190000000000000">
938<I>buchberger<MATH CLASS="INLINE">
939-
940</MATH>merge<MATH CLASS="INLINE">
941-
942</MATH>pairs<MATH CLASS="INLINE">
943-
944</MATH>use<MATH CLASS="INLINE">
945-
946</MATH>smallest<MATH CLASS="INLINE">
947-
948</MATH>length</I></A>
949</H4>
950<P><IMG WIDTH="301" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
951 SRC="img15.gif"
952 ALT="$\textstyle\parbox{\pboxargslen}{\em b c g pred ring \/}$"> [<EM>FUNCTION</EM>]
953<BLOCKQUOTE>
954Mergest lists B and C of critical pairs. This strategy is based on
955ordering the pairs according to the smallest total length of the
956two polynomials, where length is the number of terms.</BLOCKQUOTE><H4><A NAME="SECTION000200200000000000000">
957<I>buchberger<MATH CLASS="INLINE">
958-
959</MATH>merge<MATH CLASS="INLINE">
960-
961</MATH>pairs<MATH CLASS="INLINE">
962-
963</MATH>use<MATH CLASS="INLINE">
964-
965</MATH>smallest<MATH CLASS="INLINE">
966-
967</MATH>coefficient<MATH CLASS="INLINE">
968-
969</MATH>length</I></A>
970</H4>
971<P><IMG WIDTH="301" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
972 SRC="img15.gif"
973 ALT="$\textstyle\parbox{\pboxargslen}{\em b c g pred ring \/}$"> [<EM>FUNCTION</EM>]
974<BLOCKQUOTE>
975Mergest lists B and C of critical pairs. This strategy is based on
976ordering the pairs according to the smallest combined length of the
977coefficients of the two polynomials.</BLOCKQUOTE><H4><A NAME="SECTION000200210000000000000">
978<I>buchberger<MATH CLASS="INLINE">
979-
980</MATH>set<MATH CLASS="INLINE">
981-
982</MATH>pair<MATH CLASS="INLINE">
983-
984</MATH>heuristic</I></A>
985</H4>
986<P><IMG WIDTH="551" HEIGHT="173" ALIGN="MIDDLE" BORDER="0"
987 SRC="img16.gif"
988 ALT="$\textstyle\parbox{\pboxargslen}{\em method {\sf \&aux} (strategy$-$fn
989 (ecase
990 ...
991 ...ar93 'buchberger$-$merge$-$pairs$-$use$-$smallest$-$coefficient$-$length))) \/}$"> [<EM>FUNCTION</EM>]
992<BLOCKQUOTE>
993Simply sets the variable *buchberger<MATH CLASS="INLINE">
994-
995</MATH>merge<MATH CLASS="INLINE">
996-
997</MATH>pairs* to the
998heuristic function STRATEGY<MATH CLASS="INLINE">
999-
1000</MATH>FN implementing one of several
1001strategies introduces before of selecting the most promising. METHOD
1002should be one of the listed keywords.</BLOCKQUOTE><H4><A NAME="SECTION000200220000000000000">
1003<I>criterion<MATH CLASS="INLINE">
1004-
1005</MATH>1</I></A>
1006</H4>
1007<P><IMG WIDTH="533" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"
1008 SRC="img17.gif"
1009 ALT="$\textstyle\parbox{\pboxargslen}{\em pair g {\sf \&aux} (i (first pair)) (j (second pair)) \/}$"> [<EM>FUNCTION</EM>]
1010<BLOCKQUOTE>
1011Returns T if the leading monomials of the two polynomials
1012in G pointed to by the integers in PAIR have disjoint (relatively
1013prime) monomials. This test is known as the first Buchberger
1014criterion. </BLOCKQUOTE><H4><A NAME="SECTION000200230000000000000">
1015<I>criterion<MATH CLASS="INLINE">
1016-
1017</MATH>2</I></A>
1018</H4>
1019<P><IMG WIDTH="533" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"
1020 SRC="img18.gif"
1021 ALT="$\textstyle\parbox{\pboxargslen}{\em pair g m {\sf \&aux} (i (first pair)) (j (second pair)) \/}$"> [<EM>FUNCTION</EM>]
1022<BLOCKQUOTE>
1023Returns T if the leading monomial of some element P of G divides
1024the LCM of the leading monomials of the two polynomials in the
1025polynomial list G, pointed to by the two integers in PAIR, and P
1026paired with each of the polynomials pointed to by the the PAIR has
1027already been treated, as indicated by the hash table M, which stores
1028value T for every treated pair so far.</BLOCKQUOTE><H4><A NAME="SECTION000200240000000000000">
1029<I>normalize<MATH CLASS="INLINE">
1030-
1031</MATH>poly</I></A>
1032</H4>
1033<P><IMG WIDTH="446" HEIGHT="28" ALIGN="MIDDLE" BORDER="0"
1034 SRC="img9.gif"
1035 ALT="$\textstyle\parbox{\pboxargslen}{\em p ring \/}$"> [<EM>FUNCTION</EM>]
1036<BLOCKQUOTE>
1037Divide a polynomial by its leading coefficient. It assumes
1038that the division is possible, which may not always be the
1039case in rings which are not fields. The exact division operator
1040is assumed to be provided by the RING structure of the
1041COEFFICIENT<MATH CLASS="INLINE">
1042-
1043</MATH>RING package.</BLOCKQUOTE><H4><A NAME="SECTION000200250000000000000">
1044<I>normalize<MATH CLASS="INLINE">
1045-
1046</MATH>basis</I></A>
1047</H4>
1048<P><IMG WIDTH="500" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
1049 SRC="img19.gif"
1050 ALT="$\textstyle\parbox{\pboxargslen}{\em plist ring \/}$"> [<EM>FUNCTION</EM>]
1051<BLOCKQUOTE>
1052Divide every polynomial in a list PLIST by its leading coefficient.
1053Use RING structure to perform the division of the coefficients.</BLOCKQUOTE><H4><A NAME="SECTION000200260000000000000">
1054<I>reduction</I></A>
1055</H4>
1056<P><IMG WIDTH="547" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
1057 SRC="img20.gif"
1058 ALT="$\textstyle\parbox{\pboxargslen}{\em p pred ring \/}$"> [<EM>FUNCTION</EM>]
1059<BLOCKQUOTE>
1060Reduce a list of polynomials P, so that non of the terms in any of
1061the polynomials is divisible by a leading monomial of another
1062polynomial. Return the reduced list.</BLOCKQUOTE><H4><A NAME="SECTION000200270000000000000">
1063<I>reduced<MATH CLASS="INLINE">
1064-
1065</MATH>grobner</I></A>
1066</H4>
1067<P><IMG WIDTH="559" HEIGHT="50" ALIGN="MIDDLE" BORDER="0"
1068 SRC="img6.gif"
1069 ALT="$\textstyle\parbox{\pboxargslen}{\em f {\sf \&optional} (pred \char93 'lex$\gt$) (start
1070 0) (top$-$reduction$-$only
1071 nil) (ring
1072 *coefficient$-$ring*) \/}$"> [<EM>FUNCTION</EM>]
1073<BLOCKQUOTE>
1074Return the reduced Grobner basis of the ideal generated by a
1075polynomial list F. This combines calls to two functions: GROBNER and
1076REDUCTION. The parameters have the same meaning as in GROBNER or
1077BUCHBERGER. </BLOCKQUOTE><H4><A NAME="SECTION000200280000000000000">
1078<I>monom<MATH CLASS="INLINE">
1079-
1080</MATH>depends<MATH CLASS="INLINE">
1081-
1082</MATH>p</I></A>
1083</H4>
1084<P><IMG WIDTH="470" HEIGHT="27" ALIGN="MIDDLE" BORDER="0"
1085 SRC="img21.gif"
1086 ALT="$\textstyle\parbox{\pboxargslen}{\em m k \/}$"> [<EM>FUNCTION</EM>]
1087<BLOCKQUOTE>
1088Return T if the monomial M depends on variable number K.</BLOCKQUOTE><H4><A NAME="SECTION000200290000000000000">
1089<I>term<MATH CLASS="INLINE">
1090-
1091</MATH>depends<MATH CLASS="INLINE">
1092-
1093</MATH>p</I></A>
1094</H4>
1095<P><IMG WIDTH="489" HEIGHT="27" ALIGN="MIDDLE" BORDER="0"
1096 SRC="img22.gif"
1097 ALT="$\textstyle\parbox{\pboxargslen}{\em term k \/}$"> [<EM>FUNCTION</EM>]
1098<BLOCKQUOTE>
1099Return T if the term TERM depends on variable number K.</BLOCKQUOTE><H4><A NAME="SECTION000200300000000000000">
1100<I>poly<MATH CLASS="INLINE">
1101-
1102</MATH>depends<MATH CLASS="INLINE">
1103-
1104</MATH>p</I></A>
1105</H4>
1106<P><IMG WIDTH="492" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
1107 SRC="img23.gif"
1108 ALT="$\textstyle\parbox{\pboxargslen}{\em p k \/}$"> [<EM>FUNCTION</EM>]
1109<BLOCKQUOTE>
1110Return T if the term polynomial P depends on variable number K.</BLOCKQUOTE><H4><A NAME="SECTION000200310000000000000">
1111<I>ring<MATH CLASS="INLINE">
1112-
1113</MATH>intersection</I></A>
1114</H4>
1115<P><IMG WIDTH="493" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"
1116 SRC="img24.gif"
1117 ALT="$\textstyle\parbox{\pboxargslen}{\em plist k {\sf \&key} (key \char93 'identity) \/}$"> [<EM>FUNCTION</EM>]
1118<BLOCKQUOTE>
1119This function assumes that polynomial list PLIST is a Grobner basis
1120and it calculates the intersection with the ring R[x[k+1],...,x[n]],
1121i.e. it discards polynomials which depend on variables x[0], x[1],
1122..., x[k]. </BLOCKQUOTE><H4><A NAME="SECTION000200320000000000000">
1123<I>elimination<MATH CLASS="INLINE">
1124-
1125</MATH>ideal</I></A>
1126</H4>
1127<P><IMG WIDTH="491" HEIGHT="90" ALIGN="MIDDLE" BORDER="0"
1128 SRC="img25.gif"
1129 ALT="$\textstyle\parbox{\pboxargslen}{\em flist k {\sf \&key} (primary$-$order
1130 \char...
1131 ...ondary$-$order)) (top$-$reduction$-$only
1132 nil) (ring
1133 *coefficient$-$ring*) \/}$"> [<EM>FUNCTION</EM>]
1134<BLOCKQUOTE>
1135Returns the K<MATH CLASS="INLINE">
1136-
1137</MATH>th elimination ideal of the ideal generated by
1138polynomial list FLIST. Thus, a Grobner basis of the ideal generated
1139by FLIST is calculated and polynomials depending on variables 0<MATH CLASS="INLINE">
1140-
1141</MATH>K
1142are discarded. The monomial order in the calculation is an
1143elimination order formed by combining two orders: PRIMARY<MATH CLASS="INLINE">
1144-
1145</MATH>ORDER
1146used on variables 0<MATH CLASS="INLINE">
1147-
1148</MATH>K and SECONDARY<MATH CLASS="INLINE">
1149-
1150</MATH>ORDER used on variables
1151starting from variable K+1. Thus, if both orders are set to the
1152lexicographic order #'LEX<MATH CLASS="INLINE">
1153&gt;
1154</MATH> then the resulting order is simply
1155equivalent to #'LEX<MATH CLASS="INLINE">
1156&gt;
1157</MATH>. But one could use arbitrary two orders in
1158this function, for instance, two copies of #'GREVLEX<MATH CLASS="INLINE">
1159&gt;
1160</MATH> (see ORDER
1161package). When doing so, the caller must ensure that the same order
1162has been used to sort the terms of the polynomials FLIST. </BLOCKQUOTE><H4><A NAME="SECTION000200330000000000000">
1163<I>ideal<MATH CLASS="INLINE">
1164-
1165</MATH>intersection</I></A>
1166</H4>
1167<P><IMG WIDTH="487" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
1168 SRC="img26.gif"
1169 ALT="$\textstyle\parbox{\pboxargslen}{\em f g pred top$-$reduction$-$only ring \/}$"> [<EM>FUNCTION</EM>]
1170<BLOCKQUOTE>
1171Return the Grobner basis of the intersection of the ideals
1172generated by the polynomial lists F and G. PRED is an admissible
1173monomial order with respect to which the terms of F and G have been
1174sorted. This order is going to be used in the Grobner basis
1175calculation. If TOP<MATH CLASS="INLINE">
1176-
1177</MATH>REDUCTION<MATH CLASS="INLINE">
1178-
1179</MATH>ONLY is not NIL, internally the
1180Grobner basis algorithm will perform top reduction only. The RING
1181parameter, as usual, should be set to a structure defined in the
1182package COEFFICIENT<MATH CLASS="INLINE">
1183-
1184</MATH>RING, and it will be used to perform all
1185operations on coefficients.</BLOCKQUOTE><H4><A NAME="SECTION000200340000000000000">
1186<I>poly<MATH CLASS="INLINE">
1187-
1188</MATH>contract</I></A>
1189</H4>
1190<P><IMG WIDTH="512" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"
1191 SRC="img27.gif"
1192 ALT="$\textstyle\parbox{\pboxargslen}{\em f {\sf \&optional} (k 1) \/}$"> [<EM>FUNCTION</EM>]
1193<BLOCKQUOTE>
1194Return a polynomial obtained from polynomial F by dropping the
1195first K variables, if F does not depend on them. Note that this
1196operation makes the polynomial incompatible for certain arithmetical
1197operations with the original polynomial F. Calling this function on a
1198polynomial F which does depend on variables 0<MATH CLASS="INLINE">
1199-
1200</MATH>K will result in
1201error. </BLOCKQUOTE><H4><A NAME="SECTION000200350000000000000">
1202<I>poly<MATH CLASS="INLINE">
1203-
1204</MATH>lcm</I></A>
1205</H4>
1206<P><IMG WIDTH="545" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"
1207 SRC="img28.gif"
1208 ALT="$\textstyle\parbox{\pboxargslen}{\em f g {\sf \&optional} (pred \char93 'lex$\gt$) (ring
1209 *coefficient$-$ring*) \/}$"> [<EM>FUNCTION</EM>]
1210<BLOCKQUOTE>
1211Return LCM (least common multiple) of two polynomials F and G.
1212The polynomials must be ordered according to monomial order PRED
1213and their coefficients must be compatible with the RING structure
1214defined in the COEFFICIENT<MATH CLASS="INLINE">
1215-
1216</MATH>RING package.</BLOCKQUOTE><H4><A NAME="SECTION000200360000000000000">
1217<I>grobner<MATH CLASS="INLINE">
1218-
1219</MATH>gcd</I></A>
1220</H4>
1221<P><IMG WIDTH="545" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"
1222 SRC="img28.gif"
1223 ALT="$\textstyle\parbox{\pboxargslen}{\em f g {\sf \&optional} (pred \char93 'lex$\gt$) (ring
1224 *coefficient$-$ring*) \/}$"> [<EM>FUNCTION</EM>]
1225<BLOCKQUOTE>
1226Return GCD (greatest common divisor) of two polynomials F and G.
1227The polynomials must be ordered according to monomial order PRED
1228and their coefficients must be compatible with the RING structure
1229defined in the COEFFICIENT<MATH CLASS="INLINE">
1230-
1231</MATH>RING package.</BLOCKQUOTE><H4><A NAME="SECTION000200370000000000000">
1232<I>grobner<MATH CLASS="INLINE">
1233-
1234</MATH>equal</I></A>
1235</H4>
1236<P><IMG WIDTH="510" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"
1237 SRC="img29.gif"
1238 ALT="$\textstyle\parbox{\pboxargslen}{\em g1 g2 {\sf \&optional} (pred
1239 \char93 'lex$\gt$) (ring
1240 *coefficient$-$ring*) \/}$"> [<EM>FUNCTION</EM>]
1241<BLOCKQUOTE>
1242Returns T if two lists of polynomials G1 and G2, assumed to be
1243Grobner bases, generate the same ideal, and NIL otherwise.</BLOCKQUOTE><H4><A NAME="SECTION000200380000000000000">
1244<I>grobner<MATH CLASS="INLINE">
1245-
1246</MATH>subsetp</I></A>
1247</H4>
1248<P><IMG WIDTH="510" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"
1249 SRC="img29.gif"
1250 ALT="$\textstyle\parbox{\pboxargslen}{\em g1 g2 {\sf \&optional} (pred
1251 \char93 'lex$\gt$) (ring
1252 *coefficient$-$ring*) \/}$"> [<EM>FUNCTION</EM>]
1253<BLOCKQUOTE>
1254Returns T if a list of polynomials G1 generates
1255an ideal contained in the ideal generated by a polynomial list G2,
1256both G1 and G2 assumed to be Grobner bases. Returns NIL otherwise.</BLOCKQUOTE><H4><A NAME="SECTION000200390000000000000">
1257<I>grobner<MATH CLASS="INLINE">
1258-
1259</MATH>member</I></A>
1260</H4>
1261<P><IMG WIDTH="490" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"
1262 SRC="img30.gif"
1263 ALT="$\textstyle\parbox{\pboxargslen}{\em p g {\sf \&optional} (pred
1264 \char93 'lex$\gt$) (ring
1265 *coefficient$-$ring*) \/}$"> [<EM>FUNCTION</EM>]
1266<BLOCKQUOTE>
1267Returns T if a polynomial P belongs to the ideal generated by the
1268polynomial list G, which is assumed to be a Grobner basis. Returns
1269NIL otherwise. </BLOCKQUOTE><H4><A NAME="SECTION000200400000000000000">
1270<I>ideal<MATH CLASS="INLINE">
1271-
1272</MATH>equal</I></A>
1273</H4>
1274<P><IMG WIDTH="530" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
1275 SRC="img31.gif"
1276 ALT="$\textstyle\parbox{\pboxargslen}{\em f1 f2 pred top$-$reduction$-$only ring \/}$"> [<EM>FUNCTION</EM>]
1277<BLOCKQUOTE>
1278Returns T if two ideals generated by polynomial lists F1 and F2 are
1279identical. Returns NIL otherwise.</BLOCKQUOTE><H4><A NAME="SECTION000200410000000000000">
1280<I>ideal<MATH CLASS="INLINE">
1281-
1282</MATH>subsetp</I></A>
1283</H4>
1284<P><IMG WIDTH="515" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"
1285 SRC="img32.gif"
1286 ALT="$\textstyle\parbox{\pboxargslen}{\em f1 f2 {\sf \&optional} (pred
1287 \char93 'lex$\gt$) (ring
1288 *coefficient$-$ring*) \/}$"> [<EM>FUNCTION</EM>]
1289<BLOCKQUOTE>
1290Returns T if the ideal spanned by the polynomial list F1 is contained
1291in the ideal spanned by the polynomial list F2. Returns NIL
1292otherwise. </BLOCKQUOTE><H4><A NAME="SECTION000200420000000000000">
1293<I>ideal<MATH CLASS="INLINE">
1294-
1295</MATH>member</I></A>
1296</H4>
1297<P><IMG WIDTH="511" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
1298 SRC="img33.gif"
1299 ALT="$\textstyle\parbox{\pboxargslen}{\em p plist pred top$-$reduction$-$only ring \/}$"> [<EM>FUNCTION</EM>]
1300<BLOCKQUOTE>
1301Returns T if the polynomial P belongs to the ideal spanned by the
1302polynomial list PLIST, and NIL otherwise.</BLOCKQUOTE><H4><A NAME="SECTION000200430000000000000">
1303<I>ideal<MATH CLASS="INLINE">
1304-
1305</MATH>saturation<MATH CLASS="INLINE">
1306-
1307</MATH>1</I></A>
1308</H4>
1309<P><IMG WIDTH="476" HEIGHT="50" ALIGN="MIDDLE" BORDER="0"
1310 SRC="img34.gif"
1311 ALT="$\textstyle\parbox{\pboxargslen}{\em f p pred start top$-$reduction$-$only ring {\sf \&aux} (pred
1312 (elimination$-$order$-$1
1313 pred)) \/}$"> [<EM>FUNCTION</EM>]
1314<BLOCKQUOTE>
1315Returns the reduced Grobner basis of the saturation of the ideal
1316generated by a polynomial list F in the ideal generated by a single
1317polynomial P. The saturation ideal is defined as the set of
1318polynomials H such for some natural number n (* (EXPT P N) H) is in
1319the ideal F. Geometrically, over an algebraically closed field, this
1320is the set of polynomials in the ideal generated by F which do not
1321identically vanish on the variety of P.</BLOCKQUOTE><H4><A NAME="SECTION000200440000000000000">
1322<I>add<MATH CLASS="INLINE">
1323-
1324</MATH>variables</I></A>
1325</H4>
1326<P><IMG WIDTH="514" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
1327 SRC="img35.gif"
1328 ALT="$\textstyle\parbox{\pboxargslen}{\em plist n \/}$"> [<EM>FUNCTION</EM>]
1329<BLOCKQUOTE>
1330Add N new variables, adn the first N variables, to every polynomial
1331in polynomial list PLIST. The resulting polynomial will not depend on
1332these N variables. </BLOCKQUOTE><H4><A NAME="SECTION000200450000000000000">
1333<I>extend<MATH CLASS="INLINE">
1334-
1335</MATH>polynomials</I></A>
1336</H4>
1337<P><IMG WIDTH="472" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"
1338 SRC="img36.gif"
1339 ALT="$\textstyle\parbox{\pboxargslen}{\em plist {\sf \&aux} (k (length plist)) \/}$"> [<EM>FUNCTION</EM>]
1340<BLOCKQUOTE>
1341Returns polynomial list {U1*P1', U2*P2', ... , UK*PK'}
1342where Ui are new variables and PLIST={P1, P2, ... , PK} is a
1343polynomial list. PI' is obtained from PI by adding new variables U1,
1344U2, ..., UN UK as the first K variables. Thus, the resulting list is
1345consists of polynomials whose terms are ordered by the lexicographic
1346order on variables UI, with ties resolved by the monomial order which
1347was used to order the terms of the polynomials in PLIST. We note that
1348the monomial order does not explicitly participate in this
1349calculation, and neither do the variable names.</BLOCKQUOTE><H4><A NAME="SECTION000200460000000000000">
1350<I>saturation<MATH CLASS="INLINE">
1351-
1352</MATH>extension</I></A>
1353</H4>
1354<P><IMG WIDTH="465" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"
1355 SRC="img37.gif"
1356 ALT="$\textstyle\parbox{\pboxargslen}{\em f plist ring {\sf \&aux} (k
1357 (length plist)) (d
1358 (+
1359 k
1360 (length
1361 (caaar
1362 plist)))) \/}$"> [<EM>FUNCTION</EM>]
1363<BLOCKQUOTE>
1364Returns F' union {U1*P1<MATH CLASS="INLINE">
1365-
1366</MATH>1,U2*P2<MATH CLASS="INLINE">
1367-
1368</MATH>1,...,UK*PK<MATH CLASS="INLINE">
1369-
1370</MATH>1} where Ui are
1371new variables and F' is a polynomial list obtained from F by adding
1372variables U1, U2, ..., Uk as the first K variables to each polynomial
1373in F. Thus, the resulting list is consists of polynomials whose terms
1374are ordered by the lexicographic order on variables Ui, with ties
1375resolved by the monomial order which was used to order the terms of
1376the polynomials in F. We note that the monomial order does not
1377explicitly participate in this calculation, and neither do the
1378variable names. </BLOCKQUOTE><H4><A NAME="SECTION000200470000000000000">
1379<I>polysaturation<MATH CLASS="INLINE">
1380-
1381</MATH>extension</I></A>
1382</H4>
1383<P><IMG WIDTH="465" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"
1384 SRC="img37.gif"
1385 ALT="$\textstyle\parbox{\pboxargslen}{\em f plist ring {\sf \&aux} (k
1386 (length plist)) (d
1387 (+
1388 k
1389 (length
1390 (caaar
1391 plist)))) \/}$"> [<EM>FUNCTION</EM>]
1392<BLOCKQUOTE>
1393Returns F' union {U1*P1+U2*P2+UK*PK<MATH CLASS="INLINE">
1394-
1395</MATH>1} where Ui are new variables
1396and F' is a polynomial list obtained from F by adding variables U1,
1397U2, ..., Uk as the first K variables to each polynomial in F. Thus,
1398the resulting list is consists of polynomials whose terms are ordered
1399by the lexicographic order on variables Ui, with ties resolved by the
1400monomial order which was used to order the terms of the polynomials
1401in F. We note that the monomial order does not explicitly participate
1402in this calculation, and neither do the variable names. </BLOCKQUOTE><H4><A NAME="SECTION000200480000000000000">
1403<I>saturation<MATH CLASS="INLINE">
1404-
1405</MATH>extension<MATH CLASS="INLINE">
1406-
1407</MATH>1</I></A>
1408</H4>
1409<P><IMG WIDTH="444" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
1410 SRC="img38.gif"
1411 ALT="$\textstyle\parbox{\pboxargslen}{\em f p ring \/}$"> [<EM>FUNCTION</EM>]
1412<BLOCKQUOTE>
1413Return the list F' union {U*P<MATH CLASS="INLINE">
1414-
1415</MATH>1} where U is a new variable,
1416where F' is obtained from the polynomial list F by adding U as the
1417first variable. The variable U will be added as the first variable,
1418so that it can be easily eliminated.</BLOCKQUOTE><H4><A NAME="SECTION000200490000000000000">
1419<I>ideal<MATH CLASS="INLINE">
1420-
1421</MATH>polysaturation<MATH CLASS="INLINE">
1422-
1423</MATH>1</I></A>
1424</H4>
1425<P><IMG WIDTH="447" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
1426 SRC="img39.gif"
1427 ALT="$\textstyle\parbox{\pboxargslen}{\em f plist pred start top$-$reduction$-$only ring \/}$"> [<EM>FUNCTION</EM>]
1428<BLOCKQUOTE>
1429Returns the reduced Grobner basis of the ideal obtained by a
1430sequence of successive saturations in the polynomials
1431of the polynomial list PLIST of the ideal generated by the
1432polynomial list F.</BLOCKQUOTE><H4><A NAME="SECTION000200500000000000000">
1433<I>ideal<MATH CLASS="INLINE">
1434-
1435</MATH>saturation</I></A>
1436</H4>
1437<P><IMG WIDTH="497" HEIGHT="70" ALIGN="MIDDLE" BORDER="0"
1438 SRC="img40.gif"
1439 ALT="$\textstyle\parbox{\pboxargslen}{\em f g pred start top$-$reduction$-$only ring ...
1440 ...$order k :primary$-$order \char93 'lex$\gt$\space :secondary$-$order pred)) \/}$"> [<EM>FUNCTION</EM>]
1441<BLOCKQUOTE>
1442Returns the reduced Grobner basis of the saturation of the ideal
1443generated by a polynomial list F in the ideal generated a polynomial
1444list G The saturation ideal is defined as the set of polynomials H
1445such for some natural number n and some P in the ideal generated by G
1446the polynomial P**N * H is in the ideal spanned by F. Geometrically,
1447over an algebraically closed field, this is the set of polynomials in
1448the ideal generated by F which do not identically vanish on the
1449variety of G.</BLOCKQUOTE><H4><A NAME="SECTION000200510000000000000">
1450<I>ideal<MATH CLASS="INLINE">
1451-
1452</MATH>polysaturation</I></A>
1453</H4>
1454<P><IMG WIDTH="468" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
1455 SRC="img41.gif"
1456 ALT="$\textstyle\parbox{\pboxargslen}{\em f ideal$-$list pred start top$-$reduction$-$only ring \/}$"> [<EM>FUNCTION</EM>]
1457<BLOCKQUOTE>
1458Returns the reduced Grobner basis of the ideal obtained by a
1459successive applications of IDEAL<MATH CLASS="INLINE">
1460-
1461</MATH>SATURATIONS to F and
1462lists of polynomials in the list IDEAL<MATH CLASS="INLINE">
1463-
1464</MATH>LIST.</BLOCKQUOTE><H4><A NAME="SECTION000200520000000000000">
1465<I>buchberger<MATH CLASS="INLINE">
1466-
1467</MATH>criterion</I></A>
1468</H4>
1469<P><IMG WIDTH="465" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
1470 SRC="img42.gif"
1471 ALT="$\textstyle\parbox{\pboxargslen}{\em g pred ring \/}$"> [<EM>FUNCTION</EM>]
1472<BLOCKQUOTE>
1473Returns T if G is a Grobner basis, by using the Buchberger
1474criterion: for every two polynomials h1 and h2 in G the
1475S<MATH CLASS="INLINE">
1476-
1477</MATH>polynomial S(h1,h2) reduces to 0 modulo G.</BLOCKQUOTE><H4><A NAME="SECTION000200530000000000000">
1478<I>grobner<MATH CLASS="INLINE">
1479-
1480</MATH>test</I></A>
1481</H4>
1482<P><IMG WIDTH="520" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
1483 SRC="img43.gif"
1484 ALT="$\textstyle\parbox{\pboxargslen}{\em g f pred ring \/}$"> [<EM>FUNCTION</EM>]
1485<BLOCKQUOTE>
1486Test whether G is a Grobner basis and F is contained in G. Return T
1487upon success and NIL otherwise.</BLOCKQUOTE><H4><A NAME="SECTION000200540000000000000">
1488<I>minimization</I></A>
1489</H4>
1490<P><IMG WIDTH="523" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
1491 SRC="img44.gif"
1492 ALT="$\textstyle\parbox{\pboxargslen}{\em p pred \/}$"> [<EM>FUNCTION</EM>]
1493<BLOCKQUOTE>
1494Returns a sublist of the polynomial list P spanning the same
1495monomial ideal as P but minimal, i.e. no leading monomial
1496of a polynomial in the sublist divides the leading monomial
1497of another polynomial.</BLOCKQUOTE><H4><A NAME="SECTION000200550000000000000">
1498<I>add<MATH CLASS="INLINE">
1499-
1500</MATH>minimized</I></A>
1501</H4>
1502<P><IMG WIDTH="503" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
1503 SRC="img45.gif"
1504 ALT="$\textstyle\parbox{\pboxargslen}{\em f gred pred \/}$"> [<EM>FUNCTION</EM>]
1505<BLOCKQUOTE>
1506Adds a polynomial f to GRED, reduced Grobner basis, preserving the
1507property described in the documentation for MINIMIZATION.</BLOCKQUOTE><H4><A NAME="SECTION000200560000000000000">
1508<I>colon<MATH CLASS="INLINE">
1509-
1510</MATH>ideal</I></A>
1511</H4>
1512<P><IMG WIDTH="487" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
1513 SRC="img26.gif"
1514 ALT="$\textstyle\parbox{\pboxargslen}{\em f g pred top$-$reduction$-$only ring \/}$"> [<EM>FUNCTION</EM>]
1515<BLOCKQUOTE>
1516Returns the reduced Grobner basis of the colon ideal Id(F):Id(G),
1517where F and G are two lists of polynomials. The colon ideal I:J is
1518defined as the set of polynomials H such that there is a polynomial W
1519in J for which W*H belongs to I.</BLOCKQUOTE><H4><A NAME="SECTION000200570000000000000">
1520<I>colon<MATH CLASS="INLINE">
1521-
1522</MATH>ideal<MATH CLASS="INLINE">
1523-
1524</MATH>1</I></A>
1525</H4>
1526<P><IMG WIDTH="487" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
1527 SRC="img26.gif"
1528 ALT="$\textstyle\parbox{\pboxargslen}{\em f g pred top$-$reduction$-$only ring \/}$"> [<EM>FUNCTION</EM>]
1529<BLOCKQUOTE>
1530Returns the reduced Grobner basis of the colon ideal Id(F):Id({G}),
1531where F is a list of polynomials and G is a polynomial.</BLOCKQUOTE><H4><A NAME="SECTION000200580000000000000">
1532<I>pseudo<MATH CLASS="INLINE">
1533-
1534</MATH>divide</I></A>
1535</H4>
1536<P><IMG WIDTH="511" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
1537 SRC="img46.gif"
1538 ALT="$\textstyle\parbox{\pboxargslen}{\em f fl pred ring \/}$"> [<EM>FUNCTION</EM>]
1539<BLOCKQUOTE>
1540Pseudo<MATH CLASS="INLINE">
1541-
1542</MATH>divide a polynomial F by the list of polynomials FL. Return
1543multiple values. The first value is a list of quotients A.
1544The second value is the remainder R. The third value is an integer
1545count of the number of reductions performed. Finally, the fourth
1546argument is a scalar coefficient C, such that C*F can be divided by
1547FL within the ring of coefficients, which is not necessarily a field.
1548The resulting objects satisfy the equation:
1549 C*F= sum A[i]*FL[i] + R</BLOCKQUOTE><H4><A NAME="SECTION000200590000000000000">
1550<I>gebauer<MATH CLASS="INLINE">
1551-
1552</MATH>moeller</I></A>
1553</H4>
1554<P><IMG WIDTH="494" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
1555 SRC="img47.gif"
1556 ALT="$\textstyle\parbox{\pboxargslen}{\em f pred start top$-$reduction$-$only ring {\sf \&aux} b g f1 \/}$"> [<EM>FUNCTION</EM>]
1557<BLOCKQUOTE>
1558Compute Grobner basis by using the algorithm of Gebauer and Moeller.
1559This algorithm is described as BUCHBERGERNEW2 in the book by
1560Becker<MATH CLASS="INLINE">
1561-
1562</MATH>Weispfenning entitled ``Grobner Bases''</BLOCKQUOTE><H4><A NAME="SECTION000200600000000000000">
1563<I>update</I></A>
1564</H4>
1565<P><IMG WIDTH="564" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
1566 SRC="img48.gif"
1567 ALT="$\textstyle\parbox{\pboxargslen}{\em g b h pred ring {\sf \&aux} c d e b$-$new g$-$new pair \/}$"> [<EM>FUNCTION</EM>]
1568<BLOCKQUOTE>
1569An implementation of the auxillary UPDATE algorithm used by the
1570Gebauer<MATH CLASS="INLINE">
1571-
1572</MATH>Moeller algorithm. G is a list of polynomials, B is a list
1573of critical pairs and H is a new polynomial which possibly will be
1574added to G. The naming conventions used are very close to the one
1575used in the book of Becker<MATH CLASS="INLINE">
1576-
1577</MATH>Weispfenning.</BLOCKQUOTE><H4><A NAME="SECTION000200610000000000000">
1578<I>gebauer<MATH CLASS="INLINE">
1579-
1580</MATH>moeller<MATH CLASS="INLINE">
1581-
1582</MATH>merge<MATH CLASS="INLINE">
1583-
1584</MATH>pairs<MATH CLASS="INLINE">
1585-
1586</MATH>use<MATH CLASS="INLINE">
1587-
1588</MATH>mock<MATH CLASS="INLINE">
1589-
1590</MATH>spoly</I></A>
1591</H4>
1592<P><IMG WIDTH="261" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
1593 SRC="img49.gif"
1594 ALT="$\textstyle\parbox{\pboxargslen}{\em b c pred ring \/}$"> [<EM>FUNCTION</EM>]
1595<BLOCKQUOTE>
1596The merging strategy used by the Gebauer<MATH CLASS="INLINE">
1597-
1598</MATH>Moeller algorithm, based
1599on MOCK<MATH CLASS="INLINE">
1600-
1601</MATH>SPOLY; see the documentation of
1602BUCHBERGER<MATH CLASS="INLINE">
1603-
1604</MATH>MERGE<MATH CLASS="INLINE">
1605-
1606</MATH>PAIRS<MATH CLASS="INLINE">
1607-
1608</MATH>USE<MATH CLASS="INLINE">
1609-
1610</MATH>MOCK<MATH CLASS="INLINE">
1611-
1612</MATH>SPOLY.</BLOCKQUOTE><H4><A NAME="SECTION000200620000000000000">
1613<I>gebauer<MATH CLASS="INLINE">
1614-
1615</MATH>moeller<MATH CLASS="INLINE">
1616-
1617</MATH>merge<MATH CLASS="INLINE">
1618-
1619</MATH>pairs<MATH CLASS="INLINE">
1620-
1621</MATH>smallest<MATH CLASS="INLINE">
1622-
1623</MATH>lcm</I></A>
1624</H4>
1625<P><IMG WIDTH="261" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
1626 SRC="img49.gif"
1627 ALT="$\textstyle\parbox{\pboxargslen}{\em b c pred ring \/}$"> [<EM>FUNCTION</EM>]
1628<BLOCKQUOTE>
1629The merging strategy based on the smallest<MATH CLASS="INLINE">
1630-
1631</MATH>lcm (normal strategy);
1632see the documentation of BUCHBERGER<MATH CLASS="INLINE">
1633-
1634</MATH>MERGE<MATH CLASS="INLINE">
1635-
1636</MATH>PAIRS<MATH CLASS="INLINE">
1637-
1638</MATH>SMALLEST<MATH CLASS="INLINE">
1639-
1640</MATH>LCM.</BLOCKQUOTE><H4><A NAME="SECTION000200630000000000000">
1641<I>gebauer<MATH CLASS="INLINE">
1642-
1643</MATH>moeller<MATH CLASS="INLINE">
1644-
1645</MATH>merge<MATH CLASS="INLINE">
1646-
1647</MATH>pairs<MATH CLASS="INLINE">
1648-
1649</MATH>use<MATH CLASS="INLINE">
1650-
1651</MATH>smallest<MATH CLASS="INLINE">
1652-
1653</MATH>degree</I></A>
1654</H4>
1655<P><IMG WIDTH="261" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
1656 SRC="img49.gif"
1657 ALT="$\textstyle\parbox{\pboxargslen}{\em b c pred ring \/}$"> [<EM>FUNCTION</EM>]
1658<BLOCKQUOTE>
1659The merging strategy based on the smallest<MATH CLASS="INLINE">
1660-
1661</MATH>lcm (normal strategy);
1662see the documentation of
1663BUCHBERGER<MATH CLASS="INLINE">
1664-
1665</MATH>MERGE<MATH CLASS="INLINE">
1666-
1667</MATH>PAIRS<MATH CLASS="INLINE">
1668-
1669</MATH>USE<MATH CLASS="INLINE">
1670-
1671</MATH>SMALLEST<MATH CLASS="INLINE">
1672-
1673</MATH>DEGREE. </BLOCKQUOTE><H4><A NAME="SECTION000200640000000000000">
1674<I>gebauer<MATH CLASS="INLINE">
1675-
1676</MATH>moeller<MATH CLASS="INLINE">
1677-
1678</MATH>merge<MATH CLASS="INLINE">
1679-
1680</MATH>pairs<MATH CLASS="INLINE">
1681-
1682</MATH>use<MATH CLASS="INLINE">
1683-
1684</MATH>smallest<MATH CLASS="INLINE">
1685-
1686</MATH>length</I></A>
1687</H4>
1688<P><IMG WIDTH="261" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
1689 SRC="img49.gif"
1690 ALT="$\textstyle\parbox{\pboxargslen}{\em b c pred ring \/}$"> [<EM>FUNCTION</EM>]
1691<BLOCKQUOTE>
1692 </BLOCKQUOTE><H4><A NAME="SECTION000200650000000000000">
1693<I>gebauer<MATH CLASS="INLINE">
1694-
1695</MATH>moeller<MATH CLASS="INLINE">
1696-
1697</MATH>merge<MATH CLASS="INLINE">
1698-
1699</MATH>pairs<MATH CLASS="INLINE">
1700-
1701</MATH>use<MATH CLASS="INLINE">
1702-
1703</MATH>smallest<MATH CLASS="INLINE">
1704-
1705</MATH>coefficient<MATH CLASS="INLINE">
1706-
1707</MATH>length</I></A>
1708</H4>
1709<P><IMG WIDTH="261" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
1710 SRC="img49.gif"
1711 ALT="$\textstyle\parbox{\pboxargslen}{\em b c pred ring \/}$"> [<EM>FUNCTION</EM>]
1712<BLOCKQUOTE>
1713The merging strategy based on the smallest<MATH CLASS="INLINE">
1714-
1715</MATH>lcm (normal strategy);
1716see the documentation of
1717BUCHBERGER<MATH CLASS="INLINE">
1718-
1719</MATH>MERGE<MATH CLASS="INLINE">
1720-
1721</MATH>PAIRS<MATH CLASS="INLINE">
1722-
1723</MATH>USE<MATH CLASS="INLINE">
1724-
1725</MATH>SMALLEST<MATH CLASS="INLINE">
1726-
1727</MATH>COEFFICIENT<MATH CLASS="INLINE">
1728-
1729</MATH>LENGTH. </BLOCKQUOTE><H4><A NAME="SECTION000200660000000000000">
1730<I>gebauer<MATH CLASS="INLINE">
1731-
1732</MATH>moeller<MATH CLASS="INLINE">
1733-
1734</MATH>set<MATH CLASS="INLINE">
1735-
1736</MATH>pair<MATH CLASS="INLINE">
1737-
1738</MATH>heuristic</I></A>
1739</H4>
1740<P><IMG WIDTH="551" HEIGHT="173" ALIGN="MIDDLE" BORDER="0"
1741 SRC="img16.gif"
1742 ALT="$\textstyle\parbox{\pboxargslen}{\em method {\sf \&aux} (strategy$-$fn
1743 (ecase
1744 ...
1745 ...ar93 'buchberger$-$merge$-$pairs$-$use$-$smallest$-$coefficient$-$length))) \/}$"> [<EM>FUNCTION</EM>]
1746<BLOCKQUOTE>
1747 </BLOCKQUOTE><H4><A NAME="SECTION000200670000000000000">
1748<I>spoly<MATH CLASS="INLINE">
1749-
1750</MATH>sugar</I></A>
1751</H4>
1752<P><IMG WIDTH="527" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
1753 SRC="img50.gif"
1754 ALT="$\textstyle\parbox{\pboxargslen}{\em f$-$with$-$sugar g$-$with$-$sugar ring \/}$"> [<EM>FUNCTION</EM>]
1755<BLOCKQUOTE>
1756Calculate the ``sugar'' of the S<MATH CLASS="INLINE">
1757-
1758</MATH>polynomial of two polynomials with
1759sugar. A polynomial with sugar is simply a pair (P . SUGAR) where
1760SUGAR is an integer constant defined according to the following
1761algorighm: the sugar of sum or difference of two polynomials with
1762sugar is the MAX of the sugars of those two polynomials. The sugar of
1763a product of a term and a polynomial is the sum of the degree of the
1764term and the sugar of the polynomial. The idea is to accumulate
1765sugar as we perform the arithmetic operations, and that polynomials
1766with small (little) sugar should be given priority in the
1767calculations. Thus, the ``sugar strategy'' of the critical pair
1768selection is to select a pair with the smallest value of sugar of the
1769resulting S<MATH CLASS="INLINE">
1770-
1771</MATH>polynomial.</BLOCKQUOTE><H4><A NAME="SECTION000200680000000000000">
1772<I>spoly<MATH CLASS="INLINE">
1773-
1774</MATH>with<MATH CLASS="INLINE">
1775-
1776</MATH>sugar</I></A>
1777</H4>
1778<P><IMG WIDTH="484" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
1779 SRC="img51.gif"
1780 ALT="$\textstyle\parbox{\pboxargslen}{\em f$-$with$-$sugar g$-$with$-$sugar pred ring \/}$"> [<EM>FUNCTION</EM>]
1781<BLOCKQUOTE>
1782The S<MATH CLASS="INLINE">
1783-
1784</MATH>polynomials of two polynomials with SUGAR strategy.</BLOCKQUOTE><H4><A NAME="SECTION000200690000000000000">
1785<I>normal<MATH CLASS="INLINE">
1786-
1787</MATH>form<MATH CLASS="INLINE">
1788-
1789</MATH>with<MATH CLASS="INLINE">
1790-
1791</MATH>sugar</I></A>
1792</H4>
1793<P><IMG WIDTH="520" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
1794 SRC="img10.gif"
1795 ALT="$\textstyle\parbox{\pboxargslen}{\em f fl pred top$-$reduction$-$only ring \/}$"> [<EM>FUNCTION</EM>]
1796<BLOCKQUOTE>
1797Normal form of the polynomial with sugar F with respect to
1798a list of polynomials with sugar FL. Assumes that FL is not empty.
1799Parameters PRED, TOP<MATH CLASS="INLINE">
1800-
1801</MATH>REDUCTION<MATH CLASS="INLINE">
1802-
1803</MATH>ONLY and RING have the same
1804meaning as in NORMAL<MATH CLASS="INLINE">
1805-
1806</MATH>FORM. The parameter SUGAR<MATH CLASS="INLINE">
1807-
1808</MATH>LIMIT should be
1809set to a positive integer. If the sugar limit of the partial
1810remainder exceeds SUGAR<MATH CLASS="INLINE">
1811-
1812</MATH>LIMIT then the calculation is stopped and
1813the partial remainder is returned, although it is not fully reduced
1814with respect to FL. </BLOCKQUOTE><H4><A NAME="SECTION000200700000000000000">
1815<I>buchberger<MATH CLASS="INLINE">
1816-
1817</MATH>with<MATH CLASS="INLINE">
1818-
1819</MATH>sugar</I></A>
1820</H4>
1821<P><IMG WIDTH="443" HEIGHT="50" ALIGN="MIDDLE" BORDER="0"
1822 SRC="img52.gif"
1823 ALT="$\textstyle\parbox{\pboxargslen}{\em f$-$no$-$sugar pred start top$-$reduction$-$only ring {\sf \&aux} (s (1$-$\space (length f$-$no$-$sugar))) b m f \/}$"> [<EM>FUNCTION</EM>]
1824<BLOCKQUOTE>
1825Returns a Grobner basis of an ideal generated by a list of ordinary
1826polynomials F<MATH CLASS="INLINE">
1827-
1828</MATH>NO<MATH CLASS="INLINE">
1829-
1830</MATH>SUGAR. Adds initial sugar to the polynomials and
1831performs the Buchberger algorithm with ``sugar strategy''. It returns
1832an ordinary list of polynomials with no sugar. One of the most
1833effective algorithms for Grobner basis calculation.</BLOCKQUOTE><H4><A NAME="SECTION000200710000000000000">
1834<I>buchberger<MATH CLASS="INLINE">
1835-
1836</MATH>with<MATH CLASS="INLINE">
1837-
1838</MATH>sugar<MATH CLASS="INLINE">
1839-
1840</MATH>merge<MATH CLASS="INLINE">
1841-
1842</MATH>pairs</I></A>
1843</H4>
1844<P><IMG WIDTH="343" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
1845 SRC="img53.gif"
1846 ALT="$\textstyle\parbox{\pboxargslen}{\em b c g m pred ring \/}$"> [<EM>FUNCTION</EM>]
1847<BLOCKQUOTE>
1848Merges lists of critical pairs. It orders pairs according to
1849increasing sugar, with ties broken by smaller MOCK<MATH CLASS="INLINE">
1850-
1851</MATH>SPOLY value of
1852the two polynomials. In this function B must already be sorted.</BLOCKQUOTE><H4><A NAME="SECTION000200720000000000000">
1853<I>buchberger<MATH CLASS="INLINE">
1854-
1855</MATH>with<MATH CLASS="INLINE">
1856-
1857</MATH>sugar<MATH CLASS="INLINE">
1858-
1859</MATH>sort<MATH CLASS="INLINE">
1860-
1861</MATH>pairs</I></A>
1862</H4>
1863<P><IMG WIDTH="359" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
1864 SRC="img54.gif"
1865 ALT="$\textstyle\parbox{\pboxargslen}{\em c g m pred ring \/}$"> [<EM>FUNCTION</EM>]
1866<BLOCKQUOTE>
1867Sorts critical pairs C according to sugar strategy.</BLOCKQUOTE><H4><A NAME="SECTION000200730000000000000">
1868<I>criterion<MATH CLASS="INLINE">
1869-
1870</MATH>1<MATH CLASS="INLINE">
1871-
1872</MATH>with<MATH CLASS="INLINE">
1873-
1874</MATH>sugar</I></A>
1875</H4>
1876<P><IMG WIDTH="533" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"
1877 SRC="img17.gif"
1878 ALT="$\textstyle\parbox{\pboxargslen}{\em pair g {\sf \&aux} (i (first pair)) (j (second pair)) \/}$"> [<EM>FUNCTION</EM>]
1879<BLOCKQUOTE>
1880An implementation of Buchberger's first criterion for polynomials
1881with sugar. See the documentation of BUCHBERGER<MATH CLASS="INLINE">
1882-
1883</MATH>CRITERION<MATH CLASS="INLINE">
1884-
1885</MATH>1.</BLOCKQUOTE><H4><A NAME="SECTION000200740000000000000">
1886<I>criterion<MATH CLASS="INLINE">
1887-
1888</MATH>2<MATH CLASS="INLINE">
1889-
1890</MATH>with<MATH CLASS="INLINE">
1891-
1892</MATH>sugar</I></A>
1893</H4>
1894<P><IMG WIDTH="533" HEIGHT="31" ALIGN="MIDDLE" BORDER="0"
1895 SRC="img18.gif"
1896 ALT="$\textstyle\parbox{\pboxargslen}{\em pair g m {\sf \&aux} (i (first pair)) (j (second pair)) \/}$"> [<EM>FUNCTION</EM>]
1897<BLOCKQUOTE>
1898An implementation of Buchberger's first criterion for polynomials
1899with sugar. See the documentation of BUCHBERGER<MATH CLASS="INLINE">
1900-
1901</MATH>CRITERION<MATH CLASS="INLINE">
1902-
1903</MATH>2.</BLOCKQUOTE><H4><A NAME="SECTION000200750000000000000">
1904<I>gebauer<MATH CLASS="INLINE">
1905-
1906</MATH>moeller<MATH CLASS="INLINE">
1907-
1908</MATH>with<MATH CLASS="INLINE">
1909-
1910</MATH>sugar</I></A>
1911</H4>
1912<P><IMG WIDTH="494" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
1913 SRC="img47.gif"
1914 ALT="$\textstyle\parbox{\pboxargslen}{\em f pred start top$-$reduction$-$only ring {\sf \&aux} b g f1 \/}$"> [<EM>FUNCTION</EM>]
1915<BLOCKQUOTE>
1916Compute Grobner basis by using the algorithm of Gebauer and Moeller.
1917This algorithm is described as BUCHBERGERNEW2 in the book by
1918Becker<MATH CLASS="INLINE">
1919-
1920</MATH>Weispfenning entitled ``Grobner Bases''</BLOCKQUOTE><H4><A NAME="SECTION000200760000000000000">
1921<I>update<MATH CLASS="INLINE">
1922-
1923</MATH>with<MATH CLASS="INLINE">
1924-
1925</MATH>sugar</I></A>
1926</H4>
1927<P><IMG WIDTH="564" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
1928 SRC="img48.gif"
1929 ALT="$\textstyle\parbox{\pboxargslen}{\em g b h pred ring {\sf \&aux} c d e b$-$new g$-$new pair \/}$"> [<EM>FUNCTION</EM>]
1930<BLOCKQUOTE>
1931An implementation of the auxillary UPDATE algorithm used by the
1932Gebauer<MATH CLASS="INLINE">
1933-
1934</MATH>Moeller algorithm. G is a list of polynomials, B is a list
1935of critical pairs and H is a new polynomial which possibly will be
1936added to G. The naming conventions used are very close to the one
1937used in the book of Becker<MATH CLASS="INLINE">
1938-
1939</MATH>Weispfenning. Operates on polynomials
1940with sugar. </BLOCKQUOTE><H4><A NAME="SECTION000200770000000000000">
1941<I>gebauer<MATH CLASS="INLINE">
1942-
1943</MATH>moeller<MATH CLASS="INLINE">
1944-
1945</MATH>with<MATH CLASS="INLINE">
1946-
1947</MATH>sugar<MATH CLASS="INLINE">
1948-
1949</MATH>merge<MATH CLASS="INLINE">
1950-
1951</MATH>pairs</I></A>
1952</H4>
1953<P><IMG WIDTH="261" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
1954 SRC="img49.gif"
1955 ALT="$\textstyle\parbox{\pboxargslen}{\em b c pred ring \/}$"> [<EM>FUNCTION</EM>]
1956<BLOCKQUOTE>
1957Merges lists of critical pairs. It orders pairs according to
1958increasing sugar, with ties broken by smaller lcm of head monomials
1959In this function B must already be sorted. Operates on polynomials
1960with sugar. </BLOCKQUOTE><H4><A NAME="SECTION000200780000000000000">
1961<I>grobner<MATH CLASS="INLINE">
1962-
1963</MATH>primitive<MATH CLASS="INLINE">
1964-
1965</MATH>part<MATH CLASS="INLINE">
1966-
1967</MATH>with<MATH CLASS="INLINE">
1968-
1969</MATH>sugar</I></A>
1970</H4>
1971<P><IMG WIDTH="354" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
1972 SRC="img55.gif"
1973 ALT="$\textstyle\parbox{\pboxargslen}{\em h ring \/}$"> [<EM>FUNCTION</EM>]
1974<BLOCKQUOTE>
1975 </BLOCKQUOTE><HR>
1976<!--Navigation Panel-->
1977<A NAME="tex2html742"
1978 HREF="node3.html">
1979<IMG WIDTH="37" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="next" SRC="next_motif.gif"></A>
1980<A NAME="tex2html739"
1981 HREF="manual.html">
1982<IMG WIDTH="26" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="up" SRC="up_motif.gif"></A>
1983<A NAME="tex2html733"
1984 HREF="node1.html">
1985<IMG WIDTH="63" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="previous" SRC="previous_motif.gif"></A>
1986<A NAME="tex2html741"
1987 HREF="node1.html">
1988<IMG WIDTH="65" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="contents" SRC="contents_motif.gif"></A>
1989<BR>
1990<B> Next:</B> <A NAME="tex2html743"
1991 HREF="node3.html">The String Interface to</A>
1992<B> Up:</B> <A NAME="tex2html740"
1993 HREF="manual.html">CGBLisp User Guide and</A>
1994<B> Previous:</B> <A NAME="tex2html734"
1995 HREF="node1.html">Contents</A>
1996<!--End of Navigation Panel-->
1997<ADDRESS>
1998<I>Marek Rychlik</I>
1999<BR><I>3/21/1998</I>
2000</ADDRESS>
2001</BODY>
2002</HTML>
Note: See TracBrowser for help on using the repository browser.