facFqFactorizeUtil.cc File Reference

This file provides utility functions for multivariate factorization. More...

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

Go to the source code of this file.

Functions
static void	appendSwap (CFList &factors1, const CFList &factors2, const int swapLevel1, const int swapLevel2, const Variable &x)
void	swap (CFList &factors, const int swapLevel1, const int swapLevel2, const Variable &x)
	swap elements in factors More...
void	appendSwapDecompress (CFList &factors1, const CFList &factors2, const CFMap &N, const int swapLevel, const Variable &x)
	swap elements of factors2, append them to factors1 and decompress More...
void	appendSwapDecompress (CFList &factors1, const CFList &factors2, const CFMap &N, const int swapLevel1, const int swapLevel2, const Variable &x)
	swap elements of factors2, append them to factors1 and decompress More...
int *	liftingBounds (const CanonicalForm &A, const int &bivarLiftBound)
	compute lifting bounds More...
CanonicalForm	shift2Zero (const CanonicalForm &F, CFList &Feval, const CFList &evaluation, int l)
	shift evaluation point to zero More...
CanonicalForm	reverseShift (const CanonicalForm &F, const CFList &evaluation, int l)
	reverse shifting the evaluation point to zero More...
bool	isOnlyLeadingCoeff (const CanonicalForm &F)
	check if F consists of more than just the leading coeff wrt. Variable (1) More...
CanonicalForm	myGetVars (const CanonicalForm &F)
	like getVars but including multiplicities More...
int	compareByNumberOfVars (const CFFactor &F, const CFFactor &G)
CFFList	sortCFFListByNumOfVars (CFFList &F)
	sort CFFList by the number variables in a factor More...
CFList	evaluateAtZero (const CanonicalForm &F)
	evaluate F successively n-2 at 0 More...
CFList	evaluateAtEval (const CanonicalForm &F, const CFArray &eval)
	evaluate F at evaluation More...
CFList	evaluateAtEval (const CanonicalForm &F, const CFList &evaluation, int l)
	evaluate F at evaluation More...
CFList	recoverFactors (const CanonicalForm &F, const CFList &factors)
	divides factors by their content wrt. Variable(1) and checks if these polys divide F More...
CFList	recoverFactors (const CanonicalForm &F, const CFList &factors, const CFList &evaluation)
	divides factors shifted by evaluation by their content wrt. Variable(1) and checks if these polys divide F More...
CFList	recoverFactors (CanonicalForm &F, const CFList &factors, int *index)
	checks if factors divide F, if so F is divided by this factor and the factor is divided by its content wrt. Variable(1) and the entry in index at the position of the factor is set to 1, otherwise the entry in index is set to 0 More...

Detailed Description

This file provides utility functions for multivariate factorization.

Author

Martin Lee

Definition in file facFqFactorizeUtil.cc.

Function Documentation

appendSwap()

static void appendSwap ( CFList &  factors1, const CFList &  factors2, const int  swapLevel1, const int  swapLevel2, const Variable &  x  )

inlinestatic

Definition at line 22 of file facFqFactorizeUtil.cc.

{
  for (CFListIterator i= factors2; i.hasItem(); i++)
  {
    if (swapLevel1)
    {
      if (swapLevel2)
        factors1.append (swapvar (swapvar (i.getItem(), x,
                         Variable (swapLevel2)), Variable (swapLevel1), x));
      else
        factors1.append (swapvar (i.getItem(), Variable (swapLevel1), x));
    }
    else
    {
      if (swapLevel2)
        factors1.append (swapvar (i.getItem(), x, Variable (swapLevel2)));
      else
        factors1.append (i.getItem());
    }
  }
  return;
}

appendSwapDecompress() [1/2]

void appendSwapDecompress	(	CFList &	factors1,
		const CFList &	factors2,
		const CFMap &	N,
		const int	swapLevel,
		const Variable &	x
	)

swap elements of factors2, append them to factors1 and decompress

Parameters

[in,out]	factors1	a list of polys, returns swapped elements of factors2 appended to it and everything is decompressed
[in]	factors2	a list of polys
[in]	N	a map
[in]	swapLevel	level of variable to be swapped with x, 0 if no swapping
[in]	x	a variable

Definition at line 69 of file facFqFactorizeUtil.cc.

{
  for (CFListIterator i= factors1; i.hasItem(); i++)
  {
    if (swapLevel)
      i.getItem()= swapvar (i.getItem(), Variable (swapLevel), x);
    i.getItem()= N(i.getItem());
  }
  for (CFListIterator i= factors2; i.hasItem(); i++)
  {
    if (!i.getItem().inCoeffDomain())
      factors1.append (N (i.getItem()));
  }
  return;
}

appendSwapDecompress() [2/2]

void appendSwapDecompress	(	CFList &	factors1,
		const CFList &	factors2,
		const CFMap &	N,
		const int	swapLevel1,
		const int	swapLevel2,
		const Variable &	x
	)

swap elements of factors2, append them to factors1 and decompress

Parameters

[in,out]	factors1	a list of polys, returns swapped elements of factors2 appended to it and everything is decompressed
[in]	factors2	a list of polys
[in]	N	a map
[in]	swapLevel1	level of variable to be swapped with x, 0 if no swapping
[in]	swapLevel2	level of variable to be swapped with x, 0 if no swapping
[in]	x	a variable

Definition at line 87 of file facFqFactorizeUtil.cc.

{
  for (CFListIterator i= factors1; i.hasItem(); i++)
  {
    if (swapLevel1)
    {
      if (swapLevel2)
        i.getItem()=
        N (swapvar (swapvar (i.getItem(), Variable (swapLevel2), x), x,
                    Variable (swapLevel1)));
      else
        i.getItem()= N (swapvar (i.getItem(), x, Variable (swapLevel1)));
    }
    else
    {
      if (swapLevel2)
        i.getItem()= N (swapvar (i.getItem(), Variable (swapLevel2), x));
      else
        i.getItem()= N (i.getItem());
    }
  }
  for (CFListIterator i= factors2; i.hasItem(); i++)
  {
    if (!i.getItem().inCoeffDomain())
      factors1.append (N (i.getItem()));
  }
  return;
}

compareByNumberOfVars()

int compareByNumberOfVars	(	const CFFactor &	F,
		const CFFactor &	G
	)

Definition at line 180 of file facFqFactorizeUtil.cc.

{
  return getNumVars (F.factor()) < getNumVars (G.factor());
}

evaluateAtEval() [1/2]

CFList evaluateAtEval	(	const CanonicalForm &	F,
		const CFArray &	evaluation
	)

evaluate F at evaluation

Returns

evaluateAtEval returns a list containing the successive evaluations of F, last entry is F again

Parameters

[in]	F	some poly
[in]	eval	some evaluation point

Definition at line 206 of file facFqFactorizeUtil.cc.

{
  CFList result;
  CanonicalForm buf= F;
  result.insert (buf);
  int k= eval.size();
  for (int i= 1; i < k; i++)
  {
    buf= buf (eval[i], i + 2);
    result.insert (buf);
  }
  return result;
}

evaluateAtEval() [2/2]

CFList evaluateAtEval	(	const CanonicalForm &	F,
		const CFList &	evaluation,
		int	l
	)

evaluate F at evaluation

Returns

evaluateAtEval returns a list containing the successive evaluations of F starting at level l, last entry is F again

Parameters

[in]	F	some poly
[in]	evaluation	some evaluation point
[in]	l	level to start at

Definition at line 220 of file facFqFactorizeUtil.cc.

{
  CFList result;
  CanonicalForm buf= F;
  result.insert (buf);
  int k= evaluation.length() + l - 1;
  CFListIterator j= evaluation;
  for (int i= k; j.hasItem() && i > l; i--, j++)
  {
    if (F.level() < i)
      continue;
    buf= buf (j.getItem(), i);
    result.insert (buf);
  }
  return result;
}

evaluateAtZero()

CFList evaluateAtZero

(

const CanonicalForm &

F

)

evaluate F successively n-2 at 0

Returns

returns a list of successive evaluations of F, ending with F

Parameters

[in]

F

some poly

Definition at line 193 of file facFqFactorizeUtil.cc.

{
  CFList result;
  CanonicalForm buf= F;
  result.insert (buf);
  for (int i= F.level(); i > 2; i--)
  {
    buf= buf (0, i);
    result.insert (buf);
  }
  return result;
}

isOnlyLeadingCoeff()

bool isOnlyLeadingCoeff

(

const CanonicalForm &

F

)

check if F consists of more than just the leading coeff wrt. Variable (1)

Returns

as described above

Parameters

[in]

F

some poly

Definition at line 162 of file facFqFactorizeUtil.cc.

{
  return (F-LC (F,1)*power (Variable(1),degree (F,1))).isZero();
}

liftingBounds()

int * liftingBounds	(	const CanonicalForm &	A,
		const int &	bivarLiftBound
	)

compute lifting bounds

Returns

liftingBounds returns an array containing the lift bounds for A

Parameters

[in]	A	a compressed poly
[in]	bivarLiftBound	lift bound for biFactorizer()

Definition at line 118 of file facFqFactorizeUtil.cc.

{
  int j= A.level() - 1;
  int* liftBounds= new int [j];
  liftBounds[0]= bivarLiftBound;
  for (int i= 1; i < j; i++)
  {
    liftBounds[i]= degree (A, Variable (i + 2)) + 1 +
                            degree (LC (A, 1), Variable (i + 2));
  }
  return liftBounds;
}

myGetVars()

CanonicalForm myGetVars

(

const CanonicalForm &

F

)

like getVars but including multiplicities

like getVars but each variable x occuring in F is raised to x^degree (F,x)

Parameters

[in]

F

a polynomial

Definition at line 168 of file facFqFactorizeUtil.cc.

{
  CanonicalForm result= 1;
  int deg;
  for (int i= 1; i <= F.level(); i++)
  {
    if ((deg= degree (F, i)) > 0)
      result *= power (Variable (i), deg);
  }
  return result;
}

recoverFactors() [1/3]

CFList recoverFactors	(	CanonicalForm &	F,
		const CFList &	factors,
		int *	index
	)

checks if factors divide F, if so F is divided by this factor and the factor is divided by its content wrt. Variable(1) and the entry in index at the position of the factor is set to 1, otherwise the entry in index is set to 0

Returns

returns factors of F

Parameters

[in,out]	F	some poly F
[in]	factors	some list of factor candidates
[in]	index	position of real factors

Definition at line 278 of file facFqFactorizeUtil.cc.

{
  CFList result;
  CanonicalForm tmp, tmp2;
  CanonicalForm G= F;
  int j= 0;
  for (CFListIterator i= factors; i.hasItem(); i++, j++)
  {
    if (i.getItem().isZero())
    {
      index[j]= 0;
      continue;
    }
    tmp= i.getItem();
    if (fdivides (tmp, G, tmp2))
    {
      G= tmp2;
      tmp /=content (tmp, 1);
      result.append (tmp);
      index[j]= 1;
    }
    else
      index[j]= 0;
  }
  if (result.length() + 1 == factors.length())
  {
    result.append (G/content (G,1));
    F= G/content (G,1);
  }
  else
    F= G;
  return result;
}

recoverFactors() [2/3]

CFList recoverFactors	(	const CanonicalForm &	F,
		const CFList &	factors
	)

divides factors by their content wrt. Variable(1) and checks if these polys divide F

Returns

returns factors of F

Parameters

[in]	F	some poly F
[in]	factors	some list of factor candidates

Definition at line 238 of file facFqFactorizeUtil.cc.

{
  CFList result;
  CanonicalForm tmp, tmp2;
  CanonicalForm G= F;
  for (CFListIterator i= factors; i.hasItem(); i++)
  {
    tmp= i.getItem()/content (i.getItem(), 1);
    if (fdivides (tmp, G, tmp2))
    {
      G= tmp2;
      result.append (tmp);
    }
  }
  if (result.length() + 1 == factors.length())
    result.append (G/content (G,1));
  return result;
}

recoverFactors() [3/3]

CFList recoverFactors	(	const CanonicalForm &	F,
		const CFList &	factors,
		const CFList &	evaluation
	)

divides factors shifted by evaluation by their content wrt. Variable(1) and checks if these polys divide F

Returns

returns factors of F

Parameters

[in]	F	some poly F
[in]	factors	some list of factor candidates
[in]	evaluation	evaluation point

Definition at line 257 of file facFqFactorizeUtil.cc.

{
  CFList result;
  CanonicalForm tmp, tmp2;
  CanonicalForm G= F;
  for (CFListIterator i= factors; i.hasItem(); i++)
  {
    tmp= reverseShift (i.getItem(), evaluation, 2);
    tmp /= content (tmp, 1);
    if (fdivides (tmp, G, tmp2))
    {
      G= tmp2;
      result.append (tmp);
    }
  }
  if (result.length() + 1 == factors.length())
    result.append (G/content (G,1));
  return result;
}

reverseShift()

CanonicalForm reverseShift	(	const CanonicalForm &	F,
		const CFList &	evaluation,
		int	l = 2
	)

reverse shifting the evaluation point to zero

Returns

reverseShift returns a poly whose shift to zero is reversed

See also

shift2Zero(), evalPoints()

Parameters

[in]	F	a compressed poly
[in]	evaluation	a valid evaluation point
[in]	l	level at which the evaluation starts

Definition at line 148 of file facFqFactorizeUtil.cc.

{
  int k= evaluation.length() + l - 1;
  CanonicalForm result= F;
  CFListIterator j= evaluation;
  for (int i= k; j.hasItem() && (i > l - 1); i--, j++)
  {
    if (F.level() < i)
      continue;
    result= result (Variable (i) - j.getItem(), i);
  }
  return result;
}

shift2Zero()

CanonicalForm shift2Zero	(	const CanonicalForm &	F,
		CFList &	Feval,
		const CFList &	evaluation,
		int	l = 2
	)

shift evaluation point to zero

Returns

shift2Zero returns F shifted by evaluation s.t. 0 is a valid evaluation point

See also

evalPoints(), reverseShift()

Parameters

[in]	F	a compressed poly
[in,out]	Feval	an empty list, returns F successively evaluated at 0
[in]	evaluation	a valid evaluation point
[in]	l	level at which the evaluation starts

Definition at line 131 of file facFqFactorizeUtil.cc.

{
  CanonicalForm A= F;
  int k= evaluation.length() + l - 1;
  for (CFListIterator i= evaluation; i.hasItem(); i++, k--)
    A= A (Variable (k) + i.getItem(), k);
  CanonicalForm buf= A;
  Feval= CFList();
  Feval.append (buf);
  for (k= A.level(); k > 2; k--)
  {
    buf= mod (buf, Variable (k));
    Feval.insert (buf);
  }
  return A;
}

sortCFFListByNumOfVars()

CFFList sortCFFListByNumOfVars

(

CFFList &

F

)

sort CFFList by the number variables in a factor

Parameters

[in,out]

F

a list of factors

Definition at line 186 of file facFqFactorizeUtil.cc.

{
    F.sort (compareByNumberOfVars);
    CFFList result= F;
    return result;
}

swap()

void swap	(	CFList &	factors,
		const int	swapLevel1,
		const int	swapLevel2,
		const Variable &	x
	)

swap elements in factors

Parameters

[in]	factors	a list of polys, returns swapped elements of factors
[in]	swapLevel1	level of variable to be swapped with x, 0 if no swapping
[in]	swapLevel2	level of variable to be swapped with x, 0 if no swapping
[in]	x	a variable

Definition at line 47 of file facFqFactorizeUtil.cc.

{
  for (CFListIterator i= factors; i.hasItem(); i++)
  {
    if (swapLevel1)
    {
      if (swapLevel2)
        i.getItem()= swapvar (swapvar (i.getItem(), x, Variable (swapLevel2)),
                              Variable (swapLevel1), x);
      else
        i.getItem()= swapvar (i.getItem(), Variable (swapLevel1), x);
    }
    else
    {
      if (swapLevel2)
        i.getItem()= swapvar (i.getItem(), x, Variable (swapLevel2));
    }
  }
  return;
}