My Project
Loading...
Searching...
No Matches
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
32
33// set up a new orderd list of Variables.
34// we try to reorder the variables heuristically optimal.
36neworder (const CFList & PolyList)
37{
40
42
44
45 // set up oldorder and first criterion: only_in_one
46 for (int i= highest_level; i>=1; i--)
47 {
50 if (is_one.length() == 1)
51 {
54 }
55 else if (is_one.length() == 0)
56 {
57 reorder.append (Variable (i)); // assigne it the highest level
59 }
60 }
62
63 // rearrange the ordering of the variables!
67
68 TIMING_PRINT(neworder_time, "\ntime used for neworder : ");
69
71}
72
73// the same as above, only returning a list of CanonicalForms
76{
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
89{
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
100CFList
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
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
141{
143
144 for (ListCFListIterator i= Q; i.hasItem(); i++)
145 Q1.append (reorder (betterorder, i.getItem()));
146 return Q1;
147}
148
149CFList
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
186CFList
188{
189 CFList QS= PS, RS= PS, CSet, tmp;
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
215CFList
217{
218 CFList QS= PS, RS= PS, CSet, tmp;
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
245CFList
247{
248 CFList L;
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
262
263 if (result.isEmpty() || result.getFirst().inCoeffDomain())
264 return CFList(1);
265
267 CFList RS;
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
283CFList
285{
288 CanonicalForm r, cF;
289 bool noRemainder= true;
291
292 QS= uniGcd (L);
293
294 while (!RS.isEmpty())
295 {
296 noRemainder= true;
297 CSet= basicSet (QS);
298
300
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
327
329
330 RS= Union (RS, CFList (r));
331 }
332 }
333
335 {
338 }
339 else
341
342 QS= Union (CSet, RS);
343
344 contents= CFList();
346 }
347 else
349 }
350
351 return CSet;
352}
353
354/// characteristic set via modified medial set
355CFList
357 bool removeContents)
358{
359 CFList L;
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
375
376 if (result.isEmpty() || result.getFirst().inCoeffDomain())
377 return CFList(1);
378
380 CFList RS;
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
394}
395
396CFList
402
403CFList
405{
407 return modCharSet (PS, tmp, removeContents);
408}
409
412{
415
416 int count= 0;
417 int highestLevel= 1;
419
421
422 l= L;
423
424 for (iter= l; iter.hasItem(); iter++)
425 {
426 iter.getItem()= normalize (iter.getItem());
427 if (highestLevel < iter.getItem().level())
428 highestLevel= iter.getItem().level();
429 }
430
431 tmp= ListCFList (l);
432
433 while (!tmp.isEmpty())
434 {
436
437 l= tmp.getFirst();
438
439 tmp= Difference (tmp, l);
440
441 select (ppi, l.length(), ppi1, ppi2);
442
444
445 if (count > 0)
446 ppi= Union (ppi1, ListCFList (l));
447 else
448 ppi= ListCFList();
449
450 if (l.length() - 3 < highestLevel)
452 else
454
455 if (charset.length() > 0 && charset.getFirst().level() > 0)
456 {
459
462 }
463 else
464 {
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
486static bool
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
506static CFList
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
569{
571 CFList qs, cs, factorset, is, ts, L;
575 for (CFListIterator iter= PS; iter.hasItem(); iter++)
576 {
577 sqrf= 1;
578 sqrfFactors= sqrFree (iter.getItem());
579 if (sqrfFactors.getFirst().factor().inCoeffDomain())
581 for (iter2= sqrfFactors; iter2.hasItem(); iter2++)
582 sqrf *= iter2.getItem().factor();
584 L= Union (CFList (sqrf), L);
585 }
586
588
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 {
600
601 qs= qhi.getFirst();
602
604 select (ppi, qs.length(), ppi1, ppi2);
605
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
620 if (qs.length() - 3 < highestlevel)
621 cs= modCharSet (qs, StoredFactors, false);
622 else
623 cs= charSetN (qs);
625
627
628 if (!cs.isEmpty() && cs.getFirst().level() > 0)
629 {
631
632 if (indexRed <= 0) // irreducible
633 {
634 if (!isSubset (cs,qs))
636 if (!find (pi, cs))
637 {
638 pi= Union (ListCFList (cs), pi);
639 if (cs.getFirst().level() > 0)
640 {
642
643 if (indexRed <= 0) //irreducible
644 {
646 if (cs.length() == highestlevel)
647 is= factorPSet (factorset);
648 else
650 iss= adjoin (is, qs, qqi);
651 }
652 }
653 else
655 }
656 else
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 }
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
682 if (qhi.length() > 1)
683 {
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
Header for factory's main class CanonicalForm.
int degree(const CanonicalForm &f)
CanonicalForm FACTORY_PUBLIC swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition cf_ops.cc:168
List< CFList > ListCFList
int level(const CanonicalForm &f)
List< CanonicalForm > CFList
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)
CanonicalForm Prem(const CanonicalForm &F, const CanonicalForm &G)
pseudo remainder of F by G with certain factors of LC (g) cancelled
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)
CFList factorsOfInitials(const CFList &L)
void removeContent(CanonicalForm &F, CanonicalForm &cF)
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)
void sortCFListByLevel(CFList &list)
sort in descending order of level of elements
ListCFList contract(const ListCFList &cs)
CFList factorPSet(const CFList &PS)
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)
This file provides utility functions to compute characteristic sets.
CFList charSetViaCharSetN(const CFList &PS)
compute a characteristic set via medial set
CFList charSetViaModCharSet(const CFList &PS, StoreFactors &StoredFactors, bool removeContents)
characteristic set via modified medial set
static bool irreducible(const CFList &AS)
ListCFList charSeries(const CFList &L)
characteristic series
CFList charSet(const CFList &PS)
characteristic set
ListCFList irrCharSeries(const CFList &PS)
irreducible characteristic series
CFList charSetN(const CFList &PS)
medial set
CFList basicSet(const CFList &PS)
basic set in the sense of Wang a.k.a. minimal ascending set in the sense of Greuel/Pfister
CFList newordercf(const CFList &PolyList)
Definition cfCharSets.cc:75
CFList modCharSet(const CFList &L, StoreFactors &StoredFactors, bool removeContents)
modified medial set
CFList reorder(const Varlist &betterorder, const CFList &PS)
static CFList irredAS(CFList &AS, int &indexRed, CanonicalForm &reducible)
IntList neworderint(const CFList &PolyList)
Definition cfCharSets.cc:88
This file provides functions to compute characteristic sets.
Varlist neworder(const CFList &PolyList)
int l
Definition cfEzgcd.cc:100
int i
Definition cfEzgcd.cc:132
int k
Definition cfEzgcd.cc:99
CanonicalForm b
Definition cfModGcd.cc:4111
declarations of higher level algorithms.
CFFList FACTORY_PUBLIC sqrFree(const CanonicalForm &f, bool sort=false)
squarefree factorization
Definition cf_factor.cc:961
CFFList FACTORY_PUBLIC factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition cf_factor.cc:409
factory's main class
CF_NO_INLINE bool isZero() 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
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...
Factorization over algebraic function fields.
const Variable & v
< [in] a sqrfree bivariate poly
Definition facBivar.h:39
CFList tmp2
Definition facFqBivar.cc:75
int j
Definition facHensel.cc:110
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 &)
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
#define pi
Definition libparse.cc:1145
int status int void size_t count
Definition si_signals.h:69
#define Q
Definition sirandom.c:26
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition syz3.cc:1027
#define TIMING_DEFINE_PRINT(t)
Definition timing.h:95
#define TIMING_END(t)
Definition timing.h:93
#define TIMING_START(t)
Definition timing.h:92
#define TIMING_PRINT(t, msg)
Definition timing.h:97