My Project
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  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
710 Prem (const CanonicalForm &f, const CFList &L)
711 {
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 
721 CFList uniGcd (const CFList& L)
722 {
723  CFList tmp;
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 
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
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
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
805 factorPSet (const CFList& PS)
806 {
807  CFList result;
808  CFFList factors;
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
824  CFList& removedFactors)
825 {
826  CanonicalForm quot;
827  CFList testlist;
828  int n= level(r);
829  bool divides;
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
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
904 contractsub (const CFList& cs1, const CFList& cs2)
905 {
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 
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;
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 
bool isOn(int sw)
switches
void On(int sw)
switches
void Off(int sw)
switches
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Header for factory's main class CanonicalForm.
CanonicalForm FACTORY_PUBLIC content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:603
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
CanonicalForm lc(const CanonicalForm &f)
CanonicalForm FACTORY_PUBLIC icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f )
Definition: cf_gcd.cc:74
int degree(const CanonicalForm &f)
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition: cf_ops.cc:523
int level(const CanonicalForm &f)
CanonicalForm LC(const CanonicalForm &f)
int FACTORY_PUBLIC getCharacteristic()
Definition: cf_char.cc:70
void inplaceUnion(const ListCFList &a, ListCFList &b)
Union of a and b stored in b.
CFList uniGcd(const CFList &L)
void removeFactors(CanonicalForm &r, StoreFactors &StoredFactors, CFList &removedFactors)
CFList initials(const CFList &L)
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)
CFList swapvar(const CFList &PS, const Variable &x, const Variable &y)
swapvar a whole list of CanonicalForms
CanonicalForm Prem(const CanonicalForm &F, const CanonicalForm &G)
pseudo remainder of F by G with certain factors of LC (g) cancelled
int nr_of_poly(const CFList &PS, const Variable &x, Intarray &G)
CanonicalForm Premb(const CanonicalForm &f, const CFList &L)
pseudo remainder of f by L with faster test for remainder being zero
CFList only_in_one(const CFList &PS, const Variable &x)
int minLevel(const CFList &L)
CFList factorsOfInitials(const CFList &L)
int Tdeg(const CFList &PS, const Variable &x, Intarray &A, Intarray &B, Intarray &C, Intarray &D, Intarray &E, Intarray &F)
int degpsmin(const CFList &PS, const Variable &x, Intarray &A, Intarray &B, Intarray &C, Intarray &D)
#define __INIT_GAP__
void initArray(const int highest_level, Intarray &A, Intarray &B, Intarray &C, Intarray &D, Intarray &E, Intarray &F, Intarray &G)
void removeContent(CanonicalForm &F, CanonicalForm &cF)
bool contractsub(const CFList &cs1, const CFList &cs2)
void select(const ListCFList &ppi, int length, ListCFList &ppi1, ListCFList &ppi2)
bool isSubset(const CFList &PS, const CFList &Cset)
is PS a subset of Cset ?
Variable get_max_var(const CFList &PS)
void sortListCFList(ListCFList &list)
sort in descending order of length of elements
ListCFList adjoinb(const CFList &is, const CFList &qs, const ListCFList &qh, const CFList &cs)
int degpsmax(const CFList &PS, const Variable &x, Intarray &A, Intarray &C)
#define __ARRAY_INIT__
void sortCFListByLevel(CFList &list)
sort in descending order of level of elements
ListCFList contract(const ListCFList &cs)
CFList factorPSet(const CFList &PS)
bool lowerRank(const CanonicalForm &F, const CanonicalForm &G, int &ind)
Varlist reorderb(const Varlist &difference, const CFList &PS, const int highest_level)
ListCFList adjoin(const CFList &is, const CFList &qs, const ListCFList &qh)
CanonicalForm lowestRank(const CFList &L)
CanonicalForm normalize(const CanonicalForm &F)
normalize a poly, i.e. in char 0 clear denominators, remove integer content in char p divide by leadi...
This file provides utility functions to compute characteristic sets.
int l
Definition: cfEzgcd.cc:100
int m
Definition: cfEzgcd.cc:128
int i
Definition: cfEzgcd.cc:132
int k
Definition: cfEzgcd.cc:99
Variable x
Definition: cfModGcd.cc:4082
g
Definition: cfModGcd.cc:4090
CanonicalForm test
Definition: cfModGcd.cc:4096
CanonicalForm b
Definition: cfModGcd.cc:4103
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
declarations of higher level algorithms.
CFList get_Terms(const CanonicalForm &f)
Definition: cf_factor.cc:289
CFFList FACTORY_PUBLIC factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:405
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:31
FILE * f
Definition: checklibs.c:9
factory's main class
Definition: canonicalform.h:86
CF_NO_INLINE bool isZero() const
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
CF_NO_INLINE bool isOne() const
bool inCoeffDomain() const
int level() const
level() returns the level of CO.
T & getItem() const
Definition: ftmpl_list.cc:431
T getFirst() const
Definition: ftmpl_list.cc:279
void removeFirst()
Definition: ftmpl_list.cc:287
int length() const
Definition: ftmpl_list.cc:273
void append(const T &)
Definition: ftmpl_list.cc:256
void insert(const T &)
Definition: ftmpl_list.cc:193
int isEmpty() const
Definition: ftmpl_list.cc:267
class to store factors that get removed during char set computation
CFList FS2
candidate factors that might get removed
CFList FS1
factors that were removed
factory's class for variables
Definition: factory.h:127
CFFListIterator iter
Definition: facAbsBiFact.cc:53
return result
Definition: facAbsBiFact.cc:75
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:53
REvaluation E(1, terms.length(), IntRandom(25))
b *CanonicalForm B
Definition: facBivar.cc:52
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:39
int j
Definition: facHensel.cc:110
static int min(int a, int b)
Definition: fast_mult.cc:268
static int max(int a, int b)
Definition: fast_mult.cc:264
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
template bool find(const List< CanonicalForm > &, const CanonicalForm &)
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
#define D(A)
Definition: gentable.cc:131
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:257
STATIC_VAR TreeM * G
Definition: janet.cc:31
void rem(unsigned long *a, unsigned long *q, unsigned long p, int &dega, int degq)
Definition: minpoly.cc:572
static CanonicalForm * retvalue
Definition: readcf.cc:126
int status int void size_t count
Definition: si_signals.h:59
int status int void * buf
Definition: si_signals.h:59
#define A
Definition: sirandom.c:24
int gcd(int a, int b)
Definition: walkSupport.cc:836