1 /*****************************************************************************\
2 * Computer Algebra System SINGULAR
3 \*****************************************************************************/
4 /** @file cfCharSetsUtil.cc
5 *
6 * This file provides utility functions to compute characteristic sets
7 *
8 * @note some of the code is code from libfac or derived from code from libfac.
9 * Libfac is written by M. Messollen. See also COPYING for license information
10 * and README for general information on characteristic sets.
11 *
12 * @authors Martin Lee
13 *
14 **/
15 /*****************************************************************************/
16
17 #include "config.h"
18
19 #include "canonicalform.h"
20 #include "cf_algorithm.h"
21 #include "cfCharSetsUtil.h"
22
23 #define __ARRAY_INIT__ -1
24
25 // the maximal degree of polys in PS wrt. variable x
26 int
degpsmax(const CFList & PS,const Variable & x,Intarray & A,Intarray & C)27 degpsmax (const CFList & PS, const Variable & x,
28 Intarray & A, Intarray & C)
29 {
30 int varlevel= level(x);
31 if (A[varlevel] != __ARRAY_INIT__)
32 return A[varlevel];
33 int max= 0, temp, count= 0;
34
35 for (CFListIterator i= PS; i.hasItem(); i++)
36 {
37 temp= degree (i.getItem(), x);
38 if (temp > max)
39 {
40 max= temp;
41 count = 0;
42 }
43 if (temp == max)
44 count += max; // we count the number of polys
45 }
46 A[varlevel]= max;
47 C[varlevel]= count;
48 return max;
49 }
50
51 // the minimal non-zero degree of polys in PS wrt. x
52 // returns 0 if variable x doesn't occure in any of the polys
53 int
degpsmin(const CFList & PS,const Variable & x,Intarray & A,Intarray & B,Intarray & C,Intarray & D)54 degpsmin (const CFList & PS, const Variable & x, Intarray & A, Intarray & B,
55 Intarray & C, Intarray & D)
56 {
57 int varlevel= level(x);
58 if (B[varlevel] != __ARRAY_INIT__ )
59 return B[varlevel];
60 int min= degpsmax (PS, x, A, C), temp, count= 0;
61
62 if (min == 0)
63 {
64 B[varlevel]= min;
65 D[varlevel]= min;
66 return min;
67 }
68 else
69 {
70 for (CFListIterator i= PS; i.hasItem(); i++)
71 {
72 temp= degree (i.getItem(), x);
73 if (temp < min && temp != 0)
74 {
75 min= temp;
76 count= 0;
77 }
78 if (temp == min)
79 count += min; // we count the number of polys
80 }
81 }
82 B[varlevel]= min;
83 D[varlevel]= count;
84 return min;
85 }
86
87 // the minimal total degree of lcoeffs of polys in PS wrt. x
88 // for those polys having degree degpsmin in x.
89 // F will be assigned the minimal number of terms of those lcoeffs
90 int
Tdeg(const CFList & PS,const Variable & x,Intarray & A,Intarray & B,Intarray & C,Intarray & D,Intarray & E,Intarray & F)91 Tdeg (const CFList & PS, const Variable & x, Intarray & A, Intarray & B,
92 Intarray & C, Intarray & D, Intarray & E, Intarray & F)
93 {
94 int k= degpsmin (PS, x, A, B, C, D), varlevel= level(x), min= 0;
95
96 if (E[varlevel] != __ARRAY_INIT__)
97 return E [varlevel];
98 if (k == 0)
99 {
100 E[varlevel]= 0;
101 F[varlevel]= 0;
102 }
103 else
104 {
105 int nopslc= 0;
106 CFList LCdegList;
107 CanonicalForm elem;
108 CFListIterator i;
109
110 for (i= PS; i.hasItem(); i++)
111 {
112 elem= i.getItem();
113 if (degree (elem, x) == k)
114 LCdegList.append (LC (elem, x));
115 }
116
117 if (LCdegList.length() > 0)
118 {
119 CFList TermList;
120 int newmin, newnopslc;
121
122 min= totaldegree (LCdegList.getFirst());
123 TermList= get_Terms (LCdegList.getFirst());
124 nopslc= TermList.length();
125 for (i= LCdegList; i.hasItem(); i++)
126 {
127 elem= i.getItem();
128 newmin= totaldegree(elem);
129 TermList= get_Terms(elem);
130 newnopslc= TermList.length();
131 if (newmin < min)
132 min= newmin;
133 if (newnopslc < nopslc)
134 nopslc= newnopslc;
135 }
136
137 }
138 E[varlevel]= min;
139 F[varlevel]= nopslc;
140 }
141 return min;
142 }
143
144 // The number of the poly in which Variable x first occures
145 int
nr_of_poly(const CFList & PS,const Variable & x,Intarray & G)146 nr_of_poly( const CFList & PS, const Variable & x, Intarray & G)
147 {
148 int min= 0, varlevel= level(x);
149 if (G[varlevel] != __ARRAY_INIT__)
150 return G[varlevel];
151 for (CFListIterator i= PS; i.hasItem(); i++)
152 {
153 min += 1;
154 if (degree (i.getItem(), x) > 0)
155 break;
156 }
157 G[varlevel]= min;
158 return min;
159 }
160
161 int
degord(const Variable & x,const Variable & y,const CFList & PS,Intarray & A,Intarray & B,Intarray & C,Intarray & D,Intarray & E,Intarray & F,Intarray & G)162 degord (const Variable & x, const Variable & y, const CFList & PS,
163 Intarray & A, Intarray & B, Intarray & C, Intarray & D,
164 Intarray & E, Intarray & F, Intarray & G)
165 {
166 int xlevel= level(x), ylevel= level(y);
167
168 if (degpsmax(PS,y,A,C) < degpsmax(PS,x,A,C)) return 1;
169 else if (degpsmax(PS,x,A,C) < degpsmax(PS,y,A,C) ) return 0;
170 else if (C[ylevel] < C[xlevel]) return 1;
171 else if (C[xlevel] < C[ylevel]) return 0;
172 else if (degpsmin(PS,x,A,B,C,D) < degpsmin(PS,y,A,B,C,D)) return 1;
173 else if (degpsmin(PS,y,A,B,C,D) < degpsmin(PS,x,A,B,C,D)) return 0;
174 else if (D[ylevel] < D[xlevel]) return 1;
175 else if (D[xlevel] < D[ylevel]) return 0;
176 else if (Tdeg(PS,y,A,B,C,D,E,F) < Tdeg(PS,x,A,B,C,D,E,F)) return 1;
177 else if (Tdeg(PS,x,A,B,C,D,E,F) < Tdeg(PS,y,A,B,C,D,E,F)) return 0;
178 else if (F[ylevel] < F[xlevel]) return 1;
179 else if (F[xlevel] < F[ylevel]) return 0;
180 else if (nr_of_poly(PS,x,G) <= nr_of_poly(PS,y,G)) return 1;
181 else return 0;
182 }
183
184 // determine the highest variable of all involved Variables in PS
185 // NOTE:
186 // this doesn't give always the correct answer:
187 // If a variable is assigned the highest level in the definition of the
188 // original ring, but doesn't occure in any of the
189 // polynomials, get_max_var returns the variable with a level lower than
190 // the highest level.
191 // Is there a workaround?
192 // But for the redefinition of the ring this doesn't matter due to the
193 // implementation of neworder().
194
195 Variable
get_max_var(const CFList & PS)196 get_max_var (const CFList & PS)
197 {
198 Variable x= PS.getFirst().mvar(), y;
199 for (CFListIterator i= PS; i.hasItem(); i++)
200 {
201 y= i.getItem().mvar();
202 if (y > x)
203 x= y;
204 }
205 return x;
206 }
207
208
209 // determine if variable x is in one and only one of the polynomials in PS
210 // first criterion for neworder
211 CFList
only_in_one(const CFList & PS,const Variable & x)212 only_in_one (const CFList & PS, const Variable & x)
213 {
214 CFList output;
215
216 for (CFListIterator i= PS; i.hasItem(); i++ )
217 {
218 if (degree (i.getItem(), x) >= 1)
219 output.insert (i.getItem());
220 if (output.length() >= 2)
221 break;
222 }
223 return output;
224 }
225
226 // initialize all Arrays (of same range) with __ARRAY_INIT__
227 void
initArray(const int highest_level,Intarray & A,Intarray & B,Intarray & C,Intarray & D,Intarray & E,Intarray & F,Intarray & G)228 initArray (const int highest_level, Intarray & A, Intarray & B, Intarray & C,
229 Intarray & D, Intarray & E, Intarray & F, Intarray & G)
230 {
231 for (int i=1 ; i <= highest_level; i ++)
232 {
233 A[i]= __ARRAY_INIT__;
234 B[i]= __ARRAY_INIT__;
235 C[i]= __ARRAY_INIT__;
236 D[i]= __ARRAY_INIT__;
237 E[i]= __ARRAY_INIT__;
238 F[i]= __ARRAY_INIT__;
239 G[i]= __ARRAY_INIT__;
240 }
241 }
242
243 // now for the second criterion; a little more complex
244 //
245 // idea: set up seven arrays of lenth highest_level
246 // (of which some entries may be empty, because of only_in_one!)
247 // A saves maxdegree of Variable x in A(level(x))
248 // B saves mindegree of Variable x in B(level(x))
249 // C saves the number of polys in PS which have degree A(level(x)) in
250 // D(level(x))
251 // D saves the number of polys in PS which have degree B(level(x)) in
252 // D(level(x))
253 // E saves the minimal total degree of lcoeffs of polys wrt x in E(level(x))
254 // F saves the minimal number of terms of lcoeffs of E(level(x)) in F(~)
255 // G saves nr of poly Variable x has first deg <> 0
256
257 #define __INIT_GAP__ 3
258 Varlist
reorderb(const Varlist & difference,const CFList & PS,const int highest_level)259 reorderb (const Varlist & difference, const CFList & PS,
260 const int highest_level)
261 {
262 Intarray A(1, highest_level), B(1, highest_level), C(1, highest_level),
263 D(1, highest_level), E(1, highest_level), F(1, highest_level),
264 G(1, highest_level);
265 initArray (highest_level, A, B, C, D, E, F, G);
266 int i= 0, j, n= difference.length(), gap= 1 + __INIT_GAP__;
267 Variable temp;
268 Array<Variable> v(0, n);
269 VarlistIterator J;
270
271 for (J= difference; J.hasItem(); J++ )
272 {
273 v[i]= J.getItem();
274 i++;
275 }
276
277 while (gap <= n)
278 gap = __INIT_GAP__ * gap + 1;
279 gap /= __INIT_GAP__;
280
281 while (gap > 0)
282 {
283 for (i= gap; i <= n - 1; i++)
284 {
285 temp= v[i];
286 for (j= i - gap; j >=0 ; j -= gap)
287 {
288 if (degord (v[j], temp, PS, A, B, C, D, E, F, G))
289 break;
290 v[j + gap]= v[j];
291 }
292 v[j + gap]= temp;
293 }
294 gap /= __INIT_GAP__;
295 }
296 Varlist output;
297 for (i= 0; i <= n - 1; i++)
298 output.append (v[i]);
299 return output;
300 }
301
302 /// swapvar a whole list of CanonicalForms
303 CFList
swapvar(const CFList & PS,const Variable & x,const Variable & y)304 swapvar (const CFList & PS, const Variable & x, const Variable & y)
305 {
306 CFList ps;
307
308 for (CFListIterator i= PS; i.hasItem(); i++)
309 ps.append (swapvar (i.getItem(), x, y));
310 return ps;
311 }
312
313 CFFList
swapvar(const CFFList & PS,const Variable & x,const Variable & y)314 swapvar (const CFFList & PS, const Variable & x, const Variable & y)
315 {
316 CFFList ps;
317
318 for (CFFListIterator i= PS; i.hasItem(); i++)
319 ps.append (CFFactor (swapvar (i.getItem().factor(), x, y),
320 i.getItem().exp()));
321 return ps;
322 }
323
324 bool
lowerRank(const CanonicalForm & F,const CanonicalForm & G,int & ind)325 lowerRank (const CanonicalForm & F, const CanonicalForm & G, int & ind)
326 {
327 int degF, degG, levelF, levelG;
328
329 levelF= F.level();
330 levelG= G.level();
331 if (F.inCoeffDomain())
332 {
333 if (G.inCoeffDomain())
334 ind= 1;
335 return true;
336 }
337 else if (G.inCoeffDomain())
338 return false;
339 else if (levelF < levelG)
340 return true;
341 else if (levelF == levelG)
342 {
343 degF= degree(F);
344 degG= degree(G);
345 if (degF < degG)
346 return true;
347 else if (degF == degG)
348 return lowerRank (LC (F), LC (G), ind);
349 else
350 return false;
351 }
352 return false;
353 }
354
355
356 CanonicalForm
lowestRank(const CFList & L)357 lowestRank (const CFList & L)
358 {
359 CFListIterator i= L;
360 CanonicalForm f;
361 int ind= 0;
362 if (!i.hasItem())
363 return f;
364
365 f= i.getItem();
366 i++;
367
368 while (i.hasItem())
369 {
370 if (lowerRank (i.getItem(), f, ind))
371 {
372 if (ind)
373 {
374 if (size (i.getItem()) < size (f))
375 f= i.getItem();
376 ind= 0;
377 }
378 else
379 f= i.getItem();
380 }
381 i++;
382 }
383 return f;
384 }
385
minLevel(const CFList & L)386 int minLevel (const CFList& L)
387 {
388 if (L.isEmpty())
389 return 0;
390 int min= size (L.getFirst());
391 return min;
392 }
393
394 /// sort in descending order of length of elements
395 void
sortListCFList(ListCFList & list)396 sortListCFList (ListCFList& list)
397 {
398 int l= 1;
399 int k= 1;
400 CFList buf;
401 ListCFListIterator m;
402 for (ListCFListIterator i= list; l <= list.length(); i++, l++)
403 {
404 for (ListCFListIterator j= list; k <= list.length() - l; k++)
405 {
406 m= j;
407 m++;
408 if ((j.getItem().length() < m.getItem().length()) ||
409 (j.getItem().length() == m.getItem().length() &&
410 minLevel (j.getItem()) > minLevel (m.getItem())))
411 {
412 buf= m.getItem();
413 m.getItem()= j.getItem();
414 j.getItem()= buf;
415 j++;
416 j.getItem()= m.getItem();
417 }
418 else
419 j++;
420 }
421 k= 1;
422 }
423 }
424
425
426 /// sort in descending order of level of elements
427 void
sortCFListByLevel(CFList & list)428 sortCFListByLevel (CFList& list)
429 {
430 int l= 1;
431 int k= 1;
432 CanonicalForm buf;
433 CFListIterator m;
434 for (CFListIterator i= list; l <= list.length(); i++, l++)
435 {
436 for (CFListIterator j= list; k <= list.length() - l; k++)
437 {
438 m= j;
439 m++;
440 if ((size (j.getItem()) < size (m.getItem())) ||
441 ((size (j.getItem()) == size (m.getItem()))
442 && (j.getItem().level() < m.getItem().level())))
443 {
444 buf= m.getItem();
445 m.getItem()= j.getItem();
446 j.getItem()= buf;
447 j++;
448 j.getItem()= m.getItem();
449 }
450 else
451 j++;
452 }
453 k= 1;
454 }
455 }
456
457
458 /* basic operations on lists */
459 /// is PS a subset of Cset ?
460 bool
isSubset(const CFList & PS,const CFList & Cset)461 isSubset (const CFList &PS, const CFList& Cset)
462 {
463 for (CFListIterator i= PS; i.hasItem(); i++)
464 {
465 if (!find (Cset, i.getItem()))
466 return 0;
467 }
468 return 1;
469 }
470
471 /// Union of a and b stored in b
472 void
inplaceUnion(const ListCFList & a,ListCFList & b)473 inplaceUnion (const ListCFList& a, ListCFList& b)
474 {
475 if (a.isEmpty())
476 return;
477 if (b.isEmpty())
478 {
479 b= a;
480 return;
481 }
482
483 ListCFListIterator i;
484 CFList elem;
485
486 for (i= a; i.hasItem(); i++)
487 {
488 elem= i.getItem();
489 if ((!elem.isEmpty()) && (!find (b, elem)))
490 b.insert(elem);
491 }
492 }
493
494 ListCFList
adjoin(const CFList & is,const CFList & qs,const ListCFList & qh)495 adjoin (const CFList& is, const CFList& qs, const ListCFList& qh)
496 {
497 ListCFList iss, qhi;
498 ListCFListIterator j;
499 CFList iscopy, itt;
500 CFListIterator i;
501 int ind, length;
502
503 for (i= is; i.hasItem(); i++)
504 {
505 if (i.getItem().level() > 0)
506 iscopy= Union (CFList (i.getItem()), iscopy);
507 }
508 if (iscopy.isEmpty())
509 return iss;
510
511 qhi= Difference (qh, qs);
512 length= qhi.length();
513
514 for (i= iscopy; i.hasItem(); i++)
515 {
516 itt= Union (qs, CFList (i.getItem()));
517 ind= 0;
518 if (length > 0)
519 {
520 for (j= qhi; j.hasItem(); j++)
521 {
522 if (isSubset (j.getItem(), itt))
523 ind= 1;
524 }
525 }
526 if (ind == 0)
527 iss.append (itt);
528 }
529 return iss;
530 }
531
532 ListCFList
adjoinb(const CFList & is,const CFList & qs,const ListCFList & qh,const CFList & cs)533 adjoinb (const CFList & is, const CFList & qs, const ListCFList & qh,
534 const CFList & cs)
535 {
536 ListCFList iss, qhi;
537 ListCFListIterator j;
538 CFList iscopy, itt;
539 CFListIterator i;
540 int ind, length;
541
542 for (i= is ; i.hasItem(); i++)
543 {
544 if (i.getItem().level() > 0)
545 iscopy= Union (CFList (i.getItem()), iscopy);
546 }
547 if (iscopy.isEmpty())
548 return iss;
549 qhi= Difference (qh, qs);
550 length= qhi.length();
551 for (i= iscopy; i.hasItem(); i++)
552 {
553 itt= Union (Union (qs, CFList (i.getItem())), cs);
554 ind= 0;
555 if (length > 0)
556 {
557 for (j= qhi; j.hasItem(); j++)
558 {
559 if (isSubset (j.getItem(), itt))
560 ind= 1;
561 }
562 }
563 if (ind == 0)
564 iss.append(itt);
565 }
566 return iss;
567 }
568
569 void
select(const ListCFList & ppi,int length,ListCFList & ppi1,ListCFList & ppi2)570 select (const ListCFList& ppi, int length, ListCFList& ppi1, ListCFList& ppi2)
571 {
572 CFList elem;
573 for (ListCFListIterator i= ppi; i.hasItem(); i++)
574 {
575 elem= i.getItem();
576 if (!elem.isEmpty())
577 {
578 if (length <= elem.length())
579 ppi2.append(elem);
580 else
581 ppi1.append(elem);
582 }
583 }
584 }
585
586 /* end basic operations on lists */
587
588 /// normalize a poly, i.e. in char 0 clear denominators, remove integer content
589 /// in char p divide by leading coeff
normalize(const CanonicalForm & F)590 CanonicalForm normalize (const CanonicalForm& F)
591 {
592 if (F.isZero())
593 return F;
594 if (getCharacteristic() == 0)
595 {
596 CanonicalForm G;
597 bool isRat= isOn (SW_RATIONAL);
598 if (!isRat)
599 On (SW_RATIONAL);
600 G= F;
601 G *= bCommonDen (G);
602 Off (SW_RATIONAL);
603 G /= icontent (G);
604 if (isRat)
605 On (SW_RATIONAL);
606 if (lc(G) < 0)
607 G= -G;
608 return G;
609 }
610
611 return F/lc (F);
612 }
613
614 /// pseudo remainder of F by G with certain factors of LC (g) cancelled
615 CanonicalForm
Prem(const CanonicalForm & F,const CanonicalForm & G)616 Prem (const CanonicalForm& F, const CanonicalForm& G)
617 {
618 CanonicalForm f, g, l, test, lu, lv, t, retvalue;
619 int degF, degG, levelF, levelG;
620 bool reord;
621 Variable v, vg= G.mvar();
622
623 if ( (levelF= F.level()) < (levelG= G.level()))
624 return F;
625 else
626 {
627 if ( levelF == levelG )
628 {
629 f= F;
630 g= G;
631 reord= false;
632 v= F.mvar();
633 }
634 else
635 {
636 v= Variable (levelF + 1);
637 f= swapvar (F, vg, v);
638 g= swapvar (G, vg, v);
639 reord= true;
640 }
641 degG= degree (g, v );
642 degF= degree (f, v );
643 if (degG <= degF)
644 {
645 l= LC (g);
646 g= g - l*power (v, degG);
647 }
648 else
649 l= 1;
650 while ((degG <= degF) && (!f.isZero()))
651 {
652 test= gcd (l, LC(f));
653 lu= l / test;
654 lv= LC(f) / test;
655 t= g*lv*power (v, degF - degG);
656
657 if (degF == 0)
658 f= 0;
659 else
660 f= f - LC (f)*power (v, degF);
661
662 f= f*lu - t;
663 degF= degree (f, v);
664 }
665
666 if (reord)
667 retvalue= swapvar (f, vg, v);
668 else
669 retvalue= f;
670
671 return retvalue;
672 }
673 }
674
675 /// pseudo remainder of f by L with faster test for remainder being zero
676 CanonicalForm
Premb(const CanonicalForm & f,const CFList & L)677 Premb (const CanonicalForm &f, const CFList &L)
678 {
679 CanonicalForm rem= f;
680 CFList l= L;
681 l.removeFirst();
682 CFListIterator i= l;
683
684 for (i.lastItem(); i.hasItem(); i--)
685 rem= normalize (Prem (rem, i.getItem()));
686
687 CanonicalForm tmp= L.getFirst()/content (L.getFirst());
688
689 bool isRat= isOn (SW_RATIONAL);
690 int ch=getCharacteristic();
691 if (ch == 0 && !isRat)
692 On (SW_RATIONAL);
693 if (fdivides (tmp, rem))
694 {
695 if (ch == 0 && !isRat)
696 Off (SW_RATIONAL);
697 return 0;
698 }
699
700 if (ch == 0 && !isRat)
701 Off (SW_RATIONAL);
702
703 rem= normalize (Prem (rem, L.getFirst()));
704
705 return rem;
706 }
707
708 /// pseudo remainder of f by L
709 CanonicalForm
Prem(const CanonicalForm & f,const CFList & L)710 Prem (const CanonicalForm &f, const CFList &L)
711 {
712 CanonicalForm rem= f;
713 CFListIterator i= L;
714
715 for (i.lastItem(); i.hasItem(); i--)
716 rem= normalize (Prem (rem, i.getItem()));
717
718 return rem;
719 }
720
uniGcd(const CFList & L)721 CFList uniGcd (const CFList& L)
722 {
723 CFList tmp;
724 CanonicalForm g;
725 CFListIterator i;
726 for (i= L; i.hasItem(); i++)
727 {
728 if (i.getItem().isUnivariate() && i.getItem().level() == 1)
729 tmp.append (i.getItem());
730 }
731 if (tmp.length() <= 2)
732 return L;
733 i= tmp;
734 g= i.getItem();
735 i++;
736 g= gcd (g,i.getItem());
737 i++;
738 for (; i.hasItem(); i++)
739 g= gcd (g, i.getItem());
740 return Union (Difference (L, tmp), CFList (g));
741 }
742
initials(const CFList & L)743 CFList initials (const CFList& L)
744 {
745 CFList result;
746 for (CFListIterator iter= L; iter.hasItem(); iter++)
747 {
748 if (!LC(iter.getItem()).inCoeffDomain())
749 result.append (LC (iter.getItem()));
750 }
751 return result;
752 }
753
754 CFList
factorsOfInitials(const CFList & L)755 factorsOfInitials(const CFList & L)
756 {
757 CFList result;
758 CFFList factors;
759 CanonicalForm tmp;
760
761 for (CFListIterator i= L; i.hasItem(); i++)
762 {
763 factors= factorize (LC (i.getItem()));
764 for (CFFListIterator j= factors; j.hasItem(); j++)
765 {
766 tmp= j.getItem().factor();
767 if (!tmp.inCoeffDomain())
768 result= Union (result, CFList (normalize (tmp)));
769 }
770 }
771
772 return result;
773 }
774
775 void
removeContent(CanonicalForm & F,CanonicalForm & cF)776 removeContent (CanonicalForm& F, CanonicalForm& cF)
777 {
778 if (size (F) == 1)
779 {
780 CanonicalForm tmp= F;
781 F= F.mvar();
782 cF= tmp/F;
783 if (!cF.inCoeffDomain())
784 cF= normalize (cF);
785 else
786 cF= 0;
787 F= normalize (F);
788
789 return;
790 }
791
792 cF= content (F);
793
794 if (cF.inCoeffDomain())
795 cF= 0;
796 else
797 {
798 cF= normalize (cF);
799 F /= cF;
800 F= normalize (F);
801 }
802 }
803
804 CFList
factorPSet(const CFList & PS)805 factorPSet (const CFList& PS)
806 {
807 CFList result;
808 CFFList factors;
809 CFFListIterator j;
810
811 for (CFListIterator i= PS; i. hasItem(); i++)
812 {
813 factors= factorize (i.getItem());
814 if (factors.getFirst().factor().inCoeffDomain())
815 factors.removeFirst();
816 for (j= factors; j.hasItem(); j++ )
817 result= Union (result, CFList (normalize (j.getItem().factor())));
818 }
819 return result;
820 }
821
822 void
removeFactors(CanonicalForm & r,StoreFactors & StoredFactors,CFList & removedFactors)823 removeFactors (CanonicalForm& r, StoreFactors& StoredFactors,
824 CFList& removedFactors)
825 {
826 CanonicalForm quot;
827 CFList testlist;
828 int n= level(r);
829 bool divides;
830 CFListIterator j;
831
832 for (int i=1; i<= n; i++)
833 testlist.append (CanonicalForm (Variable (i)));
834
835 // remove already removed factors
836 for (j= StoredFactors.FS1; j.hasItem(); j++)
837 {
838 while (fdivides (j.getItem(), r, quot))
839 {
840 r= quot;
841 }
842 }
843
844 for (j= StoredFactors.FS2; j.hasItem(); j++)
845 {
846 divides= false;
847 if (j.getItem() != r)
848 {
849 while (fdivides (j.getItem(), r, quot))
850 {
851 divides= true;
852 r= quot;
853 }
854 if (divides)
855 removedFactors= Union (removedFactors, CFList (j.getItem()));
856 }
857 }
858 r= normalize (r);
859
860 // remove variables
861 for (j= testlist; j.hasItem() && !r.isOne(); j++)
862 {
863 divides= false;
864 if (j.getItem() != r)
865 {
866 while (fdivides (j.getItem(), r, quot))
867 {
868 divides= true;
869 r= quot;
870 }
871 if (divides)
872 removedFactors= Union (removedFactors, CFList (j.getItem()));
873 }
874 }
875 r= normalize (r);
876 }
877
878 CFList
removeContent(const CFList & PS,StoreFactors & StoredFactors)879 removeContent (const CFList & PS, StoreFactors & StoredFactors)
880 {
881 CFListIterator i= PS;
882 if ((!i.hasItem()) || (PS.getFirst().level() == 0 ))
883 return PS;
884
885 CFList output;
886 CanonicalForm cc,elem;
887
888 for (; i.hasItem(); i++)
889 {
890 elem= i.getItem();
891 cc= content (elem, elem.mvar());
892 if (cc.level() > 0 )
893 {
894 output.append (normalize (elem / cc));
895 StoredFactors.FS1 = Union (CFList (normalize (cc)), StoredFactors.FS1);
896 }
897 else
898 output.append(normalize (elem));
899 }
900 return output;
901 }
902
903 bool
contractsub(const CFList & cs1,const CFList & cs2)904 contractsub (const CFList& cs1, const CFList& cs2)
905 {
906 CFListIterator i;
907
908 CanonicalForm r;
909 for (i= cs1; i.hasItem(); i++)
910 {
911 if (Prem (i.getItem(), cs2) != 0)
912 return false;
913 }
914
915 CFList is= factorsOfInitials (cs1);
916
917 for (i= is; i.hasItem(); i++)
918 {
919 if (Prem (i.getItem(), cs2) == 0)
920 return false;
921 }
922 return true;
923 }
924
925 ListCFList
contract(const ListCFList & cs)926 contract (const ListCFList& cs)
927 {
928 ListCFList mem, ts;
929 CFList iitem, jitem;
930
931 if (cs.length() < 2)
932 return cs;
933
934 int l= cs.length();
935 int ii= 1;
936 ListCFListIterator j;
937 for (ListCFListIterator i= cs; i.hasItem() && ii < l; i++, ii++)
938 {
939 iitem= i.getItem();
940 if (!find (mem, iitem))
941 {
942 j= i;
943 j++;
944 for (; j.hasItem(); j++)
945 {
946 jitem= j.getItem();
947 if (!find (mem, jitem))
948 {
949 if (contractsub (iitem, jitem))
950 {
951 ts.append (jitem);
952 mem.append (jitem);
953 }
954 else
955 {
956 if (contractsub (jitem, iitem))
957 ts.append (iitem); // no mem.append (item) because we assume cs does not contain duplicate entries
958 }
959 }
960 }
961 }
962 }
963 return Difference (cs,ts);
964 }
965
966