facAbsFact.cc
Go to the documentation of this file.
1 /*****************************************************************************\
2  * Computer Algebra System SINGULAR
3 \*****************************************************************************/
4 /** @file facAbsFact.cc
5  *
6  * @author Martin Lee
7  *
8  **/
9 /*****************************************************************************/
10 
11 
12 #include "config.h"
13 
14 
15 #include "timing.h"
16 #include "debug.h"
17 
18 #include "facAbsBiFact.h"
19 #include "facAbsFact.h"
20 #include "facFqFactorize.h"
21 #include "facFqFactorizeUtil.h"
22 #include "facHensel.h"
23 #include "facSparseHensel.h"
24 #include "facFactorize.h"
25 #include "cf_reval.h"
26 #include "cf_primes.h"
27 #include "cf_algorithm.h"
28 #include "cfModResultant.h"
29 #include "cfUnivarGcd.h"
30 #ifdef HAVE_FLINT
31 #include "FLINTconvert.h"
32 #endif
33 #ifdef HAVE_NTL
34 #include "NTLconvert.h"
35 #include <NTL/LLL.h>
36 #endif
37 
38 #ifdef HAVE_NTL
39 TIMING_DEFINE_PRINT(abs_fac_bi_factorizer)
40 TIMING_DEFINE_PRINT(abs_fac_hensel_lift)
41 TIMING_DEFINE_PRINT(abs_fac_factor_recombination)
42 TIMING_DEFINE_PRINT(abs_fac_shift_to_zero)
43 TIMING_DEFINE_PRINT(abs_fac_precompute_leadcoeff)
44 TIMING_DEFINE_PRINT(abs_fac_evaluation)
45 TIMING_DEFINE_PRINT(abs_fac_recover_factors)
46 TIMING_DEFINE_PRINT(abs_fac_bifactor_total)
47 TIMING_DEFINE_PRINT(abs_fac_luckswang)
48 TIMING_DEFINE_PRINT(abs_fac_lcheuristic)
49 TIMING_DEFINE_PRINT(abs_fac_cleardenom)
50 TIMING_DEFINE_PRINT(abs_fac_compress)
51 
52 /// steps 4)-8) of Algorithm B.7.8. from Greuel, Pfister "A Singular
53 /// Introduction to Commutative Algebra"
55 RothsteinTragerResultant (const CanonicalForm& F, const CanonicalForm& w, int s,
57 {
58  CFList terms;
59  for (CFIterator i= w; i.hasTerms(); i++)
60  terms.append (i.coeff());
61 
66 
67  REvaluation E (1, terms.length(), IntRandom (25));
68 
69  do
70  {
71  E.nextpoint();
72  g= 0;
73  iter= terms;
74  for (int i= terms.length(); i >= 1; i--, iter++)
75  g += E[i]*iter.getItem();
76 
77  geval= g;
78  Feval= F;
79  derivFeval= derivF;
80  iter= evaluation;
81  for (int i= F.level(); i >= 2; iter++, i--)
82  {
83  Feval= Feval (iter.getItem(), i);
84  geval= geval (iter.getItem(), i);
85  derivFeval= derivFeval (iter.getItem(), i);
86  }
87 
88  H= y*derivFeval-geval;
89 
90  if (degree (Feval, x) >= 8 || degree (H, x) >= 8)
91  res= resultantZ (Feval, H, x);
92  else
93  res= resultant (Feval, H, x);
94 
95  sqrfPartRes= sqrfPart (res); //univariate poly in y
96  }
97  while (degree (sqrfPartRes) != s);
98 
99  Variable beta= rootOf (sqrfPartRes);
100 
101  CanonicalForm factor= gcd (F, beta*derivF-g);
102 
103  return CFAFList (CFAFactor (factor, getMipo (beta), 1));
104 }
105 
106 
107 /// Algorithm B.7.8 from Greuel, Pfister "A Singular Introduction to Commutative
108 /// Algebra"
109 CFAFList
110 RothsteinTrager (const CanonicalForm& F, const CFList& factors,
111  const Variable& alpha, const CFList& evaluation)
112 {
113  Variable x= Variable (1);
114  ASSERT (factors.length() == 2, "expected two factors");
115  CanonicalForm G, H;
116  if (totaldegree (factors.getFirst()) > totaldegree (factors.getLast()))
117  {
118  H= factors.getLast();
119  G= factors.getFirst();
120  }
121  else
122  {
123  H= factors.getFirst();
124  G= factors.getLast();
125  }
126  CanonicalForm derivH= deriv (H, x);
127  CanonicalForm w= G*derivH;
128  Variable y= Variable (F.level()+1);
129  w= replacevar (w, alpha, y);
130 
131  int s= totaldegree (F)/totaldegree (H);
132 
133  return RothsteinTragerResultant (F, w, s, evaluation, y);
134 }
135 
136 CFList
138  int& intervalSize)
139 {
140  CFList result;
141  Variable x= Variable (1);
142 
143  CanonicalForm LCF= LC (F, x);
144  CFList LCFeval= CFList();
145 
146  bool found= false;
147  bool allZero= true;
148  bool foundZero= false;
150  CFFList uniFactors;
152  int count= 0;
153  do
154  {
155  count++;
156  if (count==E.max() - E.min() + 1)
157  {
158  count= 1;
159  intervalSize++;
160  E= REvaluation (E.min(), E.max(), IntRandom (intervalSize));
161  E.nextpoint();
162  }
163  eval.insert (F);
164  LCFeval.insert (LCF);
165  bool bad= false;
166  for (int i= E.max(); i >= E.min(); i--)
167  {
168  eval.insert (eval.getFirst()( E [i], i));
169  LCFeval.insert (LCFeval.getFirst()( E [i], i));
170  result.append (E[i]);
171  if (!E[i].isZero())
172  allZero= false;
173  else
174  foundZero= true;
175  if (!allZero && foundZero)
176  {
177  result= CFList();
178  eval= CFList();
179  LCFeval= CFList();
180  bad= true;
181  foundZero= false;
182  break;
183  }
184  if (degree (eval.getFirst(), i - 1) != degree (F, i - 1))
185  {
186  result= CFList();
187  LCFeval= CFList();
188  eval= CFList();
189  bad= true;
190  break;
191  }
192  if ((i != 2) && (degree (LCFeval.getFirst(), i-1) != degree (LCF, i-1)))
193  {
194  result= CFList();
195  LCFeval= CFList();
196  eval= CFList();
197  bad= true;
198  break;
199  }
200  }
201 
202  if (bad)
203  {
204  E.nextpoint();
205  continue;
206  }
207 
208  if (degree (eval.getFirst()) != degree (F, 1))
209  {
210  result= CFList();
211  eval= CFList();
212  LCFeval= CFList();
213  E.nextpoint();
214  continue;
215  }
216 
217  deriv_x= deriv (eval.getFirst(), x);
218  gcd_deriv= gcd (eval.getFirst(), deriv_x);
219  if (degree (gcd_deriv) > 0)
220  {
221  result= CFList();
222  eval= CFList();
223  LCFeval= CFList();
224  E.nextpoint();
225  continue;
226  }
227  uniFactors= factorize (eval.getFirst());
228  if (uniFactors.getFirst().factor().inCoeffDomain())
229  uniFactors.removeFirst();
230  if (uniFactors.length() > 1 || uniFactors.getFirst().exp() > 1)
231  {
232  result= CFList();
233  eval= CFList();
234  LCFeval= CFList();
235  E.nextpoint();
236  continue;
237  }
238  iter= eval;
239  iter++;
241  if (degree (contentx) > 0)
242  {
243  result= CFList();
244  eval= CFList();
245  LCFeval= CFList();
246  E.nextpoint();
247  continue;
248  }
249  contentx= content (iter.getItem());
250  if (degree (contentx) > 0)
251  {
252  result= CFList();
253  eval= CFList();
254  LCFeval= CFList();
255  E.nextpoint();
256  continue;
257  }
258  found= true;
259  }
260  while (!found);
261 
262  if (!eval.isEmpty())
263  eval.removeFirst();
264  return result;
265 }
266 
268  )
269 {
270  //TODO handle homogeneous input, is already done in LIB interface but still...
271  ASSERT (getCharacteristic() == 0, "expected poly over Q");
272 
273  CanonicalForm F= G;
274 
275  CanonicalForm LcF= Lc (F);
276  bool isRat= isOn (SW_RATIONAL);
277  if (isRat)
278  F *= bCommonDen (F);
279 
280  Off (SW_RATIONAL);
281  F /= icontent (F);
282  if (isRat)
283  On (SW_RATIONAL);
284 
285  CFFList rationalFactors= factorize (F);
286 
287  CFAFList result, resultBuf;
288 
290  CFFListIterator i= rationalFactors;
291  i++;
292  for (; i.hasItem(); i++)
293  {
294  resultBuf= absFactorizeMain (i.getItem().factor());
295  for (iter= resultBuf; iter.hasItem(); iter++)
296  iter.getItem()= CFAFactor (iter.getItem().factor(),
297  iter.getItem().minpoly(), i.getItem().exp());
298  result= Union (result, resultBuf);
299  }
300 
301  if (isRat)
302  normalize (result);
303  result.insert (CFAFactor (LcF, 1, 1));
304 
305  return result;
306 }
307 
309 {
310  CanonicalForm F= bCommonDen (G)*G;
311 
312  Off (SW_RATIONAL);
313  F /= icontent (F);
314  On (SW_RATIONAL);
315 
316  if (F.inCoeffDomain())
317  return CFAFList (CFAFactor (F, 1, 1));
318 
319  // compress and find main Variable
320  CFMap N;
321  TIMING_START (abs_fac_compress)
322  CanonicalForm A= myCompress (F, N);
323  TIMING_END_AND_PRINT (abs_fac_compress,
324  "time to compress poly in abs fact: ")
325 
326  //univariate case
327  if (F.isUnivariate())
328  {
330  result= uniAbsFactorize (F);
331  if (result.getFirst().factor().inCoeffDomain())
332  result.removeFirst();
333  return result;
334  }
335 
336  //bivariate case
337  if (A.level() == 2)
338  {
340  decompress (result, N);
341  return result; //needs compressed input
342  }
343 
344  Variable x= Variable (1);
345  Variable y= Variable (2);
346 
347  CFAFList factors;
348  A *= bCommonDen (A);
349  CFList Aeval, list, evaluation, bufEvaluation, bufAeval;
350  int factorNums= 1;
351  CFAFList absBiFactors, absBufBiFactors;
352  CanonicalForm evalPoly;
353  int lift, bufLift, lengthAeval2= A.level()-2;
354  CFList* bufAeval2= new CFList [lengthAeval2];
355  CFList* Aeval2= new CFList [lengthAeval2];
356  int counter;
357  int differentSecondVar= 0;
358  CanonicalForm bufA;
359 
360  // several bivariate factorizations
361  TIMING_START (abs_fac_bifactor_total);
362  int absValue= 2;
363  REvaluation E (2, A.level(), IntRandom (absValue));
364  for (int i= 0; i < factorNums; i++)
365  {
366  counter= 0;
367  bufA= A;
368  bufAeval= CFList();
369  TIMING_START (abs_fac_evaluation);
370  bufEvaluation= evalPoints4AbsFact (bufA, bufAeval, E, absValue);
371  TIMING_END_AND_PRINT (abs_fac_evaluation,
372  "time to find evaluation point in abs fact: ");
373  E.nextpoint();
374  evalPoly= 0;
375 
376  TIMING_START (abs_fac_evaluation);
377  evaluationWRTDifferentSecondVars (bufAeval2, bufEvaluation, A);
378  TIMING_END_AND_PRINT (abs_fac_evaluation,
379  "time to eval wrt diff second vars in abs fact: ");
380 
381  for (int j= 0; j < lengthAeval2; j++)
382  {
383  if (!bufAeval2[j].isEmpty())
384  counter++;
385  }
386 
387  bufLift= degree (A, y) + 1 + degree (LC(A, x), y);
388 
389  TIMING_START (abs_fac_bi_factorizer);
390  absBufBiFactors= absBiFactorizeMain (bufAeval.getFirst(), true);
391  TIMING_END_AND_PRINT (abs_fac_bi_factorizer,
392  "time for bivariate factorization in abs fact: ");
393 
394  if (absBufBiFactors.length() == 1)
395  {
396  factors.append (CFAFactor (A, 1, 1));
397  decompress (factors, N);
398  if (isOn (SW_RATIONAL))
399  normalize (factors);
400  delete [] bufAeval2;
401  delete [] Aeval2;
402  return factors;
403  }
404 
405  if (i == 0)
406  {
407  Aeval= bufAeval;
408  evaluation= bufEvaluation;
409  absBiFactors= absBufBiFactors;
410  lift= bufLift;
411  for (int j= 0; j < lengthAeval2; j++)
412  Aeval2 [j]= bufAeval2 [j];
413  differentSecondVar= counter;
414  }
415  else
416  {
417  if (absBufBiFactors.length() < absBiFactors.length() ||
418  ((bufLift < lift) &&
419  (absBufBiFactors.length() == absBiFactors.length())) ||
420  counter > differentSecondVar)
421  {
422  Aeval= bufAeval;
423  evaluation= bufEvaluation;
424  absBiFactors= absBufBiFactors;
425  lift= bufLift;
426  for (int j= 0; j < lengthAeval2; j++)
427  Aeval2 [j]= bufAeval2 [j];
428  differentSecondVar= counter;
429  }
430  }
431  int k= 0;
432  for (CFListIterator j= bufEvaluation; j.hasItem(); j++, k++)
433  evalPoly += j.getItem()*power (x, k);
434  list.append (evalPoly);
435  }
436 
437  delete [] bufAeval2;
438 
439  CFList rationalFactors;
440  Variable v= mvar (absBiFactors.getFirst().minpoly());
441 
442  CFList biFactors;
443  for (CFAFListIterator iter= absBiFactors; iter.hasItem(); iter++)
444  biFactors.append (iter.getItem().factor());
445 
446  sortList (biFactors, x);
447 
448  int minFactorsLength;
449  bool irred= false;
450 
451  TIMING_START (abs_fac_bi_factorizer);
452  factorizationWRTDifferentSecondVars (A, Aeval2, minFactorsLength, irred, v);
453  TIMING_END_AND_PRINT (abs_fac_bi_factorizer,
454  "time for bivariate factorization wrt diff second vars in abs fact: ");
455 
456  TIMING_END_AND_PRINT (abs_fac_bifactor_total,
457  "total time for eval and bivar factors in abs fact: ");
458  if (irred)
459  {
460  factors.append (CFAFactor (A, 1, 1));
461  decompress (factors, N);
462  if (isOn (SW_RATIONAL))
463  normalize (factors);
464  delete [] Aeval2;
465  return factors;
466  }
467 
468  if (minFactorsLength == 0)
469  minFactorsLength= biFactors.length();
470  else if (biFactors.length() > minFactorsLength)
471  refineBiFactors (A, biFactors, Aeval2, evaluation, minFactorsLength);
472  minFactorsLength= tmin (minFactorsLength, biFactors.length());
473 
474  CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
475 
476  sortByUniFactors (Aeval2, lengthAeval2, uniFactors, biFactors, evaluation);
477 
478  minFactorsLength= tmin (minFactorsLength, biFactors.length());
479 
480  if (minFactorsLength == 1)
481  {
482  factors.append (CFAFactor (A, 1, 1));
483  decompress (factors, N);
484  if (isOn (SW_RATIONAL))
485  normalize (factors);
486  delete [] Aeval2;
487  return factors;
488  }
489 
490  bool found= false;
491  if (differentSecondVar == lengthAeval2)
492  {
493  bool zeroOccured= false;
494  for (CFListIterator iter= evaluation; iter.hasItem(); iter++)
495  {
496  if (iter.getItem().isZero())
497  {
498  zeroOccured= true;
499  break;
500  }
501  }
502  if (!zeroOccured)
503  {
504  rationalFactors= sparseHeuristic (A, biFactors, Aeval2, evaluation,
505  minFactorsLength);
506  if (rationalFactors.length() == biFactors.length())
507  {
508  for (CFListIterator iter= rationalFactors; iter.hasItem(); iter++)
509  {
510  if (totaldegree(iter.getItem())*degree(getMipo(v)) == totaldegree (G))
511  {
512  factors= CFAFList (CFAFactor (iter.getItem(), getMipo (v), 1));
513  found= true;
514  break;
515  }
516  }
517  // necessary since extension may be too large
518  if (!found)
519  factors= RothsteinTrager (A, rationalFactors, v, evaluation);
520 
521  decompress (factors, N);
522  normalize (factors);
523  delete [] Aeval2;
524  return factors;
525  }
526  else
527  rationalFactors= CFList();
528  //TODO case where factors.length() > 0
529  }
530  }
531 
532  CFList * oldAeval= new CFList [lengthAeval2];
533  for (int i= 0; i < lengthAeval2; i++)
534  oldAeval[i]= Aeval2[i];
535 
536  getLeadingCoeffs (A, Aeval2);
537 
538  CFList biFactorsLCs;
539  for (CFListIterator i= biFactors; i.hasItem(); i++)
540  biFactorsLCs.append (LC (i.getItem(), 1));
541 
542  Variable w;
543  TIMING_START (abs_fac_precompute_leadcoeff);
544  CFList leadingCoeffs= precomputeLeadingCoeff (LC (A, 1), biFactorsLCs, x,
545  evaluation, Aeval2, lengthAeval2, w);
546 
547  if (w.level() != 1)
548  changeSecondVariable (A, biFactors, evaluation, oldAeval, lengthAeval2,
549  uniFactors, w);
550 
551  CanonicalForm oldA= A;
552  CFList oldBiFactors= biFactors;
553 
554  CanonicalForm LCmultiplier= leadingCoeffs.getFirst();
555  bool LCmultiplierIsConst= LCmultiplier.inCoeffDomain();
556  leadingCoeffs.removeFirst();
557 
558  if (!LCmultiplierIsConst)
559  distributeLCmultiplier (A, leadingCoeffs, biFactors, evaluation,
560  LCmultiplier);
561 
562  //prepare leading coefficients
563  CFList* leadingCoeffs2= new CFList [lengthAeval2];
564  prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(), leadingCoeffs,
565  biFactors, evaluation);
566 
568  CFList bufLeadingCoeffs2= leadingCoeffs2[lengthAeval2-1];
569  CFList bufBiFactors= biFactors;
570  bufA= A;
571  CanonicalForm testVars, bufLCmultiplier= LCmultiplier;
572  if (!LCmultiplierIsConst)
573  {
574  testVars= Variable (2);
575  for (int i= 0; i < lengthAeval2; i++)
576  {
577  if (!oldAeval[i].isEmpty())
578  testVars *= oldAeval[i].getFirst().mvar();
579  }
580  }
581  TIMING_END_AND_PRINT(abs_fac_precompute_leadcoeff,
582  "time to precompute LC in abs fact: ");
583 
584  TIMING_START (abs_fac_luckswang);
585  CFList bufFactors= CFList();
586  bool LCheuristic= false;
587  if (LucksWangSparseHeuristic (A, biFactors, 2, leadingCoeffs2[lengthAeval2-1],
588  rationalFactors))
589  {
590  int check= biFactors.length();
591  int * index= new int [factors.length()];
592  CFList oldFactors= rationalFactors;
593  rationalFactors= recoverFactors (A, rationalFactors, index);
594 
595  if (check == rationalFactors.length())
596  {
597  if (w.level() != 1)
598  {
599  for (iter= rationalFactors; iter.hasItem(); iter++)
600  iter.getItem()= swapvar (iter.getItem(), w, y);
601  }
602 
603  for (CFListIterator iter= rationalFactors; iter.hasItem(); iter++)
604  {
605  if (totaldegree(iter.getItem())*degree (getMipo (v)) == totaldegree (G))
606  {
607  factors= CFAFList (CFAFactor (iter.getItem(), getMipo (v), 1));
608  found=true;
609  break;
610  }
611  }
612  // necessary since extension may be too large
613  if (!found)
614  factors= RothsteinTrager (A, rationalFactors, v, evaluation);
615 
616  decompress (factors, N);
617  normalize (factors);
618  delete [] index;
619  delete [] Aeval2;
620  TIMING_END_AND_PRINT (abs_fac_luckswang,
621  "time for successful LucksWang in abs fact: ");
622  return factors;
623  }
624  else if (rationalFactors.length() > 0)
625  {
626  int oneCount= 0;
627  CFList l;
628  for (int i= 0; i < check; i++)
629  {
630  if (index[i] == 1)
631  {
632  iter=biFactors;
633  for (int j=1; j <= i-oneCount; j++)
634  iter++;
635  iter.remove (1);
636  for (int j= 0; j < lengthAeval2; j++)
637  {
638  l= leadingCoeffs2[j];
639  iter= l;
640  for (int k=1; k <= i-oneCount; k++)
641  iter++;
642  iter.remove (1);
643  leadingCoeffs2[j]=l;
644  }
645  oneCount++;
646  }
647  }
648  bufFactors= rationalFactors;
649  rationalFactors= CFList();
650  }
651  else if (!LCmultiplierIsConst && rationalFactors.length() == 0)
652  {
653  LCheuristic= true;
654  rationalFactors= oldFactors;
655  CFList contents, LCs;
656  bool foundTrueMultiplier= false;
657  LCHeuristic2 (LCmultiplier,rationalFactors,leadingCoeffs2[lengthAeval2-1],
658  contents, LCs, foundTrueMultiplier);
659  if (foundTrueMultiplier)
660  {
661  A= oldA;
662  leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
663  for (int i= lengthAeval2-1; i > -1; i--)
664  leadingCoeffs2[i]= CFList();
665  prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),
666  leadingCoeffs, biFactors, evaluation);
667  }
668  else
669  {
670  bool foundMultiplier= false;
671  LCHeuristic3 (LCmultiplier, rationalFactors, oldBiFactors, contents,
672  oldAeval,A,leadingCoeffs2, lengthAeval2, foundMultiplier);
673  // coming from above: divide out more LCmultiplier if possible
674  if (foundMultiplier)
675  {
676  foundMultiplier= false;
677  LCHeuristic4 (oldBiFactors, oldAeval, contents, rationalFactors,
678  testVars, lengthAeval2, leadingCoeffs2, A, LCmultiplier,
679  foundMultiplier);
680  }
681  else
682  {
683  LCHeuristicCheck (LCs, contents, A, oldA,
684  leadingCoeffs2[lengthAeval2-1], foundMultiplier);
685  if (!foundMultiplier && fdivides (getVars (LCmultiplier), testVars))
686  {
687  LCHeuristic (A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
688  lengthAeval2, evaluation, oldBiFactors);
689  }
690  }
691 
692  // patch everything together again
693  leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
694  for (int i= lengthAeval2-1; i > -1; i--)
695  leadingCoeffs2[i]= CFList();
696  prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),leadingCoeffs,
697  biFactors, evaluation);
698  }
699  rationalFactors= CFList();
700  if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
701  {
702  LCheuristic= false;
703  A= bufA;
704  biFactors= bufBiFactors;
705  leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
706  LCmultiplier= bufLCmultiplier;
707  }
708  }
709  else
710  rationalFactors= CFList();
711  delete [] index;
712  }
713  TIMING_END_AND_PRINT (abs_fac_luckswang, "time for LucksWang in abs fact: ");
714 
715  TIMING_START (abs_fac_lcheuristic);
716  if (!LCheuristic && !LCmultiplierIsConst && bufFactors.isEmpty()
717  && fdivides (getVars (LCmultiplier), testVars))
718  {
719  LCheuristic= true;
720  LCHeuristic (A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
721  lengthAeval2, evaluation, oldBiFactors);
722 
723  leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
724  for (int i= lengthAeval2-1; i > -1; i--)
725  leadingCoeffs2[i]= CFList();
726  prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),leadingCoeffs,
727  biFactors, evaluation);
728 
729  if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
730  {
731  LCheuristic= false;
732  A= bufA;
733  biFactors= bufBiFactors;
734  leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
735  LCmultiplier= bufLCmultiplier;
736  }
737  }
738  TIMING_END_AND_PRINT (abs_fac_lcheuristic,
739  "time for Lc heuristic in abs fact: ");
740 
741 tryAgainWithoutHeu:
742  //shifting to zero
743  TIMING_START (abs_fac_shift_to_zero);
744  CanonicalForm denA= bCommonDen (A);
745  A *= denA;
746  A= shift2Zero (A, Aeval, evaluation);
747  A /= denA;
748 
749  for (iter= biFactors; iter.hasItem(); iter++)
750  iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
751 
752  for (int i= 0; i < lengthAeval2-1; i++)
753  leadingCoeffs2[i]= CFList();
754  for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++)
755  {
756  iter.getItem()= shift2Zero (iter.getItem(), list, evaluation);
757  for (int i= A.level() - 4; i > -1; i--)
758  {
759  if (i + 1 == lengthAeval2-1)
760  leadingCoeffs2[i].append (iter.getItem() (0, i + 4));
761  else
762  leadingCoeffs2[i].append (leadingCoeffs2[i+1].getLast() (0, i + 4));
763  }
764  }
765  TIMING_END_AND_PRINT (abs_fac_shift_to_zero,
766  "time to shift evaluation point to zero in abs fact: ");
767 
768  CFArray Pi;
769  CFList diophant;
770  int* liftBounds= new int [A.level() - 1];
771  int liftBoundsLength= A.level() - 1;
772  for (int i= 0; i < liftBoundsLength; i++)
773  liftBounds [i]= degree (A, i + 2) + 1;
774 
775  Aeval.removeFirst();
776  bool noOneToOne= false;
777 
778  TIMING_START (abs_fac_cleardenom);
779  CFList commonDenominators;
780  for (iter=biFactors; iter.hasItem(); iter++)
781  commonDenominators.append (bCommonDen (iter.getItem()));
782  CanonicalForm tmp1, tmp2, tmp3=1;
783  CFListIterator iter2;
784  for (int i= 0; i < lengthAeval2; i++)
785  {
786  iter2= commonDenominators;
787  for (iter= leadingCoeffs2[i]; iter.hasItem(); iter++, iter2++)
788  {
789  tmp1= bCommonDen (iter.getItem());
790  Off (SW_RATIONAL);
791  iter2.getItem()= lcm (iter2.getItem(), tmp1);
792  On (SW_RATIONAL);
793  }
794  }
795  tmp1= prod (commonDenominators);
796  for (iter= Aeval; iter.hasItem(); iter++)
797  {
798  tmp2= bCommonDen (iter.getItem()/denA);
799  Off (SW_RATIONAL);
800  tmp3= lcm (tmp2,tmp3);
801  On (SW_RATIONAL);
802  }
803  CanonicalForm multiplier;
804  multiplier= tmp3/tmp1;
805  iter2= commonDenominators;
806  for (iter=biFactors; iter.hasItem(); iter++, iter2++)
807  iter.getItem() *= iter2.getItem()*multiplier;
808 
809  for (iter= Aeval; iter.hasItem(); iter++)
810  iter.getItem() *= tmp3*power (multiplier, biFactors.length() - 1)/denA;
811 
812  for (int i= 0; i < lengthAeval2; i++)
813  {
814  iter2= commonDenominators;
815  for (iter= leadingCoeffs2[i]; iter.hasItem(); iter++, iter2++)
816  iter.getItem() *= iter2.getItem()*multiplier;
817  }
818 
819  TIMING_END_AND_PRINT (abs_fac_cleardenom,
820  "time to clear denominators in abs fact: ");
821 
822  TIMING_START (abs_fac_hensel_lift);
823  rationalFactors= nonMonicHenselLift (Aeval, biFactors,leadingCoeffs2,diophant,
824  Pi, liftBounds, liftBoundsLength, noOneToOne);
825  TIMING_END_AND_PRINT (abs_fac_hensel_lift,
826  "time for non monic hensel lifting in abs fact: ");
827 
828  if (!noOneToOne)
829  {
830  int check= rationalFactors.length();
831  A= oldA;
832  TIMING_START (abs_fac_recover_factors);
833  rationalFactors= recoverFactors (A, rationalFactors, evaluation);
834  TIMING_END_AND_PRINT (abs_fac_recover_factors,
835  "time to recover factors in abs fact: ");
836  if (check != rationalFactors.length())
837  noOneToOne= true;
838  else
839  rationalFactors= Union (rationalFactors, bufFactors);
840  }
841  if (noOneToOne)
842  {
843  if (!LCmultiplierIsConst && LCheuristic)
844  {
845  A= bufA;
846  biFactors= bufBiFactors;
847  leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
848  delete [] liftBounds;
849  LCheuristic= false;
850  goto tryAgainWithoutHeu;
851  //something probably went wrong in the heuristic
852  }
853 
854  A= shift2Zero (oldA, Aeval, evaluation);
855  biFactors= oldBiFactors;
856  for (iter= biFactors; iter.hasItem(); iter++)
857  iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
858  CanonicalForm LCA= LC (Aeval.getFirst(), 1);
859  CanonicalForm yToLift= power (y, lift);
860  CFListIterator i= biFactors;
861  lift= degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1;
862  i++;
863 
864  for (; i.hasItem(); i++)
865  lift= tmax (lift, degree (i.getItem(), 2)+degree (LC (i.getItem(), 1))+1);
866 
867  lift= tmax (degree (Aeval.getFirst() , 2) + 1, lift);
868 
869  i= biFactors;
870  yToLift= power (y, lift);
871  CanonicalForm dummy;
872  for (; i.hasItem(); i++)
873  {
874  LCA= LC (i.getItem(), 1);
875  extgcd (LCA, yToLift, LCA, dummy);
876  i.getItem()= mod (i.getItem()*LCA, yToLift);
877  }
878 
879  liftBoundsLength= F.level() - 1;
880  liftBounds= liftingBounds (A, lift);
881 
882  CFList MOD;
883  bool earlySuccess;
884  CFList earlyFactors;
886  CFList liftedFactors;
887  TIMING_START (abs_fac_hensel_lift);
888  liftedFactors= henselLiftAndEarly
889  (A, MOD, liftBounds, earlySuccess, earlyFactors,
890  Aeval, biFactors, evaluation, info);
891  TIMING_END_AND_PRINT (abs_fac_hensel_lift,
892  "time for hensel lifting in abs fact: ");
893 
894  TIMING_START (abs_fac_factor_recombination);
895  rationalFactors= factorRecombination (A, liftedFactors, MOD);
896  TIMING_END_AND_PRINT (abs_fac_factor_recombination,
897  "time for factor recombination in abs fact: ");
898 
899  if (earlySuccess)
900  rationalFactors= Union (rationalFactors, earlyFactors);
901 
902  for (CFListIterator i= rationalFactors; i.hasItem(); i++)
903  {
904  int kk= Aeval.getLast().level();
905  for (CFListIterator j= evaluation; j.hasItem(); j++, kk--)
906  {
907  if (i.getItem().level() < kk)
908  continue;
909  i.getItem()= i.getItem() (Variable (kk) - j.getItem(), kk);
910  }
911  }
912  }
913 
914  if (w.level() != 1)
915  {
916  for (CFListIterator iter= rationalFactors; iter.hasItem(); iter++)
917  iter.getItem()= swapvar (iter.getItem(), w, y);
918  }
919 
920  for (CFListIterator iter= rationalFactors; iter.hasItem(); iter++)
921  {
922  if (totaldegree (iter.getItem())*degree (getMipo (v)) == totaldegree (G))
923  {
924  factors= CFAFList (CFAFactor (iter.getItem(), getMipo (v), 1));
925  found= true;
926  break;
927  }
928  }
929 
930  // necessary since extension may be too large
931  if (!found)
932  factors= RothsteinTrager (A, rationalFactors, v, evaluation);
933 
934  decompress (factors, N);
935  if (isOn (SW_RATIONAL))
936  normalize (factors);
937 
938  delete [] leadingCoeffs2;
939  delete [] oldAeval;
940  delete [] Aeval2;
941  delete[] liftBounds;
942 
943  return factors;
944 }
945 
946 #endif
int status int void size_t count
Definition: si_signals.h:59
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
List< CanonicalForm > CFList
CFList LCFeval
Definition: facFactorize.cc:54
const CanonicalForm int s
Definition: facAbsFact.cc:55
int level() const
Definition: variable.h:49
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
CanonicalForm icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f )
Definition: cf_gcd.cc:71
CFList recoverFactors(const CanonicalForm &F, const CFList &factors)
divides factors by their content wrt. Variable(1) and checks if these polys divide F ...
Conversion to and from NTL.
This file defines functions for Hensel lifting.
int min() const
Definition: cf_eval.h:41
CFAFList absFactorizeMain(const CanonicalForm &G)
main absolute factorization routine, expects poly which is irreducible over Q
Definition: facAbsFact.cc:308
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:1028
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition: minpoly.cc:711
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
This file defines functions for conversion to FLINT (www.flintlib.org) and back.
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
void Off(int sw)
switches
bool inCoeffDomain() const
CFAFList absBiFactorizeMain(const CanonicalForm &G, bool full)
main absolute factorization routine, expects bivariate poly which is irreducible over Q ...
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)
#define TIMING_END_AND_PRINT(t, msg)
Definition: timing.h:89
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: variable.h:32
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
Variable x
Definition: facAbsFact.cc:62
generate random evaluation points
CanonicalForm gcd_deriv
Definition: facFactorize.cc:59
CFList evalPoints4AbsFact(const CanonicalForm &F, CFList &eval, Evaluation &E, int &intervalSize)
Definition: facAbsFact.cc:137
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
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
Variable mvar(const CanonicalForm &f)
int k
Definition: cfEzgcd.cc:93
const CanonicalForm int const CFList & evaluation
Definition: facAbsFact.cc:55
int LucksWangSparseHeuristic(const CanonicalForm &F, const CFList &factors, int level, const CFList &leadingCoeffs, CFList &result)
sparse heuristic lifting by Wang and Lucks
Variable alpha
Definition: facAbsBiFact.cc:52
This file provides functions for factorizing a multivariate polynomial over , or GF...
CanonicalForm sqrfPart(const CanonicalForm &F)
squarefree part of a poly
Definition: fac_sqrfree.cc:111
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
return CFAFList(CFAFactor(factor, getMipo(beta), 1))
static TreeM * G
Definition: janet.cc:38
CanonicalForm Lc(const CanonicalForm &f)
CanonicalForm LcF
Definition: facAbsBiFact.cc:51
int getCharacteristic()
Definition: cf_char.cc:51
CFListIterator iter
Definition: facAbsFact.cc:65
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
int level() const
level() returns the level of CO.
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
int isEmpty() const
Definition: ftmpl_list.cc:267
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
ideal lift(const ideal J, const ring r, const ideal inI, const ring s)
Definition: lift.cc:24
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:390
TIMING_DEFINE_PRINT(abs_fac_bi_factorizer) TIMING_DEFINE_PRINT(abs_fac_hensel_lift) TIMING_DEFINE_PRINT(abs_fac_factor_recombination) TIMING_DEFINE_PRINT(abs_fac_shift_to_zero) TIMING_DEFINE_PRINT(abs_fac_precompute_leadcoeff) TIMING_DEFINE_PRINT(abs_fac_evaluation) TIMING_DEFINE_PRINT(abs_fac_recover_factors) TIMING_DEFINE_PRINT(abs_fac_bifactor_total) TIMING_DEFINE_PRINT(abs_fac_luckswang) TIMING_DEFINE_PRINT(abs_fac_lcheuristic) TIMING_DEFINE_PRINT(abs_fac_cleardenom) TIMING_DEFINE_PRINT(abs_fac_compress) CFAFList RothsteinTragerResultant(const CanonicalForm &F
steps 4)-8) of Algorithm B.7.8. from Greuel, Pfister "A Singular Introduction to Commutative Algebra"...
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 ...
bivariate absolute factorization over Q described in "Modular Las Vegas Algorithms for Polynomial Abs...
CFAFList uniAbsFactorize(const CanonicalForm &F, bool full=false)
univariate absolute factorization over Q
CanonicalForm res
Definition: facAbsFact.cc:64
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
AFactor< CanonicalForm > CFAFactor
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
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
T getFirst() const
Definition: ftmpl_list.cc:279
multivariate factorization over Q(a)
int length() const
Definition: ftmpl_list.cc:273
int i
Definition: cfEzgcd.cc:123
CanonicalForm H
Definition: facAbsFact.cc:64
CanonicalForm factor
Definition: facAbsFact.cc:101
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)
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
CanonicalForm derivFeval
Definition: facAbsFact.cc:64
CanonicalForm resultantZ(const CanonicalForm &A, const CanonicalForm &B, const Variable &x, bool prob)
modular resultant algorihtm over Z
int max() const
Definition: cf_eval.h:42
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
bool isUnivariate() const
bool foundZero
Definition: facFactorize.cc:58
CanonicalForm geval
Definition: facAbsFact.cc:64
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
CanonicalForm contentx
Variable beta
Definition: facAbsFact.cc:99
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...
CanonicalForm Feval
Definition: facAbsFact.cc:64
modular resultant algorithm as described by G.
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 ...
access to prime tables
REvaluation E(1, terms.length(), IntRandom(25))
class to evaluate a polynomial at points
Definition: cf_eval.h:31
T & getItem() const
Definition: ftmpl_list.cc:431
number absValue(poly p)
int gcd(int a, int b)
Definition: walkSupport.cc:839
fq_nmod_poly_t prod
Definition: facHensel.cc:95
#define TIMING_START(t)
Definition: timing.h:87
CanonicalForm derivF
Definition: facAbsFact.cc:63
CFList tmp1
Definition: facFqBivar.cc:70
const CanonicalForm & w
Definition: facAbsFact.cc:55
T getLast() const
Definition: ftmpl_list.cc:309
void nextpoint()
Definition: cf_reval.cc:46
CanonicalForm deriv_x
Definition: facFactorize.cc:59
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition: cf_ops.cc:523
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...
#define const
Definition: fegetopt.c:41
#define ASSERT(expression, message)
Definition: cf_assert.h:99
CanonicalForm sqrfPartRes
Definition: facAbsFact.cc:64
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
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 ...
CFAFList absFactorize(const CanonicalForm &G)
absolute factorization of a multivariate poly over Q
Definition: facAbsFact.cc:267
CanonicalForm LC(const CanonicalForm &f)
CanonicalForm replacevar(const CanonicalForm &, const Variable &, const Variable &)
CanonicalForm replacevar ( const CanonicalForm & f, const Variable & x1, const Variable & x2 ) ...
Definition: cf_ops.cc:271
absolute multivariate factorization over Q
CanonicalForm resultant(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x ) ...
CanonicalForm g
Definition: facAbsFact.cc:64
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
return result
Definition: facAbsBiFact.cc:76
CFAFList RothsteinTrager(const CanonicalForm &F, const CFList &factors, const Variable &alpha, const CFList &evaluation)
Algorithm B.7.8 from Greuel, Pfister "A Singular Introduction to Commutative Algebra".
Definition: facAbsFact.cc:110
Variable rootOf(const CanonicalForm &mipo, char name)
returns a symbolic root of polynomial with name name Use it to define algebraic variables ...
Definition: variable.cc:162
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)