My Project
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

◆ buildPolyFromArray()

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 i
Definition: cfEzgcd.cc:132
factory's main class
Definition: canonicalform.h:86
return result
Definition: facAbsBiFact.cc:75
#define A
Definition: sirandom.c:24

◆ comp() [1/2]

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 }
int degree(const CanonicalForm &f)
bool inCoeffDomain() const
int level() const
level() returns the level of CO.
b *CanonicalForm B
Definition: facBivar.cc:52
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)

◆ comp() [2/2]

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)

◆ evaluate() [1/4]

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 }

◆ evaluate() [2/4]

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

◆ evaluate() [3/4]

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 }
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:53
CFList & eval
Definition: facFactorize.cc:47

◆ evaluate() [4/4]

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 }
Array< CanonicalForm > CFArray
int j
Definition: facHensel.cc:110

◆ findNormalizingFactor1()

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 }
CanonicalForm Lc(const CanonicalForm &f)
static void evalPoint(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &FEval, CanonicalForm &GEval, CFGenerator &evalPoint)
void append(const T &)
Definition: ftmpl_list.cc:256

◆ findNormalizingFactor2()

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  {
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 }
int l
Definition: cfEzgcd.cc:100
int findItem(const CFList &list, const CanonicalForm &item)
helper function
Definition: cf_map_ext.cc:41
CanonicalForm getItem(const CFList &list, const int &pos)
helper function
Definition: cf_map_ext.cc:53
T & getItem() const
Definition: ftmpl_list.cc:431
CFFListIterator iter
Definition: facAbsBiFact.cc:53

◆ getBiTerms()

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
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
CanonicalForm FACTORY_PUBLIC swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
class CFMap
Definition: cf_map.h:85
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
bool isUnivariate() const
factory's class for variables
Definition: factory.h:127
CFArray getBiTerms_helper(const CanonicalForm &F, const CFMap &M, int threshold)
helper function for getBiTerms
STATIC_VAR TreeM * G
Definition: janet.cc:31
#define M
Definition: sirandom.c:25

◆ getBiTerms_helper()

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 }
int k
Definition: cfEzgcd.cc:99
Variable x
Definition: cfModGcd.cc:4082
int status int void * buf
Definition: si_signals.h:59

◆ getEquations()

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 }
#define ASSERT(expression, message)
Definition: cf_assert.h:99

◆ getTerms()

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 }
int size() const
Definition: ftmpl_array.cc:92
CFArray getTerms(const CanonicalForm &F)
get terms of F

◆ getTerms2() [1/2]

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 }
void sort(CFArray &A, int l=0)
quick sort A

◆ getTerms2() [2/2]

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 }
CFArray getTerms2(const CanonicalForm &F)
get terms of F wrt. Variable (1)

◆ groupTogether()

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 comp(const CanonicalForm &A, const CanonicalForm &B)
compare polynomials

◆ isEqual()

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 }

◆ isZero()

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 }

◆ LucksWangSparseHeuristic()

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  int si=termsF.size();
32  int fl=factors.length();
33  //printf("size:%d, length=%d, char=%d\n",si,fl,getCharacteristic());
34  if ((si > threshold)
35  || (si <= fl)
36  )
37  return 0;
38  sort (termsF, level);
39 
40  CFArray* monoms= new CFArray [factors.length()];
41  int i= 0;
42  int num= 0;
43  for (CFListIterator iter= factors; iter.hasItem(); iter++, i++)
44  {
45  monoms[i]= getTerms (iter.getItem());
46  num += monoms [i].size();
47  sort (monoms [i]);
48  }
49 
50  i= 0;
51  CFArray* monomsLead= new CFArray [leadingCoeffs.length()];
52  for (CFListIterator iter= leadingCoeffs; iter.hasItem(); iter++, i++)
53  {
54  monomsLead[i]= getTerms (iter.getItem());
55  sort (monomsLead [i]);
56  groupTogether (monomsLead [i], level);
57  strip (monomsLead [i], level);
58  }
59 
60  CFArray solution= CFArray (num);
61  int k, d, count, j= F.level() + 1;
62  num= 0;
63  i= 0;
64  for (CFListIterator iter= factors; iter.hasItem(); i++, iter++)
65  {
66  d= degree (iter.getItem(), 1);
67  count= 0;
68  for (k= 0; k < monoms[i].size(); k++, j++, num++)
69  {
70  monoms [i][k] *= Variable (j);
71  if (degree (monoms[i][k], 1) == d)
72  {
73  solution[num]= monomsLead [i] [count];
74  count++;
75  }
76  }
77  }
78 
79  delete [] monomsLead;
80 
81  CFList tmp;
82  CFArray* stripped2= new CFArray [factors.length()];
83  for (i= factors.length() - 1; i > -1; i--)
84  {
85  tmp.insert (buildPolyFromArray (monoms [i]));
86  strip (monoms[i], stripped2 [i], level);
87  }
88  delete [] monoms;
89 
90  CanonicalForm H= prod (tmp);
91  CFArray monomsH= getMonoms (H);
92  sort (monomsH,F.level());
93 
94  groupTogether (monomsH, F.level());
95 
96  if (monomsH.size() != termsF.size())
97  {
98  delete [] stripped2;
99  return 0;
100  }
101 
102  CFArray strippedH;
103  strip (monomsH, strippedH, level);
104  CFArray strippedF;
105  strip (termsF, strippedF, level);
106 
107  if (!isEqual (strippedH, strippedF))
108  {
109  delete [] stripped2;
110  return 0;
111  }
112 
113  CFArray A= getEquations (monomsH, termsF);
114  CFArray startingSolution= solution;
115  CFArray newSolution= CFArray (solution.size());
116  result= CFList();
117  do
118  {
119  evaluate (A, solution, F.level() + 1);
120  if (isZero (A))
121  break;
122  if (!simplify (A, newSolution, F.level() + 1))
123  {
124  delete [] stripped2;
125  return 0;
126  }
127  if (isZero (newSolution))
128  break;
129  if (!merge (solution, newSolution))
130  break;
131  } while (1);
132 
133  if (isEqual (startingSolution, solution))
134  {
135  delete [] stripped2;
136  return 0;
137  }
139  num= 0;
140  for (i= 0; i < factors.length(); i++)
141  {
142  k= stripped2[i].size();
143  factor= 0;
144  for (j= 0; j < k; j++, num++)
145  {
146  if (solution [num].isZero())
147  continue;
148  factor += solution [num]*stripped2[i][j];
149  }
150  result.append (factor);
151  }
152 
153  delete [] stripped2;
154  if (result.length() > 0)
155  return 1;
156  return 0;
157 }
CanonicalForm num(const CanonicalForm &f)
List< CanonicalForm > CFList
bool isEqual(int *a, int *b, int lower, int upper)
Definition: cfGcdAlgExt.cc:946
CFArray getMonoms(const CanonicalForm &F)
extract monomials of F, parts in algebraic variable are considered coefficients
Definition: cfModGcd.cc:1957
CFArray evaluate(const CFArray &A, const CFList &evalPoints)
Definition: cfModGcd.cc:2031
int ** merge(int **points1, int sizePoints1, int **points2, int sizePoints2, int &sizeResult)
void getTerms(const CanonicalForm &f, const CanonicalForm &t, CFList &result)
get_Terms: Split the polynomial in the containing terms.
Definition: cf_factor.cc:279
int length() const
Definition: ftmpl_list.cc:273
void insert(const T &)
Definition: ftmpl_list.cc:193
CanonicalForm factor
Definition: facAbsFact.cc:97
CanonicalForm H
Definition: facAbsFact.cc:60
fq_nmod_poly_t prod
Definition: facHensel.cc:100
CanonicalForm buildPolyFromArray(const CFArray &A)
build a poly from entries in A
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
CFArray getBiTerms(const CanonicalForm &F, int threshold)
get terms of F where F is considered a bivariate poly in Variable(1), Variable (2)
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...
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
int status int void size_t count
Definition: si_signals.h:59

◆ merge()

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 }

◆ normalize()

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 }

◆ patch()

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 }

◆ quickSort()

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

◆ search()

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 }

◆ simplify() [1/2]

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 }
FILE * f
Definition: checklibs.c:9
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592

◆ simplify() [2/2]

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 }
CanonicalForm getVars(const CanonicalForm &f)
CanonicalForm getVars ( const CanonicalForm & f )
Definition: cf_ops.cc:350
CanonicalForm tailcoeff(const CanonicalForm &f)
CanonicalForm LC(const CanonicalForm &f)
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )

◆ sort()

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 }

◆ sparseHeuristic()

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 160 of file facSparseHensel.cc.

163 {
164  int j= A.level() - 1;
165  int i;
166 
167  //initialize storage
168  CFArray *** storeFactors= new CFArray** [j];
169  for (i= 0; i < j; i++)
170  storeFactors [i]= new CFArray* [2];
171 
172  CFArray eval= CFArray (j);
173  i= j - 1;
175  eval[i]= iter.getItem();
176  storeFactors [0] [0]= new CFArray [minFactorsLength];
177  storeFactors [0] [1]= new CFArray [minFactorsLength];
178  for (i= 1; i < j; i++)
179  {
180  storeFactors[i] [0]= new CFArray [minFactorsLength];
181  storeFactors[i] [1]= new CFArray [minFactorsLength];
182  }
183  //
184 
185  CFList * normalizingFactors= new CFList [j];
186  CFList uniFactors;
187  normalizingFactors [0]= findNormalizingFactor1 (biFactors,
188  evaluation.getLast(), uniFactors);
189  for (i= j - 1; i > 0; i--)
190  {
191  if (moreBiFactors[i-1].length() != minFactorsLength)
192  {
193  moreBiFactors[i-1]=
194  recombination (moreBiFactors [i-1], uniFactors, 1,
195  moreBiFactors[i-1].length()-uniFactors.length()+1,
196  eval[i], Variable (i + 2)
197  );
198  }
199  normalizingFactors [i]= findNormalizingFactor2 (moreBiFactors [i - 1],
200  eval[i], uniFactors);
201  }
202 
203  CFList tmp;
204  tmp= normalize (biFactors, normalizingFactors[0]);
205  getTerms2 (tmp, storeFactors [0] [0]);
206  storeFactors [0] [1]= evaluate (storeFactors [0] [0], minFactorsLength,
207  evaluation.getLast(), Variable (2));
208  for (i= j - 1; i > 0; i--)
209  {
210  tmp= normalize (moreBiFactors [i-1], normalizingFactors [i]);
211  getTerms2 (tmp, storeFactors [i] [0]);
212  storeFactors [i] [1]= evaluate (storeFactors [i] [0], minFactorsLength,
213  eval[i], Variable (i + 2));
214  }
215 
216 
217  int k, l, m, mm, count, sizeOfUniFactors= 0;
218  int*** seperator= new int** [j];
219  Variable x= Variable (1);
220 
221  for (i= 0; i < j; i++)
222  seperator [i]= new int* [minFactorsLength];
223  for (k= 0; k < minFactorsLength; k++)
224  {
225  for (i= 0; i < j; i++)
226  {
227  count= 0;
228  for (l= 0; l < storeFactors [i][0][k].size() - 1; l++)
229  {
230  if (degree (storeFactors[i][0][k][l], x) <
231  degree (storeFactors[i][0][k][l+1], x))
232  count++;
233  }
234  if (i == 0)
235  sizeOfUniFactors= count;
236  else if (sizeOfUniFactors != count)
237  {
238  for (m= 0; m < j; m++)
239  {
240  delete [] storeFactors [m] [0];
241  delete [] storeFactors [m] [1];
242  delete [] storeFactors [m];
243  for (mm= 0; mm < k; mm++)
244  delete [] seperator [m][mm];
245  delete [] seperator [m];
246  }
247  delete [] storeFactors;
248  delete [] seperator;
249  delete [] normalizingFactors;
250  return CFList();
251  }
252  seperator [i][k]= new int [count + 3];
253  seperator [i][k][0]= count + 1;
254  seperator [i][k][1]= 0;
255  count= 2;
256  for (l= 0; l < storeFactors [i][0][k].size() - 1; l++)
257  {
258  if (degree (storeFactors[i][0][k][l], x) <
259  degree (storeFactors[i][0][k][l+1], x))
260  {
261  seperator[i][k][count]=l + 1;
262  count++;
263  }
264  }
265  seperator [i][k][count]= storeFactors[i][0][k].size();
266  }
267  }
268 
269  CanonicalForm tmp1, factor, quot;
270  CanonicalForm B= A;
271  CFList result;
272  int maxTerms, n, index1, index2, mmm, found, columns, oneCount;
273  int ** mat;
274 
275  for (k= 0; k < minFactorsLength; k++)
276  {
277  factor= 0;
278  sizeOfUniFactors= seperator [0][k][0];
279  for (n= 1; n <= sizeOfUniFactors; n++)
280  {
281  columns= 0;
282  maxTerms= 1;
283  index1= j - 1;
284  for (i= j - 1; i >= 0; i--)
285  {
286  if (maxTerms < seperator[i][k][n+1]-seperator[i][k][n])
287  {
288  maxTerms= seperator[i][k][n + 1]-seperator[i][k][n];
289  index1= i;
290  }
291  }
292  for (i= j - 1; i >= 0; i--)
293  {
294  if (i == index1)
295  continue;
296  columns += seperator [i][k][n+1]-seperator[i][k][n];
297  }
298  mat= new int *[maxTerms];
299  mm= 0;
300  for (m= seperator[index1][k][n]; m < seperator[index1][k][n+1]; m++, mm++)
301  {
302  tmp1= storeFactors [index1][1][k][m];
303  mat[mm]= new int [columns];
304  for (i= 0; i < columns; i++)
305  mat[mm][i]= 0;
306  index2= 0;
307  for (i= j - 1; i >= 0; i--)
308  {
309  if (i == index1)
310  continue;
311  found= -1;
312  if ((found= search (storeFactors[i][1][k], tmp1,
313  seperator[i][k][n], seperator[i][k][n+1])) >= 0)
314  mat[mm][index2 + found - seperator [i][k][n]]= 1;
315  index2 += seperator [i][k][n+1]-seperator[i][k][n];
316  }
317  }
318 
319  index2= 0;
320  for (i= j - 1; i >= 0; i--)
321  {
322  if (i == index1)
323  continue;
324  oneCount= 0;
325  for (mm= 0; mm < seperator [i][k][n + 1] - seperator [i][k][n]; mm++)
326  {
327  for (m= 0; m < maxTerms; m++)
328  {
329  if (mat[m][mm+index2] == 1)
330  oneCount++;
331  }
332  }
333  if (oneCount == seperator [i][k][n+1]-seperator[i][k][n] - 1)
334  {
335  for (mm= 0; mm < seperator [i][k][n+1]-seperator[i][k][n]; mm++)
336  {
337  oneCount= 0;
338  for (m= 0; m < maxTerms; m++)
339  if (mat[m][mm+index2] == 1)
340  oneCount++;
341  if (oneCount > 0)
342  continue;
343  for (m= 0; m < maxTerms; m++)
344  {
345  oneCount= 0;
346  for (mmm= 0; mmm < seperator[i][k][n+1]-seperator[i][k][n]; mmm++)
347  {
348  if (mat[m][mmm+index2] == 1)
349  oneCount++;
350  }
351  if (oneCount > 0)
352  continue;
353  mat[m][mm+index2]= 1;
354  }
355  }
356  }
357  index2 += seperator [i][k][n+1] - seperator [i][k][n];
358  }
359 
360  //read off solution
361  mm= 0;
362  for (m= seperator[index1][k][n]; m < seperator[index1][k][n+1]; m++, mm++)
363  {
364  tmp1= storeFactors [index1][0][k][m];
365  index2= 0;
366  for (i= j - 1; i > -1; i--)
367  {
368  if (i == index1)
369  continue;
370  for (mmm= 0; mmm < seperator [i][k][n+1]-seperator[i][k][n]; mmm++)
371  if (mat[mm][mmm+index2] == 1)
372  tmp1= patch (tmp1, storeFactors[i][0][k][seperator[i][k][n]+mmm],
373  eval[i]);
374  index2 += seperator [i][k][n+1]-seperator[i][k][n];
375  }
376  factor += tmp1;
377  }
378 
379  for (m= 0; m < maxTerms; m++)
380  delete [] mat [m];
381  delete [] mat;
382  }
383 
384  if (fdivides (factor, B, quot))
385  {
386  result.append (factor);
387  B= quot;
388  if (result.length() == biFactors.length() - 1)
389  {
390  result.append (quot);
391  break;
392  }
393  }
394  }
395 
396  //delete
397  for (i= 0; i < j; i++)
398  {
399  delete [] storeFactors [i] [0];
400  delete [] storeFactors [i] [1];
401  delete [] storeFactors [i];
402  for (k= 0; k < minFactorsLength; k++)
403  delete [] seperator [i][k];
404  delete [] seperator [i];
405  }
406  delete [] seperator;
407  delete [] storeFactors;
408  delete [] normalizingFactors;
409  //
410 
411  return result;
412 }
int m
Definition: cfEzgcd.cc:128
const CanonicalForm int const CFList & evaluation
Definition: facAbsFact.cc:52
bool found
Definition: facFactorize.cc:55
CFList int & minFactorsLength
[in,out] minimal length of bivariate factors
Definition: facFactorize.h:33
CFList tmp1
Definition: facFqBivar.cc:72
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...
CFList findNormalizingFactor1(const CFList &biFactors, const CanonicalForm &evalPoint, CFList &uniFactors)
find normalizing factors for biFactors and build monic univariate factors from biFactors
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...
int search(const CFArray &A, const CanonicalForm &F, int i, int j)
search for F in A between index i and j
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 ...
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:257
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition: syz3.cc:1027

◆ strip() [1/2]

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 }
g
Definition: cfModGcd.cc:4090

◆ strip() [2/2]

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 }

◆ swap()

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 }