My Project  UNKNOWN_GIT_VERSION
Functions
facAbsFact.h File Reference
#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]G[in] poly 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 }

◆ 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]F[in] irred 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  {
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 }
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:28
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
isOn
bool isOn(int sw)
switches
Definition: canonicalform.cc:1912
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
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
lift
ideal lift(const ideal J, const ring r, const ideal inI, const ring s)
Definition: lift.cc:26
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:34
prod
fq_nmod_poly_t prod
Definition: facHensel.cc:95
CFMap
class CFMap
Definition: cf_map.h:85
sortList
void sortList(CFList &list, const Variable &x)
sort a list of polynomials by their degree in x.
Definition: facHensel.cc:441
LCHeuristic3
void LCHeuristic3(const CanonicalForm &LCmultiplier, const CFList &factors, const CFList &oldBiFactors, const CFList &contents, const CFList *oldAeval, CanonicalForm &A, CFList *&leadingCoeffs, int lengthAeval, bool &foundMultiplier)
heuristic to remove LCmultiplier from a factor based on the contents of factors. factors are assumed ...
Definition: facFqFactorize.cc:2792
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition: canonicalform.cc:1837
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))
CFAFList
return CFAFList(CFAFactor(factor, getMipo(beta), 1))
N
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:49
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
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
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
CanonicalForm
factory's main class
Definition: canonicalform.h:83
found
bool found
Definition: facFactorize.cc:56
LCHeuristicCheck
void LCHeuristicCheck(const CFList &LCs, const CFList &contents, CanonicalForm &A, const CanonicalForm &oldA, CFList &leadingCoeffs, bool &foundTrueMultiplier)
checks if prod(LCs)==LC (oldA,1) and if so divides elements of leadingCoeffs by elements in contents,...
Definition: facFqFactorize.cc:2746
minFactorsLength
CFList int & minFactorsLength
[in,out] minimal length of bivariate factors
Definition: facFactorize.h:33
evaluation
const CanonicalForm int const CFList & evaluation
Definition: facAbsFact.cc:56
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
getMipo
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
ASSERT
#define ASSERT(expression, message)
Definition: cf_assert.h:99
absFactorizeMain
CFAFList absFactorizeMain(const CanonicalForm &G)
main absolute factorization routine, expects poly which is irreducible over Q
Definition: facAbsFact.cc:308
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:56
if
if(degree(Feval, x) >=8||degree(H, x) >=8) res
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
LcF
CanonicalForm LcF
Definition: facAbsBiFact.cc:51
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
tmin
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
REvaluation
class to generate random evaluation points
Definition: cf_reval.h:26
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
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
ListIterator::hasItem
int hasItem()
Definition: ftmpl_list.cc:439
fdivides
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
Definition: cf_algorithm.cc:338
decompress
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
Definition: cfNewtonPolygon.cc:853
LCHeuristic2
void LCHeuristic2(const CanonicalForm &LCmultiplier, const CFList &factors, CFList &leadingCoeffs, CFList &contents, CFList &LCs, bool &foundTrueMultiplier)
heuristic to distribute LCmultiplier onto factors based on the contents of factors....
Definition: facFqFactorize.cc:2762
Off
void Off(int sw)
switches
Definition: canonicalform.cc:1905
List::removeFirst
void removeFirst()
Definition: ftmpl_list.cc:287
List::getFirst
T getFirst() const
Definition: ftmpl_list.cc:279
tmax
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
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
List::length
int length() const
Definition: ftmpl_list.cc:273
TIMING_END_AND_PRINT
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
normalize
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition: syz3.cc:1027
Variable
factory's class for variables
Definition: factory.h:118
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:51
LC
CanonicalForm LC(const CanonicalForm &f)
Definition: canonicalform.h:303
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
getLast
else L getLast()(0
check
int check
Definition: libparse.cc:1104
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
Union
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
absValue
number absValue(poly p)
Definition: linearAlgebra.cc:725
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
CFList
List< CanonicalForm > CFList
Definition: canonicalform.h:388
precomputeLeadingCoeff
CFList precomputeLeadingCoeff(const CanonicalForm &LCF, const CFList &LCFFactors, const Variable &alpha, const CFList &evaluation, CFList *&differentSecondVarLCs, int lSecondVarLCs, Variable &y)
computes a list l of length length(LCFFactors)+1 of polynomials such that prod (l)=LCF,...
Definition: facFqFactorize.cc:1464
henselLiftAndEarly
CFList henselLiftAndEarly(CanonicalForm &A, bool &earlySuccess, CFList &earlyFactors, DegreePattern &degs, int &liftBound, const CFList &uniFactors, const ExtensionInfo &info, const CanonicalForm &eval, modpk &b, CanonicalForm &den)
hensel Lifting and early factor detection
Definition: facFqBivar.cc:1115
tmp2
CFList tmp2
Definition: facFqBivar.cc:70
myCompress
int myCompress(const CanonicalForm &F, const CanonicalForm &G, CFMap &M, CFMap &N, bool topLevel)
compressing two polynomials F and G, M is used for compressing, N to reverse the compression
Definition: cfModGcd.cc:93
G
static TreeM * G
Definition: janet.cc:32
CanonicalForm::level
int level() const
level() returns the level of CO.
Definition: canonicalform.cc:543
List::append
void append(const T &)
Definition: ftmpl_list.cc:256
index
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
A
#define A
Definition: sirandom.c:23
info
const ExtensionInfo & info
< [in] sqrfree poly
Definition: facFqFactorize.h:38
degree
int degree(const CanonicalForm &f)
Definition: canonicalform.h:309
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
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