# source:git/factory/cfCharSets.cc@3fd99f1

spielwiese
Last change on this file since 3fd99f1 was 3fd99f1, checked in by Martin Lee <martinlee84@…>, 10 years ago
chg: more normalization
• Property mode set to 100644
File size: 15.2 KB
Line
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.
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
31TIMING_DEFINE_PRINT(neworder_time)
32
33// set up a new orderd list of Variables.
34// we try to reorder the variables heuristically optimal.
35Varlist
36neworder (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    {
52      reorder.insert (Variable (i));
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
74CFList
75newordercf (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
87IntList
88neworderint (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
100CFList
101reorder (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
119CFFList
120reorder (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
139ListCFList
140reorder (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
149CFList
150basicSet (const CFList &PS)
151{
152  CFList QS= PS, BS, RS;
153  CanonicalForm b;
154  int cb, degb;
155
156  if (PS.length() < 2)
157    return PS;
158
159  CFListIterator i;
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
187charSet (const CFList &PS)
188{
189  CFList QS= PS, RS= PS, CSet, tmp;
190  CFListIterator i;
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
215CFList
216charSetN (const CFList &PS)
217{
218  CFList QS= PS, RS= PS, CSet, tmp;
219  CFListIterator i;
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
245CFList
246charSetViaCharSetN (const CFList& PS)
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
283CFList
284modCharSet (const CFList& L, StoreFactors& StoredFactors, bool removeContents)
285{
286  CFList QS, RS= L, CSet, tmp, contents, initial, removedFactors;
287  CFListIterator i;
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
355CFList
356charSetViaModCharSet (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
396CFList
397charSetViaModCharSet (const CFList& PS, bool removeContents)
398{
399  StoreFactors tmp;
400  return charSetViaModCharSet (PS, tmp, removeContents);
401}
402
403ListCFList
404charSeries (const CFList& L)
405{
406  ListCFList tmp, result, tmp2, ppi1, ppi2, qqi, ppi, alreadyConsidered;
407  CFList l, charset, ini;
408
409  int count= 0;
410  int highestLevel= 1;
411  CFListIterator iter;
412
413  StoreFactors StoredFactors;
414
415  l= L;
416
417  for (iter= l; iter.hasItem(); iter++)
418  {
419    iter.getItem()= normalize (iter.getItem());
420    if (highestLevel < iter.getItem().level())
421      highestLevel= iter.getItem().level();
422  }
423
424  tmp= ListCFList (l);
425
426  while (!tmp.isEmpty())
427  {
428    sortListCFList (tmp);
429
430    l= tmp.getFirst();
431
432    tmp= minus (tmp, l);
433
434    select (ppi, l.length(), ppi1, ppi2);
435
436    inplaceUnion (ppi2, qqi);
437
438    if (count > 0)
439      ppi= MyUnion (ListCFList (l), ppi1);
440    else
441      ppi= ListCFList();
442
443    if (l.length() - 3 < highestLevel)
444      charset= charSetViaModCharSet (l, StoredFactors);
445    else
446      charset= charSetViaCharSetN (l);
447
448    if (charset.length() > 0 && charset.getFirst().level() > 0)
449    {
450      result= MyUnion (result, ListCFList (charset));
451      ini= factorsOfInitials (charset);
452
453      ini= Union (ini, factorPSet (StoredFactors.FS1));
454      sortCFListByLevel (ini);
455    }
456    else
457    {
458      ini= factorPSet (StoredFactors.FS1);
459      sortCFListByLevel (ini);
460    }
461
462    tmp2= adjoin (ini, l, qqi);
463    tmp= MyUnion (tmp, tmp2);
464
465    StoredFactors.FS1= CFList();
466    StoredFactors.FS2= CFList();
467
468    ppi1= ListCFList();
469    ppi2= ListCFList();
470
471    count++;
472  }
473
474  //TODO need to remove superflous components
475
476  return result;
477}
478
479static bool
480irreducible (const CFList & AS)
481{
482// AS is given by AS = { A1, A2, .. Ar }, d_i = degree(Ai)
483
484// 1) we test: if d_i > 1, d_j =1 for all j<>i, then AS is irreducible.
485  bool deg1= true;
486  for (CFListIterator i= AS ; i.hasItem(); i++)
487  {
488    if (degree (i.getItem()) > 1)
489    {
490      if (deg1)
491        deg1= false;
492      else
493        return false; // found 2nd poly with deg > 1
494    }
495  }
496  return true;
497}
498
499static CFList
500irredAS (CFList & AS, int & indexRed, CanonicalForm & reducible)
501{
502  CFFList qs;
503  CFList ts, as;
504  CanonicalForm elem;
505  bool ind= true;
506  int nr= 0;
507  CFListIterator i;
508
509  indexRed= 0;
510  for (i= AS; i.hasItem(); i++ )
511  {
512    nr += 1;
513    if (degree (i.getItem()) > 1)
514    {
515      qs= factorize (i.getItem());
516      if (qs.getFirst().factor().inCoeffDomain())
517        qs.removeFirst();
518    }
519    else
520      qs= CFFList (CFFactor (normalize (i.getItem()), 1));
521
522    if ((qs.length() >= 2 ) || (qs.getFirst().exp() > 1))
523    {
524      indexRed= nr;
525      ind= false;
526      reducible= i.getItem();
527      break;
528    }
529  }
530
531  if (ind)
532  {
533    if (irreducible (AS))  // as quasilinear? => irreducible!
534      indexRed= 0;
535    else
536    {
537      i= AS;
538      for (nr= 1; nr< AS.length(); nr++)
539      {
540        as.append (i.getItem());
541        i++;
542        if (degree (i.getItem()) > 1)
543        {  // search for a non linear elem
544          qs= facAlgFunc2 (i.getItem(), as);
545          if (qs.getFirst().factor().inCoeffDomain())
546            qs.removeFirst();
547          if (qs.length() > 1 || qs.getFirst().exp() > 1)
548          { //found elem is reducible
549            reducible= i.getItem();
550            indexRed= nr + 1;
551            break;
552          }
553        }
554      }
555    }
556  }
557  for (CFFListIterator k= qs; k.hasItem(); k++)
558    ts.append (normalize (k.getItem().factor()));
559  return ts;
560}
561
562ListCFList
563irrCharSeries (const CFList & PS)
564{
565  CanonicalForm reducible, reducible2;
566  CFList qs, cs, factorset, is, ts, L;
567  CanonicalForm sqrf;
568  CFFList sqrfFactors;
569  CFFListIterator iter2;
570  for (CFListIterator iter= PS; iter.hasItem(); iter++)
571  {
572    sqrf= 1;
573    sqrfFactors= sqrFree (iter.getItem());
574    if (sqrfFactors.getFirst().factor().inCoeffDomain())
575      sqrfFactors.removeFirst();
576    for (iter2= sqrfFactors; iter2.hasItem(); iter2++)
577      sqrf *= iter2.getItem().factor();
578    sqrf= normalize (sqrf);
579    L= Union (CFList (sqrf), L);
580  }
581
582  ListCFList pi, ppi, qqi, qsi, iss, qhi= ListCFList(L);
583
584  int nr_of_iteration= 0, indexRed, highestlevel= 0;
585
586  for (CFListIterator iter= PS; iter.hasItem(); iter++)
587  {
588    if (level (iter.getItem()) > highestlevel)
589      highestlevel= level(iter.getItem());
590  }
591
592  while (!qhi.isEmpty())
593  {
594    sortListCFList (qhi);
595
596    qs= qhi.getFirst();
597
598    ListCFList ppi1,ppi2;
599    select (ppi, qs.length(), ppi1, ppi2);
600
601    inplaceUnion (ppi2, qqi);
602
603    if (nr_of_iteration == 0)
604    {
605      nr_of_iteration += 1;
606      ppi= ListCFList();
607    }
608    else
609    {
610      nr_of_iteration += 1;
611      ppi= MyUnion (ListCFList (qs), ppi1);
612    }
613
614    StoreFactors StoredFactors;
615    cs= modCharSet (qs, StoredFactors, false);
616    cs= removeContent (cs, StoredFactors);
617
618    factorset= StoredFactors.FS1;
619
620    if (!cs.isEmpty() && cs.getFirst().level() > 0)
621    {
622      ts= irredAS (cs, indexRed, reducible);
623
624      if (indexRed <= 0) // irreducible
625      {
626        if (!isSubset (cs,qs))
627          cs= charSetViaCharSetN (Union (qs,cs));
628        if (!isMember (cs, pi))
629        {
630          pi= MyUnion (pi, ListCFList (cs));
631          if (cs.getFirst().level() > 0)
632          {
633            ts= irredAS (cs, indexRed, reducible);
634
635            if (indexRed <= 0) //irreducible
636            {
637              qsi= MyUnion (qsi, ListCFList(cs));
638              if (cs.length() == highestlevel)
639                is= factorPSet (factorset);
640              else
641                is= Union (factorsOfInitials (cs), factorPSet (factorset));
642              iss= adjoin (is, qs, qqi);
643            }
644          }
645          else
646            iss= adjoin (factorPSet (factorset), qs, qqi);
647        }
648        else
649          iss= adjoin (factorPSet (factorset), qs, qqi);
650      }
651
652      if (indexRed > 0)
653      {
654        is= factorPSet (factorset);
655        if (indexRed > 1)
656        {
657          CFList cst;
658          for (CFListIterator i= cs ; i.hasItem(); i++)
659          {
660            if (i.getItem() == reducible)
661              break;
662            else
663              cst.append (i.getItem());
664          }
665          is= Union (factorsOfInitials (cst), is);
666          iss= MyUnion (adjoin (is, qs, qqi), adjoinb (ts, qs, qqi, cst));
667        }
668        else
669          iss= adjoin (Union (is, ts), qs, qqi);
670      }
671    }
672    else
673      iss= adjoin (factorPSet (factorset), qs, qqi);
674    if (qhi.length() > 1)
675    {
676      qhi.removeFirst();
677      qhi= MyUnion (qhi, iss);
678    }
679    else
680      qhi= iss;
681  }
682  if (!qsi.isEmpty())
683    return contract (qsi);
684  return ListCFList(CFList (1)) ;
685}
686
Note: See TracBrowser for help on using the repository browser.