Functions
facSparseHensel.h File Reference

This file provides functions for sparse heuristic Hensel lifting. More...

#include "canonicalform.h"
#include "cf_map_ext.h"
#include "cf_iter.h"
#include "templates/ftmpl_functions.h"
#include "cf_algorithm.h"
#include "cf_map.h"

Go to the source code of this file.

Functions

int comp (const CanonicalForm &A, const CanonicalForm &B)
 compare polynomials More...
 
int comp (const CanonicalForm &A, const CanonicalForm &B, int level)
 compare two polynomials up to level level More...
 
void swap (CFArray &A, int i, int j)
 swap entry i and j in A More...
 
void quickSort (int lo, int hi, CFArray &A, int l)
 quick sort helper function More...
 
void sort (CFArray &A, int l=0)
 quick sort A More...
 
CFList findNormalizingFactor1 (const CFList &biFactors, const CanonicalForm &evalPoint, CFList &uniFactors)
 find normalizing factors for biFactors and build monic univariate factors from biFactors More...
 
CFList findNormalizingFactor2 (CFList &biFactors, const CanonicalForm &evalPoint, const CFList &uniFactors)
 find normalizing factors for biFactors and sort biFactors s.t. the returned biFactors evaluated at evalPoint coincide with uniFactors More...
 
CFArray getTerms (const CanonicalForm &F)
 get terms of F More...
 
CFArray getBiTerms_helper (const CanonicalForm &F, const CFMap &M, int threshold)
 helper function for getBiTerms More...
 
CFArray getBiTerms (const CanonicalForm &F, int threshold)
 get terms of F where F is considered a bivariate poly in Variable(1), Variable (2) More...
 
CanonicalForm buildPolyFromArray (const CFArray &A)
 build a poly from entries in A More...
 
void groupTogether (CFArray &A, int level)
 group together elements in A, where entries in A are put together if they coincide up to level level More...
 
void strip (CFArray &F, CFArray &G, int level)
 strip off those parts of entries in F whose level is less than or equal than level and store the stripped off parts in G More...
 
void strip (CFArray &F, int level)
 s.a. stripped off parts are not returned More...
 
CFArray getEquations (const CFArray &A, const CFArray &B)
 get equations for LucksWangSparseHeuristic More...
 
void evaluate (CFArray &A, const CanonicalForm &B, int level)
 evaluate every entry of A at B and level level More...
 
void evaluate (CFArray &A, const CFArray &B, int level)
 evaluate every entry of A at every entry of B starting at level level More...
 
CanonicalForm simplify (const CanonicalForm &A, int level)
 simplify A if possible, i.e. A consists of 2 terms and contains only one variable of level greater or equal than level More...
 
bool simplify (CFArray &A, CFArray &B, int level)
 if possible simplify A as described above and store result in B More...
 
bool merge (CFArray &A, CFArray &B)
 merge B into A if possible, i.e. every non-zero entry in A should be zero in B More...
 
bool isZero (const CFArray &A)
 checks if entries of A are zero More...
 
bool isEqual (const CFArray &A, const CFArray &B)
 checks if A equals B More...
 
CFArray getTerms2 (const CanonicalForm &F)
 get terms of F wrt. Variable (1) More...
 
void getTerms2 (const CFList &F, CFArray *result)
 get terms of entries in F and put them in result More...
 
CFArray evaluate (const CFArray &A, const CanonicalForm &eval, const Variable &y)
 evaluate entries in A at eval and y More...
 
CFArrayevaluate (CFArray *const &A, int sizeA, const CanonicalForm &eval, const Variable &y)
 s.a. More...
 
CFList normalize (const CFList &L, const CFList &normalizingFactor)
 normalize entries in L with normalizingFactor More...
 
int search (const CFArray &A, const CanonicalForm &F, int i, int j)
 search for F in A between index i and j More...
 
CanonicalForm patch (const CanonicalForm &F1, const CanonicalForm &F2, const CanonicalForm &eval)
 patch together F1 and F2 and normalize by a power of eval F1 and F2 are assumed to be bivariate with one variable having level 1 More...
 
int LucksWangSparseHeuristic (const CanonicalForm &F, const CFList &factors, int level, const CFList &leadingCoeffs, CFList &result)
 sparse heuristic lifting by Wang and Lucks More...
 
CFList sparseHeuristic (const CanonicalForm &A, const CFList &biFactors, CFList *&moreBiFactors, const CFList &evaluation, int minFactorsLength)
 sparse heuristic which patches together bivariate factors of A wrt. different second variables by their univariate images More...
 

Detailed Description

This file provides functions for sparse heuristic Hensel lifting.

Author
Martin Lee

Definition in file facSparseHensel.h.

Function Documentation

CanonicalForm buildPolyFromArray ( const CFArray A)
inline

build a poly from entries in A

Definition at line 267 of file facSparseHensel.h.

268 {
270  for (int i= A.size() - 1; i > -1; i--)
271  result += A[i];
272  return result;
273 }
int size() const
Definition: ftmpl_array.cc:92
factory's main class
Definition: canonicalform.h:75
int i
Definition: cfEzgcd.cc:123
return result
Definition: facAbsBiFact.cc:76
int comp ( const CanonicalForm A,
const CanonicalForm B 
)
inline

compare polynomials

Definition at line 25 of file facSparseHensel.h.

26 {
27  if (A.inCoeffDomain() && !B.inCoeffDomain())
28  return -1;
29  else if (!A.inCoeffDomain() && B.inCoeffDomain())
30  return 1;
31  else if (A.inCoeffDomain() && B.inCoeffDomain())
32  return 0;
33  else if (degree (A, 1) > degree (B, 1))
34  return 1;
35  else if (degree (A, 1) < degree (B, 1))
36  return -1;
37  // here A and B are not in CoeffDomain
38  int n= tmax (A.level(), B.level());
39  for (int i= 2; i <= n; i++)
40  {
41  if (degree (A,i) > degree (B,i))
42  return 1;
43  else if (degree (A,i) < degree (B,i))
44  return -1;
45  }
46  return 0;
47 }
bool inCoeffDomain() const
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
int level() const
level() returns the level of CO.
int i
Definition: cfEzgcd.cc:123
int degree(const CanonicalForm &f)
int comp ( const CanonicalForm A,
const CanonicalForm B,
int  level 
)
inline

compare two polynomials up to level level

Definition at line 51 of file facSparseHensel.h.

52 {
53  if (A.inCoeffDomain() && !B.inCoeffDomain() && B.level() <= level)
54  return -1;
55  else if (!A.inCoeffDomain() && A.level() <= level && B.inCoeffDomain())
56  return 1;
57  else if (A.inCoeffDomain() && B.inCoeffDomain())
58  return 0;
59  else if (degree (A, 1) > degree (B, 1))
60  return 1;
61  else if (degree (A, 1) < degree (B, 1))
62  return -1;
63  // here A and B are not in coeffdomain
64  for (int i= 2; i <= level; i++)
65  {
66  if (degree (A,i) > degree (B,i))
67  return 1;
68  else if (degree (A,i) < degree (B,i))
69  return -1;
70  }
71  return 0;
72 }
int level(const CanonicalForm &f)
bool inCoeffDomain() const
int level() const
level() returns the level of CO.
int i
Definition: cfEzgcd.cc:123
int degree(const CanonicalForm &f)
void evaluate ( CFArray A,
const CanonicalForm B,
int  level 
)
inline

evaluate every entry of A at B and level level

Definition at line 362 of file facSparseHensel.h.

363 {
364  int n= A.size();
365  for (int i= 0; i < n; i++)
366  {
367  if (A[i].level() < level)
368  continue;
369  else
370  A[i]= A[i] (B, level);
371  }
372 }
int level(const CanonicalForm &f)
int size() const
Definition: ftmpl_array.cc:92
int i
Definition: cfEzgcd.cc:123
b *CanonicalForm B
Definition: facBivar.cc:51
void evaluate ( CFArray A,
const CFArray B,
int  level 
)
inline

evaluate every entry of A at every entry of B starting at level level

Definition at line 377 of file facSparseHensel.h.

378 {
379  int n= B.size();
380  for (int i= 0; i < n; i++)
381  {
382  if (!B[i].isZero())
383  evaluate (A, B[i], level + i);
384  }
385 }
int level(const CanonicalForm &f)
int size() const
Definition: ftmpl_array.cc:92
int i
Definition: cfEzgcd.cc:123
bool isZero(const CFArray &A)
checks if entries of A are zero
void evaluate(CFArray &A, const CanonicalForm &B, int level)
evaluate every entry of A at B and level level
CFArray evaluate ( const CFArray A,
const CanonicalForm eval,
const Variable y 
)
inline

evaluate entries in A at eval and y

Definition at line 533 of file facSparseHensel.h.

534 {
535  int j= A.size();
536  CFArray result= CFArray (j);
537  for (int i= 0; i < j; i++)
538  result [i]= A[i] (eval, y);
539  return result;
540 }
int size() const
Definition: ftmpl_array.cc:92
Array< CanonicalForm > CFArray
int j
Definition: myNF.cc:70
int i
Definition: cfEzgcd.cc:123
return result
Definition: facAbsBiFact.cc:76
CFArray* evaluate ( CFArray *const A,
int  sizeA,
const CanonicalForm eval,
const Variable y 
)
inline

s.a.

Definition at line 544 of file facSparseHensel.h.

546 {
547  CFArray* result= new CFArray [sizeA];
548  for (int i= 0; i < sizeA; i++)
549  result[i]= evaluate (A[i], eval, y);
550  return result;
551 }
int i
Definition: cfEzgcd.cc:123
void evaluate(CFArray &A, const CanonicalForm &B, int level)
evaluate every entry of A at B and level level
return result
Definition: facAbsBiFact.cc:76
CFList findNormalizingFactor1 ( const CFList biFactors,
const CanonicalForm evalPoint,
CFList uniFactors 
)
inline

find normalizing factors for biFactors and build monic univariate factors from biFactors

Definition at line 123 of file facSparseHensel.h.

125 {
126  CFList result;
127  CanonicalForm tmp;
128  for (CFListIterator i= biFactors; i.hasItem(); i++)
129  {
130  tmp= i.getItem() (evalPoint);
131  uniFactors.append (tmp /Lc (tmp));
132  result.append (Lc (tmp));
133  }
134  return result;
135 }
factory&#39;s main class
Definition: canonicalform.h:75
CanonicalForm Lc(const CanonicalForm &f)
int i
Definition: cfEzgcd.cc:123
void append(const T &)
Definition: ftmpl_list.cc:256
static void evalPoint(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &FEval, CanonicalForm &GEval, CFGenerator &evalPoint)
return result
Definition: facAbsBiFact.cc:76
CFList findNormalizingFactor2 ( CFList biFactors,
const CanonicalForm evalPoint,
const CFList uniFactors 
)
inline

find normalizing factors for biFactors and sort biFactors s.t. the returned biFactors evaluated at evalPoint coincide with uniFactors

Definition at line 140 of file facSparseHensel.h.

142 {
143  CFList result;
144  CFList uniBiFactors= biFactors;
145  CFList newBiFactors;
146  CFList l;
147  int pos;
149  for (iter= uniBiFactors; iter.hasItem(); iter++)
150  {
151  iter.getItem()= iter.getItem() (evalPoint);
152  l.append (Lc (iter.getItem()));
153  iter.getItem() /= Lc (iter.getItem());
154  }
155  for (CFListIterator i= uniFactors; i.hasItem(); i++)
156  {
157  pos= findItem (uniBiFactors, i.getItem());
158  newBiFactors.append (getItem (biFactors, pos));
159  result.append (getItem (l, pos));
160  }
161  biFactors= newBiFactors;
162  return result;
163 }
CanonicalForm getItem(const CFList &list, const int &pos)
helper function
Definition: cf_map_ext.cc:49
CFFListIterator iter
Definition: facAbsBiFact.cc:54
CanonicalForm Lc(const CanonicalForm &f)
int i
Definition: cfEzgcd.cc:123
T & getItem() const
Definition: ftmpl_list.cc:431
void append(const T &)
Definition: ftmpl_list.cc:256
int findItem(const CFList &list, const CanonicalForm &item)
helper function
Definition: cf_map_ext.cc:37
static void evalPoint(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &FEval, CanonicalForm &GEval, CFGenerator &evalPoint)
int l
Definition: cfEzgcd.cc:94
return result
Definition: facAbsBiFact.cc:76
CFArray getBiTerms ( const CanonicalForm F,
int  threshold 
)
inline

get terms of F where F is considered a bivariate poly in Variable(1), Variable (2)

Definition at line 236 of file facSparseHensel.h.

237 {
238  if (F.inCoeffDomain())
239  {
240  CFArray result= CFArray (1);
241  result [0]= F;
242  return result;
243  }
244  if (F.isUnivariate())
245  {
246  CFArray result= CFArray (size(F));
247  int j= 0;
248  for (CFIterator i= F; i.hasTerms(); i++, j++)
249  result[j]= i.coeff()*power (F.mvar(), i.exp());
250  return result;
251  }
252 
253  CanonicalForm G= F;
254 
255  CFMap M;
256  M.newpair (Variable (1), F.mvar());
257  M.newpair (Variable (2), Variable (F.level() - 1));
258  G= swapvar (F, Variable (1), F.mvar());
259  G= swapvar (G, Variable (2), Variable (F.level() - 1));
260 
261  CFArray result= getBiTerms_helper (G, M, threshold);
262  return result;
263 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
bool inCoeffDomain() const
factory&#39;s class for variables
Definition: factory.h:115
factory&#39;s main class
Definition: canonicalform.h:75
Array< CanonicalForm > CFArray
static TreeM * G
Definition: janet.cc:38
CFArray getBiTerms_helper(const CanonicalForm &F, const CFMap &M, int threshold)
helper function for getBiTerms
int level() const
level() returns the level of CO.
#define M
Definition: sirandom.c:24
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
int j
Definition: myNF.cc:70
int i
Definition: cfEzgcd.cc:123
bool isUnivariate() const
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
class CFMap
Definition: cf_map.h:84
void newpair(const Variable &v, const CanonicalForm &s)
void CFMap::newpair ( const Variable & v, const CanonicalForm & s )
Definition: cf_map.cc:120
return result
Definition: facAbsBiFact.cc:76
CFArray getBiTerms_helper ( const CanonicalForm F,
const CFMap M,
int  threshold 
)
inline

helper function for getBiTerms

Definition at line 202 of file facSparseHensel.h.

203 {
204  CFArray buf= CFArray (size (F));
205  int k= 0, level= F.level() - 1;
206  Variable x= F.mvar();
207  Variable y= Variable (F.level() - 1);
208  Variable one= Variable (1);
209  Variable two= Variable (2);
210  CFIterator j;
211  for (CFIterator i= F; i.hasTerms(); i++)
212  {
213  if (i.coeff().level() < level)
214  {
215  buf[k]= M (i.coeff())*power (one,i.exp());
216  k++;
217  if (k > threshold)
218  break;
219  continue;
220  }
221  j= i.coeff();
222  for (;j.hasTerms() && k <= threshold; j++, k++)
223  buf[k]= power (one,i.exp())*power (two,j.exp())*M (j.coeff());
224  if (k > threshold)
225  break;
226  }
227  CFArray result= CFArray (k);
228  for (int i= 0; i < k && k <= threshold; i++)
229  result[i]= buf[i];
230  return result;
231 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
int level(const CanonicalForm &f)
factory&#39;s class for variables
Definition: factory.h:115
Array< CanonicalForm > CFArray
int k
Definition: cfEzgcd.cc:93
int level() const
level() returns the level of CO.
CF_NO_INLINE int hasTerms() const
check if iterator has reached < the end of CanonicalForm
#define M
Definition: sirandom.c:24
CF_NO_INLINE CanonicalForm coeff() const
get the current coefficient
int j
Definition: myNF.cc:70
int status int void * buf
Definition: si_signals.h:59
int i
Definition: cfEzgcd.cc:123
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
CF_NO_INLINE int exp() const
get the current exponent
Variable x
Definition: cfModGcd.cc:4023
return result
Definition: facAbsBiFact.cc:76
CFArray getEquations ( const CFArray A,
const CFArray B 
)
inline

get equations for LucksWangSparseHeuristic

Definition at line 350 of file facSparseHensel.h.

351 {
352  ASSERT (A.size() == B.size(), "size of A and B has to coincide");
353  CFArray result= CFArray (A.size());
354  int n= A.size();
355  for (int i= 0; i < n; i++)
356  result[i]= A[i]-B[i];
357  return result;
358 }
int size() const
Definition: ftmpl_array.cc:92
Array< CanonicalForm > CFArray
int i
Definition: cfEzgcd.cc:123
#define ASSERT(expression, message)
Definition: cf_assert.h:99
return result
Definition: facAbsBiFact.cc:76
CFArray getTerms ( const CanonicalForm F)
inline

get terms of F

Definition at line 167 of file facSparseHensel.h.

168 {
169  if (F.inCoeffDomain())
170  {
171  CFArray result= CFArray (1);
172  result [0]= F;
173  return result;
174  }
175  if (F.isUnivariate())
176  {
177  CFArray result= CFArray (size(F));
178  int j= 0;
179  for (CFIterator i= F; i.hasTerms(); i++, j++)
180  result[j]= i.coeff()*power (F.mvar(), i.exp());
181  return result;
182  }
183  int numMon= size (F);
184  CFArray result= CFArray (numMon);
185  int j= 0;
186  CFArray recResult;
187  Variable x= F.mvar();
188  CanonicalForm powX;
189  for (CFIterator i= F; i.hasTerms(); i++)
190  {
191  powX= power (x, i.exp());
192  recResult= getTerms (i.coeff());
193  for (int k= 0; k < recResult.size(); k++)
194  result[j+k]= powX*recResult[k];
195  j += recResult.size();
196  }
197  return result;
198 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
bool inCoeffDomain() const
factory&#39;s class for variables
Definition: factory.h:115
factory&#39;s main class
Definition: canonicalform.h:75
Array< CanonicalForm > CFArray
int k
Definition: cfEzgcd.cc:93
CFArray getTerms(const CanonicalForm &F)
get terms of F
int j
Definition: myNF.cc:70
int i
Definition: cfEzgcd.cc:123
bool isUnivariate() const
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
Variable x
Definition: cfModGcd.cc:4023
return result
Definition: facAbsBiFact.cc:76
CFArray getTerms2 ( const CanonicalForm F)
inline

get terms of F wrt. Variable (1)

Definition at line 492 of file facSparseHensel.h.

493 {
494  if (F.inCoeffDomain())
495  {
496  CFArray result= CFArray (1);
497  result[0]= F;
498  return result;
499  }
500  CFArray result= CFArray (size (F));
501  int j= 0;
502  Variable x= F.mvar();
503  Variable y= Variable (1);
504  CFIterator k;
505  for (CFIterator i= F; i.hasTerms(); i++)
506  {
507  if (i.coeff().inCoeffDomain())
508  {
509  result[j]= i.coeff()*power (x,i.exp());
510  j++;
511  }
512  else
513  {
514  for (k= i.coeff(); k.hasTerms(); k++, j++)
515  result[j]= k.coeff()*power (x,i.exp())*power (y,k.exp());
516  }
517  }
518  sort (result);
519  return result;
520 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
bool inCoeffDomain() const
factory&#39;s class for variables
Definition: factory.h:115
Array< CanonicalForm > CFArray
int k
Definition: cfEzgcd.cc:93
CF_NO_INLINE int hasTerms() const
check if iterator has reached < the end of CanonicalForm
CF_NO_INLINE CanonicalForm coeff() const
get the current coefficient
int j
Definition: myNF.cc:70
int i
Definition: cfEzgcd.cc:123
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
CF_NO_INLINE int exp() const
get the current exponent
Variable x
Definition: cfModGcd.cc:4023
void sort(CFArray &A, int l=0)
quick sort A
return result
Definition: facAbsBiFact.cc:76
void getTerms2 ( const CFList F,
CFArray result 
)
inline

get terms of entries in F and put them in result

Definition at line 524 of file facSparseHensel.h.

525 {
526  int j= 0;
527  for (CFListIterator i= F; i.hasItem(); i++, j++)
528  result[j]= getTerms2 (i.getItem());
529 }
int j
Definition: myNF.cc:70
int i
Definition: cfEzgcd.cc:123
CFArray getTerms2(const CanonicalForm &F)
get terms of F wrt. Variable (1)
void groupTogether ( CFArray A,
int  level 
)
inline

group together elements in A, where entries in A are put together if they coincide up to level level

Definition at line 278 of file facSparseHensel.h.

279 {
280  int n= A.size() - 1;
281  int k= A.size();
282  for (int i= 0; i < n; i++)
283  {
284  if (comp (A[i],A[i+1], level) == 0)
285  {
286  A[i+1] += A[i];
287  A[i]= 0;
288  k--;
289  }
290  }
291  if (A[n].isZero())
292  k--;
293  CFArray B= CFArray (k);
294  n++;
295  k= 0;
296  for (int i= 0; i < n; i++)
297  {
298  if (!A[i].isZero())
299  {
300  B[k]= A[i];
301  k++;
302  }
303  }
304  A= B;
305 }
int level(const CanonicalForm &f)
int size() const
Definition: ftmpl_array.cc:92
Array< CanonicalForm > CFArray
int k
Definition: cfEzgcd.cc:93
int comp(const CanonicalForm &A, const CanonicalForm &B)
compare polynomials
int i
Definition: cfEzgcd.cc:123
b *CanonicalForm B
Definition: facBivar.cc:51
bool isZero(const CFArray &A)
checks if entries of A are zero
bool isEqual ( const CFArray A,
const CFArray B 
)
inline

checks if A equals B

Definition at line 479 of file facSparseHensel.h.

480 {
481  if (A.size() != B.size())
482  return false;
483  int i, n= B.size();
484  for (i= 0; i < n; i++)
485  if (A[i] != B[i])
486  return false;
487  return true;
488 }
int size() const
Definition: ftmpl_array.cc:92
int i
Definition: cfEzgcd.cc:123
bool isZero ( const CFArray A)
inline

checks if entries of A are zero

Definition at line 468 of file facSparseHensel.h.

469 {
470  int n= A.size();
471  for (int i= 0; i < n; i++)
472  if (!A[i].isZero())
473  return false;
474  return true;
475 }
int size() const
Definition: ftmpl_array.cc:92
int i
Definition: cfEzgcd.cc:123
bool isZero(const CFArray &A)
checks if entries of A are zero
int LucksWangSparseHeuristic ( const CanonicalForm F,
const CFList factors,
int  level,
const CFList leadingCoeffs,
CFList result 
)

sparse heuristic lifting by Wang and Lucks

Returns
LucksWangSparseHeuristic returns true if it was successful
Parameters
[in]Fpolynomial to be factored
[in]factorsfactors of F lifted to level
[in]levellevel of lifted factors
[in]leadingCoeffsleading coefficients of factors
[in,out]resultresult

Definition at line 26 of file facSparseHensel.cc.

28 {
29  int threshold= 450;
30  CFArray termsF= getBiTerms (F, threshold);
31  if (termsF.size() > threshold)
32  return 0;
33  sort (termsF, level);
34 
35  CFArray* monoms= new CFArray [factors.length()];
36  int i= 0;
37  int num= 0;
38  for (CFListIterator iter= factors; iter.hasItem(); iter++, i++)
39  {
40  monoms[i]= getTerms (iter.getItem());
41  num += monoms [i].size();
42  sort (monoms [i]);
43  }
44 
45  i= 0;
46  CFArray* monomsLead= new CFArray [leadingCoeffs.length()];
47  for (CFListIterator iter= leadingCoeffs; iter.hasItem(); iter++, i++)
48  {
49  monomsLead[i]= getTerms (iter.getItem());
50  sort (monomsLead [i]);
51  groupTogether (monomsLead [i], level);
52  strip (monomsLead [i], level);
53  }
54 
55  CFArray solution= CFArray (num);
56  int k, d, count, j= F.level() + 1;
57  num= 0;
58  i= 0;
59  for (CFListIterator iter= factors; iter.hasItem(); i++, iter++)
60  {
61  d= degree (iter.getItem(), 1);
62  count= 0;
63  for (k= 0; k < monoms[i].size(); k++, j++, num++)
64  {
65  monoms [i][k] *= Variable (j);
66  if (degree (monoms[i][k], 1) == d)
67  {
68  solution[num]= monomsLead [i] [count];
69  count++;
70  }
71  }
72  }
73 
74  delete [] monomsLead;
75 
76  CFList tmp;
77  CFArray* stripped2= new CFArray [factors.length()];
78  for (i= factors.length() - 1; i > -1; i--)
79  {
80  tmp.insert (buildPolyFromArray (monoms [i]));
81  strip (monoms[i], stripped2 [i], level);
82  }
83  delete [] monoms;
84 
85  CanonicalForm H= prod (tmp);
86  CFArray monomsH= getMonoms (H);
87  sort (monomsH,F.level());
88 
89  groupTogether (monomsH, F.level());
90 
91  if (monomsH.size() != termsF.size())
92  {
93  delete [] stripped2;
94  return 0;
95  }
96 
97  CFArray strippedH;
98  strip (monomsH, strippedH, level);
99  CFArray strippedF;
100  strip (termsF, strippedF, level);
101 
102  if (!isEqual (strippedH, strippedF))
103  {
104  delete [] stripped2;
105  return 0;
106  }
107 
108  CFArray A= getEquations (monomsH, termsF);
109  CFArray startingSolution= solution;
110  CFArray newSolution= CFArray (solution.size());
111  result= CFList();
112  do
113  {
114  evaluate (A, solution, F.level() + 1);
115  if (isZero (A))
116  break;
117  if (!simplify (A, newSolution, F.level() + 1))
118  {
119  delete [] stripped2;
120  return 0;
121  }
122  if (isZero (newSolution))
123  break;
124  if (!merge (solution, newSolution))
125  break;
126  } while (1);
127 
128  if (isEqual (startingSolution, solution))
129  {
130  delete [] stripped2;
131  return 0;
132  }
134  num= 0;
135  for (i= 0; i < factors.length(); i++)
136  {
137  k= stripped2[i].size();
138  factor= 0;
139  for (j= 0; j < k; j++, num++)
140  {
141  if (solution [num].isZero())
142  continue;
143  factor += solution [num]*stripped2[i][j];
144  }
145  result.append (factor);
146  }
147 
148  delete [] stripped2;
149  if (result.length() > 0)
150  return 1;
151  return 0;
152 }
int status int void size_t count
Definition: si_signals.h:59
List< CanonicalForm > CFList
CFArray getBiTerms(const CanonicalForm &F, int threshold)
get terms of F where F is considered a bivariate poly in Variable(1), Variable (2) ...
int ** merge(int **points1, int sizePoints1, int **points2, int sizePoints2, int &sizeResult)
int level(const CanonicalForm &f)
CanonicalForm num(const CanonicalForm &f)
factory&#39;s class for variables
Definition: factory.h:115
int size() const
Definition: ftmpl_array.cc:92
CFFListIterator iter
Definition: facAbsBiFact.cc:54
factory&#39;s main class
Definition: canonicalform.h:75
CanonicalForm buildPolyFromArray(const CFArray &A)
build a poly from entries in A
Array< CanonicalForm > CFArray
int k
Definition: cfEzgcd.cc:93
void insert(const T &)
Definition: ftmpl_list.cc:193
CanonicalForm simplify(const CanonicalForm &A, int level)
simplify A if possible, i.e. A consists of 2 terms and contains only one variable of level greater or...
int level() const
level() returns the level of CO.
CFArray getMonoms(const CanonicalForm &F)
extract monomials of F, parts in algebraic variable are considered coefficients
Definition: cfModGcd.cc:1898
int j
Definition: myNF.cc:70
void groupTogether(CFArray &A, int level)
group together elements in A, where entries in A are put together if they coincide up to level level ...
#define A
Definition: sirandom.c:23
int length() const
Definition: ftmpl_list.cc:273
int i
Definition: cfEzgcd.cc:123
CFArray evaluate(const CFArray &A, const CFList &evalPoints)
Definition: cfModGcd.cc:1972
CanonicalForm H
Definition: facAbsFact.cc:64
CanonicalForm factor
Definition: facAbsFact.cc:101
void strip(CFArray &F, CFArray &G, int level)
strip off those parts of entries in F whose level is less than or equal than level and store the stri...
CFArray getEquations(const CFArray &A, const CFArray &B)
get equations for LucksWangSparseHeuristic
bool isEqual(int *a, int *b, int lower, int upper)
Definition: cfGcdAlgExt.cc:941
void getTerms(const CanonicalForm &f, const CanonicalForm &t, CFList &result)
get_Terms: Split the polynomial in the containing terms.
Definition: cf_factor.cc:264
T & getItem() const
Definition: ftmpl_list.cc:431
fq_nmod_poly_t prod
Definition: facHensel.cc:95
bool isZero(const CFArray &A)
checks if entries of A are zero
void sort(CFArray &A, int l=0)
quick sort A
int degree(const CanonicalForm &f)
bool merge ( CFArray A,
CFArray B 
)
inline

merge B into A if possible, i.e. every non-zero entry in A should be zero in B

Definition at line 443 of file facSparseHensel.h.

444 {
445  if (A.size() != B.size())
446  return false;
447  int n= A.size();
448  for (int i= 0; i < n; i++)
449  {
450  if (!B[i].isZero())
451  {
452  if (A[i].isZero())
453  {
454  A[i]= B[i];
455  B[i]= 0;
456  }
457  else if (A[i] == B[i])
458  B[i]= 0;
459  else
460  return false;
461  }
462  }
463  return true;
464 }
int size() const
Definition: ftmpl_array.cc:92
int i
Definition: cfEzgcd.cc:123
bool isZero(const CFArray &A)
checks if entries of A are zero
CFList normalize ( const CFList L,
const CFList normalizingFactor 
)
inline

normalize entries in L with normalizingFactor

Definition at line 555 of file facSparseHensel.h.

556 {
557  CFList result;
558  CFListIterator j= normalizingFactor;
559  for (CFListIterator i= L; i.hasItem(); i++, j++)
560  result.append (i.getItem() / j.getItem());
561  return result;
562 }
int j
Definition: myNF.cc:70
int i
Definition: cfEzgcd.cc:123
T & getItem() const
Definition: ftmpl_list.cc:431
void append(const T &)
Definition: ftmpl_list.cc:256
return result
Definition: facAbsBiFact.cc:76
CanonicalForm patch ( const CanonicalForm F1,
const CanonicalForm F2,
const CanonicalForm eval 
)
inline

patch together F1 and F2 and normalize by a power of eval F1 and F2 are assumed to be bivariate with one variable having level 1

Definition at line 577 of file facSparseHensel.h.

579 {
580  CanonicalForm result= F1;
581  if (F2.level() != 1 && !F2.inCoeffDomain())
582  {
583  int d= degree (F2);
584  result *= power (F2.mvar(), d);
585  result /= power (eval, d);
586  }
587  return result;
588 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
bool inCoeffDomain() const
factory&#39;s main class
Definition: canonicalform.h:75
int level() const
level() returns the level of CO.
int degree(const CanonicalForm &f)
return result
Definition: facAbsBiFact.cc:76
void quickSort ( int  lo,
int  hi,
CFArray A,
int  l 
)
inline

quick sort helper function

Definition at line 85 of file facSparseHensel.h.

86 {
87  int i= lo, j= hi;
88  CanonicalForm tmp= A[(lo+hi)/2];
89  while (i <= j)
90  {
91  if (l > 0)
92  {
93  while (comp (A [i], tmp, l) < 0 && i < hi) i++;
94  while (comp (tmp, A[j], l) < 0 && j > lo) j--;
95  }
96  else
97  {
98  while (comp (A [i], tmp) < 0 && i < hi) i++;
99  while (comp (tmp, A[j]) < 0 && j > lo) j--;
100  }
101  if (i <= j)
102  {
103  swap (A, i, j);
104  i++;
105  j--;
106  }
107  }
108  if (lo < j) quickSort (lo, j, A, l);
109  if (i < hi) quickSort (i, hi, A, l);
110 }
factory&#39;s main class
Definition: canonicalform.h:75
int comp(const CanonicalForm &A, const CanonicalForm &B)
compare polynomials
int j
Definition: myNF.cc:70
void quickSort(int lo, int hi, CFArray &A, int l)
quick sort helper function
void swap(CFArray &A, int i, int j)
swap entry i and j in A
int i
Definition: cfEzgcd.cc:123
int l
Definition: cfEzgcd.cc:94
int search ( const CFArray A,
const CanonicalForm F,
int  i,
int  j 
)
inline

search for F in A between index i and j

Definition at line 566 of file facSparseHensel.h.

567 {
568  for (; i < j; i++)
569  if (A[i] == F)
570  return i;
571  return -1;
572 }
int j
Definition: myNF.cc:70
int i
Definition: cfEzgcd.cc:123
CanonicalForm simplify ( const CanonicalForm A,
int  level 
)
inline

simplify A if possible, i.e. A consists of 2 terms and contains only one variable of level greater or equal than level

Definition at line 390 of file facSparseHensel.h.

391 {
392  CanonicalForm F= 0;
393  if (size (A, A.level()) == 2)
394  {
395  CanonicalForm C= getVars (A);
396  if ((C/C.mvar()).level() < level)
397  {
398  CanonicalForm B= LC (A);
399  if (B.level() < level)
400  {
401  CanonicalForm quot;
402  if (fdivides (B, A, quot))
403  F= -tailcoeff (quot);
404  }
405  }
406  }
407  return F;
408 }
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
int level(const CanonicalForm &f)
factory&#39;s main class
Definition: canonicalform.h:75
int level() const
level() returns the level of CO.
CanonicalForm getVars(const CanonicalForm &f)
CanonicalForm getVars ( const CanonicalForm & f )
Definition: cf_ops.cc:350
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
b *CanonicalForm B
Definition: facBivar.cc:51
CanonicalForm tailcoeff(const CanonicalForm &f)
CanonicalForm LC(const CanonicalForm &f)
bool simplify ( CFArray A,
CFArray B,
int  level 
)
inline

if possible simplify A as described above and store result in B

Definition at line 412 of file facSparseHensel.h.

413 {
414  int n= A.size();
416  int index;
417  for (int i= 0; i < n; i++)
418  {
419  if (!A[i].isZero())
420  {
421  f= simplify (A[i], level);
422  if (!f.isZero())
423  {
424  index= A[i].level() - level;
425  if (index < 0 || index >= B.size())
426  return false;
427  if (!B[index].isZero() && B[index] != f)
428  return false;
429  else if (B[index].isZero())
430  {
431  B[index]= f;
432  A[i]= 0;
433  }
434  }
435  }
436  }
437  return true;
438 }
int level(const CanonicalForm &f)
int size() const
Definition: ftmpl_array.cc:92
factory&#39;s main class
Definition: canonicalform.h:75
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
CanonicalForm simplify(const CanonicalForm &A, int level)
simplify A if possible, i.e. A consists of 2 terms and contains only one variable of level greater or...
FILE * f
Definition: checklibs.c:7
int i
Definition: cfEzgcd.cc:123
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
bool isZero(const CFArray &A)
checks if entries of A are zero
void sort ( CFArray A,
int  l = 0 
)
inline

quick sort A

Definition at line 114 of file facSparseHensel.h.

115 {
116  quickSort (0, A.size() - 1, A, l);
117 }
int size() const
Definition: ftmpl_array.cc:92
void quickSort(int lo, int hi, CFArray &A, int l)
quick sort helper function
#define A
Definition: sirandom.c:23
int l
Definition: cfEzgcd.cc:94
CFList sparseHeuristic ( const CanonicalForm A,
const CFList biFactors,
CFList *&  moreBiFactors,
const CFList evaluation,
int  minFactorsLength 
)

sparse heuristic which patches together bivariate factors of A wrt. different second variables by their univariate images

Returns
sparseHeuristic returns a list of found factors of A
Parameters
[in]Apolynomial to be factored
[in]biFactorsbivariate factors of A where the second variable has level 2
[in]moreBiFactorsmore bivariate factorizations wrt. different second variables
[in]evaluationevaluation point
[in]minFactorsLengthminimal length of bivariate factorizations

Definition at line 155 of file facSparseHensel.cc.

158 {
159  int j= A.level() - 1;
160  int i;
161 
162  //initialize storage
163  CFArray *** storeFactors= new CFArray** [j];
164  for (i= 0; i < j; i++)
165  storeFactors [i]= new CFArray* [2];
166 
167  CFArray eval= CFArray (j);
168  i= j - 1;
169  for (CFListIterator iter= evaluation; iter.hasItem(); iter++,i--)
170  eval[i]= iter.getItem();
171  storeFactors [0] [0]= new CFArray [minFactorsLength];
172  storeFactors [0] [1]= new CFArray [minFactorsLength];
173  for (i= 1; i < j; i++)
174  {
175  storeFactors[i] [0]= new CFArray [minFactorsLength];
176  storeFactors[i] [1]= new CFArray [minFactorsLength];
177  }
178  //
179 
180  CFList * normalizingFactors= new CFList [j];
181  CFList uniFactors;
182  normalizingFactors [0]= findNormalizingFactor1 (biFactors,
183  evaluation.getLast(), uniFactors);
184  for (i= j - 1; i > 0; i--)
185  {
186  if (moreBiFactors[i-1].length() != minFactorsLength)
187  {
188  moreBiFactors[i-1]=
189  recombination (moreBiFactors [i-1], uniFactors, 1,
190  moreBiFactors[i-1].length()-uniFactors.length()+1,
191  eval[i], Variable (i + 2)
192  );
193  }
194  normalizingFactors [i]= findNormalizingFactor2 (moreBiFactors [i - 1],
195  eval[i], uniFactors);
196  }
197 
198  CFList tmp;
199  tmp= normalize (biFactors, normalizingFactors[0]);
200  getTerms2 (tmp, storeFactors [0] [0]);
201  storeFactors [0] [1]= evaluate (storeFactors [0] [0], minFactorsLength,
202  evaluation.getLast(), Variable (2));
203  for (i= j - 1; i > 0; i--)
204  {
205  tmp= normalize (moreBiFactors [i-1], normalizingFactors [i]);
206  getTerms2 (tmp, storeFactors [i] [0]);
207  storeFactors [i] [1]= evaluate (storeFactors [i] [0], minFactorsLength,
208  eval[i], Variable (i + 2));
209  }
210 
211 
212  int k, l, m, mm, count, sizeOfUniFactors= 0;
213  int*** seperator= new int** [j];
214  Variable x= Variable (1);
215 
216  for (i= 0; i < j; i++)
217  seperator [i]= new int* [minFactorsLength];
218  for (k= 0; k < minFactorsLength; k++)
219  {
220  for (i= 0; i < j; i++)
221  {
222  count= 0;
223  for (l= 0; l < storeFactors [i][0][k].size() - 1; l++)
224  {
225  if (degree (storeFactors[i][0][k][l], x) <
226  degree (storeFactors[i][0][k][l+1], x))
227  count++;
228  }
229  if (i == 0)
230  sizeOfUniFactors= count;
231  else if (sizeOfUniFactors != count)
232  {
233  for (m= 0; m < j; m++)
234  {
235  delete [] storeFactors [m] [0];
236  delete [] storeFactors [m] [1];
237  delete [] storeFactors [m];
238  for (mm= 0; mm < k; mm++)
239  delete [] seperator [m][mm];
240  delete [] seperator [m];
241  }
242  delete [] storeFactors;
243  delete [] seperator;
244  return CFList();
245  }
246  seperator [i][k]= new int [count + 3];
247  seperator [i][k][0]= count + 1;
248  seperator [i][k][1]= 0;
249  count= 2;
250  for (l= 0; l < storeFactors [i][0][k].size() - 1; l++)
251  {
252  if (degree (storeFactors[i][0][k][l], x) <
253  degree (storeFactors[i][0][k][l+1], x))
254  {
255  seperator[i][k][count]=l + 1;
256  count++;
257  }
258  }
259  seperator [i][k][count]= storeFactors[i][0][k].size();
260  }
261  }
262 
263  CanonicalForm tmp1, factor, quot;
264  CanonicalForm B= A;
265  CFList result;
266  int maxTerms, n, index1, index2, mmm, found, columns, oneCount;
267  int ** mat;
268 
269  for (k= 0; k < minFactorsLength; k++)
270  {
271  factor= 0;
272  sizeOfUniFactors= seperator [0][k][0];
273  for (n= 1; n <= sizeOfUniFactors; n++)
274  {
275  columns= 0;
276  maxTerms= 1;
277  index1= j - 1;
278  for (i= j - 1; i >= 0; i--)
279  {
280  if (maxTerms < seperator[i][k][n+1]-seperator[i][k][n])
281  {
282  maxTerms= seperator[i][k][n + 1]-seperator[i][k][n];
283  index1= i;
284  }
285  }
286  for (i= j - 1; i >= 0; i--)
287  {
288  if (i == index1)
289  continue;
290  columns += seperator [i][k][n+1]-seperator[i][k][n];
291  }
292  mat= new int *[maxTerms];
293  mm= 0;
294  for (m= seperator[index1][k][n]; m < seperator[index1][k][n+1]; m++, mm++)
295  {
296  tmp1= storeFactors [index1][1][k][m];
297  mat[mm]= new int [columns];
298  for (i= 0; i < columns; i++)
299  mat[mm][i]= 0;
300  index2= 0;
301  for (i= j - 1; i >= 0; i--)
302  {
303  if (i == index1)
304  continue;
305  found= -1;
306  if ((found= search (storeFactors[i][1][k], tmp1,
307  seperator[i][k][n], seperator[i][k][n+1])) >= 0)
308  mat[mm][index2 + found - seperator [i][k][n]]= 1;
309  index2 += seperator [i][k][n+1]-seperator[i][k][n];
310  }
311  }
312 
313  index2= 0;
314  for (i= j - 1; i >= 0; i--)
315  {
316  if (i == index1)
317  continue;
318  oneCount= 0;
319  for (mm= 0; mm < seperator [i][k][n + 1] - seperator [i][k][n]; mm++)
320  {
321  for (m= 0; m < maxTerms; m++)
322  {
323  if (mat[m][mm+index2] == 1)
324  oneCount++;
325  }
326  }
327  if (oneCount == seperator [i][k][n+1]-seperator[i][k][n] - 1)
328  {
329  for (mm= 0; mm < seperator [i][k][n+1]-seperator[i][k][n]; mm++)
330  {
331  oneCount= 0;
332  for (m= 0; m < maxTerms; m++)
333  if (mat[m][mm+index2] == 1)
334  oneCount++;
335  if (oneCount > 0)
336  continue;
337  for (m= 0; m < maxTerms; m++)
338  {
339  oneCount= 0;
340  for (mmm= 0; mmm < seperator[i][k][n+1]-seperator[i][k][n]; mmm++)
341  {
342  if (mat[m][mmm+index2] == 1)
343  oneCount++;
344  }
345  if (oneCount > 0)
346  continue;
347  mat[m][mm+index2]= 1;
348  }
349  }
350  }
351  index2 += seperator [i][k][n+1] - seperator [i][k][n];
352  }
353 
354  //read off solution
355  mm= 0;
356  for (m= seperator[index1][k][n]; m < seperator[index1][k][n+1]; m++, mm++)
357  {
358  tmp1= storeFactors [index1][0][k][m];
359  index2= 0;
360  for (i= j - 1; i > -1; i--)
361  {
362  if (i == index1)
363  continue;
364  for (mmm= 0; mmm < seperator [i][k][n+1]-seperator[i][k][n]; mmm++)
365  if (mat[mm][mmm+index2] == 1)
366  tmp1= patch (tmp1, storeFactors[i][0][k][seperator[i][k][n]+mmm],
367  eval[i]);
368  index2 += seperator [i][k][n+1]-seperator[i][k][n];
369  }
370  factor += tmp1;
371  }
372 
373  for (m= 0; m < maxTerms; m++)
374  delete [] mat [m];
375  delete [] mat;
376  }
377 
378  if (fdivides (factor, B, quot))
379  {
380  result.append (factor);
381  B= quot;
382  if (result.length() == biFactors.length() - 1)
383  {
384  result.append (quot);
385  break;
386  }
387  }
388  }
389 
390  //delete
391  for (i= 0; i < j; i++)
392  {
393  delete [] storeFactors [i] [0];
394  delete [] storeFactors [i] [1];
395  delete [] storeFactors [i];
396  for (k= 0; k < minFactorsLength; k++)
397  delete [] seperator [i][k];
398  delete [] seperator [i];
399  }
400  delete [] seperator;
401  delete [] storeFactors;
402  //
403 
404  return result;
405 }
int status int void size_t count
Definition: si_signals.h:59
List< CanonicalForm > CFList
CFList findNormalizingFactor1(const CFList &biFactors, const CanonicalForm &evalPoint, CFList &uniFactors)
find normalizing factors for biFactors and build monic univariate factors from biFactors ...
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition: syz3.cc:1028
factory&#39;s class for variables
Definition: factory.h:115
int size() const
Definition: ftmpl_array.cc:92
CFFListIterator iter
Definition: facAbsBiFact.cc:54
CFList int & minFactorsLength
[in,out] minimal length of < bivariate factors
Definition: facFactorize.h:31
factory&#39;s main class
Definition: canonicalform.h:75
Array< CanonicalForm > CFArray
int k
Definition: cfEzgcd.cc:93
int level() const
level() returns the level of CO.
bool found
Definition: facFactorize.cc:56
CanonicalForm patch(const CanonicalForm &F1, const CanonicalForm &F2, const CanonicalForm &eval)
patch together F1 and F2 and normalize by a power of eval F1 and F2 are assumed to be bivariate with ...
int j
Definition: myNF.cc:70
int search(const CFArray &A, const CanonicalForm &F, int i, int j)
search for F in A between index i and j
#define A
Definition: sirandom.c:23
CFList & eval
Definition: facFactorize.cc:48
int m
Definition: cfEzgcd.cc:119
int length() const
Definition: ftmpl_list.cc:273
int i
Definition: cfEzgcd.cc:123
CFArray evaluate(const CFArray &A, const CFList &evalPoints)
Definition: cfModGcd.cc:1972
CFList recombination(const CFList &factors1, const CFList &factors2, int s, int thres, const CanonicalForm &evalPoint, const Variable &x)
recombination of bivariate factors factors1 s. t. the result evaluated at evalPoint coincides with fa...
CanonicalForm factor
Definition: facAbsFact.cc:101
CFArray getTerms2(const CanonicalForm &F)
get terms of F wrt. Variable (1)
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
T & getItem() const
Definition: ftmpl_list.cc:431
b *CanonicalForm B
Definition: facBivar.cc:51
CFList tmp1
Definition: facFqBivar.cc:70
T getLast() const
Definition: ftmpl_list.cc:309
Variable x
Definition: cfModGcd.cc:4023
void append(const T &)
Definition: ftmpl_list.cc:256
int degree(const CanonicalForm &f)
CFList findNormalizingFactor2(CFList &biFactors, const CanonicalForm &evalPoint, const CFList &uniFactors)
find normalizing factors for biFactors and sort biFactors s.t. the returned biFactors evaluated at ev...
return result
Definition: facAbsBiFact.cc:76
int l
Definition: cfEzgcd.cc:94
void strip ( CFArray F,
CFArray G,
int  level 
)
inline

strip off those parts of entries in F whose level is less than or equal than level and store the stripped off parts in G

Definition at line 310 of file facSparseHensel.h.

311 {
312  int n, m, i, j;
314  m= F.size();
315  G= CFArray (m);
316  for (j= 0; j < m; j++)
317  {
318  g= 1;
319  for (i= 1; i <= level; i++)
320  {
321  if ((n= degree (F[j],i)) > 0)
322  g *= power (Variable (i), n);
323  }
324  F[j] /= g;
325  G[j]= g;
326  }
327 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
int level(const CanonicalForm &f)
factory&#39;s class for variables
Definition: factory.h:115
int size() const
Definition: ftmpl_array.cc:92
factory&#39;s main class
Definition: canonicalform.h:75
Array< CanonicalForm > CFArray
g
Definition: cfModGcd.cc:4031
int j
Definition: myNF.cc:70
int m
Definition: cfEzgcd.cc:119
int i
Definition: cfEzgcd.cc:123
int degree(const CanonicalForm &f)
void strip ( CFArray F,
int  level 
)
inline

s.a. stripped off parts are not returned

Definition at line 331 of file facSparseHensel.h.

332 {
333  int n, m, i;
335  m= F.size();
336  for (int j= 0; j < m; j++)
337  {
338  g= 1;
339  for (i= 1; i <= level; i++)
340  {
341  if ((n= degree (F[j],i)) > 0)
342  g *= power (Variable (i), n);
343  }
344  F[j] /= g;
345  }
346 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
int level(const CanonicalForm &f)
factory&#39;s class for variables
Definition: factory.h:115
int size() const
Definition: ftmpl_array.cc:92
factory&#39;s main class
Definition: canonicalform.h:75
g
Definition: cfModGcd.cc:4031
int j
Definition: myNF.cc:70
int m
Definition: cfEzgcd.cc:119
int i
Definition: cfEzgcd.cc:123
int degree(const CanonicalForm &f)
void swap ( CFArray A,
int  i,
int  j 
)
inline

swap entry i and j in A

Definition at line 76 of file facSparseHensel.h.

77 {
78  CanonicalForm tmp= A[i];
79  A[i]= A[j];
80  A[j]= tmp;
81 }
factory&#39;s main class
Definition: canonicalform.h:75
int j
Definition: myNF.cc:70
int i
Definition: cfEzgcd.cc:123