My Project  UNKNOWN_GIT_VERSION
Functions
facSparseHensel.cc File Reference

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

#include "config.h"
#include "cf_assert.h"
#include "facSparseHensel.h"
#include "cf_algorithm.h"
#include "cfModGcd.h"
#include "facFqFactorize.h"

Go to the source code of this file.

Functions

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 implements functions for sparse heuristic Hensel lifting.

ABSTRACT: "A fast implementation of polynomial factorization" by M. Lucks and "Effective polynomial computation" by R. Zippel

Author
Martin Lee

Definition in file facSparseHensel.cc.

Function Documentation

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

◆ 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 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 }
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
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
x
Variable x
Definition: cfModGcd.cc:4023
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
isEqual
bool isEqual(int *a, int *b, int lower, int upper)
Definition: cfGcdAlgExt.cc:947
length
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:263
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
iter
CFFListIterator iter
Definition: facAbsBiFact.cc:54
CanonicalForm
factory's main class
Definition: canonicalform.h:83
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
Array
Definition: ftmpl_array.h:17
Array::size
int size() const
Definition: ftmpl_array.cc:92
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
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
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:118
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
m
int m
Definition: cfEzgcd.cc:121
l
int l
Definition: cfEzgcd.cc:93
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
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
CanonicalForm::level
int level() const
level() returns the level of CO.
Definition: canonicalform.cc:543
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:87
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