facAlgFunc.h File Reference

Factorization over algebraic function fields. More...

#include "canonicalform.h"

Go to the source code of this file.

Functions
CanonicalForm	alg_gcd (const CanonicalForm &, const CanonicalForm &, const CFList &)
CFFList	facAlgFunc2 (const CanonicalForm &f, const CFList &as)
	factorize a polynomial f that is irreducible over the ground field modulo an extension given by an irreducible characteristic set as, f is assumed to be integral, i.e. , and each element of as is assumed to be integral as well. must be either or . More...
CFFList	facAlgFunc (const CanonicalForm &f, const CFList &as)
	factorize a polynomial f modulo an extension given by an irreducible characteristic set as, f is assumed to be integral, i.e. , and each element of as is assumed to be integral as well. must be either or . More...

Detailed Description

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 facAlgFunc.h.

Function Documentation

alg_gcd()

CanonicalForm alg_gcd	(	const CanonicalForm &	fff,
		const CanonicalForm &	ggg,
		const CFList &	as
	)

Definition at line 61 of file facAlgFunc.cc.

{
  if (fff.inCoeffDomain() || ggg.inCoeffDomain())
    return 1;
  CanonicalForm f=fff;
  CanonicalForm g=ggg;
  f=Prem(f,as);
  g=Prem(g,as);
  if ( f.isZero() )
  {
    if ( g.lc().sign() < 0 ) return -g;
    else                     return g;
  }
  else  if ( g.isZero() )
  {
    if ( f.lc().sign() < 0 ) return -f;
    else                     return f;
  }
 
  int v= as.getLast().level();
  if (f.level() <= v || g.level() <= v)
    return 1;
 
  CanonicalForm res;
 
  // does as appear in f and g ?
  bool has_alg_var=false;
  for ( CFListIterator j=as;j.hasItem(); j++ )
  {
    Variable v=j.getItem().mvar();
    if (hasVar (f, v))
      has_alg_var=true;
    if (hasVar (g, v))
      has_alg_var=true;
  }
  if (!has_alg_var)
  {
    /*if ((hasAlgVar(f))
    || (hasAlgVar(g)))
    {
      Varlist ord;
      for ( CFListIterator j=as;j.hasItem(); j++ )
        ord.append(j.getItem().mvar());
      res=algcd(f,g,as,ord);
    }
    else*/
    if (!hasAlgVar (f) && !hasAlgVar (g))
      return res=gcd(f,g);
  }
 
  int mvf=f.level();
  int mvg=g.level();
  if (mvg > mvf)
  {
    CanonicalForm tmp=f; f=g; g=tmp;
    int tmp2=mvf; mvf=mvg; mvg=tmp2;
  }
  if (g.inBaseDomain() || f.inBaseDomain())
    return CanonicalForm(1);
 
  CanonicalForm c_f= alg_content (f, as);
 
  if (mvf != mvg)
  {
    res= alg_gcd (g, c_f, as);
    return res;
  }
  Variable x= f.mvar();
 
  // now: mvf==mvg, f.level()==g.level()
  CanonicalForm c_g= alg_content (g, as);
 
  int delta= degree (f) - degree (g);
 
  f= divide (f, c_f, as);
  g= divide (g, c_g, as);
 
  // gcd of contents
  CanonicalForm c_gcd= alg_gcd (c_f, c_g, as);
  CanonicalForm tmp;
 
  if (delta < 0)
  {
    tmp= f;
    f= g;
    g= tmp;
    delta= -delta;
  }
 
  CanonicalForm r= 1;
 
  while (degree (g, x) > 0)
  {
    r= Prem (f, g);
    r= Prem (r, as);
    if (!r.isZero())
    {
      r= divide (r, alg_content (r,as), as);
      r /= vcontent (r,Variable (v+1));
    }
    f= g;
    g= r;
  }
 
  if (degree (g, x) == 0)
    return c_gcd;
 
  c_f= alg_content (f, as);
 
  f= divide (f, c_f, as);
 
  f *= c_gcd;
  f /= vcontent (f, Variable (v+1));
 
  return f;
}

facAlgFunc()

CFFList facAlgFunc	(	const CanonicalForm &	f,
		const CFList &	as
	)

factorize a polynomial f modulo an extension given by an irreducible characteristic set as, f is assumed to be integral, i.e. , and each element of as is assumed to be integral as well. must be either or .

Returns

the returned factors are not necessarily monic but only primitive and the product of the factors equals f up to a unit.

factorize a polynomial f modulo an extension given by an irreducible characteristic set as, f is assumed to be integral, i.e. , and each element of as is assumed to be integral as well. must be either or .

Parameters

[in]	f	univariate poly
[in]	as	irreducible characteristic set

Definition at line 1043 of file facAlgFunc.cc.

{
  bool isRat= isOn (SW_RATIONAL);
  if (!isRat && getCharacteristic() == 0)
    On (SW_RATIONAL);
  CFFList Output, output, Factors= factorize(f);
  if (Factors.getFirst().factor().inCoeffDomain())
    Factors.removeFirst();
 
  if (as.length() == 0)
  {
    if (!isRat && getCharacteristic() == 0)
      Off (SW_RATIONAL);
    return Factors;
  }
  if (f.level() <= as.getLast().level())
  {
    if (!isRat && getCharacteristic() == 0)
      Off (SW_RATIONAL);
    return Factors;
  }
 
  for (CFFListIterator i=Factors; i.hasItem(); i++)
  {
    if (i.getItem().factor().level() > as.getLast().level())
    {
      output= facAlgFunc2 (i.getItem().factor(), as);
      for (CFFListIterator j= output; j.hasItem(); j++)
        Output= append (Output, CFFactor (j.getItem().factor(),
                                          j.getItem().exp()*i.getItem().exp()));
    }
  }
 
  if (!isRat && getCharacteristic() == 0)
    Off (SW_RATIONAL);
  return Output;
}

facAlgFunc2()

CFFList facAlgFunc2	(	const CanonicalForm &	f,
		const CFList &	as
	)

factorize a polynomial f that is irreducible over the ground field modulo an extension given by an irreducible characteristic set as, f is assumed to be integral, i.e. , and each element of as is assumed to be integral as well. must be either or .

Returns

the returned factors are not necessarily monic but only primitive and the product of the factors equals f up to a unit.

factorize a polynomial f that is irreducible over the ground field modulo an extension given by an irreducible characteristic set as, f is assumed to be integral, i.e. , and each element of as is assumed to be integral as well. must be either or .

Parameters

[in]	f	univariate poly
[in]	as	irreducible characteristic set

Definition at line 905 of file facAlgFunc.cc.

{
  bool isRat= isOn (SW_RATIONAL);
  if (!isRat && getCharacteristic() == 0)
    On (SW_RATIONAL);
  Variable vf=f.mvar();
  CFListIterator i;
  CFFListIterator jj;
  CFList reduceresult;
  CFFList result;
 
// F1: [Test trivial cases]
// 1) first trivial cases:
  if (vf.level() <= as.getLast().level())
  {
    if (!isRat && getCharacteristic() == 0)
      Off (SW_RATIONAL);
    return CFFList(CFFactor(f,1));
  }
 
// 2) Setup list of those polys in AS having degree > 1
  CFList Astar;
  Variable x;
  CanonicalForm elem;
  Varlist ord, uord;
  for (int ii= 1; ii < level (vf); ii++)
    uord.append (Variable (ii));
 
  for (i= as; i.hasItem(); i++)
  {
    elem= i.getItem();
    x= elem.mvar();
    if (degree (elem, x) > 1)  // otherwise it's not an extension
    {
      Astar.append (elem);
      ord.append (x);
    }
  }
  uord= Difference (uord, ord);
 
// 3) second trivial cases: we already proved irr. of f over no extensions
  if (Astar.length() == 0)
  {
    if (!isRat && getCharacteristic() == 0)
      Off (SW_RATIONAL);
    return CFFList (CFFactor (f, 1));
  }
 
// 4) Look if elements in uord actually occur in any of the minimal
//    polynomials. If no element of uord occures in any of the minimal
//    polynomials the field is an alg. number field not an alg. function field
  Varlist newuord= varsInAs (uord, Astar);
 
  CFFList Factorlist;
  Varlist gcdord= Union (ord, newuord);
  gcdord.append (f.mvar());
  bool isFunctionField= (newuord.length() > 0);
 
  // TODO alg_sqrfree?
  CanonicalForm Fgcd= 0;
  if (isFunctionField)
    Fgcd= alg_gcd (f, f.deriv(), Astar);
 
  bool derivZero= f.deriv().isZero();
  if (isFunctionField && (degree (Fgcd, f.mvar()) > 0) && !derivZero)
  {
    CanonicalForm Ggcd= divide(f, Fgcd,Astar);
    if (getCharacteristic() == 0)
    {
      CFFList result= facAlgFunc2 (Ggcd, as); //Ggcd is the squarefree part of f
      multiplicity (result, f, Astar);
      if (!isRat && getCharacteristic() == 0)
        Off (SW_RATIONAL);
      return result;
    }
 
    Fgcd= pp (Fgcd);
    Ggcd= pp (Ggcd);
    if (!isRat && getCharacteristic() == 0)
      Off (SW_RATIONAL);
    return merge (facAlgFunc2 (Fgcd, as), facAlgFunc2 (Ggcd, as));
  }
 
  if (getCharacteristic() > 0)
  {
    IntList degreelist;
    Variable vminpoly;
    for (i= Astar; i.hasItem(); i++)
      degreelist.append (degree (i.getItem()));
 
    int extdeg= getDegOfExt (degreelist, degree (f));
 
    if (newuord.length() == 0) // no parameters
    {
      if (extdeg > 1)
      {
        CanonicalForm MIPO= generateMipo (extdeg);
        vminpoly= rootOf(MIPO);
      }
      Factorlist= Trager(f, Astar, vminpoly, as, isFunctionField);
      if (extdeg > 1)
        prune (vminpoly);
      return Factorlist;
    }
    else if (isInseparable(Astar) || derivZero) // inseparable case
    {
      Factorlist= SteelTrager (f, Astar);
      return Factorlist;
    }
    else // separable case
    {
      if (extdeg > 1)
      {
        CanonicalForm MIPO=generateMipo (extdeg);
        vminpoly= rootOf (MIPO);
      }
      Factorlist= Trager (f, Astar, vminpoly, as, isFunctionField);
      if (extdeg > 1)
        prune (vminpoly);
      return Factorlist;
    }
  }
  else // char 0
  {
    Variable vminpoly;
    Factorlist= Trager (f, Astar, vminpoly, as, isFunctionField);
    if (!isRat && getCharacteristic() == 0)
      Off (SW_RATIONAL);
    return Factorlist;
  }
 
  return CFFList (CFFactor(f,1));
}