Loading...
Searching...
No Matches
facFqFactorizeUtil.h File Reference

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

`#include "canonicalform.h"`
`#include "cf_map.h"`

Go to the source code of this file.

## Functions

static void | decompressAppend (CFList &factors1, const CFList &factors2, const CFMap &N)
| append factors2 to factors1 and decompress
void | appendSwap (CFList &factors1, const CFList &factors2, const int swapLevel1, const int swapLevel2, const Variable &x)
| swap elements in factors2 and append them to factors1
void | swap (CFList &factors, const int swapLevel1, const int swapLevel2, const Variable &x)
| swap elements in factors
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
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
int * | liftingBounds (const CanonicalForm &A, const int &bivarLiftBound)
| compute lifting bounds
CanonicalForm | shift2Zero (const CanonicalForm &F, CFList &Feval, const CFList &evaluation, int l=2)
| shift evaluation point to zero
CanonicalForm | reverseShift (const CanonicalForm &F, const CFList &evaluation, int l=2)
| reverse shifting the evaluation point to zero
bool | isOnlyLeadingCoeff (const CanonicalForm &F)
| check if F consists of more than just the leading coeff wrt. Variable (1)
CFFList | sortCFFListByNumOfVars (CFFList &F)
| sort CFFList by the number variables in a factor
CanonicalForm | myGetVars (const CanonicalForm &F)
| like getVars but each variable x occuring in F is raised to x^degree (F,x)
CFList | evaluateAtEval (const CanonicalForm &F, const CFArray &evaluation)
| evaluate F at evaluation
CFList | evaluateAtEval (const CanonicalForm &F, const CFList &evaluation, int l)
| evaluate F at evaluation
CFList | evaluateAtZero (const CanonicalForm &F)
| evaluate F successively n-2 at 0
CFList | recoverFactors (const CanonicalForm &F, const CFList &factors)
| divides factors by their content wrt. Variable(1) and checks if these polys divide F
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
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

## Detailed Description

This file provides utility functions for multivariate factorization.

Author
  Martin Lee

Definition in file facFqFactorizeUtil.h.

## Function Documentation

## appendSwap()

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

swap elements in factors2 and append them to factors1

Parameters

  [in,out] | factors1 | a list of polys, returns swapped elements of factors2 appended to it
  [in] | factors2 | a list of polys
  [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

## 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;
}
swapvar
CanonicalForm FACTORY_PUBLIC swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition cf_ops.cc:168
CFListIterator
ListIterator< CanonicalForm > CFListIterator
Definition canonicalform.h:396
N
const CanonicalForm CFMap CFMap & N
Definition cfEzgcd.cc:56
i
int i
Definition cfEzgcd.cc:132
x
Variable x
Definition cfModGcd.cc:4090
List::append
void append(const T &)
Definition ftmpl_list.cc:256
Variable
factory's class for variables
Definition factory.h:127
factors2
const CFList & factors2
Definition facFqBivarUtil.cc:42

## 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;
}

## decompressAppend()

void decompressAppend | ( | CFList & | factors1,
|  | const CFList & | factors2,
|  | const CFMap & | N )

inline static

append factors2 to factors1 and decompress

Parameters

  [in,out] | factors1 | a list of polys, returns factors2 appended to it and everything is decompressed
  [in] | factors2 | a list of polys
  [in] | N | a map

Definition at line 23 of file facFqFactorizeUtil.h.

{
for (CFListIterator i= factors1; i.hasItem(); i++)
i.getItem()= N (i.getItem());
for (CFListIterator i= factors2; i.hasItem(); i++)
factors1.append (N (i.getItem()));
}

## 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] | evaluation | 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;
}
CFList
List< CanonicalForm > CFList
Definition canonicalform.h:395
k
int k
Definition cfEzgcd.cc:99
CanonicalForm
factory's main class
Definition canonicalform.h:86
result
return result
Definition facAbsBiFact.cc:76
eval
CFList & eval
Definition facFactorize.cc:47
buf
int status int void * buf
Definition si_signals.h:69

## 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;
}
l
int l
Definition cfEzgcd.cc:100
CanonicalForm::level
int level() const
level() returns the level of CO.
Definition canonicalform.cc:576
evaluation
const CanonicalForm int const CFList & evaluation
Definition facAbsFact.cc:52
j
int j
Definition facHensel.cc:110

## 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();
}
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition canonicalform.cc:1896
degree
int degree(const CanonicalForm &f)
Definition canonicalform.h:316
LC
CanonicalForm LC(const CanonicalForm &f)
Definition canonicalform.h:310

## 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;
}
A
#define A
Definition sirandom.c:24

## myGetVars()

CanonicalForm myGetVars | ( | const CanonicalForm & | F | ) |

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

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;
}
content
CanonicalForm FACTORY_PUBLIC content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f ).
Definition cf_gcd.cc:603
fdivides
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
List::length
int length() const
Definition ftmpl_list.cc:273
tmp2
CFList tmp2
Definition facFqBivar.cc:75
G
STATIC_VAR TreeM * G
Definition janet.cc:31
index
static int index(p_Length length, p_Ord ord)
Definition p_Procs_Impl.h:592

## 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)
reverse shifting the evaluation point to zero
Definition facFqFactorizeUtil.cc:148

## 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;
}
mod
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
Feval
CanonicalForm Feval
Definition facAbsFact.cc:60

## 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;
}
CFFList
List< CFFactor > CFFList
Definition canonicalform.h:393
List::sort
void sort(int(*)(const T &, const T &))
Definition ftmpl_list.cc:339
compareByNumberOfVars
int compareByNumberOfVars(const CFFactor &F, const CFFactor &G)
Definition facFqFactorizeUtil.cc:180

## 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;
}