My Project  debian-1:4.1.1-p2+ds-4build1
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);
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  }
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
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  {
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);
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);
404 
405  CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
406 
407  sortByUniFactors (Aeval2, lengthAeval2, uniFactors, biFactors, evaluation);
408 
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;
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,
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;
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  {
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  {
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.h
nonMonicHenselLift
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
SW_RATIONAL
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
distributeLCmultiplier
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...
Definition: facFqFactorize.cc:2574
gcd_deriv
CanonicalForm gcd_deriv
Definition: facFactorize.cc:59
isOn
bool isOn(int sw)
switches
Definition: canonicalform.cc:1912
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
y
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
recoverFactors
CFList recoverFactors(const CanonicalForm &F, const CFList &factors)
divides factors by their content wrt. Variable(1) and checks if these polys divide F
Definition: facFqFactorizeUtil.cc:238
cf_reval.h
lift
ideal lift(const ideal J, const ring r, const ideal inI, const ring s)
Definition: lift.cc:25
result
return result
Definition: facFactorize.cc:153
evaluationWRTDifferentSecondVars
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...
Definition: facFqFactorize.cc:1950
irred
CFList int bool & irred
[in,out] Is A irreducible?
Definition: facFactorize.h:31
prod
fq_nmod_poly_t prod
Definition: facHensel.cc:95
LCFeval
CFList LCFeval
Definition: facFactorize.cc:54
CFMap
class CFMap
Definition: cf_map.h:84
sortList
void sortList(CFList &list, const Variable &x)
sort a list of polynomials by their degree in x.
Definition: facHensel.cc:441
LCHeuristic3
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 ...
Definition: facFqFactorize.cc:2792
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition: canonicalform.cc:1837
Evaluation
class to evaluate a polynomial at points
Definition: cf_eval.h:31
bad
bool bad
Definition: facFactorize.cc:65
level
int level(const CanonicalForm &f)
Definition: canonicalform.h:324
mod
CF_NO_INLINE CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
Definition: cf_inline.cc:564
N
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:48
getLeadingCoeffs
void getLeadingCoeffs(const CanonicalForm &A, CFList *&Aeval)
extract leading coefficients wrt Variable(1) from bivariate factors obtained from factorizations of A...
Definition: facFqFactorize.cc:2216
cf_random.h
TIMING_DEFINE_PRINT
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
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 the...
Definition: facSparseHensel.cc:155
deriv
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
Definition: canonicalform.h:339
w
const CanonicalForm & w
Definition: facAbsFact.cc:55
extgcd
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
facSparseHensel.h
cfUnivarGcd.h
facFqFactorizeUtil.h
lcmContent
CanonicalForm lcmContent(const CanonicalForm &A, CFList &contentAi)
compute the LCM of the contents of A wrt to each variable occuring in A.
Definition: facFqFactorize.cc:954
CanonicalForm
factory's main class
Definition: canonicalform.h:77
found
bool found
Definition: facFactorize.cc:56
LCHeuristicCheck
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,...
Definition: facFqFactorize.cc:2746
minFactorsLength
CFList int & minFactorsLength
[in,out] minimal length of bivariate factors
Definition: facFactorize.h:31
evaluation
const CanonicalForm int const CFList & evaluation
Definition: facAbsFact.cc:55
buildUniFactors
CFList buildUniFactors(const CFList &biFactors, const CanonicalForm &evalPoint, const Variable &y)
plug in evalPoint for y in a list of polys
Definition: facFqFactorize.cc:2304
i
int i
Definition: cfEzgcd.cc:125
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
changeSecondVariable
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
Definition: facFqFactorize.cc:2527
buf
int status int void * buf
Definition: si_signals.h:58
content
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:180
appendSwapDecompress
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...
Definition: facFqBivarUtil.cc:70
TIMING_START
TIMING_START(fac_alg_resultant)
getVars
CanonicalForm getVars(const CanonicalForm &f)
CanonicalForm getVars ( const CanonicalForm & f )
Definition: cf_ops.cc:350
Aeval
CFList *& Aeval
<[in] poly
Definition: facFactorize.h:31
conv
CFList conv(const CFFList &L)
convert a CFFList to a CFList by dropping the multiplicity
Definition: facBivar.cc:126
IntRandom
generate random integers
Definition: cf_random.h:55
evalPoints
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...
Definition: facFqFactorize.cc:740
List::isEmpty
int isEmpty() const
Definition: ftmpl_list.cc:267
factorRecombination
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
cf_map_ext.h
allZero
bool allZero
Definition: facFactorize.cc:57
LucksWangSparseHeuristic
int LucksWangSparseHeuristic(const CanonicalForm &F, const CFList &factors, int level, const CFList &leadingCoeffs, CFList &result)
sparse heuristic lifting by Wang and Lucks
Definition: facSparseHensel.cc:26
cf_algorithm.h
tmin
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
ratBiSqrfFactorize
CFList ratBiSqrfFactorize(const CanonicalForm &G, const Variable &v=Variable(1))
factorize a squarefree bivariate polynomial over .
Definition: facBivar.h:46
REvaluation
class to generate random evaluation points
Definition: cf_reval.h:25
LCHeuristic
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...
Definition: facFqFactorize.cc:2598
Variable::level
int level() const
Definition: factory.h:134
append
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
Definition: facAlgFuncUtil.cc:32
factorize
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:390
prepareLeadingCoeffs
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 ...
Definition: facFqFactorize.cc:2365
factorizationWRTDifferentSecondVars
void factorizationWRTDifferentSecondVars(const CanonicalForm &A, CFList *&Aeval, int &minFactorsLength, bool &irred, const Variable &w)
Definition: facFactorize.cc:157
tmp1
CFList tmp1
Definition: facFqBivar.cc:70
LCHeuristic4
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...
Definition: facFqFactorize.cc:2840
eval
CFList & eval
Definition: facFactorize.cc:48
iter
CFListIterator iter
Definition: facFactorize.cc:60
foundZero
bool foundZero
Definition: facFactorize.cc:58
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
decompress
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
Definition: cfNewtonPolygon.cc:853
LCHeuristic2
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....
Definition: facFqFactorize.cc:2762
Off
void Off(int sw)
switches
Definition: canonicalform.cc:1905
List::removeFirst
void removeFirst()
Definition: ftmpl_list.cc:287
List::getFirst
T getFirst() const
Definition: ftmpl_list.cc:279
tmax
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
deriv_x
CanonicalForm deriv_x
Definition: facFactorize.cc:59
ListIterator::remove
void remove(int moveright)
Definition: ftmpl_list.cc:526
multiFactorize
CFList multiFactorize(const CanonicalForm &F, const Variable &v)
Factorization over Q (a)
Definition: facFactorize.cc:194
bCommonDen
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
Definition: cf_algorithm.cc:293
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition: canonicalform.cc:119
List::length
int length() const
Definition: ftmpl_list.cc:273
TIMING_END_AND_PRINT
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
normalize
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition: syz3.cc:1026
Variable
factory's class for variables
Definition: factory.h:117
ListIterator::getItem
T & getItem() const
Definition: ftmpl_list.cc:431
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
ExtensionInfo
Definition: ExtensionInfo.h:50
LC
CanonicalForm LC(const CanonicalForm &f)
Definition: canonicalform.h:303
facHensel.h
refineBiFactors
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
Definition: facFqFactorize.cc:2318
facFactorize.h
getLast
else L getLast()(0
check
int check
Definition: libparse.cc:1103
l
int l
Definition: cfEzgcd.cc:93
lcm
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition: minpoly.cc:709
liftingBounds
int * liftingBounds(const CanonicalForm &A, const int &bivarLiftBound)
compute lifting bounds
Definition: facFqFactorizeUtil.cc:118
E
CFList Evaluation & E
Definition: facFactorize.cc:49
cf_assert.h
contentx
CanonicalForm contentx
Definition: facFactorize.cc:129
CanonicalForm::isUnivariate
bool isUnivariate() const
Definition: canonicalform.cc:152
Union
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
gcd
int gcd(int a, int b)
Definition: walkSupport.cc:836
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
sortByUniFactors
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...
Definition: facFqFactorize.cc:2234
x
Variable x
Definition: facFactorize.cc:51
List< CanonicalForm >
CFList
List< CanonicalForm > CFList
Definition: canonicalform.h:388
precomputeLeadingCoeff
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,...
Definition: facFqFactorize.cc:1464
henselLiftAndEarly
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
tmp2
CFList tmp2
Definition: facFqBivar.cc:70
myCompress
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
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:585
A
#define A
Definition: sirandom.c:23
info
const ExtensionInfo & info
< [in] sqrfree poly
Definition: facFqFactorize.h:38
degree
int degree(const CanonicalForm &f)
Definition: canonicalform.h:309
List::insert
void insert(const T &)
Definition: ftmpl_list.cc:193
LCF
CanonicalForm LCF
Definition: facFactorize.cc:53
shift2Zero
CanonicalForm shift2Zero(const CanonicalForm &F, CFList &Feval, const CFList &evaluation, int l)
shift evaluation point to zero
Definition: facFqFactorizeUtil.cc:131
On
void On(int sw)
switches
Definition: canonicalform.cc:1898
debug.h
List::getLast
T getLast() const
Definition: ftmpl_list.cc:309
ListIterator
Definition: ftmpl_list.h:17
facFqFactorize.h