My Project  debian-1:4.1.2-p1+ds-2
cfCharSets.cc
Go to the documentation of this file.
1 /*****************************************************************************\
2  * Computer Algebra System SINGULAR
3 \*****************************************************************************/
4 /** @file cfCharSets.cc
5  *
6  * This file provides 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  * ABSTRACT: Descriptions can be found in Wang "On the Parallelization of
13  * characteristic-set based algorithms" or Greuel/Pfister "A Singular
14  * Introduction to Commutative Algebra".
15  *
16  * @authors Martin Lee
17  *
18  **/
19 /*****************************************************************************/
20 
21 #include "config.h"
22 
23 #include "timing.h"
24 
25 #include "canonicalform.h"
26 #include "cfCharSets.h"
27 #include "cfCharSetsUtil.h"
28 #include "cf_algorithm.h"
29 #include "facAlgFunc.h"
30 
31 TIMING_DEFINE_PRINT(neworder_time)
32 
33 // set up a new orderd list of Variables.
34 // we try to reorder the variables heuristically optimal.
35 Varlist
36 neworder (const CFList & PolyList)
37 {
38  CFList PS= PolyList, PS1=PolyList;
39  Varlist oldorder, reorder, difference;
40 
41  TIMING_START (neworder_time);
42 
43  int highest_level= level (get_max_var (PS));
44 
45  // set up oldorder and first criterion: only_in_one
46  for (int i= highest_level; i>=1; i--)
47  {
48  oldorder.insert (Variable (i));
49  CFList is_one= only_in_one (PS1, Variable (i));
50  if (is_one.length() == 1)
51  {
53  PS1= Difference (PS1, is_one);
54  }
55  else if (is_one.length() == 0)
56  {
57  reorder.append (Variable (i)); // assigne it the highest level
58  PS1= Difference (PS1, is_one);
59  }
60  }
61  difference= Difference (oldorder, reorder);
62 
63  // rearrange the ordering of the variables!
64  difference= reorderb (difference, PS, highest_level);
65  reorder= Union (reorder, difference);
66  TIMING_END(neworder_time);
67 
68  TIMING_PRINT(neworder_time, "\ntime used for neworder : ");
69 
70  return Union (reorder, Difference (oldorder, reorder));
71 }
72 
73 // the same as above, only returning a list of CanonicalForms
74 CFList
75 newordercf (const CFList & PolyList)
76 {
77  Varlist reorder= neworder (PolyList);
78  CFList output;
79 
80  for (VarlistIterator i=reorder; i.hasItem(); i++)
81  output.append (CanonicalForm (i.getItem()));
82 
83  return output;
84 }
85 
86 // the same as above, only returning a list of ints
87 IntList
88 neworderint (const CFList & PolyList)
89 {
90  Varlist reorder= neworder (PolyList);
91  IntList output;
92 
93  for (VarlistIterator i= reorder; i.hasItem(); i++)
94  output.append (level (i.getItem()));
95 
96  return output;
97 }
98 
99 // a library function: we reorganize the global variable ordering
100 CFList
101 reorder (const Varlist & betterorder, const CFList & PS)
102 {
103  int i= 1, n= betterorder.length();
104  Intarray v (1, n);
105  CFList ps= PS;
106 
107  //initalize:
108  for (VarlistIterator j= betterorder; j.hasItem(); j++)
109  {
110  v[i]= level (j.getItem());
111  i++;
112  }
113  // reorder:
114  for (i= 1; i <= n; i++)
115  ps= swapvar (ps, Variable (v[i]), Variable (n + i));
116  return ps;
117 }
118 
119 CFFList
120 reorder (const Varlist & betterorder, const CFFList & PS)
121 {
122  int i= 1, n= betterorder.length();
123  Intarray v (1, n);
124  CFFList ps= PS;
125 
126  //initalize:
127  for (VarlistIterator j= betterorder; j.hasItem(); j++)
128  {
129  v[i]= level (j.getItem());
130  i++;
131  }
132 
133  // reorder:
134  for (i= 1; i <= n; i++)
135  ps= swapvar (ps, Variable (v[i]), Variable (n + i));
136  return ps;
137 }
138 
140 reorder (const Varlist & betterorder, const ListCFList & Q)
141 {
142  ListCFList Q1;
143 
144  for (ListCFListIterator i= Q; i.hasItem(); i++)
145  Q1.append (reorder (betterorder, i.getItem()));
146  return Q1;
147 }
148 
149 CFList
150 basicSet (const CFList &PS)
151 {
152  CFList QS= PS, BS, RS;
154  int cb, degb;
155 
156  if (PS.length() < 2)
157  return PS;
158 
160 
161  while (!QS.isEmpty())
162  {
163  b= lowestRank (QS);
164  cb= b.level();
165 
166  BS= Union(CFList (b), BS);
167 
168  if (cb <= 0)
169  return CFList();
170  else
171  {
172  degb= degree (b);
173  RS= CFList();
174  for (i= QS; i.hasItem(); i++)
175  {
176  if (degree (i.getItem(), cb) < degb)
177  RS= Union (CFList (i.getItem()), RS);
178  }
179  QS= RS;
180  }
181  }
182 
183  return BS;
184 }
185 
186 CFList
187 charSet (const CFList &PS)
188 {
189  CFList QS= PS, RS= PS, CSet, tmp;
191  CanonicalForm r;
192 
193  while (!RS.isEmpty())
194  {
195  CSet= basicSet (QS);
196 
197  RS= CFList();
198  if (CSet.length() > 0 && CSet.getFirst().level() > 0)
199  {
200  tmp= Difference (QS, CSet);
201  for (i= tmp; i.hasItem(); i++)
202  {
203  r= Prem (i.getItem(), CSet);
204  if (r != 0)
205  RS= Union (RS, CFList (r));
206  }
207  QS= Union (QS, RS);
208  }
209  }
210 
211  return CSet;
212 }
213 
214 /// medial set
215 CFList
216 charSetN (const CFList &PS)
217 {
218  CFList QS= PS, RS= PS, CSet, tmp;
220  CanonicalForm r;
221 
222  while (!RS.isEmpty())
223  {
224  QS= uniGcd (QS);
225  CSet= basicSet (QS);
226 
227  RS= CFList();
228  if (CSet.length() > 0 && CSet.getFirst().level() > 0)
229  {
230  tmp= Difference (QS, CSet);
231  for (i= tmp; i.hasItem(); i++)
232  {
233  r= Prem (i.getItem(), CSet);
234  if (!r.isZero())
235  RS= Union (RS, CFList (r));
236  }
237  QS= Union (CSet, RS);
238  }
239  }
240 
241  return CSet;
242 }
243 
244 /// compute a characteristic set via medial set
245 CFList
247 {
248  CFList L;
249  CFFList sqrfFactors;
250  CanonicalForm sqrf;
251  CFFListIterator iter2;
252  for (CFListIterator iter= PS; iter.hasItem(); iter++)
253  {
254  sqrf= 1;
255  sqrfFactors= sqrFree (iter.getItem());
256  for (iter2= sqrfFactors; iter2.hasItem(); iter2++)
257  sqrf *= iter2.getItem().factor();
258  L= Union (L, CFList (normalize (sqrf)));
259  }
260 
261  CFList result= charSetN (L);
262 
263  if (result.isEmpty() || result.getFirst().inCoeffDomain())
264  return CFList(1);
265 
266  CanonicalForm r;
267  CFList RS;
268  CFList tmp= Difference (L, result);
269 
270  for (CFListIterator i= tmp; i.hasItem(); i++)
271  {
272  r= Premb (i.getItem(), result);
273  if (!r.isZero())
274  RS= Union (RS, CFList (r));
275  }
276  if (RS.isEmpty())
277  return result;
278 
279  return charSetViaCharSetN (Union (L, Union (RS, result)));
280 }
281 
282 /// modified medial set
283 CFList
284 modCharSet (const CFList& L, StoreFactors& StoredFactors, bool removeContents)
285 {
286  CFList QS, RS= L, CSet, tmp, contents, initial, removedFactors;
288  CanonicalForm r, cF;
289  bool noRemainder= true;
290  StoreFactors StoredFactors2;
291 
292  QS= uniGcd (L);
293 
294  while (!RS.isEmpty())
295  {
296  noRemainder= true;
297  CSet= basicSet (QS);
298 
299  initial= factorsOfInitials (CSet);
300 
301  StoredFactors2.FS1= StoredFactors.FS1;
302  StoredFactors2.FS2= Union (StoredFactors2.FS2, initial);
303 
304  RS= CFList();
305 
306  if (CSet.length() > 0 && CSet.getFirst().level() > 0)
307  {
308  tmp= Difference (QS, CSet);
309 
310  for (i= tmp; i.hasItem(); i++)
311  {
312  r= Prem (i.getItem(), CSet);
313  if (!r.isZero())
314  {
315  noRemainder= false;
316  if (removeContents)
317  {
318  removeContent (r, cF);
319 
320  if (!cF.isZero())
321  contents= Union (contents, factorPSet (CFList(cF))); //factorPSet maybe too much it should suffice to do a squarefree factorization instead
322  }
323 
324  removeFactors (r, StoredFactors2, removedFactors);
325  StoredFactors2.FS1= Union (StoredFactors2.FS1, removedFactors);
326  StoredFactors2.FS2= Difference (StoredFactors2.FS2, removedFactors);
327 
328  removedFactors= CFList();
329 
330  RS= Union (RS, CFList (r));
331  }
332  }
333 
334  if (removeContents && !noRemainder)
335  {
336  StoredFactors.FS1= Union (StoredFactors2.FS1, contents);
337  StoredFactors.FS2= StoredFactors2.FS2;
338  }
339  else
340  StoredFactors= StoredFactors2;
341 
342  QS= Union (CSet, RS);
343 
344  contents= CFList();
345  removedFactors= CFList();
346  }
347  else
348  StoredFactors= StoredFactors2;
349  }
350 
351  return CSet;
352 }
353 
354 /// characteristic set via modified medial set
355 CFList
356 charSetViaModCharSet (const CFList& PS, StoreFactors& StoredFactors,
357  bool removeContents)
358 {
359  CFList L;
360  CFFList sqrfFactors;
361  CanonicalForm sqrf;
362  CFFListIterator iter2;
363  for (CFListIterator iter= PS; iter.hasItem(); iter++)
364  {
365  sqrf= 1;
366  sqrfFactors= sqrFree (iter.getItem());
367  for (iter2= sqrfFactors; iter2.hasItem(); iter2++)
368  sqrf *= iter2.getItem().factor();
369  L= Union (L, CFList (normalize (sqrf)));
370  }
371 
372  L= uniGcd (L);
373 
374  CFList result= modCharSet (L, StoredFactors, removeContents);
375 
376  if (result.isEmpty() || result.getFirst().inCoeffDomain())
377  return CFList(1);
378 
379  CanonicalForm r;
380  CFList RS;
381  CFList tmp= Difference (L, result);
382 
383  for (CFListIterator i= tmp; i.hasItem(); i++)
384  {
385  r= Premb (i.getItem(), result);
386  if (!r.isZero())
387  RS= Union (RS, CFList (r));
388  }
389  if (RS.isEmpty())
390  return result;
391 
392  return charSetViaModCharSet (Union (L, Union (RS, result)), StoredFactors,
393  removeContents);
394 }
395 
396 CFList
397 charSetViaModCharSet (const CFList& PS, bool removeContents)
398 {
399  StoreFactors tmp;
400  return charSetViaModCharSet (PS, tmp, removeContents);
401 }
402 
403 CFList
404 modCharSet (const CFList& PS, bool removeContents)
405 {
406  StoreFactors tmp;
407  return modCharSet (PS, tmp, removeContents);
408 }
409 
411 charSeries (const CFList& L)
412 {
413  ListCFList tmp, result, tmp2, ppi1, ppi2, qqi, ppi, alreadyConsidered;
414  CFList l, charset, ini;
415 
416  int count= 0;
417  int highestLevel= 1;
419 
420  StoreFactors StoredFactors;
421 
422  l= L;
423 
424  for (iter= l; iter.hasItem(); iter++)
425  {
427  if (highestLevel < iter.getItem().level())
428  highestLevel= iter.getItem().level();
429  }
430 
431  tmp= ListCFList (l);
432 
433  while (!tmp.isEmpty())
434  {
435  sortListCFList (tmp);
436 
437  l= tmp.getFirst();
438 
439  tmp= Difference (tmp, l);
440 
441  select (ppi, l.length(), ppi1, ppi2);
442 
443  inplaceUnion (ppi2, qqi);
444 
445  if (count > 0)
446  ppi= Union (ppi1, ListCFList (l));
447  else
448  ppi= ListCFList();
449 
450  if (l.length() - 3 < highestLevel)
451  charset= charSetViaModCharSet (l, StoredFactors);
452  else
453  charset= charSetViaCharSetN (l);
454 
455  if (charset.length() > 0 && charset.getFirst().level() > 0)
456  {
457  result= Union (ListCFList (charset), result);
458  ini= factorsOfInitials (charset);
459 
460  ini= Union (ini, factorPSet (StoredFactors.FS1));
461  sortCFListByLevel (ini);
462  }
463  else
464  {
465  ini= factorPSet (StoredFactors.FS1);
466  sortCFListByLevel (ini);
467  }
468 
469  tmp2= adjoin (ini, l, qqi);
470  tmp= Union (tmp2, tmp);
471 
472  StoredFactors.FS1= CFList();
473  StoredFactors.FS2= CFList();
474 
475  ppi1= ListCFList();
476  ppi2= ListCFList();
477 
478  count++;
479  }
480 
481  //TODO need to remove superflous components
482 
483  return result;
484 }
485 
486 static bool
487 irreducible (const CFList & AS)
488 {
489 // AS is given by AS = { A1, A2, .. Ar }, d_i = degree(Ai)
490 
491 // 1) we test: if d_i > 1, d_j =1 for all j<>i, then AS is irreducible.
492  bool deg1= true;
493  for (CFListIterator i= AS ; i.hasItem(); i++)
494  {
495  if (degree (i.getItem()) > 1)
496  {
497  if (deg1)
498  deg1= false;
499  else
500  return false; // found 2nd poly with deg > 1
501  }
502  }
503  return true;
504 }
505 
506 static CFList
507 irredAS (CFList & AS, int & indexRed, CanonicalForm & reducible)
508 {
509  CFFList qs;
510  CFList ts, as;
511  CanonicalForm elem;
512  bool ind= true;
513  int nr= 0;
515 
516  indexRed= 0;
517  for (i= AS; i.hasItem(); i++ )
518  {
519  nr += 1;
520  qs= factorize (i.getItem());
521  if (qs.getFirst().factor().inCoeffDomain())
522  qs.removeFirst();
523 
524  if ((qs.length() >= 2 ) || (qs.getFirst().exp() > 1))
525  {
526  indexRed= nr;
527  ind= false;
528  reducible= i.getItem();
529  break;
530  }
531  }
532 
533  if (ind)
534  {
535  if (irreducible (AS)) // as quasilinear? => irreducible!
536  indexRed= 0;
537  else
538  {
539  i= AS;
540  for (nr= 1; nr< AS.length(); nr++)
541  {
542  as.append (i.getItem());
543  i++;
544  if (degree (i.getItem()) > 1)
545  { // search for a non linear elem
546  qs= facAlgFunc2 (i.getItem(), as);
547  if (qs.length() > 0)
548  {
549  if (qs.getFirst().factor().inCoeffDomain())
550  qs.removeFirst();
551  if (qs.length() > 1 || qs.getFirst().exp() > 1)
552  { //found elem is reducible
553  reducible= i.getItem();
554  indexRed= nr + 1;
555  break;
556  }
557  }
558  }
559  }
560  }
561  }
562  for (CFFListIterator k= qs; k.hasItem(); k++)
563  ts.append (normalize (k.getItem().factor()));
564  return ts;
565 }
566 
568 irrCharSeries (const CFList & PS)
569 {
570  CanonicalForm reducible, reducible2;
571  CFList qs, cs, factorset, is, ts, L;
572  CanonicalForm sqrf;
573  CFFList sqrfFactors;
574  CFFListIterator iter2;
575  for (CFListIterator iter= PS; iter.hasItem(); iter++)
576  {
577  sqrf= 1;
578  sqrfFactors= sqrFree (iter.getItem());
579  if (sqrfFactors.getFirst().factor().inCoeffDomain())
580  sqrfFactors.removeFirst();
581  for (iter2= sqrfFactors; iter2.hasItem(); iter2++)
582  sqrf *= iter2.getItem().factor();
583  sqrf= normalize (sqrf);
584  L= Union (CFList (sqrf), L);
585  }
586 
587  ListCFList pi, ppi, qqi, qsi, iss, qhi= ListCFList(L);
588 
589  int nr_of_iteration= 0, indexRed, highestlevel= 0;
590 
591  for (CFListIterator iter= PS; iter.hasItem(); iter++)
592  {
593  if (level (iter.getItem()) > highestlevel)
594  highestlevel= level(iter.getItem());
595  }
596 
597  while (!qhi.isEmpty())
598  {
599  sortListCFList (qhi);
600 
601  qs= qhi.getFirst();
602 
603  ListCFList ppi1,ppi2;
604  select (ppi, qs.length(), ppi1, ppi2);
605 
606  inplaceUnion (ppi2, qqi);
607 
608  if (nr_of_iteration == 0)
609  {
610  nr_of_iteration += 1;
611  ppi= ListCFList();
612  }
613  else
614  {
615  nr_of_iteration += 1;
616  ppi= Union (ppi1, ListCFList (qs));
617  }
618 
619  StoreFactors StoredFactors;
620  if (qs.length() - 3 < highestlevel)
621  cs= modCharSet (qs, StoredFactors, false);
622  else
623  cs= charSetN (qs);
624  cs= removeContent (cs, StoredFactors);
625 
626  factorset= StoredFactors.FS1;
627 
628  if (!cs.isEmpty() && cs.getFirst().level() > 0)
629  {
630  ts= irredAS (cs, indexRed, reducible);
631 
632  if (indexRed <= 0) // irreducible
633  {
634  if (!isSubset (cs,qs))
635  cs= charSetViaCharSetN (Union (qs,cs));
636  if (!find (pi, cs))
637  {
638  pi= Union (ListCFList (cs), pi);
639  if (cs.getFirst().level() > 0)
640  {
641  ts= irredAS (cs, indexRed, reducible);
642 
643  if (indexRed <= 0) //irreducible
644  {
645  qsi= Union (ListCFList(cs), qsi);
646  if (cs.length() == highestlevel)
647  is= factorPSet (factorset);
648  else
649  is= Union (factorsOfInitials (cs), factorPSet (factorset));
650  iss= adjoin (is, qs, qqi);
651  }
652  }
653  else
654  iss= adjoin (factorPSet (factorset), qs, qqi);
655  }
656  else
657  iss= adjoin (factorPSet (factorset), qs, qqi);
658  }
659 
660  if (indexRed > 0)
661  {
662  is= factorPSet (factorset);
663  if (indexRed > 1)
664  {
665  CFList cst;
666  for (CFListIterator i= cs ; i.hasItem(); i++)
667  {
668  if (i.getItem() == reducible)
669  break;
670  else
671  cst.append (i.getItem());
672  }
673  is= Union (factorsOfInitials (Union (cst, CFList (reducible))), is);
674  iss= Union (adjoinb (ts, qs, qqi, cst), adjoin (is, qs, qqi));
675  }
676  else
677  iss= adjoin (Union (is, ts), qs, qqi);
678  }
679  }
680  else
681  iss= adjoin (factorPSet (factorset), qs, qqi);
682  if (qhi.length() > 1)
683  {
684  qhi.removeFirst();
685  qhi= Union (iss, qhi);
686  }
687  else
688  qhi= iss;
689  }
690  if (!qsi.isEmpty())
691  return contract (qsi);
692  return ListCFList(CFList (1)) ;
693 }
694 
cfCharSets.h
timing.h
TIMING_DEFINE_PRINT
TIMING_DEFINE_PRINT(neworder_time) Varlist new order(const CFList &PolyList)
Definition: cfCharSets.cc:31
StoreFactors::FS2
CFList FS2
candidate factors that might get removed
Definition: cfCharSetsUtil.h:32
j
int j
Definition: facHensel.cc:105
contract
ListCFList contract(const ListCFList &cs)
Definition: cfCharSetsUtil.cc:925
k
int k
Definition: cfEzgcd.cc:92
canonicalform.h
Prem
CanonicalForm Prem(const CanonicalForm &F, const CanonicalForm &G)
pseudo remainder of F by G with certain factors of LC (g) cancelled
Definition: cfCharSetsUtil.cc:616
result
return result
Definition: facAbsBiFact.cc:76
StoreFactors
class to store factors that get removed during char set computation
Definition: cfCharSetsUtil.h:28
basicSet
CFList basicSet(const CFList &PS)
basic set in the sense of Wang a.k.a. minimal ascending set in the sense of Greuel/Pfister
Definition: cfCharSets.cc:150
irredAS
static CFList irredAS(CFList &AS, int &indexRed, CanonicalForm &reducible)
Definition: cfCharSets.cc:507
ListCFList
List< CFList > ListCFList
Definition: canonicalform.h:392
charSeries
ListCFList charSeries(const CFList &L)
characteristic series
Definition: cfCharSets.cc:411
TIMING_END
#define TIMING_END(t)
Definition: timing.h:93
only_in_one
CFList only_in_one(const CFList &PS, const Variable &x)
Definition: cfCharSetsUtil.cc:212
neworder
Varlist neworder(const CFList &PolyList)
modCharSet
CFList modCharSet(const CFList &L, StoreFactors &StoredFactors, bool removeContents)
modified medial set
Definition: cfCharSets.cc:284
factorsOfInitials
CFList factorsOfInitials(const CFList &L)
Definition: cfCharSetsUtil.cc:754
level
int level(const CanonicalForm &f)
Definition: canonicalform.h:324
initial
poly initial(const poly p, const ring r, const gfan::ZVector &w)
Returns the initial form of p with respect to w.
Definition: initial.cc:30
charSetViaCharSetN
CFList charSetViaCharSetN(const CFList &PS)
compute a characteristic set via medial set
Definition: cfCharSets.cc:246
iter
CFFListIterator iter
Definition: facAbsBiFact.cc:54
Premb
CanonicalForm Premb(const CanonicalForm &f, const CFList &L)
pseudo remainder of f by L with faster test for remainder being zero
Definition: cfCharSetsUtil.cc:677
b
CanonicalForm b
Definition: cfModGcd.cc:4044
CanonicalForm
factory's main class
Definition: canonicalform.h:77
newordercf
CFList newordercf(const CFList &PolyList)
Definition: cfCharSets.cc:75
isSubset
bool isSubset(const CFList &PS, const CFList &Cset)
is PS a subset of Cset ?
Definition: cfCharSetsUtil.cc:461
sortCFListByLevel
void sortCFListByLevel(CFList &list)
sort in descending order of level of elements
Definition: cfCharSetsUtil.cc:428
pi
#define pi
Definition: libparse.cc:1144
i
int i
Definition: cfEzgcd.cc:125
swapvar
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
Array
Definition: ftmpl_array.h:17
Difference
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
select
void select(const ListCFList &ppi, int length, ListCFList &ppi1, ListCFList &ppi2)
Definition: cfCharSetsUtil.cc:570
reorder
CFList reorder(const Varlist &betterorder, const CFList &PS)
Definition: cfCharSets.cc:101
TIMING_START
TIMING_START(fac_alg_resultant)
List::isEmpty
int isEmpty() const
Definition: ftmpl_list.cc:267
StoreFactors::FS1
CFList FS1
factors that were removed
Definition: cfCharSetsUtil.h:31
cf_algorithm.h
Q
STATIC_VAR jList * Q
Definition: janet.cc:30
removeFactors
void removeFactors(CanonicalForm &r, StoreFactors &StoredFactors, CFList &removedFactors)
Definition: cfCharSetsUtil.cc:822
adjoin
ListCFList adjoin(const CFList &is, const CFList &qs, const ListCFList &qh)
Definition: cfCharSetsUtil.cc:495
get_max_var
Variable get_max_var(const CFList &PS)
Definition: cfCharSetsUtil.cc:196
factorize
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:390
reorderb
Varlist reorderb(const Varlist &difference, const CFList &PS, const int highest_level)
Definition: cfCharSetsUtil.cc:259
TIMING_PRINT
#define TIMING_PRINT(t, msg)
Definition: timing.h:97
ListIterator::hasItem
int hasItem()
Definition: ftmpl_list.cc:439
charSet
CFList charSet(const CFList &PS)
characteristic set
Definition: cfCharSets.cc:187
List::removeFirst
void removeFirst()
Definition: ftmpl_list.cc:287
List::getFirst
T getFirst() const
Definition: ftmpl_list.cc:279
sortListCFList
void sortListCFList(ListCFList &list)
sort in descending order of length of elements
Definition: cfCharSetsUtil.cc:396
List::length
int length() const
Definition: ftmpl_list.cc:273
uniGcd
CFList uniGcd(const CFList &L)
Definition: cfCharSetsUtil.cc:720
normalize
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition: syz3.cc:1025
Variable
factory's class for variables
Definition: factory.h:117
ListIterator::getItem
T & getItem() const
Definition: ftmpl_list.cc:431
adjoinb
ListCFList adjoinb(const CFList &is, const CFList &qs, const ListCFList &qh, const CFList &cs)
Definition: cfCharSetsUtil.cc:533
charSetViaModCharSet
CFList charSetViaModCharSet(const CFList &PS, StoreFactors &StoredFactors, bool removeContents)
characteristic set via modified medial set
Definition: cfCharSets.cc:356
facAlgFunc2
CFFList facAlgFunc2(const CanonicalForm &f, const CFList &as)
factorize a polynomial that is irreducible over the ground field modulo an extension given by an irre...
Definition: facAlgFunc.cc:905
charSetN
CFList charSetN(const CFList &PS)
medial set
Definition: cfCharSets.cc:216
lowestRank
CanonicalForm lowestRank(const CFList &L)
Definition: cfCharSetsUtil.cc:357
sqrFree
CFFList sqrFree(const CanonicalForm &f, bool sort=false)
squarefree factorization
Definition: cf_factor.cc:757
find
template bool find(const List< CanonicalForm > &, const CanonicalForm &)
l
int l
Definition: cfEzgcd.cc:93
neworderint
IntList neworderint(const CFList &PolyList)
Definition: cfCharSets.cc:88
Union
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
cfCharSetsUtil.h
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
List
Definition: ftmpl_list.h:20
irreducible
static bool irreducible(const CFList &AS)
Definition: cfCharSets.cc:487
CFList
List< CanonicalForm > CFList
Definition: canonicalform.h:388
count
int status int void size_t count
Definition: si_signals.h:58
CanonicalForm::isZero
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
tmp2
CFList tmp2
Definition: facFqBivar.cc:70
facAlgFunc.h
factorPSet
CFList factorPSet(const CFList &PS)
Definition: cfCharSetsUtil.cc:804
irrCharSeries
ListCFList irrCharSeries(const CFList &PS)
irreducible characteristic series
Definition: cfCharSets.cc:568
CanonicalForm::level
int level() const
level() returns the level of CO.
Definition: canonicalform.cc:543
List::append
void append(const T &)
Definition: ftmpl_list.cc:256
removeContent
void removeContent(CanonicalForm &F, CanonicalForm &cF)
Definition: cfCharSetsUtil.cc:775
degree
int degree(const CanonicalForm &f)
Definition: canonicalform.h:309
List::insert
void insert(const T &)
Definition: ftmpl_list.cc:193
inplaceUnion
void inplaceUnion(const ListCFList &a, ListCFList &b)
Union of a and b stored in b.
Definition: cfCharSetsUtil.cc:473
ListIterator
Definition: ftmpl_list.h:17