My Project  debian-1:4.1.1-p2+ds-4build4
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 
907  CanonicalForm r;
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 
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 icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f )
Definition: cf_gcd.cc:71
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
int getCharacteristic()
Definition: cf_char.cc:51
CanonicalForm lc(const CanonicalForm &f)
int degree(const CanonicalForm &f)
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition: cf_ops.cc:523
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:180
int level(const CanonicalForm &f)
CanonicalForm LC(const CanonicalForm &f)
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:93
int m
Definition: cfEzgcd.cc:121
int i
Definition: cfEzgcd.cc:125
int k
Definition: cfEzgcd.cc:92
Variable x
Definition: cfModGcd.cc:4023
g
Definition: cfModGcd.cc:4031
CanonicalForm test
Definition: cfModGcd.cc:4037
CanonicalForm b
Definition: cfModGcd.cc:4044
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.
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:390
CFList get_Terms(const CanonicalForm &f)
Definition: cf_factor.cc:274
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
FILE * f
Definition: checklibs.c:9
factory's main class
Definition: canonicalform.h:83
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
bool inCoeffDomain() const
int level() const
level() returns the level of CO.
CF_NO_INLINE bool isOne() const
CF_INLINE bool CanonicalForm::isOne, isZero () const.
Definition: cf_inline.cc:354
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:118
CFFListIterator iter
Definition: facAbsBiFact.cc:54
return result
Definition: facAbsBiFact.cc:76
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
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:37
int j
Definition: facHensel.cc:105
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:129
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:267
static TreeM * G
Definition: janet.cc:32
void rem(unsigned long *a, unsigned long *q, unsigned long p, int &dega, int degq)
Definition: minpoly.cc:572
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:23
int gcd(int a, int b)
Definition: walkSupport.cc:836