My Project
facSparseHensel.h
Go to the documentation of this file.
1 /*****************************************************************************\
2  * Computer Algebra System SINGULAR
3 \*****************************************************************************/
4 /** @file facSparseHensel.h
5  *
6  * This file provides functions for sparse heuristic Hensel lifting
7  *
8  * @author Martin Lee
9  *
10  **/
11 /*****************************************************************************/
12 
13 #ifndef FAC_SPARSE_HENSEL_H
14 #define FAC_SPARSE_HENSEL_H
15 
16 #include "canonicalform.h"
17 #include "cf_map_ext.h"
18 #include "cf_iter.h"
20 #include "cf_algorithm.h"
21 #include "cf_map.h"
22 
23 /// compare polynomials
24 inline
25 int comp (const CanonicalForm& A, const CanonicalForm& B)
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 }
48 
49 /// compare two polynomials up to level @a level
50 inline
51 int comp (const CanonicalForm& A, const CanonicalForm& B, int level)
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 }
73 
74 /// swap entry @a i and @a j in @a A
75 inline
76 void swap (CFArray& A, int i, int j)
77 {
78  CanonicalForm tmp= A[i];
79  A[i]= A[j];
80  A[j]= tmp;
81 }
82 
83 /// quick sort helper function
84 inline
85 void quickSort (int lo, int hi, CFArray& A, int l)
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 }
111 
112 /// quick sort @a A
113 inline
114 void sort (CFArray& A, int l= 0)
115 {
116  quickSort (0, A.size() - 1, A, l);
117 }
118 
119 
120 /// find normalizing factors for @a biFactors and build monic univariate factors
121 /// from @a biFactors
122 inline CFList
124  CFList& uniFactors)
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 }
136 
137 /// find normalizing factors for @a biFactors and sort @a biFactors s.t.
138 /// the returned @a biFactors evaluated at evalPoint coincide with @a uniFactors
139 inline CFList
141  const CFList& uniFactors)
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 }
164 
165 /// get terms of @a F
166 inline CFArray
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 }
199 
200 /// helper function for getBiTerms
201 inline CFArray
202 getBiTerms_helper (const CanonicalForm& F, const CFMap& M, int threshold)
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 }
232 
233 /// get terms of @a F where F is considered a bivariate poly in Variable(1),
234 /// Variable (2)
235 inline CFArray
236 getBiTerms (const CanonicalForm& F, int threshold)
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 }
264 
265 /// build a poly from entries in @a A
266 inline CanonicalForm
268 {
270  for (int i= A.size() - 1; i > -1; i--)
271  result += A[i];
272  return result;
273 }
274 
275 /// group together elements in @a A, where entries in @a A are put together
276 /// if they coincide up to level @a level
277 inline void
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 }
306 
307 /// strip off those parts of entries in @a F whose level is less than or equal
308 /// than @a level and store the stripped off parts in @a G
309 inline void
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 }
328 
329 /// s.a. stripped off parts are not returned
330 inline void
331 strip (CFArray& F, int level)
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 }
347 
348 /// get equations for LucksWangSparseHeuristic
349 inline
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 }
359 
360 /// evaluate every entry of @a A at @a B and level @a level
361 inline void
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 }
373 
374 /// evaluate every entry of @a A at every entry of @a B starting at level @a
375 /// level
376 inline void
377 evaluate (CFArray& A, const CFArray& B, int level)
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 }
386 
387 /// simplify @a A if possible, i.e. @a A consists of 2 terms and contains only
388 /// one variable of level greater or equal than @a level
389 inline CanonicalForm
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 }
409 
410 /// if possible simplify @a A as described above and store result in @a B
411 inline bool
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 }
439 
440 /// merge @a B into @a A if possible, i.e. every non-zero entry in @a A should
441 /// be zero in @a B
442 inline bool
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 }
465 
466 /// checks if entries of @a A are zero
467 inline bool
468 isZero (const CFArray& A)
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 }
476 
477 /// checks if @a A equals @a B
478 inline bool
479 isEqual (const CFArray& A, const CFArray& B)
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 }
489 
490 /// get terms of @a F wrt. Variable (1)
491 inline CFArray
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 }
521 
522 /// get terms of entries in @a F and put them in @a result
523 inline
524 void getTerms2 (const CFList& F, CFArray* result)
525 {
526  int j= 0;
527  for (CFListIterator i= F; i.hasItem(); i++, j++)
528  result[j]= getTerms2 (i.getItem());
529 }
530 
531 /// evaluate entries in @a A at @a eval and @a y
532 inline CFArray
533 evaluate (const CFArray& A, const CanonicalForm& eval, const Variable& y)
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 }
541 
542 /// s.a.
543 inline CFArray*
544 evaluate (CFArray* const& A, int sizeA, const CanonicalForm& eval,
545  const Variable& y)
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 }
552 
553 /// normalize entries in @a L with @a normalizingFactor
554 inline
555 CFList normalize (const CFList& L, const CFList& normalizingFactor)
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 }
563 
564 /// search for @a F in @a A between index @a i and @a j
565 inline
566 int search (const CFArray& A, const CanonicalForm& F, int i, int j)
567 {
568  for (; i < j; i++)
569  if (A[i] == F)
570  return i;
571  return -1;
572 }
573 
574 /// patch together @a F1 and @a F2 and normalize by a power of @a eval
575 /// @a F1 and @a F2 are assumed to be bivariate with one variable having level 1
576 inline
578  const CanonicalForm& eval)
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 }
589 
590 /// sparse heuristic lifting by Wang and Lucks
591 ///
592 /// @return @a LucksWangSparseHeuristic returns true if it was successful
593 int
594 LucksWangSparseHeuristic (const CanonicalForm& F, ///<[in] polynomial to be
595  ///< factored
596  const CFList& factors, ///<[in] factors of F
597  ///< lifted to level
598  int level, ///<[in] level of lifted
599  ///< factors
600  const CFList& leadingCoeffs,///<[in] leading
601  ///< coefficients of
602  ///< factors
603  CFList& result ///<[in,out] result
604  );
605 
606 /// sparse heuristic which patches together bivariate factors of @a A wrt.
607 /// different second variables by their univariate images
608 ///
609 /// @return @a sparseHeuristic returns a list of found factors of A
610 CFList
611 sparseHeuristic (const CanonicalForm& A, ///<[in] polynomial to be factored
612  const CFList& biFactors, ///<[in] bivariate factors of A where
613  ///< the second variable has level 2
614  CFList*& moreBiFactors, ///<[in] more bivariate factorizations
615  ///< wrt. different second variables
616  const CFList& evaluation,///<[in] evaluation point
617  int minFactorsLength ///<[in] minimal length of bivariate
618  ///< factorizations
619  );
620 
621 #endif
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Header for factory's main class CanonicalForm.
CanonicalForm getVars(const CanonicalForm &f)
CanonicalForm getVars ( const CanonicalForm & f )
Definition: cf_ops.cc:350
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
CanonicalForm tailcoeff(const CanonicalForm &f)
int degree(const CanonicalForm &f)
Array< CanonicalForm > CFArray
CanonicalForm FACTORY_PUBLIC swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
CanonicalForm Lc(const CanonicalForm &f)
int level(const CanonicalForm &f)
CanonicalForm LC(const CanonicalForm &f)
int l
Definition: cfEzgcd.cc:100
int m
Definition: cfEzgcd.cc:128
int i
Definition: cfEzgcd.cc:132
int k
Definition: cfEzgcd.cc:99
Variable x
Definition: cfModGcd.cc:4082
g
Definition: cfModGcd.cc:4090
static void evalPoint(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &FEval, CanonicalForm &GEval, CFGenerator &evalPoint)
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
declarations of higher level algorithms.
#define ASSERT(expression, message)
Definition: cf_assert.h:99
Iterators for CanonicalForm's.
map polynomials
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
This file implements functions to map between extensions of finite fields.
FILE * f
Definition: checklibs.c:9
int size() const
Definition: ftmpl_array.cc:92
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
class CFMap
Definition: cf_map.h:85
factory's main class
Definition: canonicalform.h:86
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
bool inCoeffDomain() const
int level() const
level() returns the level of CO.
bool isUnivariate() const
T & getItem() const
Definition: ftmpl_list.cc:431
void append(const T &)
Definition: ftmpl_list.cc:256
factory's class for variables
Definition: factory.h:127
CFFListIterator iter
Definition: facAbsBiFact.cc:53
return result
Definition: facAbsBiFact.cc:75
const CanonicalForm int const CFList & evaluation
Definition: facAbsFact.cc:52
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:53
b *CanonicalForm B
Definition: facBivar.cc:52
CFList & eval
Definition: facFactorize.cc:47
CFList int & minFactorsLength
[in,out] minimal length of bivariate factors
Definition: facFactorize.h:33
int j
Definition: facHensel.cc:110
CanonicalForm buildPolyFromArray(const CFArray &A)
build a poly from entries in A
bool isEqual(const CFArray &A, const CFArray &B)
checks if A equals B
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 getTerms2(const CanonicalForm &F)
get terms of F wrt. Variable (1)
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...
int LucksWangSparseHeuristic(const CanonicalForm &F, const CFList &factors, int level, const CFList &leadingCoeffs, CFList &result)
sparse heuristic lifting by Wang and Lucks
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
void quickSort(int lo, int hi, CFArray &A, int l)
quick sort helper function
int comp(const CanonicalForm &A, const CanonicalForm &B)
compare polynomials
CFList findNormalizingFactor1(const CFList &biFactors, const CanonicalForm &evalPoint, CFList &uniFactors)
find normalizing factors for biFactors and build monic univariate factors from biFactors
CFList normalize(const CFList &L, const CFList &normalizingFactor)
normalize entries in L with normalizingFactor
void swap(CFArray &A, int i, int j)
swap entry i and j in A
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...
CFArray getBiTerms_helper(const CanonicalForm &F, const CFMap &M, int threshold)
helper function for getBiTerms
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 ...
CFArray getTerms(const CanonicalForm &F)
get terms of F
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...
void sort(CFArray &A, int l=0)
quick sort A
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
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 the...
CFArray getEquations(const CFArray &A, const CFArray &B)
get equations for LucksWangSparseHeuristic
some useful template functions.
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
STATIC_VAR TreeM * G
Definition: janet.cc:31
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
int status int void * buf
Definition: si_signals.h:59
#define A
Definition: sirandom.c:24
#define M
Definition: sirandom.c:25