Functions
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

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.

24 {
25  for (CFListIterator i= factors2; i.hasItem(); i++)
26  {
27  if (swapLevel1)
28  {
29  if (swapLevel2)
30  factors1.append (swapvar (swapvar (i.getItem(), x,
31  Variable (swapLevel2)), Variable (swapLevel1), x));
32  else
33  factors1.append (swapvar (i.getItem(), Variable (swapLevel1), x));
34  }
35  else
36  {
37  if (swapLevel2)
38  factors1.append (swapvar (i.getItem(), x, Variable (swapLevel2)));
39  else
40  factors1.append (i.getItem());
41  }
42  }
43  return;
44 }
factory's class for variables
Definition: variable.h:32
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
void append(const T &)
Definition: ftmpl_list.cc:256
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: variable.h:32
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
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: variable.h:32
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
int compareByNumberOfVars ( const CFFactor F,
const CFFactor G 
)

Definition at line 180 of file facFqFactorizeUtil.cc.

181 {
182  return getNumVars (F.factor()) < getNumVars (G.factor());
183 }
T factor() const
Definition: ftmpl_factor.h:32
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition: cf_ops.cc:314
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]evalsome 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 }
int size() const
Definition: ftmpl_array.cc:92
factory'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
int i
Definition: cfEzgcd.cc:123
return result
Definition: facAbsBiFact.cc:76
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'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 level() const
level() returns the level of CO.
int j
Definition: myNF.cc:70
int status int void * buf
Definition: si_signals.h:59
int length() const
Definition: ftmpl_list.cc:273
int i
Definition: cfEzgcd.cc:123
T & getItem() const
Definition: ftmpl_list.cc:431
int l
Definition: cfEzgcd.cc:94
return result
Definition: facAbsBiFact.cc:76
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's main class
Definition: canonicalform.h:75
void insert(const T &)
Definition: ftmpl_list.cc:193
int level() const
level() returns the level of CO.
int status int void * buf
Definition: si_signals.h:59
int i
Definition: cfEzgcd.cc:123
return result
Definition: facAbsBiFact.cc:76
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's class for variables
Definition: variable.h:32
int degree(const CanonicalForm &f)
CanonicalForm LC(const CanonicalForm &f)
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's class for variables
Definition: variable.h:32
int level() const
level() returns the level of CO.
int j
Definition: myNF.cc:70
int i
Definition: cfEzgcd.cc:123
int degree(const CanonicalForm &f)
CanonicalForm LC(const CanonicalForm &f)
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]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's class for variables
Definition: variable.h:32
factory's main class
Definition: canonicalform.h:75
int level() const
level() returns the level of CO.
int i
Definition: cfEzgcd.cc:123
int degree(const CanonicalForm &f)
return result
Definition: facAbsBiFact.cc:76
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'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 length() const
Definition: ftmpl_list.cc:273
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 )
void append(const T &)
Definition: ftmpl_list.cc:256
return result
Definition: facAbsBiFact.cc:76
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'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 length() const
Definition: ftmpl_list.cc:273
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 )
void append(const T &)
Definition: ftmpl_list.cc:256
return result
Definition: facAbsBiFact.cc:76
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'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 length() const
Definition: ftmpl_list.cc:273
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:597
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
void append(const T &)
Definition: ftmpl_list.cc:256
return result
Definition: facAbsBiFact.cc:76
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's class for variables
Definition: variable.h:32
factory's main class
Definition: canonicalform.h:75
int k
Definition: cfEzgcd.cc:93
const CanonicalForm int const CFList & evaluation
Definition: facAbsFact.cc:55
int level() const
level() returns the level of CO.
int j
Definition: myNF.cc:70
int length() const
Definition: ftmpl_list.cc:273
int i
Definition: cfEzgcd.cc:123
T & getItem() const
Definition: ftmpl_list.cc:431
return result
Definition: facAbsBiFact.cc:76
int l
Definition: cfEzgcd.cc:94
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's class for variables
Definition: variable.h:32
factory's main class
Definition: canonicalform.h:75
int k
Definition: cfEzgcd.cc:93
void insert(const T &)
Definition: ftmpl_list.cc:193
int level() const
level() returns the level of CO.
int status int void * buf
Definition: si_signals.h:59
#define A
Definition: sirandom.c:23
int length() const
Definition: ftmpl_list.cc:273
int i
Definition: cfEzgcd.cc:123
void append(const T &)
Definition: ftmpl_list.cc:256
int l
Definition: cfEzgcd.cc:94
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
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's class for variables
Definition: variable.h:32
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