Functions
facAbsFact.h File Reference

absolute multivariate factorization over Q More...

#include "facAbsBiFact.h"

Go to the source code of this file.

Functions

CFAFList absFactorizeMain (const CanonicalForm &F)
 main absolute factorization routine, expects poly which is irreducible over Q More...
 
CFAFList absFactorize (const CanonicalForm &G)
 absolute factorization of a multivariate poly over Q More...
 

Detailed Description

absolute multivariate factorization over Q

Author
Martin Lee

Definition in file facAbsFact.h.

Function Documentation

§ absFactorize()

CFAFList absFactorize ( const CanonicalForm G)

absolute factorization of a multivariate poly over Q

Returns
absFactorize returns a list whose entries contain three entities: an absolute irreducible factor, an irreducible univariate polynomial that defines the minimal field extension over which the irreducible factor is defined (note: in case the factor is already defined over Q[t]/(t), 1 is returned), and the multiplicity of the absolute irreducible factor
Parameters
[in]Gpoly over Q

Definition at line 267 of file facAbsFact.cc.

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 }
CanonicalForm icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f )
Definition: cf_gcd.cc:71
CFAFList absFactorizeMain(const CanonicalForm &G)
main absolute factorization routine, expects poly which is irreducible over Q
Definition: facAbsFact.cc:308
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition: syz3.cc:1027
void Off(int sw)
switches
factory's main class
Definition: canonicalform.h:75
void insert(const T &)
Definition: ftmpl_list.cc:193
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
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:390
AFactor< CanonicalForm > CFAFactor
T & getItem() const
Definition: ftmpl_list.cc:431
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
bool isOn(int sw)
switches
void On(int sw)
switches
int i
Definition: cfEzgcd.cc:123
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
#define ASSERT(expression, message)
Definition: cf_assert.h:99
return result
Definition: facAbsBiFact.cc:76

§ absFactorizeMain()

CFAFList absFactorizeMain ( const CanonicalForm F)

main absolute factorization routine, expects poly which is irreducible over Q

Returns
absFactorizeMain returns a list whose entries contain three entities: an absolute irreducible factor, an irreducible univariate polynomial that defines the minimal field extension over which the irreducible factor is defined (note: in case the factor is already defined over Q[t]/(t), 1 is returned as defining poly), and the multiplicity of the absolute irreducible factor
Parameters
[in]Firred poly over Q

Definition at line 308 of file facAbsFact.cc.

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  {
339  CFAFList result= absBiFactorizeMain (A);
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  {
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 }
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
CanonicalForm shift2Zero(const CanonicalForm &F, CFList &Feval, const CFList &evaluation, int l)
shift evaluation point to zero
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
List< CanonicalForm > CFList
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 ...
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition: syz3.cc:1027
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition: minpoly.cc:711
void changeSecondVariable(CanonicalForm &A, CFList &biFactors, CFList &evaluation, CFList *&oldAeval, int lengthAeval2, const CFList &uniFactors, const Variable &w)
changes the second variable to be w and updates all relevant data
CF_NO_INLINE CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
Definition: cf_inline.cc:564
int isEmpty() const
Definition: ftmpl_list.cc:267
void Off(int sw)
switches
CFAFList absBiFactorizeMain(const CanonicalForm &G, bool full)
main absolute factorization routine, expects bivariate poly which is irreducible over Q ...
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 &)
TIMING_START(fac_alg_resultant)
void sortByUniFactors(CFList *&Aeval, int AevalLength, CFList &uniFactors, CFList &biFactors, const CFList &evaluation)
sort bivariate factors in Aeval such that their corresponding univariate factors coincide with uniFac...
factory&#39;s class for variables
Definition: factory.h:115
CFList henselLiftAndEarly(CanonicalForm &A, bool &earlySuccess, CFList &earlyFactors, DegreePattern &degs, int &liftBound, const CFList &uniFactors, const ExtensionInfo &info, const CanonicalForm &eval, modpk &b, CanonicalForm &den)
hensel Lifting and early factor detection
Definition: facFqBivar.cc:1115
CFList *& Aeval
<[in] poly
Definition: facFactorize.h:31
Variable x
Definition: facAbsFact.cc:62
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
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
return CFAFList(CFAFactor(factor, getMipo(beta), 1))
static TreeM * G
Definition: janet.cc:38
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
Definition: cf_map.cc:210
CFListIterator iter
Definition: facAbsFact.cc:65
Rational abs(const Rational &a)
Definition: GMPrat.cc:443
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
bool found
Definition: facFactorize.cc:56
CFList factorRecombination(CFList &factors, CanonicalForm &F, const CanonicalForm &N, DegreePattern &degs, const CanonicalForm &eval, int s, int thres, const modpk &b, const CanonicalForm &den)
naive factor recombination as decribed in "Factoring multivariate polynomials over a finite field" by...
Definition: facFqBivar.cc:561
T getFirst() const
Definition: ftmpl_list.cc:279
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
ideal lift(const ideal J, const ring r, const ideal inI, const ring s)
Definition: lift.cc:26
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 ...
CFAFList uniAbsFactorize(const CanonicalForm &F, bool full=false)
univariate absolute factorization over Q
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:49
CanonicalForm getVars(const CanonicalForm &f)
CanonicalForm getVars ( const CanonicalForm & f )
Definition: cf_ops.cc:350
int j
Definition: myNF.cc:70
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
int level() const
Definition: factory.h:132
T & getItem() const
Definition: ftmpl_list.cc:431
const ExtensionInfo & info
< [in] sqrfree poly
#define A
Definition: sirandom.c:23
else L getLast()(0
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.
if(degree(Feval, x) >=8||degree(H, x) >=8) res
bool isOn(int sw)
switches
void On(int sw)
switches
int i
Definition: cfEzgcd.cc:123
T getLast() const
Definition: ftmpl_list.cc:309
CFList tmp2
Definition: facFqBivar.cc:70
void factorizationWRTDifferentSecondVars(const CanonicalForm &A, CFList *&Aeval, int &minFactorsLength, bool &irred, const Variable &w)
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
class CFMap
Definition: cf_map.h:84
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
void evaluationWRTDifferentSecondVars(CFList *&Aeval, const CFList &evaluation, const CanonicalForm &A)
evaluate a poly A with main variable at level 1 at an evaluation point in K^(n-1) wrt different secon...
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
CFList buildUniFactors(const CFList &biFactors, const CanonicalForm &evalPoint, const Variable &y)
plug in evalPoint for y in a list of polys
CFList sparseHeuristic(const CanonicalForm &A, const CFList &biFactors, CFList *&moreBiFactors, const CFList &evaluation, int minFactorsLength)
sparse heuristic which patches together bivariate factors of A wrt. different second variables by the...
void LCHeuristic3(const CanonicalForm &LCmultiplier, const CFList &factors, const CFList &oldBiFactors, const CFList &contents, const CFList *oldAeval, CanonicalForm &A, CFList *&leadingCoeffs, int lengthAeval, bool &foundMultiplier)
heuristic to remove LCmultiplier from a factor based on the contents of factors. factors are assumed ...
int length() const
Definition: ftmpl_list.cc:273
REvaluation E(1, terms.length(), IntRandom(25))
number absValue(poly p)
fq_nmod_poly_t prod
Definition: facHensel.cc:95
CFList tmp1
Definition: facFqBivar.cc:70
const CanonicalForm & w
Definition: facAbsFact.cc:55
void nextpoint()
Definition: cf_reval.cc:46
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition: cf_ops.cc:523
CFList int bool & irred
[in,out] Is A irreducible?
Definition: facFactorize.h:31
void LCHeuristicCheck(const CFList &LCs, const CFList &contents, CanonicalForm &A, const CanonicalForm &oldA, CFList &leadingCoeffs, bool &foundTrueMultiplier)
checks if prod(LCs)==LC (oldA,1) and if so divides elements of leadingCoeffs by elements in contents...
int level() const
level() returns the level of CO.
void append(const T &)
Definition: ftmpl_list.cc:256
int degree(const CanonicalForm &f)
void prepareLeadingCoeffs(CFList *&LCs, CanonicalForm &A, CFList &Aeval, int n, const CFList &leadingCoeffs, const CFList &biFactors, const CFList &evaluation)
normalize precomputed leading coefficients such that leading coefficients evaluated at evaluation in ...
polyrec * poly
Definition: hilb.h:10
CanonicalForm LC(const CanonicalForm &f)
void LCHeuristic2(const CanonicalForm &LCmultiplier, const CFList &factors, CFList &leadingCoeffs, CFList &contents, CFList &LCs, bool &foundTrueMultiplier)
heuristic to distribute LCmultiplier onto factors based on the contents of factors. factors are assumed to come from LucksWangSparseHeuristic. If not successful contents will contain the content of each element of factors and LCs will contain the LC of each element of factors divided by its content
void getLeadingCoeffs(const CanonicalForm &A, CFList *&Aeval)
extract leading coefficients wrt Variable(1) from bivariate factors obtained from factorizations of A...
int * liftingBounds(const CanonicalForm &A, const int &bivarLiftBound)
compute lifting bounds
int l
Definition: cfEzgcd.cc:94
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
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
bool inCoeffDomain() const