Functions
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 More...
 
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 More...
 
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=2)
 shift evaluation point to zero More...
 
CanonicalForm reverseShift (const CanonicalForm &F, const CFList &evaluation, int l=2)
 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...
 
CFFList sortCFFListByNumOfVars (CFFList &F)
 sort CFFList by the number variables in a factor More...
 
CanonicalForm myGetVars (const CanonicalForm &F)
 like getVars but each variable x occuring in F is raised to x^degree (F,x) More...
 
CFList evaluateAtEval (const CanonicalForm &F, const CFArray &evaluation)
 evaluate F at evaluation More...
 
CFList evaluateAtEval (const CanonicalForm &F, const CFList &evaluation, int l)
 evaluate F at evaluation More...
 
CFList evaluateAtZero (const CanonicalForm &F)
 evaluate F successively n-2 at 0 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.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]factors1a list of polys, returns swapped elements of factors2 appended to it
[in]factors2a list of polys
[in]swapLevel1level of variable to be swapped with x, 0 if no swapping
[in]swapLevel2level of variable to be swapped with x, 0 if no swapping
[in]xa 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]factors1a list of polys, returns swapped elements of factors2 appended to it and everything is decompressed
[in]factors2a list of polys
[in]Na map
[in]swapLevellevel of variable to be swapped with x, 0 if no swapping
[in]xa variable

Definition at line 69 of file facFqFactorizeUtil.cc.

72 {
73  for (CFListIterator i= factors1; i.hasItem(); i++)
74  {
75  if (swapLevel)
76  i.getItem()= swapvar (i.getItem(), Variable (swapLevel), x);
77  i.getItem()= N(i.getItem());
78  }
79  for (CFListIterator i= factors2; i.hasItem(); i++)
80  {
81  if (!i.getItem().inCoeffDomain())
82  factors1.append (N (i.getItem()));
83  }
84  return;
85 }
factory's class for variables
Definition: factory.h:115
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:49
int i
Definition: cfEzgcd.cc:123
Variable x
Definition: cfModGcd.cc:4023
void append(const T &)
Definition: ftmpl_list.cc:256

§ 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]factors1a list of polys, returns swapped elements of factors2 appended to it and everything is decompressed
[in]factors2a list of polys
[in]Na map
[in]swapLevel1level of variable to be swapped with x, 0 if no swapping
[in]swapLevel2level of variable to be swapped with x, 0 if no swapping
[in]xa variable

Definition at line 87 of file facFqFactorizeUtil.cc.

90 {
91  for (CFListIterator i= factors1; i.hasItem(); i++)
92  {
93  if (swapLevel1)
94  {
95  if (swapLevel2)
96  i.getItem()=
97  N (swapvar (swapvar (i.getItem(), Variable (swapLevel2), x), x,
98  Variable (swapLevel1)));
99  else
100  i.getItem()= N (swapvar (i.getItem(), x, Variable (swapLevel1)));
101  }
102  else
103  {
104  if (swapLevel2)
105  i.getItem()= N (swapvar (i.getItem(), Variable (swapLevel2), x));
106  else
107  i.getItem()= N (i.getItem());
108  }
109  }
110  for (CFListIterator i= factors2; i.hasItem(); i++)
111  {
112  if (!i.getItem().inCoeffDomain())
113  factors1.append (N (i.getItem()));
114  }
115  return;
116 }
factory's class for variables
Definition: factory.h:115
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:49
int i
Definition: cfEzgcd.cc:123
Variable x
Definition: cfModGcd.cc:4023
void append(const T &)
Definition: ftmpl_list.cc:256

§ decompressAppend()

static void decompressAppend ( CFList factors1,
const CFList factors2,
const CFMap N 
)
inlinestatic

append factors2 to factors1 and decompress

Parameters
[in,out]factors1a list of polys, returns factors2 appended to it and everything is decompressed
[in]factors2a list of polys
[in]Na map

Definition at line 23 of file facFqFactorizeUtil.h.

30 {
31  for (CFListIterator i= factors1; i.hasItem(); i++)
32  i.getItem()= N (i.getItem());
33  for (CFListIterator i= factors2; i.hasItem(); i++)
34  factors1.append (N (i.getItem()));
35 }
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:49
int i
Definition: cfEzgcd.cc:123
void append(const T &)
Definition: ftmpl_list.cc:256

§ 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]Fsome poly
[in]evaluationsome evaluation point

Definition at line 206 of file facFqFactorizeUtil.cc.

207 {
208  CFList result;
209  CanonicalForm buf= F;
210  result.insert (buf);
211  int k= eval.size();
212  for (int i= 1; i < k; i++)
213  {
214  buf= buf (eval[i], i + 2);
215  result.insert (buf);
216  }
217  return result;
218 }
factory&#39;s main class
Definition: canonicalform.h:75
int k
Definition: cfEzgcd.cc:93
void insert(const T &)
Definition: ftmpl_list.cc:193
int status int void * buf
Definition: si_signals.h:59
CFList & eval
Definition: facFactorize.cc:48
int i
Definition: cfEzgcd.cc:123
return result
Definition: facAbsBiFact.cc:76

§ 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]Fsome poly
[in]evaluationsome evaluation point
[in]llevel to start at

Definition at line 220 of file facFqFactorizeUtil.cc.

221 {
222  CFList result;
223  CanonicalForm buf= F;
224  result.insert (buf);
225  int k= evaluation.length() + l - 1;
227  for (int i= k; j.hasItem() && i > l; i--, j++)
228  {
229  if (F.level() < i)
230  continue;
231  buf= buf (j.getItem(), i);
232  result.insert (buf);
233  }
234  return result;
235 }
factory&#39;s main class
Definition: canonicalform.h:75
int k
Definition: cfEzgcd.cc:93
const CanonicalForm int const CFList & evaluation
Definition: facAbsFact.cc:55
void insert(const T &)
Definition: ftmpl_list.cc:193
int j
Definition: myNF.cc:70
int status int void * buf
Definition: si_signals.h:59
T & getItem() const
Definition: ftmpl_list.cc:431
int i
Definition: cfEzgcd.cc:123
int length() const
Definition: ftmpl_list.cc:273
int level() const
level() returns the level of CO.
int l
Definition: cfEzgcd.cc:94
return result
Definition: facAbsBiFact.cc:76

§ 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]Fsome poly

Definition at line 193 of file facFqFactorizeUtil.cc.

194 {
195  CFList result;
196  CanonicalForm buf= F;
197  result.insert (buf);
198  for (int i= F.level(); i > 2; i--)
199  {
200  buf= buf (0, i);
201  result.insert (buf);
202  }
203  return result;
204 }
factory&#39;s main class
Definition: canonicalform.h:75
void insert(const T &)
Definition: ftmpl_list.cc:193
int status int void * buf
Definition: si_signals.h:59
int i
Definition: cfEzgcd.cc:123
int level() const
level() returns the level of CO.
return result
Definition: facAbsBiFact.cc:76

§ 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]Fsome poly

Definition at line 162 of file facFqFactorizeUtil.cc.

163 {
164  return (F-LC (F,1)*power (Variable(1),degree (F,1))).isZero();
165 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
factory&#39;s class for variables
Definition: factory.h:115
int degree(const CanonicalForm &f)
CanonicalForm LC(const CanonicalForm &f)

§ 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]Aa compressed poly
[in]bivarLiftBoundlift bound for biFactorizer()

Definition at line 118 of file facFqFactorizeUtil.cc.

119 {
120  int j= A.level() - 1;
121  int* liftBounds= new int [j];
122  liftBounds[0]= bivarLiftBound;
123  for (int i= 1; i < j; i++)
124  {
125  liftBounds[i]= degree (A, Variable (i + 2)) + 1 +
126  degree (LC (A, 1), Variable (i + 2));
127  }
128  return liftBounds;
129 }
factory&#39;s class for variables
Definition: factory.h:115
int j
Definition: myNF.cc:70
int i
Definition: cfEzgcd.cc:123
int level() const
level() returns the level of CO.
int degree(const CanonicalForm &f)
CanonicalForm LC(const CanonicalForm &f)

§ 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]Fa polynomial

Definition at line 168 of file facFqFactorizeUtil.cc.

169 {
171  int deg;
172  for (int i= 1; i <= F.level(); i++)
173  {
174  if ((deg= degree (F, i)) > 0)
175  result *= power (Variable (i), deg);
176  }
177  return result;
178 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
factory&#39;s class for variables
Definition: factory.h:115
factory&#39;s main class
Definition: canonicalform.h:75
int i
Definition: cfEzgcd.cc:123
int level() const
level() returns the level of CO.
int degree(const CanonicalForm &f)
return result
Definition: facAbsBiFact.cc:76

§ recoverFactors() [1/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]Fsome poly F
[in]factorssome list of factor candidates

Definition at line 238 of file facFqFactorizeUtil.cc.

239 {
240  CFList result;
241  CanonicalForm tmp, tmp2;
242  CanonicalForm G= F;
243  for (CFListIterator i= factors; i.hasItem(); i++)
244  {
245  tmp= i.getItem()/content (i.getItem(), 1);
246  if (fdivides (tmp, G, tmp2))
247  {
248  G= tmp2;
249  result.append (tmp);
250  }
251  }
252  if (result.length() + 1 == factors.length())
253  result.append (G/content (G,1));
254  return result;
255 }
factory&#39;s main class
Definition: canonicalform.h:75
static TreeM * G
Definition: janet.cc:38
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:180
int i
Definition: cfEzgcd.cc:123
CFList tmp2
Definition: facFqBivar.cc:70
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
int length() const
Definition: ftmpl_list.cc:273
void append(const T &)
Definition: ftmpl_list.cc:256
return result
Definition: facAbsBiFact.cc:76

§ recoverFactors() [2/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]Fsome poly F
[in]factorssome list of factor candidates
[in]evaluationevaluation point

Definition at line 257 of file facFqFactorizeUtil.cc.

259 {
260  CFList result;
261  CanonicalForm tmp, tmp2;
262  CanonicalForm G= F;
263  for (CFListIterator i= factors; i.hasItem(); i++)
264  {
265  tmp= reverseShift (i.getItem(), evaluation, 2);
266  tmp /= content (tmp, 1);
267  if (fdivides (tmp, G, tmp2))
268  {
269  G= tmp2;
270  result.append (tmp);
271  }
272  }
273  if (result.length() + 1 == factors.length())
274  result.append (G/content (G,1));
275  return result;
276 }
CanonicalForm reverseShift(const CanonicalForm &F, const CFList &evaluation, int l)
reverse shifting the evaluation point to zero
factory&#39;s main class
Definition: canonicalform.h:75
const CanonicalForm int const CFList & evaluation
Definition: facAbsFact.cc:55
static TreeM * G
Definition: janet.cc:38
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:180
int i
Definition: cfEzgcd.cc:123
CFList tmp2
Definition: facFqBivar.cc:70
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
int length() const
Definition: ftmpl_list.cc:273
void append(const T &)
Definition: ftmpl_list.cc:256
return result
Definition: facAbsBiFact.cc:76

§ recoverFactors() [3/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]Fsome poly F
[in]factorssome list of factor candidates
[in]indexposition of real factors

Definition at line 278 of file facFqFactorizeUtil.cc.

279 {
280  CFList result;
281  CanonicalForm tmp, tmp2;
282  CanonicalForm G= F;
283  int j= 0;
284  for (CFListIterator i= factors; i.hasItem(); i++, j++)
285  {
286  if (i.getItem().isZero())
287  {
288  index[j]= 0;
289  continue;
290  }
291  tmp= i.getItem();
292  if (fdivides (tmp, G, tmp2))
293  {
294  G= tmp2;
295  tmp /=content (tmp, 1);
296  result.append (tmp);
297  index[j]= 1;
298  }
299  else
300  index[j]= 0;
301  }
302  if (result.length() + 1 == factors.length())
303  {
304  result.append (G/content (G,1));
305  F= G/content (G,1);
306  }
307  else
308  F= G;
309  return result;
310 }
factory&#39;s main class
Definition: canonicalform.h:75
static TreeM * G
Definition: janet.cc:38
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:180
int j
Definition: myNF.cc:70
int i
Definition: cfEzgcd.cc:123
CFList tmp2
Definition: facFqBivar.cc:70
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
int length() const
Definition: ftmpl_list.cc:273
void append(const T &)
Definition: ftmpl_list.cc:256
return result
Definition: facAbsBiFact.cc:76

§ 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]Fa compressed poly
[in]evaluationa valid evaluation point
[in]llevel at which the evaluation starts

Definition at line 148 of file facFqFactorizeUtil.cc.

149 {
150  int k= evaluation.length() + l - 1;
153  for (int i= k; j.hasItem() && (i > l - 1); i--, j++)
154  {
155  if (F.level() < i)
156  continue;
157  result= result (Variable (i) - j.getItem(), i);
158  }
159  return result;
160 }
factory&#39;s class for variables
Definition: factory.h:115
factory&#39;s main class
Definition: canonicalform.h:75
int k
Definition: cfEzgcd.cc:93
const CanonicalForm int const CFList & evaluation
Definition: facAbsFact.cc:55
int j
Definition: myNF.cc:70
T & getItem() const
Definition: ftmpl_list.cc:431
int i
Definition: cfEzgcd.cc:123
int length() const
Definition: ftmpl_list.cc:273
int level() const
level() returns the level of CO.
return result
Definition: facAbsBiFact.cc:76
int l
Definition: cfEzgcd.cc:94

§ 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]Fa compressed poly
[in,out]Fevalan empty list, returns F successively evaluated at 0
[in]evaluationa valid evaluation point
[in]llevel at which the evaluation starts

Definition at line 131 of file facFqFactorizeUtil.cc.

132 {
133  CanonicalForm A= F;
134  int k= evaluation.length() + l - 1;
135  for (CFListIterator i= evaluation; i.hasItem(); i++, k--)
136  A= A (Variable (k) + i.getItem(), k);
138  Feval= CFList();
139  Feval.append (buf);
140  for (k= A.level(); k > 2; k--)
141  {
142  buf= mod (buf, Variable (k));
143  Feval.insert (buf);
144  }
145  return A;
146 }
List< CanonicalForm > CFList
CF_NO_INLINE CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
Definition: cf_inline.cc:564
factory&#39;s class for variables
Definition: factory.h:115
factory&#39;s main class
Definition: canonicalform.h:75
int k
Definition: cfEzgcd.cc:93
void insert(const T &)
Definition: ftmpl_list.cc:193
int status int void * buf
Definition: si_signals.h:59
#define A
Definition: sirandom.c:23
int i
Definition: cfEzgcd.cc:123
int length() const
Definition: ftmpl_list.cc:273
int level() const
level() returns the level of CO.
void append(const T &)
Definition: ftmpl_list.cc:256
int l
Definition: cfEzgcd.cc:94

§ sortCFFListByNumOfVars()

CFFList sortCFFListByNumOfVars ( CFFList F)

sort CFFList by the number variables in a factor

Parameters
[in,out]Fa list of factors

Definition at line 186 of file facFqFactorizeUtil.cc.

187 {
189  CFFList result= F;
190  return result;
191 }
int compareByNumberOfVars(const CFFactor &F, const CFFactor &G)
return result
Definition: facAbsBiFact.cc:76
void sort(int(*)(const T &, const T &))
Definition: ftmpl_list.cc:339

§ swap()

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

swap elements in factors

Parameters
[in]factorsa list of polys, returns swapped elements of factors
[in]swapLevel1level of variable to be swapped with x, 0 if no swapping
[in]swapLevel2level of variable to be swapped with x, 0 if no swapping
[in]xa variable

Definition at line 47 of file facFqFactorizeUtil.cc.

49 {
50  for (CFListIterator i= factors; i.hasItem(); i++)
51  {
52  if (swapLevel1)
53  {
54  if (swapLevel2)
55  i.getItem()= swapvar (swapvar (i.getItem(), x, Variable (swapLevel2)),
56  Variable (swapLevel1), x);
57  else
58  i.getItem()= swapvar (i.getItem(), Variable (swapLevel1), x);
59  }
60  else
61  {
62  if (swapLevel2)
63  i.getItem()= swapvar (i.getItem(), x, Variable (swapLevel2));
64  }
65  }
66  return;
67 }
factory&#39;s class for variables
Definition: factory.h:115
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
int i
Definition: cfEzgcd.cc:123
Variable x
Definition: cfModGcd.cc:4023