Macros | Functions
cfCharSetsUtil.cc File Reference

This file provides utility functions to compute characteristic sets. More...

#include "config.h"
#include "canonicalform.h"
#include "cf_algorithm.h"
#include "cfCharSetsUtil.h"

Go to the source code of this file.

Macros

#define __ARRAY_INIT__   -1
 
#define __INIT_GAP__   3
 

Functions

int degpsmax (const CFList &PS, const Variable &x, Intarray &A, Intarray &C)
 
int degpsmin (const CFList &PS, const Variable &x, Intarray &A, Intarray &B, Intarray &C, Intarray &D)
 
int Tdeg (const CFList &PS, const Variable &x, Intarray &A, Intarray &B, Intarray &C, Intarray &D, Intarray &E, Intarray &F)
 
int nr_of_poly (const CFList &PS, const Variable &x, Intarray &G)
 
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)
 
Variable get_max_var (const CFList &PS)
 
CFList only_in_one (const CFList &PS, const Variable &x)
 
void initArray (const int highest_level, Intarray &A, Intarray &B, Intarray &C, Intarray &D, Intarray &E, Intarray &F, Intarray &G)
 
Varlist reorderb (const Varlist &difference, const CFList &PS, const int highest_level)
 
CFList swapvar (const CFList &PS, const Variable &x, const Variable &y)
 swapvar a whole list of CanonicalForms More...
 
CFFList swapvar (const CFFList &PS, const Variable &x, const Variable &y)
 
bool lowerRank (const CanonicalForm &F, const CanonicalForm &G, int &ind)
 
CanonicalForm lowestRank (const CFList &L)
 
int minLevel (const CFList &L)
 
void sortListCFList (ListCFList &list)
 sort in descending order of length of elements More...
 
void sortCFListByLevel (CFList &list)
 sort in descending order of level of elements More...
 
bool isSubset (const CFList &PS, const CFList &Cset)
 is PS a subset of Cset ? More...
 
void inplaceUnion (const ListCFList &a, ListCFList &b)
 Union of a and b stored in b. More...
 
ListCFList adjoin (const CFList &is, const CFList &qs, const ListCFList &qh)
 
ListCFList adjoinb (const CFList &is, const CFList &qs, const ListCFList &qh, const CFList &cs)
 
void select (const ListCFList &ppi, int length, ListCFList &ppi1, ListCFList &ppi2)
 
CanonicalForm normalize (const CanonicalForm &F)
 normalize a poly, i.e. in char 0 clear denominators, remove integer content in char p divide by leading coeff More...
 
CanonicalForm Prem (const CanonicalForm &F, const CanonicalForm &G)
 pseudo remainder of F by G with certain factors of LC (g) cancelled More...
 
CanonicalForm Premb (const CanonicalForm &f, const CFList &L)
 pseudo remainder of f by L with faster test for remainder being zero More...
 
CanonicalForm Prem (const CanonicalForm &f, const CFList &L)
 pseudo remainder of f by L More...
 
CFList uniGcd (const CFList &L)
 
CFList initials (const CFList &L)
 
CFList factorsOfInitials (const CFList &L)
 
void removeContent (CanonicalForm &F, CanonicalForm &cF)
 
CFList factorPSet (const CFList &PS)
 
void removeFactors (CanonicalForm &r, StoreFactors &StoredFactors, CFList &removedFactors)
 
CFList removeContent (const CFList &PS, StoreFactors &StoredFactors)
 
bool contractsub (const CFList &cs1, const CFList &cs2)
 
ListCFList contract (const ListCFList &cs)
 

Detailed Description

This file provides utility functions to compute characteristic sets.

Note
some of the code is code from libfac or derived from code from libfac. Libfac is written by M. Messollen. See also COPYING for license information and README for general information on characteristic sets.
Authors
Martin Lee

Definition in file cfCharSetsUtil.cc.

Macro Definition Documentation

#define __ARRAY_INIT__   -1

Definition at line 23 of file cfCharSetsUtil.cc.

#define __INIT_GAP__   3

Definition at line 257 of file cfCharSetsUtil.cc.

Function Documentation

ListCFList adjoin ( const CFList is,
const CFList qs,
const ListCFList qh 
)

Definition at line 495 of file cfCharSetsUtil.cc.

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 }
bool isSubset(const CFList &PS, const CFList &Cset)
is PS a subset of Cset ?
int isEmpty() const
Definition: ftmpl_list.cc:267
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
int j
Definition: myNF.cc:70
int length() const
Definition: ftmpl_list.cc:273
int i
Definition: cfEzgcd.cc:123
T & getItem() const
Definition: ftmpl_list.cc:431
void append(const T &)
Definition: ftmpl_list.cc:256
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
ListCFList adjoinb ( const CFList is,
const CFList qs,
const ListCFList qh,
const CFList cs 
)

Definition at line 533 of file cfCharSetsUtil.cc.

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 }
bool isSubset(const CFList &PS, const CFList &Cset)
is PS a subset of Cset ?
int isEmpty() const
Definition: ftmpl_list.cc:267
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
int j
Definition: myNF.cc:70
int length() const
Definition: ftmpl_list.cc:273
int i
Definition: cfEzgcd.cc:123
T & getItem() const
Definition: ftmpl_list.cc:431
void append(const T &)
Definition: ftmpl_list.cc:256
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
ListCFList contract ( const ListCFList cs)

Definition at line 925 of file cfCharSetsUtil.cc.

926 {
927  ListCFList mem, ts;
928  CFList iitem, jitem;
929 
930  if (cs.length() < 2)
931  return cs;
932 
933  int l= cs.length();
934  int ii= 1;
936  for (ListCFListIterator i= cs; i.hasItem() && ii < l; i++, ii++)
937  {
938  iitem= i.getItem();
939  if (!find (mem, iitem))
940  {
941  j= i;
942  j++;
943  for (; j.hasItem(); j++)
944  {
945  jitem= j.getItem();
946  if (!find (mem, jitem))
947  {
948  if (contractsub (iitem, jitem))
949  {
950  ts.append (jitem);
951  mem.append (jitem);
952  }
953  else
954  {
955  if (contractsub (jitem, iitem))
956  ts.append (iitem); // no mem.append (item) because we assume cs does not contain duplicate entries
957  }
958  }
959  }
960  }
961  }
962  return Difference (cs,ts);
963 }
bool contractsub(const CFList &cs1, const CFList &cs2)
template bool find(const List< CanonicalForm > &, const CanonicalForm &)
int j
Definition: myNF.cc:70
int length() const
Definition: ftmpl_list.cc:273
int i
Definition: cfEzgcd.cc:123
T & getItem() const
Definition: ftmpl_list.cc:431
void append(const T &)
Definition: ftmpl_list.cc:256
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
int l
Definition: cfEzgcd.cc:94
bool contractsub ( const CFList cs1,
const CFList cs2 
)

Definition at line 903 of file cfCharSetsUtil.cc.

904 {
906 
908  for (i= cs1; i.hasItem(); i++)
909  {
910  if (Prem (i.getItem(), cs2) != 0)
911  return false;
912  }
913 
914  CFList is= factorsOfInitials (cs1);
915 
916  for (i= is; i.hasItem(); i++)
917  {
918  if (Prem (i.getItem(), cs2) == 0)
919  return false;
920  }
921  return true;
922 }
CFList factorsOfInitials(const CFList &L)
factory's main class
Definition: canonicalform.h:75
const ring r
Definition: syzextra.cc:208
int i
Definition: cfEzgcd.cc:123
T & getItem() const
Definition: ftmpl_list.cc:431
CanonicalForm Prem(const CanonicalForm &F, const CanonicalForm &G)
pseudo remainder of F by G with certain factors of LC (g) cancelled
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 
)

Definition at line 162 of file cfCharSetsUtil.cc.

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 }
int level(const CanonicalForm &f)
int degpsmax(const CFList &PS, const Variable &x, Intarray &A, Intarray &C)
int nr_of_poly(const CFList &PS, const Variable &x, Intarray &G)
int degpsmin(const CFList &PS, const Variable &x, Intarray &A, Intarray &B, Intarray &C, Intarray &D)
int Tdeg(const CFList &PS, const Variable &x, Intarray &A, Intarray &B, Intarray &C, Intarray &D, Intarray &E, Intarray &F)
int degpsmax ( const CFList PS,
const Variable x,
Intarray A,
Intarray C 
)

Definition at line 27 of file cfCharSetsUtil.cc.

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 }
int status int void size_t count
Definition: si_signals.h:59
int level(const CanonicalForm &f)
static int max(int a, int b)
Definition: fast_mult.cc:264
int i
Definition: cfEzgcd.cc:123
#define __ARRAY_INIT__
Variable x
Definition: cfModGcd.cc:4023
int degree(const CanonicalForm &f)
int degpsmin ( const CFList PS,
const Variable x,
Intarray A,
Intarray B,
Intarray C,
Intarray D 
)

Definition at line 54 of file cfCharSetsUtil.cc.

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 }
int status int void size_t count
Definition: si_signals.h:59
int level(const CanonicalForm &f)
static int min(int a, int b)
Definition: fast_mult.cc:268
int degpsmax(const CFList &PS, const Variable &x, Intarray &A, Intarray &C)
int i
Definition: cfEzgcd.cc:123
#define __ARRAY_INIT__
Variable x
Definition: cfModGcd.cc:4023
int degree(const CanonicalForm &f)
CFList factorPSet ( const CFList PS)

Definition at line 804 of file cfCharSetsUtil.cc.

805 {
806  CFList result;
807  CFFList factors;
809 
810  for (CFListIterator i= PS; i. hasItem(); i++)
811  {
812  factors= factorize (i.getItem());
813  if (factors.getFirst().factor().inCoeffDomain())
814  factors.removeFirst();
815  for (j= factors; j.hasItem(); j++ )
816  result= Union (result, CFList (normalize (j.getItem().factor())));
817  }
818  return result;
819 }
CanonicalForm normalize(const CanonicalForm &F)
normalize a poly, i.e. in char 0 clear denominators, remove integer content in char p divide by leadi...
void removeFirst()
Definition: ftmpl_list.cc:287
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:390
int j
Definition: myNF.cc:70
T getFirst() const
Definition: ftmpl_list.cc:279
int i
Definition: cfEzgcd.cc:123
T & getItem() const
Definition: ftmpl_list.cc:431
return result
Definition: facAbsBiFact.cc:76
CFList factorsOfInitials ( const CFList L)

Definition at line 754 of file cfCharSetsUtil.cc.

755 {
756  CFList result;
757  CFFList factors;
758  CanonicalForm tmp;
759 
760  for (CFListIterator i= L; i.hasItem(); i++)
761  {
762  factors= factorize (LC (i.getItem()));
763  for (CFFListIterator j= factors; j.hasItem(); j++)
764  {
765  tmp= j.getItem().factor();
766  if (!tmp.inCoeffDomain())
767  result= Union (result, CFList (normalize (tmp)));
768  }
769  }
770 
771  return result;
772 }
CanonicalForm normalize(const CanonicalForm &F)
normalize a poly, i.e. in char 0 clear denominators, remove integer content in char p divide by leadi...
bool inCoeffDomain() const
factory's main class
Definition: canonicalform.h:75
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:390
int j
Definition: myNF.cc:70
int i
Definition: cfEzgcd.cc:123
CanonicalForm LC(const CanonicalForm &f)
return result
Definition: facAbsBiFact.cc:76
Variable get_max_var ( const CFList PS)

Definition at line 196 of file cfCharSetsUtil.cc.

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 }
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
factory's class for variables
Definition: variable.h:32
T getFirst() const
Definition: ftmpl_list.cc:279
int i
Definition: cfEzgcd.cc:123
Variable x
Definition: cfModGcd.cc:4023
void initArray ( const int  highest_level,
Intarray A,
Intarray B,
Intarray C,
Intarray D,
Intarray E,
Intarray F,
Intarray G 
)

Definition at line 228 of file cfCharSetsUtil.cc.

230 {
231  for (int i=1 ; i <= highest_level; i ++)
232  {
233  A[i]= __ARRAY_INIT__;
234  B[i]= __ARRAY_INIT__;
235  C[i]= __ARRAY_INIT__;
236  D[i]= __ARRAY_INIT__;
237  E[i]= __ARRAY_INIT__;
238  F[i]= __ARRAY_INIT__;
239  G[i]= __ARRAY_INIT__;
240  }
241 }
int i
Definition: cfEzgcd.cc:123
#define __ARRAY_INIT__
CFList initials ( const CFList L)

Definition at line 742 of file cfCharSetsUtil.cc.

743 {
744  CFList result;
745  for (CFListIterator iter= L; iter.hasItem(); iter++)
746  {
747  if (!LC(iter.getItem()).inCoeffDomain())
748  result.append (LC (iter.getItem()));
749  }
750  return result;
751 }
CFFListIterator iter
Definition: facAbsBiFact.cc:54
T & getItem() const
Definition: ftmpl_list.cc:431
void append(const T &)
Definition: ftmpl_list.cc:256
CanonicalForm LC(const CanonicalForm &f)
return result
Definition: facAbsBiFact.cc:76
void inplaceUnion ( const ListCFList a,
ListCFList b 
)

Union of a and b stored in b.

Definition at line 473 of file cfCharSetsUtil.cc.

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 }
const poly a
Definition: syzextra.cc:212
void insert(const T &)
Definition: ftmpl_list.cc:193
template bool find(const List< CanonicalForm > &, const CanonicalForm &)
int isEmpty() const
Definition: ftmpl_list.cc:267
int i
Definition: cfEzgcd.cc:123
T & getItem() const
Definition: ftmpl_list.cc:431
bool isSubset ( const CFList PS,
const CFList Cset 
)

is PS a subset of Cset ?

Definition at line 461 of file cfCharSetsUtil.cc.

462 {
463  for (CFListIterator i= PS; i.hasItem(); i++)
464  {
465  if (!find (Cset, i.getItem()))
466  return 0;
467  }
468  return 1;
469 }
template bool find(const List< CanonicalForm > &, const CanonicalForm &)
int i
Definition: cfEzgcd.cc:123
bool lowerRank ( const CanonicalForm F,
const CanonicalForm G,
int &  ind 
)

Definition at line 325 of file cfCharSetsUtil.cc.

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 }
bool inCoeffDomain() const
int level() const
level() returns the level of CO.
bool lowerRank(const CanonicalForm &F, const CanonicalForm &G, int &ind)
int degree(const CanonicalForm &f)
CanonicalForm LC(const CanonicalForm &f)
CanonicalForm lowestRank ( const CFList L)

Definition at line 357 of file cfCharSetsUtil.cc.

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 }
factory's main class
Definition: canonicalform.h:75
bool lowerRank(const CanonicalForm &F, const CanonicalForm &G, int &ind)
FILE * f
Definition: checklibs.c:7
int i
Definition: cfEzgcd.cc:123
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
T & getItem() const
Definition: ftmpl_list.cc:431
int minLevel ( const CFList L)

Definition at line 386 of file cfCharSetsUtil.cc.

387 {
388  if (L.isEmpty())
389  return 0;
390  int min= size (L.getFirst());
391  return min;
392 }
static int min(int a, int b)
Definition: fast_mult.cc:268
int isEmpty() const
Definition: ftmpl_list.cc:267
T getFirst() const
Definition: ftmpl_list.cc:279
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
CanonicalForm normalize ( const CanonicalForm F)

normalize a poly, i.e. in char 0 clear denominators, remove integer content in char p divide by leading coeff

Definition at line 590 of file cfCharSetsUtil.cc.

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);
602  Off (SW_RATIONAL);
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 }
CanonicalForm icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f )
Definition: cf_gcd.cc:71
void Off(int sw)
switches
factory's main class
Definition: canonicalform.h:75
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
static TreeM * G
Definition: janet.cc:38
int getCharacteristic()
Definition: cf_char.cc:51
CanonicalForm lc(const CanonicalForm &f)
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
bool isOn(int sw)
switches
void On(int sw)
switches
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
int nr_of_poly ( const CFList PS,
const Variable x,
Intarray G 
)

Definition at line 146 of file cfCharSetsUtil.cc.

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 }
int level(const CanonicalForm &f)
static int min(int a, int b)
Definition: fast_mult.cc:268
int i
Definition: cfEzgcd.cc:123
#define __ARRAY_INIT__
Variable x
Definition: cfModGcd.cc:4023
int degree(const CanonicalForm &f)
CFList only_in_one ( const CFList PS,
const Variable x 
)

Definition at line 212 of file cfCharSetsUtil.cc.

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 }
void insert(const T &)
Definition: ftmpl_list.cc:193
int length() const
Definition: ftmpl_list.cc:273
int i
Definition: cfEzgcd.cc:123
Variable x
Definition: cfModGcd.cc:4023
int degree(const CanonicalForm &f)

pseudo remainder of F by G with certain factors of LC (g) cancelled

Definition at line 616 of file cfCharSetsUtil.cc.

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 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
factory's class for variables
Definition: variable.h:32
factory's main class
Definition: canonicalform.h:75
g
Definition: cfModGcd.cc:4031
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
static TreeM * G
Definition: janet.cc:38
int level() const
level() returns the level of CO.
FILE * f
Definition: checklibs.c:7
CanonicalForm test
Definition: cfModGcd.cc:4037
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
int gcd(int a, int b)
Definition: walkSupport.cc:839
CFList swapvar(const CFList &PS, const Variable &x, const Variable &y)
swapvar a whole list of CanonicalForms
int degree(const CanonicalForm &f)
CanonicalForm LC(const CanonicalForm &f)
int l
Definition: cfEzgcd.cc:94
CanonicalForm Prem ( const CanonicalForm f,
const CFList L 
)

pseudo remainder of f by L

Definition at line 709 of file cfCharSetsUtil.cc.

710 {
712  CFListIterator i= L;
713 
714  for (i.lastItem(); i.hasItem(); i--)
715  rem= normalize (Prem (rem, i.getItem()));
716 
717  return rem;
718 }
void rem(unsigned long *a, unsigned long *q, unsigned long p, int &dega, int degq)
Definition: minpoly.cc:574
CanonicalForm normalize(const CanonicalForm &F)
normalize a poly, i.e. in char 0 clear denominators, remove integer content in char p divide by leadi...
void lastItem()
Definition: ftmpl_list.cc:485
factory's main class
Definition: canonicalform.h:75
FILE * f
Definition: checklibs.c:7
int i
Definition: cfEzgcd.cc:123
T & getItem() const
Definition: ftmpl_list.cc:431
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

Definition at line 677 of file cfCharSetsUtil.cc.

678 {
680  CFList l= L;
681  l.removeFirst();
682  CFListIterator i= l;
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  if (getCharacteristic() == 0 && !isRat)
691  On (SW_RATIONAL);
692  if (fdivides (tmp, rem))
693  {
694  if (getCharacteristic() == 0 && !isRat)
695  Off (SW_RATIONAL);
696  return 0;
697  }
698 
699  if (getCharacteristic() == 0 && !isRat)
700  Off (SW_RATIONAL);
701 
702  rem= normalize (Prem (rem, L.getFirst()));
703 
704  return rem;
705 }
void rem(unsigned long *a, unsigned long *q, unsigned long p, int &dega, int degq)
Definition: minpoly.cc:574
CanonicalForm normalize(const CanonicalForm &F)
normalize a poly, i.e. in char 0 clear denominators, remove integer content in char p divide by leadi...
void Off(int sw)
switches
void lastItem()
Definition: ftmpl_list.cc:485
factory's main class
Definition: canonicalform.h:75
int getCharacteristic()
Definition: cf_char.cc:51
void removeFirst()
Definition: ftmpl_list.cc:287
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:180
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
bool isOn(int sw)
switches
void On(int sw)
switches
T getFirst() const
Definition: ftmpl_list.cc:279
FILE * f
Definition: checklibs.c:7
int i
Definition: cfEzgcd.cc:123
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
T & getItem() const
Definition: ftmpl_list.cc:431
CanonicalForm Prem(const CanonicalForm &F, const CanonicalForm &G)
pseudo remainder of F by G with certain factors of LC (g) cancelled
int l
Definition: cfEzgcd.cc:94
void removeContent ( CanonicalForm F,
CanonicalForm cF 
)

Definition at line 775 of file cfCharSetsUtil.cc.

776 {
777  if (size (F) == 1)
778  {
779  CanonicalForm tmp= F;
780  F= F.mvar();
781  cF= tmp/F;
782  if (!cF.inCoeffDomain())
783  cF= normalize (cF);
784  else
785  cF= 0;
786  F= normalize (F);
787 
788  return;
789  }
790 
791  cF= content (F);
792 
793  if (cF.inCoeffDomain())
794  cF= 0;
795  else
796  {
797  cF= normalize (cF);
798  F /= cF;
799  F= normalize (F);
800  }
801 }
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
CanonicalForm normalize(const CanonicalForm &F)
normalize a poly, i.e. in char 0 clear denominators, remove integer content in char p divide by leadi...
bool inCoeffDomain() const
factory's main class
Definition: canonicalform.h:75
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:180
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
CFList removeContent ( const CFList PS,
StoreFactors StoredFactors 
)

Definition at line 878 of file cfCharSetsUtil.cc.

879 {
880  CFListIterator i= PS;
881  if ((!i.hasItem()) || (PS.getFirst().level() == 0 ))
882  return PS;
883 
884  CFList output;
885  CanonicalForm cc,elem;
886 
887  for (; i.hasItem(); i++)
888  {
889  elem= i.getItem();
890  cc= content (elem, elem.mvar());
891  if (cc.level() > 0 )
892  {
893  output.append (normalize (elem / cc));
894  StoredFactors.FS1 = Union (CFList (normalize (cc)), StoredFactors.FS1);
895  }
896  else
897  output.append(normalize (elem));
898  }
899  return output;
900 }
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
CFList FS1
factors that were removed
CanonicalForm normalize(const CanonicalForm &F)
normalize a poly, i.e. in char 0 clear denominators, remove integer content in char p divide by leadi...
factory's main class
Definition: canonicalform.h:75
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:180
int level() const
level() returns the level of CO.
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
T getFirst() const
Definition: ftmpl_list.cc:279
int i
Definition: cfEzgcd.cc:123
T & getItem() const
Definition: ftmpl_list.cc:431
void append(const T &)
Definition: ftmpl_list.cc:256
void removeFactors ( CanonicalForm r,
StoreFactors StoredFactors,
CFList removedFactors 
)

Definition at line 822 of file cfCharSetsUtil.cc.

824 {
825  CanonicalForm quot;
826  CFList testlist;
827  int n= level(r);
828  bool divides;
830 
831  for (int i=1; i<= n; i++)
832  testlist.append (CanonicalForm (Variable (i)));
833 
834  // remove already removed factors
835  for (j= StoredFactors.FS1; j.hasItem(); j++)
836  {
837  while (fdivides (j.getItem(), r, quot))
838  {
839  r= quot;
840  }
841  }
842 
843  for (j= StoredFactors.FS2; j.hasItem(); j++)
844  {
845  divides= false;
846  if (j.getItem() != r)
847  {
848  while (fdivides (j.getItem(), r, quot))
849  {
850  divides= true;
851  r= quot;
852  }
853  if (divides)
854  removedFactors= Union (removedFactors, CFList (j.getItem()));
855  }
856  }
857  r= normalize (r);
858 
859  // remove variables
860  for (j= testlist; j.hasItem() && !r.isOne(); j++)
861  {
862  divides= false;
863  if (j.getItem() != r)
864  {
865  while (fdivides (j.getItem(), r, quot))
866  {
867  divides= true;
868  r= quot;
869  }
870  if (divides)
871  removedFactors= Union (removedFactors, CFList (j.getItem()));
872  }
873  }
874  r= normalize (r);
875 }
CFList FS1
factors that were removed
int level(const CanonicalForm &f)
CanonicalForm normalize(const CanonicalForm &F)
normalize a poly, i.e. in char 0 clear denominators, remove integer content in char p divide by leadi...
factory's class for variables
Definition: variable.h:32
const CanonicalForm CFMap CFMap int &both_non_zero int n
Definition: cfEzgcd.cc:52
factory's main class
Definition: canonicalform.h:75
CF_NO_INLINE bool isOne() const
CF_INLINE bool CanonicalForm::isOne, isZero () const.
Definition: cf_inline.cc:354
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
const ring r
Definition: syzextra.cc:208
int j
Definition: myNF.cc:70
CFList FS2
candidate factors that might get removed
int i
Definition: cfEzgcd.cc:123
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
T & getItem() const
Definition: ftmpl_list.cc:431
void append(const T &)
Definition: ftmpl_list.cc:256
Varlist reorderb ( const Varlist difference,
const CFList PS,
const int  highest_level 
)

Definition at line 259 of file cfCharSetsUtil.cc.

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);
269  VarlistIterator J;
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 }
#define D(A)
Definition: gentable.cc:119
factory's class for variables
Definition: variable.h:32
const CanonicalForm CFMap CFMap int &both_non_zero int n
Definition: cfEzgcd.cc:52
void initArray(const int highest_level, Intarray &A, Intarray &B, Intarray &C, Intarray &D, Intarray &E, Intarray &F, Intarray &G)
static TreeM * G
Definition: janet.cc:38
int j
Definition: myNF.cc:70
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)
#define A
Definition: sirandom.c:23
int length() const
Definition: ftmpl_list.cc:273
int i
Definition: cfEzgcd.cc:123
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
REvaluation E(1, terms.length(), IntRandom(25))
T & getItem() const
Definition: ftmpl_list.cc:431
b *CanonicalForm B
Definition: facBivar.cc:51
void append(const T &)
Definition: ftmpl_list.cc:256
#define __INIT_GAP__
void select ( const ListCFList ppi,
int  length,
ListCFList ppi1,
ListCFList ppi2 
)

Definition at line 570 of file cfCharSetsUtil.cc.

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 }
int isEmpty() const
Definition: ftmpl_list.cc:267
int length() const
Definition: ftmpl_list.cc:273
int i
Definition: cfEzgcd.cc:123
void append(const T &)
Definition: ftmpl_list.cc:256
void sortCFListByLevel ( CFList list)

sort in descending order of level of elements

Definition at line 428 of file cfCharSetsUtil.cc.

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 }
factory's main class
Definition: canonicalform.h:75
int k
Definition: cfEzgcd.cc:93
int j
Definition: myNF.cc:70
int status int void * buf
Definition: si_signals.h:59
int m
Definition: cfEzgcd.cc:119
int length() const
Definition: ftmpl_list.cc:273
int i
Definition: cfEzgcd.cc:123
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
T & getItem() const
Definition: ftmpl_list.cc:431
int l
Definition: cfEzgcd.cc:94
void sortListCFList ( ListCFList list)

sort in descending order of length of elements

Definition at line 396 of file cfCharSetsUtil.cc.

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 }
int minLevel(const CFList &L)
int k
Definition: cfEzgcd.cc:93
int j
Definition: myNF.cc:70
int status int void * buf
Definition: si_signals.h:59
int m
Definition: cfEzgcd.cc:119
int length() const
Definition: ftmpl_list.cc:273
int i
Definition: cfEzgcd.cc:123
T & getItem() const
Definition: ftmpl_list.cc:431
int l
Definition: cfEzgcd.cc:94
CFList swapvar ( const CFList PS,
const Variable x,
const Variable y 
)

swapvar a whole list of CanonicalForms

Definition at line 304 of file cfCharSetsUtil.cc.

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 }
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
int i
Definition: cfEzgcd.cc:123
Variable x
Definition: cfModGcd.cc:4023
CFList swapvar(const CFList &PS, const Variable &x, const Variable &y)
swapvar a whole list of CanonicalForms
void append(const T &)
Definition: ftmpl_list.cc:256
CFFList swapvar ( const CFFList PS,
const Variable x,
const Variable y 
)

Definition at line 314 of file cfCharSetsUtil.cc.

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 }
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
int i
Definition: cfEzgcd.cc:123
Variable x
Definition: cfModGcd.cc:4023
CFList swapvar(const CFList &PS, const Variable &x, const Variable &y)
swapvar a whole list of CanonicalForms
void append(const T &)
Definition: ftmpl_list.cc:256
int Tdeg ( const CFList PS,
const Variable x,
Intarray A,
Intarray B,
Intarray C,
Intarray D,
Intarray E,
Intarray F 
)

Definition at line 91 of file cfCharSetsUtil.cc.

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 }
int level(const CanonicalForm &f)
static int min(int a, int b)
Definition: fast_mult.cc:268
factory's main class
Definition: canonicalform.h:75
int k
Definition: cfEzgcd.cc:93
CFList get_Terms(const CanonicalForm &f)
Definition: cf_factor.cc:274
int degpsmin(const CFList &PS, const Variable &x, Intarray &A, Intarray &B, Intarray &C, Intarray &D)
T getFirst() const
Definition: ftmpl_list.cc:279
int length() const
Definition: ftmpl_list.cc:273
int i
Definition: cfEzgcd.cc:123
#define __ARRAY_INIT__
T & getItem() const
Definition: ftmpl_list.cc:431
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition: cf_ops.cc:523
void append(const T &)
Definition: ftmpl_list.cc:256
int degree(const CanonicalForm &f)
CanonicalForm LC(const CanonicalForm &f)
CFList uniGcd ( const CFList L)

Definition at line 720 of file cfCharSetsUtil.cc.

721 {
722  CFList tmp;
725  for (i= L; i.hasItem(); i++)
726  {
727  if (i.getItem().isUnivariate() && i.getItem().level() == 1)
728  tmp.append (i.getItem());
729  }
730  if (tmp.length() <= 2)
731  return L;
732  i= tmp;
733  g= i.getItem();
734  i++;
735  g= gcd (g,i.getItem());
736  i++;
737  for (; i.hasItem(); i++)
738  g= gcd (g, i.getItem());
739  return Union (Difference (L, tmp), CFList (g));
740 }
factory's main class
Definition: canonicalform.h:75
g
Definition: cfModGcd.cc:4031
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
int length() const
Definition: ftmpl_list.cc:273
int i
Definition: cfEzgcd.cc:123
T & getItem() const
Definition: ftmpl_list.cc:431
int gcd(int a, int b)
Definition: walkSupport.cc:839
void append(const T &)
Definition: ftmpl_list.cc:256
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)