cfCharSetsUtil.cc
Go to the documentation of this file.
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
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
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
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;
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
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
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
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
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
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
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
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
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
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 
357 lowestRank (const CFList & L)
358 {
359  CFListIterator i= L;
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 
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
397 {
398  int l= 1;
399  int k= 1;
400  CFList buf;
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
429 {
430  int l= 1;
431  int k= 1;
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
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
474 {
475  if (a.isEmpty())
476  return;
477  if (b.isEmpty())
478  {
479  b= a;
480  return;
481  }
482 
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 
495 adjoin (const CFList& is, const CFList& qs, const ListCFList& qh)
496 {
497  ListCFList iss, qhi;
499  CFList iscopy, itt;
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 
533 adjoinb (const CFList & is, const CFList & qs, const ListCFList & qh,
534  const CFList & cs)
535 {
536  ListCFList iss, qhi;
538  CFList iscopy, itt;
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
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
591 {
592  if (F.isZero())
593  return F;
594  if (getCharacteristic() == 0)
595  {
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
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
677 Premb (const CanonicalForm &f, const CFList &L)
678 {
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  if (getCharacteristic() == 0 && !isRat)
691  On (SW_RATIONAL);
692  if (fdivides (tmp, rem))
693  {
694  if (getCharacteristic() == 0 && !isRat)
695  Off (SW_RATIONAL);
696  return 0;
697  }
698 
699  if (getCharacteristic() == 0 && !isRat)
700  Off (SW_RATIONAL);
701 
702  rem= normalize (Prem (rem, L.getFirst()));
703 
704  return rem;
705 }
706 
707 /// pseudo remainder of f by L
709 Prem (const CanonicalForm &f, const CFList &L)
710 {
712  CFListIterator i= L;
713 
714  for (i.lastItem(); i.hasItem(); i--)
715  rem= normalize (Prem (rem, i.getItem()));
716 
717  return rem;
718 }
719 
720 CFList uniGcd (const CFList& L)
721 {
722  CFList tmp;
725  for (i= L; i.hasItem(); i++)
726  {
727  if (i.getItem().isUnivariate() && i.getItem().level() == 1)
728  tmp.append (i.getItem());
729  }
730  if (tmp.length() <= 2)
731  return L;
732  i= tmp;
733  g= i.getItem();
734  i++;
735  g= gcd (g,i.getItem());
736  i++;
737  for (; i.hasItem(); i++)
738  g= gcd (g, i.getItem());
739  return Union (Difference (L, tmp), CFList (g));
740 }
741 
743 {
744  CFList result;
745  for (CFListIterator iter= L; iter.hasItem(); iter++)
746  {
747  if (!LC(iter.getItem()).inCoeffDomain())
748  result.append (LC (iter.getItem()));
749  }
750  return result;
751 }
752 
753 CFList
755 {
756  CFList result;
757  CFFList factors;
758  CanonicalForm tmp;
759 
760  for (CFListIterator i= L; i.hasItem(); i++)
761  {
762  factors= factorize (LC (i.getItem()));
763  for (CFFListIterator j= factors; j.hasItem(); j++)
764  {
765  tmp= j.getItem().factor();
766  if (!tmp.inCoeffDomain())
767  result= Union (result, CFList (normalize (tmp)));
768  }
769  }
770 
771  return result;
772 }
773 
774 void
776 {
777  if (size (F) == 1)
778  {
779  CanonicalForm tmp= F;
780  F= F.mvar();
781  cF= tmp/F;
782  if (!cF.inCoeffDomain())
783  cF= normalize (cF);
784  else
785  cF= 0;
786  F= normalize (F);
787 
788  return;
789  }
790 
791  cF= content (F);
792 
793  if (cF.inCoeffDomain())
794  cF= 0;
795  else
796  {
797  cF= normalize (cF);
798  F /= cF;
799  F= normalize (F);
800  }
801 }
802 
803 CFList
804 factorPSet (const CFList& PS)
805 {
806  CFList result;
807  CFFList factors;
809 
810  for (CFListIterator i= PS; i. hasItem(); i++)
811  {
812  factors= factorize (i.getItem());
813  if (factors.getFirst().factor().inCoeffDomain())
814  factors.removeFirst();
815  for (j= factors; j.hasItem(); j++ )
816  result= Union (result, CFList (normalize (j.getItem().factor())));
817  }
818  return result;
819 }
820 
821 void
823  CFList& removedFactors)
824 {
825  CanonicalForm quot;
826  CFList testlist;
827  int n= level(r);
828  bool divides;
830 
831  for (int i=1; i<= n; i++)
832  testlist.append (CanonicalForm (Variable (i)));
833 
834  // remove already removed factors
835  for (j= StoredFactors.FS1; j.hasItem(); j++)
836  {
837  while (fdivides (j.getItem(), r, quot))
838  {
839  r= quot;
840  }
841  }
842 
843  for (j= StoredFactors.FS2; j.hasItem(); j++)
844  {
845  divides= false;
846  if (j.getItem() != r)
847  {
848  while (fdivides (j.getItem(), r, quot))
849  {
850  divides= true;
851  r= quot;
852  }
853  if (divides)
854  removedFactors= Union (removedFactors, CFList (j.getItem()));
855  }
856  }
857  r= normalize (r);
858 
859  // remove variables
860  for (j= testlist; j.hasItem() && !r.isOne(); j++)
861  {
862  divides= false;
863  if (j.getItem() != r)
864  {
865  while (fdivides (j.getItem(), r, quot))
866  {
867  divides= true;
868  r= quot;
869  }
870  if (divides)
871  removedFactors= Union (removedFactors, CFList (j.getItem()));
872  }
873  }
874  r= normalize (r);
875 }
876 
877 CFList
878 removeContent (const CFList & PS, StoreFactors & StoredFactors)
879 {
880  CFListIterator i= PS;
881  if ((!i.hasItem()) || (PS.getFirst().level() == 0 ))
882  return PS;
883 
884  CFList output;
885  CanonicalForm cc,elem;
886 
887  for (; i.hasItem(); i++)
888  {
889  elem= i.getItem();
890  cc= content (elem, elem.mvar());
891  if (cc.level() > 0 )
892  {
893  output.append (normalize (elem / cc));
894  StoredFactors.FS1 = Union (CFList (normalize (cc)), StoredFactors.FS1);
895  }
896  else
897  output.append(normalize (elem));
898  }
899  return output;
900 }
901 
902 bool
903 contractsub (const CFList& cs1, const CFList& cs2)
904 {
906 
908  for (i= cs1; i.hasItem(); i++)
909  {
910  if (Prem (i.getItem(), cs2) != 0)
911  return false;
912  }
913 
914  CFList is= factorsOfInitials (cs1);
915 
916  for (i= is; i.hasItem(); i++)
917  {
918  if (Prem (i.getItem(), cs2) == 0)
919  return false;
920  }
921  return true;
922 }
923 
925 contract (const ListCFList& cs)
926 {
927  ListCFList mem, ts;
928  CFList iitem, jitem;
929 
930  if (cs.length() < 2)
931  return cs;
932 
933  int l= cs.length();
934  int ii= 1;
936  for (ListCFListIterator i= cs; i.hasItem() && ii < l; i++, ii++)
937  {
938  iitem= i.getItem();
939  if (!find (mem, iitem))
940  {
941  j= i;
942  j++;
943  for (; j.hasItem(); j++)
944  {
945  jitem= j.getItem();
946  if (!find (mem, jitem))
947  {
948  if (contractsub (iitem, jitem))
949  {
950  ts.append (jitem);
951  mem.append (jitem);
952  }
953  else
954  {
955  if (contractsub (jitem, iitem))
956  ts.append (iitem); // no mem.append (item) because we assume cs does not contain duplicate entries
957  }
958  }
959  }
960  }
961  }
962  return Difference (cs,ts);
963 }
964 
int status int void size_t count
Definition: si_signals.h:59
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
void sortCFListByLevel(CFList &list)
sort in descending order of level of elements
void removeFactors(CanonicalForm &r, StoreFactors &StoredFactors, CFList &removedFactors)
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
ListCFList adjoin(const CFList &is, const CFList &qs, const ListCFList &qh)
CanonicalForm icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f )
Definition: cf_gcd.cc:71
CF_NO_INLINE bool isOne() const
CF_INLINE bool CanonicalForm::isOne, isZero () const.
Definition: cf_inline.cc:354
#define D(A)
Definition: gentable.cc:123
Variable get_max_var(const CFList &PS)
bool contractsub(const CFList &cs1, const CFList &cs2)
void rem(unsigned long *a, unsigned long *q, unsigned long p, int &dega, int degq)
Definition: minpoly.cc:574
const poly a
Definition: syzextra.cc:212
CFList FS1
factors that were removed
int level(const CanonicalForm &f)
void inplaceUnion(const ListCFList &a, ListCFList &b)
Union of a and b stored in b.
Varlist reorderb(const Varlist &difference, const CFList &PS, const int highest_level)
int isEmpty() const
Definition: ftmpl_list.cc:267
CanonicalForm normalize(const CanonicalForm &F)
normalize a poly, i.e. in char 0 clear denominators, remove integer content in char p divide by leadi...
void Off(int sw)
switches
CFList factorsOfInitials(const CFList &L)
static int min(int a, int b)
Definition: fast_mult.cc:268
void sortListCFList(ListCFList &list)
sort in descending order of length of elements
factory&#39;s class for variables
Definition: factory.h:115
class to store factors that get removed during char set computation
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
CFList uniGcd(const CFList &L)
int degpsmax(const CFList &PS, const Variable &x, Intarray &A, Intarray &C)
void lastItem()
Definition: ftmpl_list.cc:485
int minLevel(const CFList &L)
bool isSubset(const CFList &PS, const CFList &Cset)
is PS a subset of Cset ?
void removeContent(CanonicalForm &F, CanonicalForm &cF)
CFFListIterator iter
Definition: facAbsBiFact.cc:54
factory&#39;s main class
Definition: canonicalform.h:75
void initArray(const int highest_level, Intarray &A, Intarray &B, Intarray &C, Intarray &D, Intarray &E, Intarray &F, Intarray &G)
g
Definition: cfModGcd.cc:4031
int k
Definition: cfEzgcd.cc:93
void insert(const T &)
Definition: ftmpl_list.cc:193
static TreeM * G
Definition: janet.cc:38
int getCharacteristic()
Definition: cf_char.cc:51
template bool find(const List< CanonicalForm > &, const CanonicalForm &)
void removeFirst()
Definition: ftmpl_list.cc:287
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:180
T getFirst() const
Definition: ftmpl_list.cc:279
CanonicalForm lc(const CanonicalForm &f)
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
This file provides utility functions to compute characteristic sets.
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:390
CFList factorPSet(const CFList &PS)
bool lowerRank(const CanonicalForm &F, const CanonicalForm &G, int &ind)
ListCFList adjoinb(const CFList &is, const CFList &qs, const ListCFList &qh, const CFList &cs)
const ring r
Definition: syzextra.cc:208
int nr_of_poly(const CFList &PS, const Variable &x, Intarray &G)
CFList initials(const CFList &L)
int j
Definition: myNF.cc:70
static int max(int a, int b)
Definition: fast_mult.cc:264
CFList get_Terms(const CanonicalForm &f)
Definition: cf_factor.cc:274
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)
int status int void * buf
Definition: si_signals.h:59
T & getItem() const
Definition: ftmpl_list.cc:431
CFList FS2
candidate factors that might get removed
#define A
Definition: sirandom.c:23
void select(const ListCFList &ppi, int length, ListCFList &ppi1, ListCFList &ppi2)
int degpsmin(const CFList &PS, const Variable &x, Intarray &A, Intarray &B, Intarray &C, Intarray &D)
ListCFList contract(const ListCFList &cs)
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
int m
Definition: cfEzgcd.cc:119
bool isOn(int sw)
switches
void On(int sw)
switches
FILE * f
Definition: checklibs.c:9
int i
Definition: cfEzgcd.cc:123
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
declarations of higher level algorithms.
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
CanonicalForm test
Definition: cfModGcd.cc:4037
CanonicalForm lowestRank(const CFList &L)
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
CFList only_in_one(const CFList &PS, const Variable &x)
int Tdeg(const CFList &PS, const Variable &x, Intarray &A, Intarray &B, Intarray &C, Intarray &D, Intarray &E, Intarray &F)
int length() const
Definition: ftmpl_list.cc:273
REvaluation E(1, terms.length(), IntRandom(25))
#define __ARRAY_INIT__
b *CanonicalForm B
Definition: facBivar.cc:51
int gcd(int a, int b)
Definition: walkSupport.cc:839
Variable x
Definition: cfModGcd.cc:4023
CanonicalForm Premb(const CanonicalForm &f, const CFList &L)
pseudo remainder of f by L with faster test for remainder being zero
CanonicalForm Prem(const CanonicalForm &F, const CanonicalForm &G)
pseudo remainder of F by G with certain factors of LC (g) cancelled
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition: cf_ops.cc:523
int level() const
level() returns the level of CO.
CFList swapvar(const CFList &PS, const Variable &x, const Variable &y)
swapvar a whole list of CanonicalForms
void append(const T &)
Definition: ftmpl_list.cc:256
int degree(const CanonicalForm &f)
CanonicalForm LC(const CanonicalForm &f)
#define __INIT_GAP__
const poly b
Definition: syzextra.cc:213
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
return result
Definition: facAbsBiFact.cc:76
int l
Definition: cfEzgcd.cc:94
Header for factory&#39;s main class CanonicalForm.
bool inCoeffDomain() const