My Project  debian-1:4.1.2-p1+ds-2
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,
56  const CFList& evaluation, const Variable& y)
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;
81  for (int i= F.level(); i >= 2; iter++, i--)
82  {
83  Feval= Feval (iter.getItem(), i);
84  geval= geval (iter.getItem(), i);
86  }
87 
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 
100 
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);
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  }
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 {
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);
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);
473 
474  CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
475 
476  sortByUniFactors (Aeval2, lengthAeval2, uniFactors, biFactors, evaluation);
477 
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;
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,
506  if (rationalFactors.length() == biFactors.length())
507  {
508  for (CFListIterator iter= rationalFactors; iter.hasItem(); iter++)
509  {
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  {
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;
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  {
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  {
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
Evaluation::min
int min() const
Definition: cf_eval.h:41
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
RothsteinTrager
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
SW_RATIONAL
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:29
evalPoints4AbsFact
CFList evalPoints4AbsFact(const CanonicalForm &F, CFList &eval, Evaluation &E, int &intervalSize)
Definition: facAbsFact.cc:137
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
icontent
CanonicalForm icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f )
Definition: cf_gcd.cc:71
CFIterator
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
y
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
uniAbsFactorize
CFAFList uniAbsFactorize(const CanonicalForm &F, bool full=false)
univariate absolute factorization over Q
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
result
return result
Definition: facAbsBiFact.cc:76
cf_reval.h
resultantZ
CanonicalForm resultantZ(const CanonicalForm &A, const CanonicalForm &B, const Variable &x, bool prob)
modular resultant algorihtm over Z
Definition: cfModResultant.cc:560
check
VAR int check
Definition: libparse.cc:1105
lift
ideal lift(const ideal J, const ring r, const ideal inI, const ring s)
Definition: lift.cc:25
absBiFactorizeMain
CFAFList absBiFactorizeMain(const CanonicalForm &G, bool full)
main absolute factorization routine, expects bivariate poly which is irreducible over Q
Definition: facAbsBiFact.cc:187
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
absFactorize
CFAFList absFactorize(const CanonicalForm &G)
absolute factorization of a multivariate poly over Q
Definition: facAbsFact.cc:267
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
mvar
Variable mvar(const CanonicalForm &f)
Definition: canonicalform.h:327
mod
CF_NO_INLINE CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
Definition: cf_inline.cc:564
E
REvaluation E(1, terms.length(), IntRandom(25))
rootOf
Variable rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables
Definition: variable.cc:162
CFAFList
return CFAFList(CFAFactor(factor, getMipo(beta), 1))
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_primes.h
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
getCharacteristic
int getCharacteristic()
Definition: cf_char.cc:51
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
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
cfModResultant.h
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
sqrfPart
CanonicalForm sqrfPart(const CanonicalForm &F)
squarefree part of a poly
Definition: fac_sqrfree.cc:111
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
Lc
CanonicalForm Lc(const CanonicalForm &f)
Definition: canonicalform.h:300
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
facAbsFact.h
getMipo
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
res
CanonicalForm res
Definition: facAbsFact.cc:64
ASSERT
#define ASSERT(expression, message)
Definition: cf_assert.h:99
content
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:175
absFactorizeMain
CFAFList absFactorizeMain(const CanonicalForm &G)
main absolute factorization routine, expects poly which is irreducible over Q
Definition: facAbsFact.cc:308
g
CanonicalForm g
Definition: facAbsFact.cc:64
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
IntRandom
generate random integers
Definition: cf_random.h:55
alpha
Variable alpha
Definition: facAbsBiFact.cc:52
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
derivFeval
CanonicalForm derivFeval
Definition: facAbsFact.cc:64
allZero
bool allZero
Definition: facFactorize.cc:57
G
STATIC_VAR TreeM * G
Definition: janet.cc:31
LcF
CanonicalForm LcF
Definition: facAbsBiFact.cc:51
NTLconvert.h
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
AFactor
Definition: ftmpl_afactor.h:17
cf_algorithm.h
tmin
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
REvaluation
class to generate random evaluation points
Definition: cf_reval.h:25
facAbsBiFact.h
CFAFactor
AFactor< CanonicalForm > CFAFactor
Definition: canonicalform.h:382
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
Feval
CanonicalForm Feval
Definition: facAbsFact.cc:64
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
FLINTconvert.h
eval
CFList & eval
Definition: facFactorize.cc:48
sqrfPartRes
CanonicalForm sqrfPartRes
Definition: facAbsFact.cc:64
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
beta
Variable beta
Definition: facAbsFact.cc:99
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
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
TIMING_DEFINE_PRINT
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"
List::length
int length() const
Definition: ftmpl_list.cc:273
factor
CanonicalForm factor
Definition: facAbsFact.cc:101
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:1025
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
resultant
CanonicalForm resultant(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
Definition: cf_resultant.cc:173
getLast
else L getLast()(0
Evaluation::max
int max() const
Definition: cf_eval.h:42
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
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
absValue
number absValue(poly p)
Definition: linearAlgebra.cc:725
derivF
CanonicalForm derivF
Definition: facAbsFact.cc:63
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: facAbsFact.cc:62
REvaluation::nextpoint
void nextpoint()
Definition: cf_reval.cc:46
List
Definition: ftmpl_list.h:20
iter
CFListIterator iter
Definition: facAbsFact.cc:65
s
const CanonicalForm int s
Definition: facAbsFact.cc:55
replacevar
CanonicalForm replacevar(const CanonicalForm &, const Variable &, const Variable &)
CanonicalForm replacevar ( const CanonicalForm & f, const Variable & x1, const Variable & x2 )
Definition: cf_ops.cc:271
CFList
List< CanonicalForm > CFList
Definition: canonicalform.h:388
count
int status int void size_t count
Definition: si_signals.h:58
H
CanonicalForm H
Definition: facAbsFact.cc:64
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
geval
CanonicalForm geval
Definition: facAbsFact.cc:64
index
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:585
A
#define A
Definition: sirandom.c:24
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
totaldegree
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition: cf_ops.cc:523
ListIterator
Definition: ftmpl_list.h:17
facFqFactorize.h