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);
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
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;
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
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
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
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
196get_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
211CFList
212only_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__
227void
228initArray (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 {
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
259reorderb (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);
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
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{
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
533adjoinb (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
569void
570select (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);
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
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)
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{
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
775void
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
804CFList
806{
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
822void
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
878CFList
879removeContent (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
903bool
904contractsub (const CFList& cs1, const CFList& cs2)
905{
907
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
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: variable.h:33
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 > 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: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
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