facAlgFuncUtil.h File Reference

Utility functions for factorization over algebraic function fields. More...

Go to the source code of this file.

Functions
CFFList	append (const CFFList &Inputlist, const CFFactor &TheFactor)
CFFList	merge (const CFFList &Inputlist1, const CFFList &Inputlist2)
Varlist	varsInAs (const Varlist &uord, const CFList &As)
int	hasVar (const CanonicalForm &f, const Variable &v)
int	hasAlgVar (const CanonicalForm &f)
CanonicalForm	generateMipo (int degOfExt)
CanonicalForm	alg_lc (const CanonicalForm &f)
CanonicalForm	alg_LC (const CanonicalForm &f, int lev)
void	deflateDegree (const CanonicalForm &F, int &pExp, int n)
CanonicalForm	deflatePoly (const CanonicalForm &F, int exps, int n)
CanonicalForm	inflatePoly (const CanonicalForm &F, int exps, int n)
void	multiplicity (CFFList &factors, const CanonicalForm &F, const CFList &as)
CanonicalForm	backSubst (const CanonicalForm &F, const CFList &a, const CFList &b)
CanonicalForm	subst (const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
CanonicalForm	divide (const CanonicalForm &ff, const CanonicalForm &f, const CFList &as)
CanonicalForm	QuasiInverse (const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm	evaluate (const CanonicalForm &f, const CanonicalForm &g, const CanonicalForm &h, const CanonicalForm &powH, const Variable &v)
	evaluate f at g/h at v such that powH*f is integral i.e. powH is assumed to be h^degree(f,v) More...
int	getDegOfExt (IntList &degreelist, int n)
bool	isInseparable (const CFList &Astar)

Detailed Description

Utility functions for factorization over algebraic function fields.

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.

Author

Martin Lee

Definition in file facAlgFuncUtil.h.

Function Documentation

CanonicalForm alg_lc

(

const CanonicalForm &

f

)

Definition at line 100 of file facAlgFuncUtil.cc.

{
  if (f.level()>0)
  {
    return alg_lc(f.LC());
  }

  return f;
}

CanonicalForm alg_LC	(	const CanonicalForm &	f,
		int	lev
	)

Definition at line 110 of file facAlgFuncUtil.cc.

{
  CanonicalForm result= f;
  while (result.level() > lev)
    result= LC (result);
  return result;
}

CFFList append	(	const CFFList &	Inputlist,
		const CFFactor &	TheFactor
	)

Definition at line 32 of file facAlgFuncUtil.cc.

{
  CFFList Outputlist;
  CFFactor copy;
  CFFListIterator i;
  int exp=0;

  for (i= Inputlist; i.hasItem() ; i++)
  {
    copy= i.getItem();
    if (copy.factor() == TheFactor.factor())
      exp += copy.exp();
    else
      Outputlist.append(copy);
  }
  Outputlist.append (CFFactor (TheFactor.factor(), exp + TheFactor.exp()));
  return Outputlist;
}

CanonicalForm backSubst	(	const CanonicalForm &	F,
		const CFList &	a,
		const CFList &	b
	)

Definition at line 192 of file facAlgFuncUtil.cc.

{
  ASSERT (a.length() == b.length() - 1, "wrong length of lists in backSubst");
  CanonicalForm result= F;
  Variable tmp;
  CFList tmp2= b;
  tmp= tmp2.getLast().mvar();
  tmp2.removeLast();
  for (CFListIterator iter= a; iter.hasItem(); iter++)
  {
    result= result (tmp+iter.getItem()*tmp2.getLast().mvar(), tmp);
    tmp= tmp2.getLast().mvar();
    tmp2.removeLast();
  }
  return result;
}

void deflateDegree	(	const CanonicalForm &	F,
		int &	pExp,
		int	n
	)

Definition at line 209 of file facAlgFuncUtil.cc.

{
  if (n == 0 || n > F.level())
  {
    pExp= -1;
    return;
  }
  if (F.level() == n)
  {
    ASSERT (F.deriv().isZero(), "derivative of F is not zero");
    int termCount=0;
    CFIterator i= F;
    for (; i.hasTerms(); i++)
    {
      if (i.exp() != 0)
        termCount++;
    }

    int j= 1;
    i= F;
    for (;j < termCount; j++, i++)
      ;

    int exp= i.exp();
    int count= 0;
    int p= getCharacteristic();
    while ((exp >= p) && (exp != 0) && (exp % p == 0))
    {
      exp /= p;
      count++;
    }
    pExp= count;
  }
  else
  {
    CFIterator i= F;
    deflateDegree (i.coeff(), pExp, n);
    i++;
    int tmp= pExp;
    for (; i.hasTerms(); i++)
    {
      deflateDegree (i.coeff(), pExp, n);
      if (tmp == -1)
        tmp= pExp;
      else if (tmp != -1 && pExp != -1)
        pExp= (pExp < tmp) ? pExp : tmp;
      else
        pExp= tmp;
    }
  }
}

CanonicalForm deflatePoly	(	const CanonicalForm &	F,
		int	exps,
		int	n
	)

Definition at line 274 of file facAlgFuncUtil.cc.

{
  if (n == 0 || exps <= 0 || F.level() < n)
    return F;
  if (F.level() == n)
    return deflatePoly (F, exps);
  else
  {
    CanonicalForm result= 0;
    for (CFIterator i= F; i.hasTerms(); i++)
      result += deflatePoly (i.coeff(), exps, n)*power(F.mvar(), i.exp());
    return result;
  }
}

CanonicalForm divide	(	const CanonicalForm &	ff,
		const CanonicalForm &	f,
		const CFList &	as
	)

Definition at line 523 of file facAlgFuncUtil.cc.

{
  CanonicalForm r, m, q;

  if (f.inCoeffDomain())
  {
    bool isRat= isOn(SW_RATIONAL);
    if (getCharacteristic() == 0)
      On(SW_RATIONAL);
    q= ff/f;
    if (!isRat && getCharacteristic() == 0)
      Off(SW_RATIONAL);
  }
  else
    r= Sprem (ff, f, m, q);

  r= Prem (q, as);
  return r;
}

CanonicalForm evaluate	(	const CanonicalForm &	f,
		const CanonicalForm &	g,
		const CanonicalForm &	h,
		const CanonicalForm &	powH,
		const Variable &	v
	)

evaluate f at g/h at v such that powH*f is integral i.e. powH is assumed to be h^degree(f,v)

Definition at line 700 of file facAlgFuncUtil.cc.

{
  if (f.inCoeffDomain())
  {
    return f*powH;
  }

  Variable x = f.mvar();
  if ( v > x )
    return f*powH;
  else  if ( v == x )
    return evaluate (f, g, h, powH);

  // v is less than main variable of f
  CanonicalForm result= 0;
  for (CFIterator i= f; i.hasTerms(); i++)
    result += evaluate (i.coeff(), g, h, powH, v)*power (x, i.exp());
  return result;
}

CanonicalForm generateMipo

(

int

degOfExt

)

Definition at line 90 of file facAlgFuncUtil.cc.

{
#ifndef HAVE_NTL
  FFRandom gen;
  return find_irreducible (degOfExt, gen, Variable (1));
#else
  return randomIrredpoly (degOfExt, Variable (1));
#endif
}

int getDegOfExt	(	IntList &	degreelist,
		int	n
	)

Definition at line 566 of file facAlgFuncUtil.cc.

{
  int charac= getCharacteristic();
  setCharacteristic(0); // need it for k !
  int k= 1, m= 1, length= degreelist.length();
  IntListIterator i;

  for (i= degreelist; i.hasItem(); i++)
     m= m*i.getItem();
  int q= charac;
  while (q <= ((n*m)*(n*m)/2))
  {
    k= k+1;
    q= q*charac;
  }
  int l= 0;
  do
  {
    for (i= degreelist; i.hasItem(); i++)
    {
      l= l + 1;
      if (igcd (k, i.getItem()) == 1)
      {
        if (l == length)
        {
          setCharacteristic (charac);
          return k;
        }
      }
      else
        break;
    }
    k= k + 1;
    l= 0;
  }
  while (1);
}

int hasAlgVar

(

const CanonicalForm &

f

)

Definition at line 393 of file facAlgFuncUtil.cc.

{
  if (f.inBaseDomain())
    return 0;
  if (f.inCoeffDomain())
  {
    if (f.level() != 0)
      return 1;
    return hasAlgVar(f.LC());
  }
  if (f.inPolyDomain())
  {
    if (hasAlgVar(f.LC()))
      return 1;
    for (CFIterator i= f; i.hasTerms(); i++)
    {
      if (hasAlgVar (i.coeff()))
        return 1;
    }
  }
  return 0;
}

int hasVar	(	const CanonicalForm &	f,
		const Variable &	v
	)

Definition at line 368 of file facAlgFuncUtil.cc.

{
  if (f.inBaseDomain())
    return 0;
  if (f.inCoeffDomain())
  {
    if (f.mvar() == v)
      return 1;
    return hasAlgVar (f.LC(), v);
  }
  if (f.inPolyDomain())
  {
    if (f.mvar() == v)
      return 1;
    if (hasVar (f.LC(), v))
      return 1;
    for (CFIterator i= f; i.hasTerms(); i++)
    {
      if (hasVar (i.coeff(), v))
        return 1;
    }
  }
  return 0;
}

CanonicalForm inflatePoly	(	const CanonicalForm &	F,
		int	exps,
		int	n
	)

Definition at line 302 of file facAlgFuncUtil.cc.

{
  if (n == 0 || exps <= 0 || F.level() < n)
    return F;
  if (F.level() == n)
    return inflatePoly (F, exps);
  else
  {
    CanonicalForm result= 0;
    for (CFIterator i= F; i.hasTerms(); i++)
      result += inflatePoly (i.coeff(), exps, n)*power(F.mvar(), i.exp());
    return result;
  }
}

bool isInseparable

(

const CFList &

Astar

)

Definition at line 545 of file facAlgFuncUtil.cc.

{
  CanonicalForm elem;

  if (Astar.length() == 0)
    return false;
  for (CFListIterator i= Astar; i.hasItem(); i++)
  {
    elem= i.getItem();
    if (elem.deriv().isZero())
      return true;
  }
  return false;
}

CFFList merge	(	const CFFList &	Inputlist1,
		const CFFList &	Inputlist2
	)

Definition at line 52 of file facAlgFuncUtil.cc.

{
  CFFList Outputlist;
  CFFListIterator i;

  for (i= Inputlist1; i.hasItem(); i++)
    Outputlist= append (Outputlist, i.getItem());
  for (i= Inputlist2; i.hasItem() ; i++)
    Outputlist= append (Outputlist, i.getItem());

  return Outputlist;
}

void multiplicity	(	CFFList &	factors,
		const CanonicalForm &	F,
		const CFList &	as
	)

Definition at line 318 of file facAlgFuncUtil.cc.

{
  CanonicalForm G= F;
  Variable x= F.mvar();
  CanonicalForm q, r;
  int count= -1;
  for (CFFListIterator iter=factors; iter.hasItem(); iter++)
  {
    count= -1;
    if (iter.getItem().factor().inCoeffDomain())
      continue;
    while (1)
    {
      psqr (G, iter.getItem().factor(), q, r, x);

      q= Prem (q, as);
      r= Prem (r, as);
      if (!r.isZero())
        break;
      count++;
      G= q;
    }
    iter.getItem()= CFFactor (iter.getItem().factor(),
                              iter.getItem().exp() + count);
  }
}

CanonicalForm QuasiInverse	(	const CanonicalForm &	f,
		const CanonicalForm &	g,
		const Variable &	x
	)

Definition at line 605 of file facAlgFuncUtil.cc.

{
  CanonicalForm pi, pi1, q, t0, t1, Hi, bi, pi2;
  bool isRat= isOn (SW_RATIONAL);
  pi= f;
  pi1= g;
  if (isRat)
  {
    pi *= bCommonDen (pi);
    pi1 *= bCommonDen (pi1);
  }
  CanonicalForm m,tmp;
  if (isRat && getCharacteristic() == 0)
    Off (SW_RATIONAL);

  pi= pi/content (pi,x);
  pi1= pi1/content (pi1,x);

  t0= 0;
  t1= 1;
  bi= 1;

  int delta= degree (f, x) - degree (g, x);
  Hi= power (LC (pi1, x), delta);
  if ( (delta+1) % 2 )
      bi = 1;
  else
      bi = -1;

  while (degree (pi1,x) > 0)
  {
    psqr (pi, pi1, q, pi2, m, x);
    pi2 /= bi;

    tmp= t1;
    t1= t0*m - t1*q;
    t0= tmp;
    t1 /= bi;
    pi= pi1;
    pi1= pi2;
    if (degree (pi1, x) > 0)
    {
      delta= degree (pi, x) - degree (pi1, x);
      if ((delta + 1) % 2)
        bi= LC (pi, x)*power (Hi, delta);
      else
        bi= -LC (pi, x)*power (Hi, delta);
      Hi= power (LC (pi1, x), delta)/power (Hi, delta - 1);
    }
  }
  t1 /= gcd (pi1, t1);
  if (isRat && getCharacteristic() == 0)
    On (SW_RATIONAL);
  return t1;
}

CanonicalForm subst	(	const CanonicalForm &	f,
		const CFList &	a,
		const CFList &	b,
		const CanonicalForm &	Rstar,
		bool	isFunctionField
	)

Definition at line 120 of file facAlgFuncUtil.cc.

{
  if (isFunctionField)
    ASSERT (2*a.length() == b.length(), "wrong length of lists");
  else
    ASSERT (a.length() == b.length(), "lists of equal length expected");
  CFListIterator j= b;
  CanonicalForm result= f, tmp, powj;
  CFListIterator i= a;
  int length= a.length();
  int count= 0;
  for (; i.hasItem() && j.hasItem(); i++, j++, count++)
  {
    if (length - count == 2)
    {
      if (!isFunctionField)
      {
        result= result (b.getLast(), a.getLast().mvar());
        result= result (j.getItem(), i.getItem().mvar());
        break;
      }
      else
      {
        tmp= b.getLast();
        j++;
        j++;
        powj= power (tmp, degree (result, a.getLast().mvar()));
        result= evaluate (result, j.getItem(), tmp, powj, a.getLast().mvar());

        if (fdivides (powj, result, tmp))
          result= tmp;

        result /= vcontent (result, Variable (a.getLast().level() + 1));
        j--;
        j--;
        tmp= j.getItem();
        j++;
        powj= power (j.getItem(), degree (result, i.getItem().mvar()));
        result= evaluate (result, tmp, j.getItem(), powj, i.getItem().mvar());

        if (fdivides (powj, result, tmp))
          result= tmp;

        result /= vcontent (result, Variable (i.getItem().level() + 1));
        break;
      }
    }
    else
    {
      if (!isFunctionField)
        result= result (j.getItem(), i.getItem().mvar());
      else
      {
        tmp= j.getItem();
        j++;
        powj= power (j.getItem(), degree (result, i.getItem().mvar()));
        result= evaluate (result, tmp, j.getItem(), powj, i.getItem().mvar());

        if (fdivides (powj, result, tmp))
          result= tmp;

        result /= vcontent (result, Variable (i.getItem().level() + 1));
      }
    }
  }
  result= Prem (result, CFList (Rstar));
  result /= vcontent (result, Variable (Rstar.level() + 1));
  return result;
}

Varlist varsInAs	(	const Varlist &	uord,
		const CFList &	As
	)

Definition at line 66 of file facAlgFuncUtil.cc.

{
  Varlist output;
  CanonicalForm elem;
  Variable x;

  for (VarlistIterator i= uord; i.hasItem(); i++)
  {
    x= i.getItem();
    for (CFListIterator j= Astar; j.hasItem(); j++ )
    {
      elem= j.getItem();
      if (degree (elem, x) > 0) // x actually occures in Astar
      {
        output.append (x);
        break;
      }
    }
  }
  return output;
}