My Project  debian-1:4.1.1-p2+ds-4build2
Functions
facFqFactorizeUtil.cc File Reference
#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.

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 }

◆ 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

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 }

◆ 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

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 }

◆ compareByNumberOfVars()

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 }

◆ 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

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 }

◆ 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

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 }

◆ 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

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 }

◆ isOnlyLeadingCoeff()

bool isOnlyLeadingCoeff ( const CanonicalForm F)

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

Returns
as described above

Definition at line 162 of file facFqFactorizeUtil.cc.

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

◆ liftingBounds()

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

compute lifting bounds

Returns
liftingBounds returns an array containing the lift bounds for A

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 }

◆ 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)

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 }

◆ 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

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 }

◆ 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

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 }

◆ 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

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 }

◆ 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()

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 }

◆ 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()

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 }

◆ sortCFFListByNumOfVars()

CFFList sortCFFListByNumOfVars ( CFFList F)

sort CFFList by the number variables in a factor

Definition at line 186 of file facFqFactorizeUtil.cc.

187 {
189  CFFList result= F;
190  return result;
191 }

◆ swap()

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

swap elements in factors

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 }
reverseShift
CanonicalForm reverseShift(const CanonicalForm &F, const CFList &evaluation, int l)
reverse shifting the evaluation point to zero
Definition: facFqFactorizeUtil.cc:148
j
int j
Definition: facHensel.cc:105
k
int k
Definition: cfEzgcd.cc:92
Factor::factor
T factor() const
Definition: ftmpl_factor.h:30
x
Variable x
Definition: cfModGcd.cc:4023
result
return result
Definition: facAbsBiFact.cc:76
compareByNumberOfVars
int compareByNumberOfVars(const CFFactor &F, const CFFactor &G)
Definition: facFqFactorizeUtil.cc:180
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition: canonicalform.cc:1837
mod
CF_NO_INLINE CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
Definition: cf_inline.cc:564
N
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:49
CanonicalForm
factory's main class
Definition: canonicalform.h:77
evaluation
const CanonicalForm int const CFList & evaluation
Definition: facAbsFact.cc:56
factors2
const CFList & factors2
Definition: facFqBivarUtil.cc:42
i
int i
Definition: cfEzgcd.cc:125
swapvar
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
buf
int status int void * buf
Definition: si_signals.h:59
content
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:180
Feval
CanonicalForm Feval
Definition: facAbsFact.cc:64
eval
CFList & eval
Definition: facFactorize.cc:48
fdivides
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
Definition: cf_algorithm.cc:338
List::length
int length() const
Definition: ftmpl_list.cc:273
Variable
factory's class for variables
Definition: factory.h:117
getNumVars
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition: cf_ops.cc:314
LC
CanonicalForm LC(const CanonicalForm &f)
Definition: canonicalform.h:303
l
int l
Definition: cfEzgcd.cc:93
List< CanonicalForm >
CFList
List< CanonicalForm > CFList
Definition: canonicalform.h:388
tmp2
CFList tmp2
Definition: facFqBivar.cc:70
G
static TreeM * G
Definition: janet.cc:32
CanonicalForm::level
int level() const
level() returns the level of CO.
Definition: canonicalform.cc:543
List::append
void append(const T &)
Definition: ftmpl_list.cc:256
index
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
A
#define A
Definition: sirandom.c:23
degree
int degree(const CanonicalForm &f)
Definition: canonicalform.h:309
List::sort
void sort(int(*)(const T &, const T &))
Definition: ftmpl_list.cc:339
ListIterator
Definition: ftmpl_list.h:17