My Project
Loading...
Searching...
No Matches
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
26int
27degpsmax (const CFList & PS, const Variable & x,
28 Intarray & A, Intarray & C)
29{
30 int varlevel= level(x);
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
53int
54degpsmin (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;
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
90int
91Tdeg (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
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;
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 {
120 int newmin, newnopslc;
121
125 for (i= LCdegList; i.hasItem(); i++)
126 {
127 elem= i.getItem();
128 newmin= totaldegree(elem);
129 TermList= get_Terms(elem);
131 if (newmin < min)
132 min= newmin;
133 if (newnopslc < nopslc)
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
145int
146nr_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
161int
162degord (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
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
211CFList
212only_in_one (const CFList & PS, const Variable & x)
213{
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__
227void
229 Intarray & D, Intarray & E, Intarray & F, Intarray & G)
230{
231 for (int i=1 ; i <= highest_level; i ++)
232 {
235 C[i]= __ARRAY_INIT__;
238 F[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
260 const int highest_level)
261{
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__;
268 Array<Variable> v(0, n);
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 }
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
303CFList
304swapvar (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
314swapvar (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
324bool
325lowerRank (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
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
386int 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
395void
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
427void
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 ?
460bool
461isSubset (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
472void
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
495adjoin (const CFList& is, const CFList& qs, const ListCFList& qh)
496{
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
533adjoinb (const CFList & is, const CFList & qs, const ListCFList & qh,
534 const CFList & cs)
535{
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
569void
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);
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
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
677Premb (const CanonicalForm &f, const CFList &L)
678{
680 CFList l= L;
681 l.removeFirst();
683
684 for (i.lastItem(); i.hasItem(); i--)
685 rem= normalize (Prem (rem, i.getItem()));
686
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)
697 return 0;
698 }
699
700 if (ch == 0 && !isRat)
702
703 rem= normalize (Prem (rem, L.getFirst()));
704
705 return rem;
706}
707
708/// pseudo remainder of f by L
710Prem (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
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{
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
754CFList
756{
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())
769 }
770 }
771
772 return result;
773}
774
775void
777{
778 if (size (F) == 1)
779 {
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
804CFList
806{
810
811 for (CFListIterator i= PS; i. hasItem(); i++)
812 {
813 factors= factorize (i.getItem());
814 if (factors.getFirst().factor().inCoeffDomain())
816 for (j= factors; j.hasItem(); j++ )
817 result= Union (result, CFList (normalize (j.getItem().factor())));
818 }
819 return result;
820}
821
822void
825{
828 int n= level(r);
829 bool divides;
831
832 for (int i=1; i<= n; 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)
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)
873 }
874 }
875 r= normalize (r);
876}
877
878CFList
880{
882 if ((!i.hasItem()) || (PS.getFirst().level() == 0 ))
883 return PS;
884
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));
896 }
897 else
898 output.append(normalize (elem));
899 }
900 return output;
901}
902
903bool
905{
907
909 for (i= cs1; i.hasItem(); i++)
910 {
911 if (Prem (i.getItem(), cs2) != 0)
912 return false;
913 }
914
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
927{
928 ListCFList mem, ts;
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:4090
g
Definition cfModGcd.cc:4098
CanonicalForm test
Definition cfModGcd.cc:4104
CanonicalForm b
Definition cfModGcd.cc:4111
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:293
CFFList FACTORY_PUBLIC factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition cf_factor.cc:409
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
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 getFirst() const
void removeFirst()
int length() const
void append(const T &)
void insert(const T &)
int isEmpty() const
class to store factors that get removed during char set computation
factory's class for variables
Definition factory.h:127
CFFListIterator iter
return result
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 > Union(const List< Variable > &, const List< Variable > &)
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
template bool find(const List< CanonicalForm > &, const CanonicalForm &)
#define D(A)
Definition gentable.cc:126
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:69
int status int void * buf
Definition si_signals.h:69
#define A
Definition sirandom.c:24
int gcd(int a, int b)