facFactorize.cc
Go to the documentation of this file.
1 /*****************************************************************************\
2  * Computer Algebra System SINGULAR
3 \*****************************************************************************/
4 /** @file facFactorize.cc
5  *
6  * multivariate factorization over Q(a)
7  *
8  * @author Martin Lee
9  *
10  **/
11 /*****************************************************************************/
12 
13 
14 #include "config.h"
15 
16 
17 #include "cf_assert.h"
18 #include "debug.h"
19 #include "timing.h"
20 
21 #include "cf_algorithm.h"
22 #include "facFqFactorizeUtil.h"
23 #include "facFactorize.h"
24 #include "facFqFactorize.h"
25 #include "cf_random.h"
26 #include "facHensel.h"
27 #include "cf_map_ext.h"
28 #include "cf_reval.h"
29 #include "facSparseHensel.h"
30 #include "cfUnivarGcd.h"
31 
32 TIMING_DEFINE_PRINT(fac_bi_factorizer)
33 TIMING_DEFINE_PRINT(fac_hensel_lift)
34 TIMING_DEFINE_PRINT(fac_factor_recombination)
35 TIMING_DEFINE_PRINT(fac_shift_to_zero)
36 TIMING_DEFINE_PRINT(fac_precompute_leadcoeff)
37 TIMING_DEFINE_PRINT(fac_evaluation)
38 TIMING_DEFINE_PRINT(fac_recover_factors)
39 TIMING_DEFINE_PRINT(fac_preprocess_and_content)
40 TIMING_DEFINE_PRINT(fac_bifactor_total)
41 TIMING_DEFINE_PRINT(fac_luckswang)
42 TIMING_DEFINE_PRINT(fac_lcheuristic)
43 TIMING_DEFINE_PRINT(fac_cleardenom)
44 TIMING_DEFINE_PRINT(fac_content)
45 TIMING_DEFINE_PRINT(fac_compress)
46 
47 #ifdef HAVE_NTL
49 {
50  CFList result;
52 
55 
56  bool found= false;
57  bool allZero= true;
58  bool foundZero= false;
61  do
62  {
63  eval.insert (F);
64  LCFeval.insert (LCF);
65  bool bad= false;
66  for (int i= E.max(); i >= E.min(); i--)
67  {
68  eval.insert (eval.getFirst()( E [i], i));
69  LCFeval.insert (LCFeval.getFirst() (E [i], i));
70  result.append (E[i]);
71  if (!E[i].isZero())
72  allZero= false;
73  else
74  foundZero= true;
75  if (!allZero && foundZero)
76  {
77  result= CFList();
78  eval= CFList();
79  LCFeval= CFList();
80  bad= true;
81  foundZero= false;
82  break;
83  }
84  if (degree (eval.getFirst(), i - 1) != degree (F, i - 1))
85  {
86  result= CFList();
87  eval= CFList();
88  LCFeval= CFList();
89  bad= true;
90  break;
91  }
92  if ((i != 2) && (degree (LCFeval.getFirst(), i-1) != degree (LCF, i-1)))
93  {
94  result= CFList();
95  eval= CFList();
96  LCFeval= CFList();
97  bad= true;
98  break;
99  }
100  }
101 
102  if (bad)
103  {
104  E.nextpoint();
105  continue;
106  }
107 
108  if (degree (eval.getFirst()) != degree (F, 1))
109  {
110  result= CFList();
111  eval= CFList();
112  LCFeval= CFList();
113  E.nextpoint();
114  continue;
115  }
116 
117  deriv_x= deriv (eval.getFirst(), x);
118  gcd_deriv= gcd (eval.getFirst(), deriv_x);
119  if (degree (gcd_deriv) > 0)
120  {
121  result= CFList();
122  eval= CFList();
123  LCFeval= CFList();
124  E.nextpoint();
125  continue;
126  }
127  iter= eval;
128  iter++;
130  if (degree (contentx) > 0)
131  {
132  result= CFList();
133  eval= CFList();
134  LCFeval= CFList();
135  E.nextpoint();
136  continue;
137  }
138  contentx= content (iter.getItem());
139  if (degree (contentx) > 0)
140  {
141  result= CFList();
142  eval= CFList();
143  LCFeval= CFList();
144  E.nextpoint();
145  continue;
146  }
147  found= true;
148  }
149  while (!found);
150 
151  if (!eval.isEmpty())
152  eval.removeFirst();
153  return result;
154 }
155 
156 void
158  int& minFactorsLength, bool& irred,
159  const Variable& w)
160 {
161  Variable x= Variable (1);
162  minFactorsLength= 0;
163  irred= false;
164  Variable v;
165  CFList factors;
166  CanonicalForm LCA= LC (A,1);
167  for (int j= 0; j < A.level() - 2; j++)
168  {
169  if (!Aeval[j].isEmpty())
170  {
171  v= Variable (Aeval[j].getFirst().level());
172 
173  factors= ratBiSqrfFactorize (Aeval[j].getFirst(), w);
174  if (factors.getFirst().inCoeffDomain())
175  factors.removeFirst();
176 
177  if (minFactorsLength == 0)
178  minFactorsLength= factors.length();
179  else
180  minFactorsLength= tmin (minFactorsLength, factors.length());
181 
182  if (factors.length() == 1)
183  {
184  irred= true;
185  return;
186  }
187  sortList (factors, x);
188  Aeval [j]= factors;
189  }
190  }
191 }
192 
193 CFList
195 {
196  if (F.inCoeffDomain())
197  return CFList (F);
198 
199  TIMING_START (fac_preprocess_and_content);
200  // compress and find main Variable
201  CFMap N;
202  TIMING_START (fac_compress)
203  CanonicalForm A= myCompress (F, N);
204  TIMING_END_AND_PRINT (fac_compress, "time to compress poly over Q: ")
205 
206  //univariate case
207  if (F.isUnivariate())
208  {
209  CFList result;
210  if (v.level() != 1)
211  result= conv (factorize (F, v));
212  else
213  result= conv (factorize (F,true));
214  if (result.getFirst().inCoeffDomain())
215  result.removeFirst();
216  return result;
217  }
218 
219  //bivariate case
220  if (A.level() == 2)
221  {
222  CFList buf= ratBiSqrfFactorize (F, v);
223  if (buf.getFirst().inCoeffDomain())
224  buf.removeFirst();
225  return buf;
226  }
227 
228  Variable x= Variable (1);
229  Variable y= Variable (2);
230 
231  // remove content
232  TIMING_START (fac_content);
233  CFList contentAi;
234  CanonicalForm lcmCont= lcmContent (A, contentAi);
235  A /= lcmCont;
236  TIMING_END_AND_PRINT (fac_content, "time to extract content over Q: ");
237 
238  // trivial after content removal
239  CFList contentAFactors;
240  if (A.inCoeffDomain())
241  {
242  for (CFListIterator i= contentAi; i.hasItem(); i++)
243  {
244  if (i.getItem().inCoeffDomain())
245  continue;
246  else
247  {
248  lcmCont /= i.getItem();
249  contentAFactors=
250  Union (multiFactorize (lcmCont, v),
251  multiFactorize (i.getItem(), v));
252  break;
253  }
254  }
255  decompress (contentAFactors, N);
256  if (isOn (SW_RATIONAL))
257  normalize (contentAFactors);
258  return contentAFactors;
259  }
260 
261  // factorize content
262  TIMING_START (fac_content);
263  contentAFactors= multiFactorize (lcmCont, v);
264  TIMING_END_AND_PRINT (fac_content, "time to factor content over Q: ");
265 
266  // univariate after content removal
267  CFList factors;
268  if (A.isUnivariate ())
269  {
270  if (v.level() != 1)
271  factors= conv (factorize (A, v));
272  else
273  factors= conv (factorize (A,true));
274  append (factors, contentAFactors);
275  decompress (factors, N);
276  return factors;
277  }
278 
279  A *= bCommonDen (A);
280  CFList Aeval, list, evaluation, bufEvaluation, bufAeval;
281  int factorNums= 2;
282  //p is irreducible. But factorize does not recognizes this. However, if you
283  //change factorNums to 2 at line 281 in facFactorize.cc it will. That change
284  //might impair performance in some cases since you do twice as many
285  //bivariate factorizations as before. Otherwise you need to change
286  //precomputeLeadingCoeff to detect these cases and trigger more bivariate
287  // factorizations.
288  // (http://www.singular.uni-kl.de:8002/trac/ticket/666)
289  CFList biFactors, bufBiFactors;
290  CanonicalForm evalPoly;
291  int lift, bufLift, lengthAeval2= A.level()-2;
292  CFList* bufAeval2= new CFList [lengthAeval2];
293  CFList* Aeval2= new CFList [lengthAeval2];
294  int counter;
295  int differentSecondVar= 0;
296  CanonicalForm bufA;
297  TIMING_END_AND_PRINT (fac_preprocess_and_content,
298  "time to preprocess poly and extract content over Q: ");
299 
300  // several bivariate factorizations
301  TIMING_START (fac_bifactor_total);
302  REvaluation E (2, A.level(), IntRandom (25));
303  for (int i= 0; i < factorNums; i++)
304  {
305  counter= 0;
306  bufA= A;
307  bufAeval= CFList();
308  TIMING_START (fac_evaluation);
309  bufEvaluation= evalPoints (bufA, bufAeval, E);
310  TIMING_END_AND_PRINT (fac_evaluation,
311  "time to find evaluation point over Q: ");
312  E.nextpoint();
313  evalPoly= 0;
314 
315  TIMING_START (fac_evaluation);
316  evaluationWRTDifferentSecondVars (bufAeval2, bufEvaluation, A);
317  TIMING_END_AND_PRINT (fac_evaluation,
318  "time to eval wrt diff second vars over Q: ");
319 
320  for (int j= 0; j < lengthAeval2; j++)
321  {
322  if (!bufAeval2[j].isEmpty())
323  counter++;
324  }
325 
326  bufLift= degree (A, y) + 1 + degree (LC(A, x), y);
327 
328  TIMING_START (fac_bi_factorizer);
329  bufBiFactors= ratBiSqrfFactorize (bufAeval.getFirst(), v);
330  TIMING_END_AND_PRINT (fac_bi_factorizer,
331  "time for bivariate factorization: ");
332  bufBiFactors.removeFirst();
333 
334  if (bufBiFactors.length() == 1)
335  {
336  factors.append (A);
337  appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
338  if (isOn (SW_RATIONAL))
339  normalize (factors);
340  delete [] bufAeval2;
341  delete [] Aeval2;
342  return factors;
343  }
344 
345  if (i == 0)
346  {
347  Aeval= bufAeval;
348  evaluation= bufEvaluation;
349  biFactors= bufBiFactors;
350  lift= bufLift;
351  for (int j= 0; j < lengthAeval2; j++)
352  Aeval2 [j]= bufAeval2 [j];
353  differentSecondVar= counter;
354  }
355  else
356  {
357  if (bufBiFactors.length() < biFactors.length() ||
358  ((bufLift < lift) && (bufBiFactors.length() == biFactors.length())) ||
359  counter > differentSecondVar)
360  {
361  Aeval= bufAeval;
362  evaluation= bufEvaluation;
363  biFactors= bufBiFactors;
364  lift= bufLift;
365  for (int j= 0; j < lengthAeval2; j++)
366  Aeval2 [j]= bufAeval2 [j];
367  differentSecondVar= counter;
368  }
369  }
370  int k= 0;
371  for (CFListIterator j= bufEvaluation; j.hasItem(); j++, k++)
372  evalPoly += j.getItem()*power (x, k);
373  list.append (evalPoly);
374  }
375 
376  delete [] bufAeval2;
377 
378  sortList (biFactors, x);
379 
380  int minFactorsLength;
381  bool irred= false;
382  TIMING_START (fac_bi_factorizer);
383  factorizationWRTDifferentSecondVars (A, Aeval2, minFactorsLength, irred, v);
384  TIMING_END_AND_PRINT (fac_bi_factorizer,
385  "time for bivariate factorization wrt diff second vars over Q: ");
386 
387  TIMING_END_AND_PRINT (fac_bifactor_total,
388  "total time for eval and bivar factors over Q: ");
389  if (irred)
390  {
391  factors.append (A);
392  appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
393  if (isOn (SW_RATIONAL))
394  normalize (factors);
395  delete [] Aeval2;
396  return factors;
397  }
398 
399  if (minFactorsLength == 0)
400  minFactorsLength= biFactors.length();
401  else if (biFactors.length() > minFactorsLength)
402  refineBiFactors (A, biFactors, Aeval2, evaluation, minFactorsLength);
403  minFactorsLength= tmin (minFactorsLength, biFactors.length());
404 
405  CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
406 
407  sortByUniFactors (Aeval2, lengthAeval2, uniFactors, biFactors, evaluation);
408 
409  minFactorsLength= tmin (minFactorsLength, biFactors.length());
410 
411  if (minFactorsLength == 1)
412  {
413  factors.append (A);
414  appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
415  if (isOn (SW_RATIONAL))
416  normalize (factors);
417  delete [] Aeval2;
418  return factors;
419  }
420 
421  if (differentSecondVar == lengthAeval2)
422  {
423  bool zeroOccured= false;
424  for (CFListIterator iter= evaluation; iter.hasItem(); iter++)
425  {
426  if (iter.getItem().isZero())
427  {
428  zeroOccured= true;
429  break;
430  }
431  }
432  if (!zeroOccured)
433  {
434  factors= sparseHeuristic (A, biFactors, Aeval2, evaluation,
435  minFactorsLength);
436  if (factors.length() == biFactors.length())
437  {
438  appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
439  normalize (factors);
440  delete [] Aeval2;
441  return factors;
442  }
443  else
444  factors= CFList();
445  //TODO case where factors.length() > 0
446  }
447  }
448 
449  CFList * oldAeval= new CFList [lengthAeval2];
450  for (int i= 0; i < lengthAeval2; i++)
451  oldAeval[i]= Aeval2[i];
452 
453  getLeadingCoeffs (A, Aeval2);
454 
455  CFList biFactorsLCs;
456  for (CFListIterator i= biFactors; i.hasItem(); i++)
457  biFactorsLCs.append (LC (i.getItem(), 1));
458 
459  Variable w;
460  TIMING_START (fac_precompute_leadcoeff);
461  CFList leadingCoeffs= precomputeLeadingCoeff (LC (A, 1), biFactorsLCs, x,
462  evaluation, Aeval2, lengthAeval2, w);
463 
464  if (w.level() != 1)
465  changeSecondVariable (A, biFactors, evaluation, oldAeval, lengthAeval2,
466  uniFactors, w);
467 
468  CanonicalForm oldA= A;
469  CFList oldBiFactors= biFactors;
470 
471  CanonicalForm LCmultiplier= leadingCoeffs.getFirst();
472  bool LCmultiplierIsConst= LCmultiplier.inCoeffDomain();
473  leadingCoeffs.removeFirst();
474 
475  if (!LCmultiplierIsConst)
476  distributeLCmultiplier (A, leadingCoeffs, biFactors, evaluation, LCmultiplier);
477 
478  //prepare leading coefficients
479  CFList* leadingCoeffs2= new CFList [lengthAeval2];
480  prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(), leadingCoeffs,
481  biFactors, evaluation);
482 
484  CFList bufLeadingCoeffs2= leadingCoeffs2[lengthAeval2-1];
485  bufBiFactors= biFactors;
486  bufA= A;
487  CanonicalForm testVars, bufLCmultiplier= LCmultiplier;
488  if (!LCmultiplierIsConst)
489  {
490  testVars= Variable (2);
491  for (int i= 0; i < lengthAeval2; i++)
492  {
493  if (!oldAeval[i].isEmpty())
494  testVars *= oldAeval[i].getFirst().mvar();
495  }
496  }
497  TIMING_END_AND_PRINT(fac_precompute_leadcoeff,
498  "time to precompute LC over Q: ");
499 
500  TIMING_START (fac_luckswang);
501  CFList bufFactors= CFList();
502  bool LCheuristic= false;
503  if (LucksWangSparseHeuristic (A, biFactors, 2, leadingCoeffs2[lengthAeval2-1],
504  factors))
505  {
506  int check= biFactors.length();
507  int * index= new int [factors.length()];
508  CFList oldFactors= factors;
509  factors= recoverFactors (A, factors, index);
510 
511  if (check == factors.length())
512  {
513  if (w.level() != 1)
514  {
515  for (iter= factors; iter.hasItem(); iter++)
516  iter.getItem()= swapvar (iter.getItem(), w, y);
517  }
518 
519  appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
520  normalize (factors);
521  delete [] index;
522  delete [] Aeval2;
523  TIMING_END_AND_PRINT (fac_luckswang,
524  "time for successful LucksWang over Q: ");
525  return factors;
526  }
527  else if (factors.length() > 0)
528  {
529  int oneCount= 0;
530  CFList l;
531  for (int i= 0; i < check; i++)
532  {
533  if (index[i] == 1)
534  {
535  iter=biFactors;
536  for (int j=1; j <= i-oneCount; j++)
537  iter++;
538  iter.remove (1);
539  for (int j= 0; j < lengthAeval2; j++)
540  {
541  l= leadingCoeffs2[j];
542  iter= l;
543  for (int k=1; k <= i-oneCount; k++)
544  iter++;
545  iter.remove (1);
546  leadingCoeffs2[j]=l;
547  }
548  oneCount++;
549  }
550  }
551  bufFactors= factors;
552  factors= CFList();
553  }
554  else if (!LCmultiplierIsConst && factors.length() == 0)
555  {
556  LCheuristic= true;
557  factors= oldFactors;
558  CFList contents, LCs;
559  bool foundTrueMultiplier= false;
560  LCHeuristic2 (LCmultiplier, factors, leadingCoeffs2[lengthAeval2-1],
561  contents, LCs, foundTrueMultiplier);
562  if (foundTrueMultiplier)
563  {
564  A= oldA;
565  leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
566  for (int i= lengthAeval2-1; i > -1; i--)
567  leadingCoeffs2[i]= CFList();
568  prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),
569  leadingCoeffs, biFactors, evaluation);
570  }
571  else
572  {
573  bool foundMultiplier= false;
574  LCHeuristic3 (LCmultiplier, factors, oldBiFactors, contents, oldAeval,
575  A, leadingCoeffs2, lengthAeval2, foundMultiplier);
576  // coming from above: divide out more LCmultiplier if possible
577  if (foundMultiplier)
578  {
579  foundMultiplier= false;
580  LCHeuristic4 (oldBiFactors, oldAeval, contents, factors, testVars,
581  lengthAeval2, leadingCoeffs2, A, LCmultiplier,
582  foundMultiplier);
583  }
584  else
585  {
586  LCHeuristicCheck (LCs, contents, A, oldA,
587  leadingCoeffs2[lengthAeval2-1], foundMultiplier);
588  if (!foundMultiplier && fdivides (getVars (LCmultiplier), testVars))
589  {
590  LCHeuristic (A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
591  lengthAeval2, evaluation, oldBiFactors);
592  }
593  }
594 
595  // patch everything together again
596  leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
597  for (int i= lengthAeval2-1; i > -1; i--)
598  leadingCoeffs2[i]= CFList();
599  prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),leadingCoeffs,
600  biFactors, evaluation);
601  }
602  factors= CFList();
603  if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
604  {
605  LCheuristic= false;
606  A= bufA;
607  biFactors= bufBiFactors;
608  leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
609  LCmultiplier= bufLCmultiplier;
610  }
611  }
612  else
613  factors= CFList();
614  delete [] index;
615  }
616  TIMING_END_AND_PRINT (fac_luckswang, "time for LucksWang over Q: ");
617 
618  TIMING_START (fac_lcheuristic);
619  if (!LCheuristic && !LCmultiplierIsConst && bufFactors.isEmpty()
620  && fdivides (getVars (LCmultiplier), testVars))
621  {
622  LCheuristic= true;
623  LCHeuristic (A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
624  lengthAeval2, evaluation, oldBiFactors);
625 
626  leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
627  for (int i= lengthAeval2-1; i > -1; i--)
628  leadingCoeffs2[i]= CFList();
629  prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),leadingCoeffs,
630  biFactors, evaluation);
631 
632  if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
633  {
634  LCheuristic= false;
635  A= bufA;
636  biFactors= bufBiFactors;
637  leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
638  LCmultiplier= bufLCmultiplier;
639  }
640  }
641  TIMING_END_AND_PRINT (fac_lcheuristic, "time for Lc heuristic over Q: ");
642 
643 tryAgainWithoutHeu:
644  //shifting to zero
645  TIMING_START (fac_shift_to_zero);
646  CanonicalForm denA= bCommonDen (A);
647  A *= denA;
648  A= shift2Zero (A, Aeval, evaluation);
649  A /= denA;
650 
651  for (iter= biFactors; iter.hasItem(); iter++)
652  iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
653 
654  for (int i= 0; i < lengthAeval2-1; i++)
655  leadingCoeffs2[i]= CFList();
656  for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++)
657  {
658  iter.getItem()= shift2Zero (iter.getItem(), list, evaluation);
659  for (int i= A.level() - 4; i > -1; i--)
660  {
661  if (i + 1 == lengthAeval2-1)
662  leadingCoeffs2[i].append (iter.getItem() (0, i + 4));
663  else
664  leadingCoeffs2[i].append (leadingCoeffs2[i+1].getLast() (0, i + 4));
665  }
666  }
667  TIMING_END_AND_PRINT (fac_shift_to_zero,
668  "time to shift evaluation point to zero: ");
669 
670  CFArray Pi;
671  CFList diophant;
672  int* liftBounds= new int [A.level() - 1];
673  int liftBoundsLength= A.level() - 1;
674  for (int i= 0; i < liftBoundsLength; i++)
675  liftBounds [i]= degree (A, i + 2) + 1;
676 
677  Aeval.removeFirst();
678  bool noOneToOne= false;
679 
680  TIMING_START (fac_cleardenom);
681  CFList commonDenominators;
682  for (iter=biFactors; iter.hasItem(); iter++)
683  commonDenominators.append (bCommonDen (iter.getItem()));
684  CanonicalForm tmp1, tmp2, tmp3=1;
685  CFListIterator iter2;
686  for (int i= 0; i < lengthAeval2; i++)
687  {
688  iter2= commonDenominators;
689  for (iter= leadingCoeffs2[i]; iter.hasItem(); iter++, iter2++)
690  {
691  tmp1= bCommonDen (iter.getItem());
692  Off (SW_RATIONAL);
693  iter2.getItem()= lcm (iter2.getItem(), tmp1);
694  On (SW_RATIONAL);
695  }
696  }
697  tmp1= prod (commonDenominators);
698  for (iter= Aeval; iter.hasItem(); iter++)
699  {
700  tmp2= bCommonDen (iter.getItem()/denA);
701  Off (SW_RATIONAL);
702  tmp3= lcm (tmp2,tmp3);
703  On (SW_RATIONAL);
704  }
705  CanonicalForm multiplier;
706  multiplier= tmp3/tmp1;
707  iter2= commonDenominators;
708  for (iter=biFactors; iter.hasItem(); iter++, iter2++)
709  iter.getItem() *= iter2.getItem()*multiplier;
710 
711  for (iter= Aeval; iter.hasItem(); iter++)
712  iter.getItem() *= tmp3*power (multiplier, biFactors.length() - 1)/denA;
713 
714  for (int i= 0; i < lengthAeval2; i++)
715  {
716  iter2= commonDenominators;
717  for (iter= leadingCoeffs2[i]; iter.hasItem(); iter++, iter2++)
718  iter.getItem() *= iter2.getItem()*multiplier;
719  }
720  TIMING_END_AND_PRINT (fac_cleardenom, "time to clear denominators: ");
721 
722  TIMING_START (fac_hensel_lift);
723  factors= nonMonicHenselLift (Aeval, biFactors, leadingCoeffs2, diophant,
724  Pi, liftBounds, liftBoundsLength, noOneToOne);
725  TIMING_END_AND_PRINT (fac_hensel_lift,
726  "time for non monic hensel lifting over Q: ");
727 
728  if (!noOneToOne)
729  {
730  int check= factors.length();
731  A= oldA;
732  TIMING_START (fac_recover_factors);
733  factors= recoverFactors (A, factors, evaluation);
734  TIMING_END_AND_PRINT (fac_recover_factors,
735  "time to recover factors over Q: ");
736  if (check != factors.length())
737  noOneToOne= true;
738  else
739  factors= Union (factors, bufFactors);
740  }
741  if (noOneToOne)
742  {
743  if (!LCmultiplierIsConst && LCheuristic)
744  {
745  A= bufA;
746  biFactors= bufBiFactors;
747  leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
748  delete [] liftBounds;
749  LCheuristic= false;
750  goto tryAgainWithoutHeu;
751  //something probably went wrong in the heuristic
752  }
753 
754  A= shift2Zero (oldA, Aeval, evaluation);
755  biFactors= oldBiFactors;
756  for (iter= biFactors; iter.hasItem(); iter++)
757  iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
758  CanonicalForm LCA= LC (Aeval.getFirst(), 1);
759  CanonicalForm yToLift= power (y, lift);
760  CFListIterator i= biFactors;
761  lift= degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1;
762  i++;
763 
764  for (; i.hasItem(); i++)
765  lift= tmax (lift, degree (i.getItem(), 2)+degree (LC (i.getItem(), 1))+1);
766 
767  lift= tmax (degree (Aeval.getFirst() , 2) + 1, lift);
768 
769  i= biFactors;
770  yToLift= power (y, lift);
771  CanonicalForm dummy;
772  for (; i.hasItem(); i++)
773  {
774  LCA= LC (i.getItem(), 1);
775  extgcd (LCA, yToLift, LCA, dummy);
776  i.getItem()= mod (i.getItem()*LCA, yToLift);
777  }
778 
779  liftBoundsLength= F.level() - 1;
780  liftBounds= liftingBounds (A, lift);
781 
782  CFList MOD;
783  bool earlySuccess;
784  CFList earlyFactors;
786  CFList liftedFactors;
787  TIMING_START (fac_hensel_lift);
788  liftedFactors= henselLiftAndEarly
789  (A, MOD, liftBounds, earlySuccess, earlyFactors,
790  Aeval, biFactors, evaluation, info);
791  TIMING_END_AND_PRINT (fac_hensel_lift, "time for hensel lifting: ");
792 
793  TIMING_START (fac_factor_recombination);
794  factors= factorRecombination (A, liftedFactors, MOD);
795  TIMING_END_AND_PRINT (fac_factor_recombination,
796  "time for factor recombination: ");
797 
798  if (earlySuccess)
799  factors= Union (factors, earlyFactors);
800 
801  for (CFListIterator i= factors; i.hasItem(); i++)
802  {
803  int kk= Aeval.getLast().level();
804  for (CFListIterator j= evaluation; j.hasItem(); j++, kk--)
805  {
806  if (i.getItem().level() < kk)
807  continue;
808  i.getItem()= i.getItem() (Variable (kk) - j.getItem(), kk);
809  }
810  }
811  }
812 
813  if (w.level() != 1)
814  {
815  for (CFListIterator iter= factors; iter.hasItem(); iter++)
816  iter.getItem()= swapvar (iter.getItem(), w, y);
817  }
818 
819  append (factors, contentAFactors);
820  decompress (factors, N);
821  if (isOn (SW_RATIONAL))
822  normalize (factors);
823 
824  delete [] leadingCoeffs2;
825  delete [] oldAeval;
826  delete [] Aeval2;
827  delete[] liftBounds;
828 
829  return factors;
830 }
831 
832 #endif
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
CanonicalForm shift2Zero(const CanonicalForm &F, CFList &Feval, const CFList &evaluation, int l)
shift evaluation point to zero
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
List< CanonicalForm > CFList
CFList LCFeval
Definition: facFactorize.cc:54
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
CFList recoverFactors(const CanonicalForm &F, const CFList &factors)
divides factors by their content wrt. Variable(1) and checks if these polys divide F ...
This file defines functions for Hensel lifting.
This file provides utility functions for multivariate factorization.
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition: syz3.cc:1027
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition: minpoly.cc:711
int level(const CanonicalForm &f)
void changeSecondVariable(CanonicalForm &A, CFList &biFactors, CFList &evaluation, CFList *&oldAeval, int lengthAeval2, const CFList &uniFactors, const Variable &w)
changes the second variable to be w and updates all relevant data
CF_NO_INLINE CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
Definition: cf_inline.cc:564
int isEmpty() const
Definition: ftmpl_list.cc:267
void Off(int sw)
switches
CanonicalForm LCF
Definition: facFactorize.cc:53
functions to print debug output
CanonicalForm extgcd(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b)
CanonicalForm extgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a...
Definition: cfUnivarGcd.cc:173
int check
Definition: libparse.cc:1104
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
virtual void nextpoint()
Definition: cf_eval.cc:43
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
TIMING_START(fac_alg_resultant)
CFList evalPoints(const CanonicalForm &F, CFList &eval, const Variable &alpha, CFList &list, const bool &GF, bool &fail)
evaluation point search for multivariate factorization, looks for a (F.level() - 1)-tuple such that t...
void sortByUniFactors(CFList *&Aeval, int AevalLength, CFList &uniFactors, CFList &biFactors, const CFList &evaluation)
sort bivariate factors in Aeval such that their corresponding univariate factors coincide with uniFac...
factory&#39;s class for variables
Definition: factory.h:115
CFList henselLiftAndEarly(CanonicalForm &A, bool &earlySuccess, CFList &earlyFactors, DegreePattern &degs, int &liftBound, const CFList &uniFactors, const ExtensionInfo &info, const CanonicalForm &eval, modpk &b, CanonicalForm &den)
hensel Lifting and early factor detection
Definition: facFqBivar.cc:1115
bool bad
Definition: facFactorize.cc:65
CFList *& Aeval
<[in] poly
Definition: facFactorize.h:31
generate random evaluation points
CanonicalForm gcd_deriv
Definition: facFactorize.cc:59
return result
CFList int & minFactorsLength
[in,out] minimal length of bivariate factors
Definition: facFactorize.h:31
void LCHeuristic(CanonicalForm &A, const CanonicalForm &LCmultiplier, CFList &biFactors, CFList *&leadingCoeffs, const CFList *oldAeval, int lengthAeval, const CFList &evaluation, const CFList &oldBiFactors)
heuristic to distribute LCmultiplier onto factors based on the variables that occur in LCmultiplier a...
factory&#39;s main class
Definition: canonicalform.h:75
class to generate random evaluation points
Definition: cf_reval.h:25
int myCompress(const CanonicalForm &F, const CanonicalForm &G, CFMap &M, CFMap &N, bool topLevel)
compressing two polynomials F and G, M is used for compressing, N to reverse the compression ...
Definition: cfModGcd.cc:93
assertions for Factory
void LCHeuristic4(const CFList &oldBiFactors, const CFList *oldAeval, const CFList &contents, const CFList &factors, const CanonicalForm &testVars, int lengthAeval, CFList *&leadingCoeffs, CanonicalForm &A, CanonicalForm &LCmultiplier, bool &foundMultiplier)
heuristic to remove factors of LCmultiplier from factors. More precisely checks if elements of conten...
generate random integers
Definition: cf_random.h:55
int k
Definition: cfEzgcd.cc:93
const CanonicalForm int const CFList & evaluation
Definition: facAbsFact.cc:55
void appendSwapDecompress(CFList &factors1, const CFList &factors2, const CFList &factors3, const bool swap1, const bool swap2, const CFMap &N)
first swap Variables in factors1 if necessary, then append factors2 and factors3 on factors1 and fina...
int LucksWangSparseHeuristic(const CanonicalForm &F, const CFList &factors, int level, const CFList &leadingCoeffs, CFList &result)
sparse heuristic lifting by Wang and Lucks
This file provides functions for factorizing a multivariate polynomial over , or GF...
CFList nonMonicHenselLift(const CFList &F, const CFList &factors, const CFList &LCs, CFList &diophant, CFArray &Pi, CFMatrix &M, int lOld, int &lNew, const CFList &MOD, bool &noOneToOne)
Definition: facHensel.cc:2709
void insert(const T &)
Definition: ftmpl_list.cc:193
TIMING_DEFINE_PRINT(fac_bi_factorizer) TIMING_DEFINE_PRINT(fac_hensel_lift) TIMING_DEFINE_PRINT(fac_factor_recombination) TIMING_DEFINE_PRINT(fac_shift_to_zero) TIMING_DEFINE_PRINT(fac_precompute_leadcoeff) TIMING_DEFINE_PRINT(fac_evaluation) TIMING_DEFINE_PRINT(fac_recover_factors) TIMING_DEFINE_PRINT(fac_preprocess_and_content) TIMING_DEFINE_PRINT(fac_bifactor_total) TIMING_DEFINE_PRINT(fac_luckswang) TIMING_DEFINE_PRINT(fac_lcheuristic) TIMING_DEFINE_PRINT(fac_cleardenom) TIMING_DEFINE_PRINT(fac_content) TIMING_DEFINE_PRINT(fac_compress) CFList evalPoints(const CanonicalForm &F
int max() const
Definition: cf_eval.h:42
void removeFirst()
Definition: ftmpl_list.cc:287
void sortList(CFList &list, const Variable &x)
sort a list of polynomials by their degree in x.
Definition: facHensel.cc:441
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:180
This file implements functions to map between extensions of finite fields.
bool found
Definition: facFactorize.cc:56
CFList factorRecombination(CFList &factors, CanonicalForm &F, const CanonicalForm &N, DegreePattern &degs, const CanonicalForm &eval, int s, int thres, const modpk &b, const CanonicalForm &den)
naive factor recombination as decribed in "Factoring multivariate polynomials over a finite field" by...
Definition: facFqBivar.cc:561
T getFirst() const
Definition: ftmpl_list.cc:279
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
CFList conv(const CFFList &L)
convert a CFFList to a CFList by dropping the multiplicity
Definition: facBivar.cc:124
ideal lift(const ideal J, const ring r, const ideal inI, const ring s)
Definition: lift.cc:26
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:390
This file provides functions for sparse heuristic Hensel lifting.
ExtensionInfo contains information about extension.
Definition: ExtensionInfo.h:50
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
void refineBiFactors(const CanonicalForm &A, CFList &biFactors, CFList *const &Aeval, const CFList &evaluation, int minFactorsLength)
refine a bivariate factorization of A with l factors to one with minFactorsLength if possible ...
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:49
univariate Gcd over finite fields and Z, extended GCD over finite fields and Q
CanonicalForm getVars(const CanonicalForm &f)
CanonicalForm getVars ( const CanonicalForm & f )
Definition: cf_ops.cc:350
int j
Definition: myNF.cc:70
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
CFList multiFactorize(const CanonicalForm &F, const Variable &v)
Factorization over Q (a)
int status int void * buf
Definition: si_signals.h:59
int level() const
Definition: factory.h:132
bool isUnivariate() const
T & getItem() const
Definition: ftmpl_list.cc:431
const ExtensionInfo & info
< [in] sqrfree poly
#define A
Definition: sirandom.c:23
bool allZero
Definition: facFactorize.cc:57
else L getLast()(0
CFList & eval
Definition: facFactorize.cc:48
void distributeLCmultiplier(CanonicalForm &A, CFList &leadingCoeffs, CFList &biFactors, const CFList &evaluation, const CanonicalForm &LCmultipler)
distributes a divisor LCmultiplier of LC(A,1) on the bivariate factors and the precomputed leading co...
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
CFList precomputeLeadingCoeff(const CanonicalForm &LCF, const CFList &LCFFactors, const Variable &alpha, const CFList &evaluation, CFList *&differentSecondVarLCs, int lSecondVarLCs, Variable &y)
computes a list l of length length(LCFFactors)+1 of polynomials such that prod (l)=LCF, note that the first entry of l may be non constant. Intended to be used to precompute coefficients of a polynomial f from its bivariate factorizations.
bool isOn(int sw)
switches
void On(int sw)
switches
multivariate factorization over Q(a)
int i
Definition: cfEzgcd.cc:123
T getLast() const
Definition: ftmpl_list.cc:309
generate random integers, random elements of finite fields
CFList tmp2
Definition: facFqBivar.cc:70
declarations of higher level algorithms.
void factorizationWRTDifferentSecondVars(const CanonicalForm &A, CFList *&Aeval, int &minFactorsLength, bool &irred, const Variable &w)
int min() const
Definition: cf_eval.h:41
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
bool foundZero
Definition: facFactorize.cc:58
CanonicalForm contentx
class CFMap
Definition: cf_map.h:84
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
void evaluationWRTDifferentSecondVars(CFList *&Aeval, const CFList &evaluation, const CanonicalForm &A)
evaluate a poly A with main variable at level 1 at an evaluation point in K^(n-1) wrt different secon...
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
CFList buildUniFactors(const CFList &biFactors, const CanonicalForm &evalPoint, const Variable &y)
plug in evalPoint for y in a list of polys
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...
void LCHeuristic3(const CanonicalForm &LCmultiplier, const CFList &factors, const CFList &oldBiFactors, const CFList &contents, const CFList *oldAeval, CanonicalForm &A, CFList *&leadingCoeffs, int lengthAeval, bool &foundMultiplier)
heuristic to remove LCmultiplier from a factor based on the contents of factors. factors are assumed ...
int length() const
Definition: ftmpl_list.cc:273
CFList ratBiSqrfFactorize(const CanonicalForm &G, const Variable &v=Variable(1))
factorize a squarefree bivariate polynomial over .
Definition: facBivar.h:46
class to evaluate a polynomial at points
Definition: cf_eval.h:31
CFListIterator iter
Definition: facFactorize.cc:60
CFList Evaluation & E
Definition: facFactorize.cc:49
int gcd(int a, int b)
Definition: walkSupport.cc:839
fq_nmod_poly_t prod
Definition: facHensel.cc:95
CFList tmp1
Definition: facFqBivar.cc:70
const CanonicalForm & w
Definition: facAbsFact.cc:55
Variable x
Definition: facFactorize.cc:51
CanonicalForm lcmContent(const CanonicalForm &A, CFList &contentAi)
compute the LCM of the contents of A wrt to each variable occuring in A.
CanonicalForm deriv_x
Definition: facFactorize.cc:59
bool isZero(const CFArray &A)
checks if entries of A are zero
CFList int bool & irred
[in,out] Is A irreducible?
Definition: facFactorize.h:31
void LCHeuristicCheck(const CFList &LCs, const CFList &contents, CanonicalForm &A, const CanonicalForm &oldA, CFList &leadingCoeffs, bool &foundTrueMultiplier)
checks if prod(LCs)==LC (oldA,1) and if so divides elements of leadingCoeffs by elements in contents...
int level() const
level() returns the level of CO.
void append(const T &)
Definition: ftmpl_list.cc:256
int degree(const CanonicalForm &f)
void prepareLeadingCoeffs(CFList *&LCs, CanonicalForm &A, CFList &Aeval, int n, const CFList &leadingCoeffs, const CFList &biFactors, const CFList &evaluation)
normalize precomputed leading coefficients such that leading coefficients evaluated at evaluation in ...
CanonicalForm LC(const CanonicalForm &f)
void LCHeuristic2(const CanonicalForm &LCmultiplier, const CFList &factors, CFList &leadingCoeffs, CFList &contents, CFList &LCs, bool &foundTrueMultiplier)
heuristic to distribute LCmultiplier onto factors based on the contents of factors. factors are assumed to come from LucksWangSparseHeuristic. If not successful contents will contain the content of each element of factors and LCs will contain the LC of each element of factors divided by its content
void getLeadingCoeffs(const CanonicalForm &A, CFList *&Aeval)
extract leading coefficients wrt Variable(1) from bivariate factors obtained from factorizations of A...
int * liftingBounds(const CanonicalForm &A, const int &bivarLiftBound)
compute lifting bounds
int l
Definition: cfEzgcd.cc:94
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
bool inCoeffDomain() const