My Project  UNKNOWN_GIT_VERSION
Functions
facSparseHensel.h File Reference
#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 }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

◆ 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]F[in] polynomial to be factored
[in]factors[in] factors of F lifted to level
[in]level[in] level of lifted factors
[in]leadingCoeffs[in] leading coefficients of factors
[in,out]result[in,out] result

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 }

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

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

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

◆ 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]A[in] polynomial to be factored
[in]biFactors[in] bivariate factors of A where the second variable has level 2
[in]moreBiFactors[in] more bivariate factorizations wrt. different second variables
[in]evaluation[in] evaluation point
[in]minFactorsLength[in] minimal 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;
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  delete [] normalizingFactors;
245  return CFList();
246  }
247  seperator [i][k]= new int [count + 3];
248  seperator [i][k][0]= count + 1;
249  seperator [i][k][1]= 0;
250  count= 2;
251  for (l= 0; l < storeFactors [i][0][k].size() - 1; l++)
252  {
253  if (degree (storeFactors[i][0][k][l], x) <
254  degree (storeFactors[i][0][k][l+1], x))
255  {
256  seperator[i][k][count]=l + 1;
257  count++;
258  }
259  }
260  seperator [i][k][count]= storeFactors[i][0][k].size();
261  }
262  }
263 
264  CanonicalForm tmp1, factor, quot;
265  CanonicalForm B= A;
266  CFList result;
267  int maxTerms, n, index1, index2, mmm, found, columns, oneCount;
268  int ** mat;
269 
270  for (k= 0; k < minFactorsLength; k++)
271  {
272  factor= 0;
273  sizeOfUniFactors= seperator [0][k][0];
274  for (n= 1; n <= sizeOfUniFactors; n++)
275  {
276  columns= 0;
277  maxTerms= 1;
278  index1= j - 1;
279  for (i= j - 1; i >= 0; i--)
280  {
281  if (maxTerms < seperator[i][k][n+1]-seperator[i][k][n])
282  {
283  maxTerms= seperator[i][k][n + 1]-seperator[i][k][n];
284  index1= i;
285  }
286  }
287  for (i= j - 1; i >= 0; i--)
288  {
289  if (i == index1)
290  continue;
291  columns += seperator [i][k][n+1]-seperator[i][k][n];
292  }
293  mat= new int *[maxTerms];
294  mm= 0;
295  for (m= seperator[index1][k][n]; m < seperator[index1][k][n+1]; m++, mm++)
296  {
297  tmp1= storeFactors [index1][1][k][m];
298  mat[mm]= new int [columns];
299  for (i= 0; i < columns; i++)
300  mat[mm][i]= 0;
301  index2= 0;
302  for (i= j - 1; i >= 0; i--)
303  {
304  if (i == index1)
305  continue;
306  found= -1;
307  if ((found= search (storeFactors[i][1][k], tmp1,
308  seperator[i][k][n], seperator[i][k][n+1])) >= 0)
309  mat[mm][index2 + found - seperator [i][k][n]]= 1;
310  index2 += seperator [i][k][n+1]-seperator[i][k][n];
311  }
312  }
313 
314  index2= 0;
315  for (i= j - 1; i >= 0; i--)
316  {
317  if (i == index1)
318  continue;
319  oneCount= 0;
320  for (mm= 0; mm < seperator [i][k][n + 1] - seperator [i][k][n]; mm++)
321  {
322  for (m= 0; m < maxTerms; m++)
323  {
324  if (mat[m][mm+index2] == 1)
325  oneCount++;
326  }
327  }
328  if (oneCount == seperator [i][k][n+1]-seperator[i][k][n] - 1)
329  {
330  for (mm= 0; mm < seperator [i][k][n+1]-seperator[i][k][n]; mm++)
331  {
332  oneCount= 0;
333  for (m= 0; m < maxTerms; m++)
334  if (mat[m][mm+index2] == 1)
335  oneCount++;
336  if (oneCount > 0)
337  continue;
338  for (m= 0; m < maxTerms; m++)
339  {
340  oneCount= 0;
341  for (mmm= 0; mmm < seperator[i][k][n+1]-seperator[i][k][n]; mmm++)
342  {
343  if (mat[m][mmm+index2] == 1)
344  oneCount++;
345  }
346  if (oneCount > 0)
347  continue;
348  mat[m][mm+index2]= 1;
349  }
350  }
351  }
352  index2 += seperator [i][k][n+1] - seperator [i][k][n];
353  }
354 
355  //read off solution
356  mm= 0;
357  for (m= seperator[index1][k][n]; m < seperator[index1][k][n+1]; m++, mm++)
358  {
359  tmp1= storeFactors [index1][0][k][m];
360  index2= 0;
361  for (i= j - 1; i > -1; i--)
362  {
363  if (i == index1)
364  continue;
365  for (mmm= 0; mmm < seperator [i][k][n+1]-seperator[i][k][n]; mmm++)
366  if (mat[mm][mmm+index2] == 1)
367  tmp1= patch (tmp1, storeFactors[i][0][k][seperator[i][k][n]+mmm],
368  eval[i]);
369  index2 += seperator [i][k][n+1]-seperator[i][k][n];
370  }
371  factor += tmp1;
372  }
373 
374  for (m= 0; m < maxTerms; m++)
375  delete [] mat [m];
376  delete [] mat;
377  }
378 
379  if (fdivides (factor, B, quot))
380  {
381  result.append (factor);
382  B= quot;
383  if (result.length() == biFactors.length() - 1)
384  {
385  result.append (quot);
386  break;
387  }
388  }
389  }
390 
391  //delete
392  for (i= 0; i < j; i++)
393  {
394  delete [] storeFactors [i] [0];
395  delete [] storeFactors [i] [1];
396  delete [] storeFactors [i];
397  for (k= 0; k < minFactorsLength; k++)
398  delete [] seperator [i][k];
399  delete [] seperator [i];
400  }
401  delete [] seperator;
402  delete [] storeFactors;
403  delete [] normalizingFactors;
404  //
405 
406  return result;
407 }

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

◆ 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 }
evaluate
CFArray evaluate(const CFArray &A, const CFList &evalPoints)
Definition: cfModGcd.cc:1972
isZero
bool isZero(const CFArray &A)
checks if entries of A are zero
Definition: facSparseHensel.h:468
j
int j
Definition: facHensel.cc:105
f
FILE * f
Definition: checklibs.c:9
k
int k
Definition: cfEzgcd.cc:92
getBiTerms
CFArray getBiTerms(const CanonicalForm &F, int threshold)
get terms of F where F is considered a bivariate poly in Variable(1), Variable (2)
Definition: facSparseHensel.h:236
CFIterator
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
x
Variable x
Definition: cfModGcd.cc:4023
getBiTerms_helper
CFArray getBiTerms_helper(const CanonicalForm &F, const CFMap &M, int threshold)
helper function for getBiTerms
Definition: facSparseHensel.h:202
y
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
result
return result
Definition: facAbsBiFact.cc:76
recombination
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...
Definition: facFqFactorize.cc:2100
CFArray
Array< CanonicalForm > CFArray
Definition: canonicalform.h:390
num
CanonicalForm num(const CanonicalForm &f)
Definition: canonicalform.h:330
search
int search(const CFArray &A, const CanonicalForm &F, int i, int j)
search for F in A between index i and j
Definition: facSparseHensel.h:566
prod
fq_nmod_poly_t prod
Definition: facHensel.cc:95
CFMap
class CFMap
Definition: cf_map.h:84
isEqual
bool isEqual(int *a, int *b, int lower, int upper)
Definition: cfGcdAlgExt.cc:947
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition: canonicalform.cc:1837
length
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:263
g
g
Definition: cfModGcd.cc:4031
level
int level(const CanonicalForm &f)
Definition: canonicalform.h:324
getEquations
CFArray getEquations(const CFArray &A, const CFArray &B)
get equations for LucksWangSparseHeuristic
Definition: facSparseHensel.h:350
getTerms2
CFArray getTerms2(const CanonicalForm &F)
get terms of F wrt. Variable (1)
Definition: facSparseHensel.h:492
getItem
CanonicalForm getItem(const CFList &list, const int &pos)
helper function
Definition: cf_map_ext.cc:49
iter
CFFListIterator iter
Definition: facAbsBiFact.cc:54
CanonicalForm
factory's main class
Definition: canonicalform.h:77
found
bool found
Definition: facFactorize.cc:56
minFactorsLength
CFList int & minFactorsLength
[in,out] minimal length of bivariate factors
Definition: facFactorize.h:33
evaluation
const CanonicalForm int const CFList & evaluation
Definition: facAbsFact.cc:56
getMonoms
CFArray getMonoms(const CanonicalForm &F)
extract monomials of F, parts in algebraic variable are considered coefficients
Definition: cfModGcd.cc:1898
i
int i
Definition: cfEzgcd.cc:125
Lc
CanonicalForm Lc(const CanonicalForm &f)
Definition: canonicalform.h:300
swapvar
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
Array
Definition: ftmpl_array.h:17
ASSERT
#define ASSERT(expression, message)
Definition: cf_assert.h:99
M
#define M
Definition: sirandom.c:24
buf
int status int void * buf
Definition: si_signals.h:59
Array::size
int size() const
Definition: ftmpl_array.cc:92
getVars
CanonicalForm getVars(const CanonicalForm &f)
CanonicalForm getVars ( const CanonicalForm & f )
Definition: cf_ops.cc:350
getTerms
CFArray getTerms(const CanonicalForm &F)
get terms of F
Definition: facSparseHensel.h:167
evalPoint
static void evalPoint(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &FEval, CanonicalForm &GEval, CFGenerator &evalPoint)
Definition: cfModResultant.cc:311
swap
void swap(CFArray &A, int i, int j)
swap entry i and j in A
Definition: facSparseHensel.h:76
size
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
tmp1
CFList tmp1
Definition: facFqBivar.cc:70
eval
CFList & eval
Definition: facFactorize.cc:48
sort
void sort(CFArray &A, int l=0)
quick sort A
Definition: facSparseHensel.h:114
ListIterator::hasItem
int hasItem()
Definition: ftmpl_list.cc:439
fdivides
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
Definition: cf_algorithm.cc:338
patch
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 ...
Definition: facSparseHensel.h:577
tmax
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
simplify
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...
Definition: facSparseHensel.h:390
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition: canonicalform.cc:119
findNormalizingFactor2
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...
Definition: facSparseHensel.h:140
List::length
int length() const
Definition: ftmpl_list.cc:273
factor
CanonicalForm factor
Definition: facAbsFact.cc:101
normalize
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition: syz3.cc:1027
buildPolyFromArray
CanonicalForm buildPolyFromArray(const CFArray &A)
build a poly from entries in A
Definition: facSparseHensel.h:267
Variable
factory's class for variables
Definition: factory.h:117
ListIterator::getItem
T & getItem() const
Definition: ftmpl_list.cc:431
groupTogether
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
Definition: facSparseHensel.h:278
B
b *CanonicalForm B
Definition: facBivar.cc:52
CanonicalForm::mvar
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
Definition: canonicalform.cc:560
quickSort
void quickSort(int lo, int hi, CFArray &A, int l)
quick sort helper function
Definition: facSparseHensel.h:85
LC
CanonicalForm LC(const CanonicalForm &f)
Definition: canonicalform.h:303
findItem
int findItem(const CFList &list, const CanonicalForm &item)
helper function
Definition: cf_map_ext.cc:37
m
int m
Definition: cfEzgcd.cc:121
l
int l
Definition: cfEzgcd.cc:93
CanonicalForm::isUnivariate
bool isUnivariate() const
Definition: canonicalform.cc:152
tailcoeff
CanonicalForm tailcoeff(const CanonicalForm &f)
Definition: canonicalform.h:318
List< CanonicalForm >
CFList
List< CanonicalForm > CFList
Definition: canonicalform.h:388
count
int status int void size_t count
Definition: si_signals.h:59
strip
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...
Definition: facSparseHensel.h:310
H
CanonicalForm H
Definition: facAbsFact.cc:64
comp
int comp(const CanonicalForm &A, const CanonicalForm &B)
compare polynomials
Definition: facSparseHensel.h:25
getTerms
void getTerms(const CanonicalForm &f, const CanonicalForm &t, CFList &result)
get_Terms: Split the polynomial in the containing terms.
Definition: cf_factor.cc:264
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
evaluate
void evaluate(CFArray &A, const CanonicalForm &B, int level)
evaluate every entry of A at B and level level
Definition: facSparseHensel.h:362
A
#define A
Definition: sirandom.c:23
degree
int degree(const CanonicalForm &f)
Definition: canonicalform.h:309
merge
int ** merge(int **points1, int sizePoints1, int **points2, int sizePoints2, int &sizeResult)
Definition: cfNewtonPolygon.cc:230
List::insert
void insert(const T &)
Definition: ftmpl_list.cc:193
ListIterator
Definition: ftmpl_list.h:17
findNormalizingFactor1
CFList findNormalizingFactor1(const CFList &biFactors, const CanonicalForm &evalPoint, CFList &uniFactors)
find normalizing factors for biFactors and build monic univariate factors from biFactors
Definition: facSparseHensel.h:123