cfCharSetsUtil.h File Reference

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

Go to the source code of this file.

Data Structures
class	StoreFactors
	class to store factors that get removed during char set computation More...

Functions
Variable	get_max_var (const CFList &PS)
CFList	only_in_one (const CFList &PS, const Variable &x)
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)
CanonicalForm	lowestRank (const CFList &L)
CFList	initials (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...
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	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)
ListCFList	contract (const ListCFList &cs)
bool	isSubset (const CFList &PS, const CFList &Cset)
	is PS a subset of Cset ? 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	inplaceUnion (const ListCFList &a, ListCFList &b)
	Union of a and b stored in b. More...
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...

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.

ABSTRACT: Descriptions can be found in Wang "On the Parallelization of characteristic-set based algorithms" or Greuel/Pfister "A Singular Introduction to Commutative Algebra".

Author

Martin Lee

Definition in file cfCharSetsUtil.h.

Function Documentation

adjoin()

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

Definition at line 495 of file cfCharSetsUtil.cc.

{
  ListCFList iss, qhi;
  ListCFListIterator j;
  CFList iscopy, itt;
  CFListIterator i;
  int ind, length;
 
  for (i= is; i.hasItem(); i++)
  {
    if (i.getItem().level() > 0)
      iscopy= Union (CFList (i.getItem()), iscopy);
  }
  if (iscopy.isEmpty())
    return iss;
 
  qhi= Difference (qh, qs);
  length= qhi.length();
 
  for (i= iscopy; i.hasItem(); i++)
  {
    itt= Union (qs, CFList (i.getItem()));
    ind= 0;
    if (length > 0)
    {
      for (j= qhi; j.hasItem(); j++)
      {
        if (isSubset (j.getItem(), itt))
          ind= 1;
      }
    }
    if (ind == 0)
      iss.append (itt);
  }
  return iss;
}

adjoinb()

ListCFList adjoinb	(	const CFList &	is,
		const CFList &	qs,
		const ListCFList &	qh,
		const CFList &	cs
	)

Definition at line 533 of file cfCharSetsUtil.cc.

{
  ListCFList iss, qhi;
  ListCFListIterator j;
  CFList iscopy, itt;
  CFListIterator i;
  int ind, length;
 
  for (i= is ; i.hasItem(); i++)
  {
    if (i.getItem().level() > 0)
      iscopy= Union (CFList (i.getItem()), iscopy);
  }
  if (iscopy.isEmpty())
    return iss;
  qhi= Difference (qh, qs);
  length= qhi.length();
  for (i= iscopy; i.hasItem(); i++)
  {
    itt= Union (Union (qs, CFList (i.getItem())), cs);
    ind= 0;
    if (length > 0)
    {
      for (j= qhi; j.hasItem(); j++)
      {
        if (isSubset (j.getItem(), itt))
          ind= 1;
      }
    }
    if (ind == 0)
      iss.append(itt);
  }
  return iss;
}

contract()

ListCFList contract

(

const ListCFList &

cs

)

Definition at line 926 of file cfCharSetsUtil.cc.

{
  ListCFList mem, ts;
  CFList iitem, jitem;
 
  if (cs.length() < 2)
    return cs;
 
  int l= cs.length();
  int ii= 1;
  ListCFListIterator j;
  for (ListCFListIterator i= cs; i.hasItem() && ii < l; i++, ii++)
  {
    iitem= i.getItem();
    if (!find (mem, iitem))
    {
      j= i;
      j++;
      for (; j.hasItem(); j++)
      {
        jitem= j.getItem();
        if (!find (mem, jitem))
        {
          if (contractsub (iitem, jitem))
          {
            ts.append (jitem);
            mem.append (jitem);
          }
          else
          {
            if (contractsub (jitem, iitem))
              ts.append (iitem); // no mem.append (item) because we assume cs does not contain duplicate entries
          }
        }
      }
    }
  }
  return Difference (cs,ts);
}

factorPSet()

CFList factorPSet

(

const CFList &

PS

)

Definition at line 805 of file cfCharSetsUtil.cc.

{
  CFList result;
  CFFList factors;
  CFFListIterator j;
 
  for (CFListIterator i= PS; i. hasItem(); i++)
  {
    factors= factorize (i.getItem());
    if (factors.getFirst().factor().inCoeffDomain())
      factors.removeFirst();
    for (j= factors; j.hasItem(); j++ )
      result= Union (result, CFList (normalize (j.getItem().factor())));
  }
  return result;
}

factorsOfInitials()

CFList factorsOfInitials

(

const CFList &

L

)

Definition at line 755 of file cfCharSetsUtil.cc.

{
  CFList result;
  CFFList factors;
  CanonicalForm tmp;
 
  for (CFListIterator i= L; i.hasItem(); i++)
  {
    factors= factorize (LC (i.getItem()));
    for (CFFListIterator j= factors; j.hasItem(); j++)
    {
      tmp= j.getItem().factor();
      if (!tmp.inCoeffDomain())
        result= Union (result, CFList (normalize (tmp)));
    }
  }
 
  return result;
}

get_max_var()

Variable get_max_var

(

const CFList &

PS

)

Definition at line 196 of file cfCharSetsUtil.cc.

{
  Variable x= PS.getFirst().mvar(), y;
  for (CFListIterator i= PS; i.hasItem(); i++)
  {
    y= i.getItem().mvar();
    if (y > x)
      x= y;
  }
  return x;
}

initials()

CFList initials

(

const CFList &

L

)

Definition at line 743 of file cfCharSetsUtil.cc.

{
  CFList result;
  for (CFListIterator iter= L; iter.hasItem(); iter++)
  {
    if (!LC(iter.getItem()).inCoeffDomain())
      result.append (LC (iter.getItem()));
  }
  return result;
}

inplaceUnion()

void inplaceUnion	(	const ListCFList &	a,
		ListCFList &	b
	)

Union of a and b stored in b.

Definition at line 473 of file cfCharSetsUtil.cc.

{
  if (a.isEmpty())
    return;
  if (b.isEmpty())
  {
    b= a;
    return;
  }
 
  ListCFListIterator i;
  CFList elem;
 
  for (i= a; i.hasItem(); i++)
  {
    elem= i.getItem();
    if ((!elem.isEmpty()) && (!find (b, elem)))
      b.insert(elem);
  }
}

isSubset()

bool isSubset	(	const CFList &	PS,
		const CFList &	Cset
	)

is PS a subset of Cset ?

Definition at line 461 of file cfCharSetsUtil.cc.

{
  for (CFListIterator i= PS; i.hasItem(); i++)
  {
    if (!find (Cset, i.getItem()))
      return 0;
  }
  return 1;
}

lowestRank()

CanonicalForm lowestRank

(

const CFList &

L

)

Definition at line 357 of file cfCharSetsUtil.cc.

{
  CFListIterator i= L;
  CanonicalForm f;
  int ind= 0;
  if (!i.hasItem())
    return f;
 
  f= i.getItem();
  i++;
 
  while (i.hasItem())
  {
    if (lowerRank (i.getItem(), f, ind))
    {
      if (ind)
      {
        if (size (i.getItem()) < size (f))
          f= i.getItem();
        ind= 0;
      }
      else
        f= i.getItem();
    }
    i++;
  }
  return f;
}

normalize()

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.

{
  if (F.isZero())
    return F;
  if (getCharacteristic() == 0)
  {
    CanonicalForm G;
    bool isRat= isOn (SW_RATIONAL);
    if (!isRat)
      On (SW_RATIONAL);
    G= F;
    G *= bCommonDen (G);
    Off (SW_RATIONAL);
    G /= icontent (G);
    if (isRat)
      On (SW_RATIONAL);
    if (lc(G) < 0)
      G= -G;
    return G;
  }
 
  return F/lc (F);
}

only_in_one()

CFList only_in_one	(	const CFList &	PS,
		const Variable &	x
	)

Definition at line 212 of file cfCharSetsUtil.cc.

{
  CFList output;
 
  for (CFListIterator i= PS; i.hasItem(); i++ )
  {
    if (degree (i.getItem(), x) >= 1)
      output.insert (i.getItem());
    if (output.length() >= 2)
      break;
  }
  return output;
}

Prem() [1/2]

CanonicalForm Prem	(	const CanonicalForm &	F,
		const CanonicalForm &	G
	)

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

Definition at line 616 of file cfCharSetsUtil.cc.

{
  CanonicalForm f, g, l, test, lu, lv, t, retvalue;
  int degF, degG, levelF, levelG;
  bool reord;
  Variable v, vg= G.mvar();
 
  if ( (levelF= F.level()) < (levelG= G.level()))
    return F;
  else
  {
    if ( levelF == levelG )
    {
      f= F;
      g= G;
      reord= false;
      v= F.mvar();
    }
    else
    {
      v= Variable (levelF + 1);
      f= swapvar (F, vg, v);
      g= swapvar (G, vg, v);
      reord= true;
    }
    degG= degree (g, v );
    degF= degree (f, v );
    if (degG <= degF)
    {
      l= LC (g);
      g= g - l*power (v, degG);
    }
    else
      l= 1;
    while ((degG <= degF) && (!f.isZero()))
    {
      test= gcd (l, LC(f));
      lu= l / test;
      lv= LC(f) / test;
      t= g*lv*power (v, degF - degG);
 
      if (degF == 0)
        f= 0;
      else
        f= f - LC (f)*power (v, degF);
 
      f= f*lu - t;
      degF= degree (f, v);
    }
 
    if (reord)
      retvalue= swapvar (f, vg, v);
    else
      retvalue= f;
 
    return retvalue;
  }
}

Prem() [2/2]

CanonicalForm Prem	(	const CanonicalForm &	f,
		const CFList &	L
	)

pseudo remainder of f by L

Definition at line 710 of file cfCharSetsUtil.cc.

{
  CanonicalForm rem= f;
  CFListIterator i= L;
 
  for (i.lastItem(); i.hasItem(); i--)
    rem= normalize (Prem (rem, i.getItem()));
 
  return rem;
}

Premb()

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.

{
  CanonicalForm rem= f;
  CFList l= L;
  l.removeFirst();
  CFListIterator i= l;
 
  for (i.lastItem(); i.hasItem(); i--)
    rem= normalize (Prem (rem, i.getItem()));
 
  CanonicalForm tmp= L.getFirst()/content (L.getFirst());
 
  bool isRat= isOn (SW_RATIONAL);
  int ch=getCharacteristic();
  if (ch == 0 && !isRat)
    On (SW_RATIONAL);
  if (fdivides (tmp, rem))
  {
    if (ch == 0 && !isRat)
      Off (SW_RATIONAL);
    return 0;
  }
 
  if (ch == 0 && !isRat)
    Off (SW_RATIONAL);
 
  rem= normalize (Prem (rem, L.getFirst()));
 
  return rem;
}

removeContent() [1/2]

void removeContent	(	CanonicalForm &	F,
		CanonicalForm &	cF
	)

Definition at line 776 of file cfCharSetsUtil.cc.

{
  if (size (F) == 1)
  {
    CanonicalForm tmp= F;
    F= F.mvar();
    cF= tmp/F;
    if (!cF.inCoeffDomain())
      cF= normalize (cF);
    else
      cF= 0;
    F= normalize (F);
 
    return;
  }
 
  cF= content (F);
 
  if (cF.inCoeffDomain())
    cF= 0;
  else
  {
    cF= normalize (cF);
    F /= cF;
    F= normalize (F);
  }
}

removeContent() [2/2]

CFList removeContent	(	const CFList &	PS,
		StoreFactors &	StoredFactors
	)

Definition at line 879 of file cfCharSetsUtil.cc.

{
  CFListIterator i= PS;
  if ((!i.hasItem()) || (PS.getFirst().level() == 0 ))
    return PS;
 
  CFList output;
  CanonicalForm cc,elem;
 
  for (; i.hasItem(); i++)
  {
    elem= i.getItem();
    cc= content (elem, elem.mvar());
    if (cc.level() > 0 )
    {
      output.append (normalize (elem / cc));
      StoredFactors.FS1 = Union (CFList (normalize (cc)), StoredFactors.FS1);
    }
    else
      output.append(normalize (elem));
  }
  return output;
}

removeFactors()

void removeFactors	(	CanonicalForm &	r,
		StoreFactors &	StoredFactors,
		CFList &	removedFactors
	)

Definition at line 823 of file cfCharSetsUtil.cc.

{
  CanonicalForm quot;
  CFList testlist;
  int n= level(r);
  bool divides;
  CFListIterator j;
 
  for (int i=1; i<= n; i++)
    testlist.append (CanonicalForm (Variable (i)));
 
  // remove already removed factors
  for (j= StoredFactors.FS1; j.hasItem(); j++)
  {
    while (fdivides (j.getItem(), r, quot))
    {
      r= quot;
    }
  }
 
  for (j= StoredFactors.FS2; j.hasItem(); j++)
  {
    divides= false;
    if (j.getItem() != r)
    {
      while (fdivides (j.getItem(), r, quot))
      {
        divides= true;
        r= quot;
      }
      if (divides)
        removedFactors= Union (removedFactors, CFList (j.getItem()));
    }
  }
  r= normalize (r);
 
  // remove variables
  for (j= testlist; j.hasItem() && !r.isOne(); j++)
  {
    divides= false;
    if (j.getItem() != r)
    {
      while (fdivides (j.getItem(), r, quot))
      {
        divides= true;
        r= quot;
      }
      if (divides)
        removedFactors= Union (removedFactors, CFList (j.getItem()));
     }
  }
  r= normalize (r);
}

reorderb()

Varlist reorderb	(	const Varlist &	difference,
		const CFList &	PS,
		const int	highest_level
	)

Definition at line 259 of file cfCharSetsUtil.cc.

{
  Intarray A(1, highest_level), B(1, highest_level), C(1, highest_level),
           D(1, highest_level), E(1, highest_level), F(1, highest_level),
           G(1, highest_level);
  initArray (highest_level, A, B, C, D, E, F, G);
  int i= 0, j, n= difference.length(), gap= 1 + __INIT_GAP__;
  Variable temp;
  Array<Variable> v(0, n);
  VarlistIterator J;
 
  for (J= difference; J.hasItem(); J++ )
  {
    v[i]= J.getItem();
    i++;
  }
 
  while (gap <= n)
    gap = __INIT_GAP__ * gap + 1;
  gap /= __INIT_GAP__;
 
  while (gap > 0)
  {
    for (i= gap; i <= n - 1; i++)
    {
      temp= v[i];
      for (j= i - gap; j >=0 ; j -= gap)
      {
        if (degord (v[j], temp, PS, A, B, C, D, E, F, G))
          break;
        v[j + gap]= v[j];
      }
      v[j + gap]= temp;
    }
    gap /= __INIT_GAP__;
  }
  Varlist output;
  for (i= 0; i <= n - 1; i++)
    output.append (v[i]);
  return output;
}

select()

void select	(	const ListCFList &	ppi,
		int	length,
		ListCFList &	ppi1,
		ListCFList &	ppi2
	)

Definition at line 570 of file cfCharSetsUtil.cc.

{
  CFList elem;
  for (ListCFListIterator i= ppi; i.hasItem(); i++)
  {
    elem= i.getItem();
    if (!elem.isEmpty())
    {
      if (length <= elem.length())
        ppi2.append(elem);
      else
        ppi1.append(elem);
    }
  }
}

sortCFListByLevel()

void sortCFListByLevel

(

CFList &

list

)

sort in descending order of level of elements

Definition at line 428 of file cfCharSetsUtil.cc.

{
  int l= 1;
  int k= 1;
  CanonicalForm buf;
  CFListIterator m;
  for (CFListIterator i= list; l <= list.length(); i++, l++)
  {
    for (CFListIterator j= list; k <= list.length() - l; k++)
    {
      m= j;
      m++;
      if ((size (j.getItem()) < size (m.getItem())) ||
          ((size (j.getItem()) == size (m.getItem()))
            && (j.getItem().level() < m.getItem().level())))
      {
        buf= m.getItem();
        m.getItem()= j.getItem();
        j.getItem()= buf;
        j++;
        j.getItem()= m.getItem();
      }
      else
        j++;
    }
    k= 1;
  }
}

sortListCFList()

void sortListCFList

(

ListCFList &

list

)

sort in descending order of length of elements

Definition at line 396 of file cfCharSetsUtil.cc.

{
  int l= 1;
  int k= 1;
  CFList buf;
  ListCFListIterator m;
  for (ListCFListIterator i= list; l <= list.length(); i++, l++)
  {
    for (ListCFListIterator j= list; k <= list.length() - l; k++)
    {
      m= j;
      m++;
      if ((j.getItem().length() < m.getItem().length()) ||
          (j.getItem().length() == m.getItem().length() &&
           minLevel (j.getItem()) > minLevel (m.getItem())))
      {
        buf= m.getItem();
        m.getItem()= j.getItem();
        j.getItem()= buf;
        j++;
        j.getItem()= m.getItem();
      }
      else
        j++;
    }
    k= 1;
  }
}

swapvar() [1/2]

CFFList swapvar	(	const CFFList &	PS,
		const Variable &	x,
		const Variable &	y
	)

Definition at line 314 of file cfCharSetsUtil.cc.

{
  CFFList ps;
 
  for (CFFListIterator i= PS; i.hasItem(); i++)
    ps.append (CFFactor (swapvar (i.getItem().factor(), x, y),
                         i.getItem().exp()));
  return ps;
}

swapvar() [2/2]

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.

{
  CFList ps;
 
  for (CFListIterator i= PS; i.hasItem(); i++)
    ps.append (swapvar (i.getItem(), x, y));
  return ps;
}

uniGcd()

CFList uniGcd

(

const CFList &

L

)

Definition at line 721 of file cfCharSetsUtil.cc.

{
  CFList tmp;
  CanonicalForm g;
  CFListIterator i;
  for (i= L; i.hasItem(); i++)
  {
    if (i.getItem().isUnivariate() && i.getItem().level() == 1)
      tmp.append (i.getItem());
  }
  if (tmp.length() <= 2)
    return L;
  i= tmp;
  g= i.getItem();
  i++;
  g= gcd (g,i.getItem());
  i++;
  for (; i.hasItem(); i++)
    g= gcd (g, i.getItem());
  return Union (Difference (L, tmp), CFList (g));
}