My Project
Loading...
Searching...
No Matches
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 FACTORY_PUBLIC 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 FACTORY_PUBLIC 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 262 of file facAbsFact.cc.

264{
265 //TODO handle homogeneous input, is already done in LIB interface but still...
266 ASSERT (getCharacteristic() == 0, "expected poly over Q");
267
268 CanonicalForm F= G;
269
270 CanonicalForm LcF= Lc (F);
271 bool isRat= isOn (SW_RATIONAL);
272 if (isRat)
273 F *= bCommonDen (F);
274
276 F /= icontent (F);
277 if (isRat)
278 On (SW_RATIONAL);
279
280 CFFList rationalFactors= factorize (F);
281
282 CFAFList result, resultBuf;
283
285 CFFListIterator i= rationalFactors;
286 i++;
287 for (; i.hasItem(); i++)
288 {
289 resultBuf= absFactorizeMain (i.getItem().factor());
290 for (iter= resultBuf; iter.hasItem(); iter++)
291 iter.getItem()= CFAFactor (iter.getItem().factor(),
292 iter.getItem().minpoly(), i.getItem().exp());
293 result= Union (result, resultBuf);
294 }
295
296 if (isRat)
298 result.insert (CFAFactor (LcF, 1, 1));
299
300 return result;
301}
bool isOn(int sw)
switches
void On(int sw)
switches
void Off(int sw)
switches
AFactor< CanonicalForm > CFAFactor
CanonicalForm FACTORY_PUBLIC icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f )
Definition: cf_gcd.cc:74
CanonicalForm Lc(const CanonicalForm &f)
int FACTORY_PUBLIC getCharacteristic()
Definition: cf_char.cc:70
int i
Definition: cfEzgcd.cc:132
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
CFFList FACTORY_PUBLIC factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:405
#define ASSERT(expression, message)
Definition: cf_assert.h:99
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:31
factory's main class
Definition: canonicalform.h:86
T & getItem() const
Definition: ftmpl_list.cc:431
CanonicalForm LcF
Definition: facAbsBiFact.cc:50
return result
Definition: facAbsBiFact.cc:75
CFListIterator iter
Definition: facAbsFact.cc:61
CFAFList absFactorizeMain(const CanonicalForm &G)
main absolute factorization routine, expects poly which is irreducible over Q
Definition: facAbsFact.cc:303
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
STATIC_VAR TreeM * G
Definition: janet.cc:31
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition: syz3.cc:1027

◆ 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 303 of file facAbsFact.cc.

304{
306
308 F /= icontent (F);
309 On (SW_RATIONAL);
310
311 if (F.inCoeffDomain())
312 return CFAFList (CFAFactor (F, 1, 1));
313
314 // compress and find main Variable
315 CFMap N;
316 TIMING_START (abs_fac_compress)
318 TIMING_END_AND_PRINT (abs_fac_compress,
319 "time to compress poly in abs fact: ")
320
321 //univariate case
322 if (F.isUnivariate())
323 {
326 if (result.getFirst().factor().inCoeffDomain())
327 result.removeFirst();
328 return result;
329 }
330
331 //bivariate case
332 if (A.level() == 2)
333 {
336 return result; //needs compressed input
337 }
338
339 Variable x= Variable (1);
340 Variable y= Variable (2);
341
342 CFAFList factors;
343 A *= bCommonDen (A);
344 CFList Aeval, list, evaluation, bufEvaluation, bufAeval;
345 int factorNums= 1;
346 CFAFList absBiFactors, absBufBiFactors;
347 CanonicalForm evalPoly;
348 int lift, bufLift, lengthAeval2= A.level()-2;
349 CFList* bufAeval2= new CFList [lengthAeval2];
350 CFList* Aeval2= new CFList [lengthAeval2];
351 int counter;
352 int differentSecondVar= 0;
353 CanonicalForm bufA;
354
355 // several bivariate factorizations
356 TIMING_START (abs_fac_bifactor_total);
357 int absValue= 2;
358 REvaluation E (2, A.level(), IntRandom (absValue));
359 for (int i= 0; i < factorNums; i++)
360 {
361 counter= 0;
362 bufA= A;
363 bufAeval= CFList();
364 TIMING_START (abs_fac_evaluation);
365 bufEvaluation= evalPoints4AbsFact (bufA, bufAeval, E, absValue);
366 TIMING_END_AND_PRINT (abs_fac_evaluation,
367 "time to find evaluation point in abs fact: ");
368 E.nextpoint();
369 evalPoly= 0;
370
371 TIMING_START (abs_fac_evaluation);
372 evaluationWRTDifferentSecondVars (bufAeval2, bufEvaluation, A);
373 TIMING_END_AND_PRINT (abs_fac_evaluation,
374 "time to eval wrt diff second vars in abs fact: ");
375
376 for (int j= 0; j < lengthAeval2; j++)
377 {
378 if (!bufAeval2[j].isEmpty())
379 counter++;
380 }
381
382 bufLift= degree (A, y) + 1 + degree (LC(A, x), y);
383
384 TIMING_START (abs_fac_bi_factorizer);
385 absBufBiFactors= absBiFactorizeMain (bufAeval.getFirst(), true);
386 TIMING_END_AND_PRINT (abs_fac_bi_factorizer,
387 "time for bivariate factorization in abs fact: ");
388
389 if (absBufBiFactors.length() == 1)
390 {
391 factors.append (CFAFactor (A, 1, 1));
392 decompress (factors, N);
393 if (isOn (SW_RATIONAL))
394 normalize (factors);
395 delete [] bufAeval2;
396 delete [] Aeval2;
397 return factors;
398 }
399
400 if (i == 0)
401 {
402 Aeval= bufAeval;
403 evaluation= bufEvaluation;
404 absBiFactors= absBufBiFactors;
405 lift= bufLift;
406 for (int j= 0; j < lengthAeval2; j++)
407 Aeval2 [j]= bufAeval2 [j];
408 differentSecondVar= counter;
409 }
410 else
411 {
412 if (absBufBiFactors.length() < absBiFactors.length() ||
413 ((bufLift < lift) &&
414 (absBufBiFactors.length() == absBiFactors.length())) ||
415 counter > differentSecondVar)
416 {
417 Aeval= bufAeval;
418 evaluation= bufEvaluation;
419 absBiFactors= absBufBiFactors;
420 lift= bufLift;
421 for (int j= 0; j < lengthAeval2; j++)
422 Aeval2 [j]= bufAeval2 [j];
423 differentSecondVar= counter;
424 }
425 }
426 int k= 0;
427 for (CFListIterator j= bufEvaluation; j.hasItem(); j++, k++)
428 evalPoly += j.getItem()*power (x, k);
429 list.append (evalPoly);
430 }
431
432 delete [] bufAeval2;
433
434 CFList rationalFactors;
435 Variable v= mvar (absBiFactors.getFirst().minpoly());
436
437 CFList biFactors;
438 for (CFAFListIterator iter= absBiFactors; iter.hasItem(); iter++)
439 biFactors.append (iter.getItem().factor());
440
441 sortList (biFactors, x);
442
444 bool irred= false;
445
446 TIMING_START (abs_fac_bi_factorizer);
448 TIMING_END_AND_PRINT (abs_fac_bi_factorizer,
449 "time for bivariate factorization wrt diff second vars in abs fact: ");
450
451 TIMING_END_AND_PRINT (abs_fac_bifactor_total,
452 "total time for eval and bivar factors in abs fact: ");
453 if (irred)
454 {
455 factors.append (CFAFactor (A, 1, 1));
456 decompress (factors, N);
457 if (isOn (SW_RATIONAL))
458 normalize (factors);
459 delete [] Aeval2;
460 return factors;
461 }
462
463 if (minFactorsLength == 0)
464 minFactorsLength= biFactors.length();
465 else if (biFactors.length() > minFactorsLength)
466 refineBiFactors (A, biFactors, Aeval2, evaluation, minFactorsLength);
468
469 CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
470
471 sortByUniFactors (Aeval2, lengthAeval2, uniFactors, biFactors, evaluation);
472
474
475 if (minFactorsLength == 1)
476 {
477 factors.append (CFAFactor (A, 1, 1));
478 decompress (factors, N);
479 if (isOn (SW_RATIONAL))
480 normalize (factors);
481 delete [] Aeval2;
482 return factors;
483 }
484
485 bool found= false;
486 if (differentSecondVar == lengthAeval2)
487 {
488 bool zeroOccured= false;
490 {
491 if (iter.getItem().isZero())
492 {
493 zeroOccured= true;
494 break;
495 }
496 }
497 if (!zeroOccured)
498 {
499 rationalFactors= sparseHeuristic (A, biFactors, Aeval2, evaluation,
501 if (rationalFactors.length() == biFactors.length())
502 {
503 for (CFListIterator iter= rationalFactors; iter.hasItem(); iter++)
504 {
506 {
507 factors= CFAFList (CFAFactor (iter.getItem(), getMipo (v), 1));
508 found= true;
509 break;
510 }
511 }
512 // necessary since extension may be too large
513 if (!found)
514 factors= RothsteinTrager (A, rationalFactors, v, evaluation);
515
516 decompress (factors, N);
517 normalize (factors);
518 delete [] Aeval2;
519 return factors;
520 }
521 else
522 rationalFactors= CFList();
523 //TODO case where factors.length() > 0
524 }
525 }
526
527 CFList * oldAeval= new CFList [lengthAeval2];
528 for (int i= 0; i < lengthAeval2; i++)
529 oldAeval[i]= Aeval2[i];
530
531 getLeadingCoeffs (A, Aeval2);
532
533 CFList biFactorsLCs;
534 for (CFListIterator i= biFactors; i.hasItem(); i++)
535 biFactorsLCs.append (LC (i.getItem(), 1));
536
537 Variable w;
538 TIMING_START (abs_fac_precompute_leadcoeff);
539 CFList leadingCoeffs= precomputeLeadingCoeff (LC (A, 1), biFactorsLCs, x,
540 evaluation, Aeval2, lengthAeval2, w);
541
542 if (w.level() != 1)
543 changeSecondVariable (A, biFactors, evaluation, oldAeval, lengthAeval2,
544 uniFactors, w);
545
546 CanonicalForm oldA= A;
547 CFList oldBiFactors= biFactors;
548
549 CanonicalForm LCmultiplier= leadingCoeffs.getFirst();
550 bool LCmultiplierIsConst= LCmultiplier.inCoeffDomain();
551 leadingCoeffs.removeFirst();
552
553 if (!LCmultiplierIsConst)
554 distributeLCmultiplier (A, leadingCoeffs, biFactors, evaluation,
555 LCmultiplier);
556
557 //prepare leading coefficients
558 CFList* leadingCoeffs2= new CFList [lengthAeval2];
559 prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(), leadingCoeffs,
560 biFactors, evaluation);
561
563 CFList bufLeadingCoeffs2= leadingCoeffs2[lengthAeval2-1];
564 CFList bufBiFactors= biFactors;
565 bufA= A;
566 CanonicalForm testVars, bufLCmultiplier= LCmultiplier;
567 if (!LCmultiplierIsConst)
568 {
569 testVars= Variable (2);
570 for (int i= 0; i < lengthAeval2; i++)
571 {
572 if (!oldAeval[i].isEmpty())
573 testVars *= oldAeval[i].getFirst().mvar();
574 }
575 }
576 TIMING_END_AND_PRINT(abs_fac_precompute_leadcoeff,
577 "time to precompute LC in abs fact: ");
578
579 TIMING_START (abs_fac_luckswang);
580 CFList bufFactors= CFList();
581 bool LCheuristic= false;
582 if (LucksWangSparseHeuristic (A, biFactors, 2, leadingCoeffs2[lengthAeval2-1],
583 rationalFactors))
584 {
585 int check= biFactors.length();
586 int * index= new int [factors.length()];
587 CFList oldFactors= rationalFactors;
588 rationalFactors= recoverFactors (A, rationalFactors, index);
589
590 if (check == rationalFactors.length())
591 {
592 if (w.level() != 1)
593 {
594 for (iter= rationalFactors; iter.hasItem(); iter++)
595 iter.getItem()= swapvar (iter.getItem(), w, y);
596 }
597
598 for (CFListIterator iter= rationalFactors; iter.hasItem(); iter++)
599 {
601 {
602 factors= CFAFList (CFAFactor (iter.getItem(), getMipo (v), 1));
603 found=true;
604 break;
605 }
606 }
607 // necessary since extension may be too large
608 if (!found)
609 factors= RothsteinTrager (A, rationalFactors, v, evaluation);
610
611 decompress (factors, N);
612 normalize (factors);
613 delete [] index;
614 delete [] Aeval2;
615 TIMING_END_AND_PRINT (abs_fac_luckswang,
616 "time for successful LucksWang in abs fact: ");
617 return factors;
618 }
619 else if (rationalFactors.length() > 0)
620 {
621 int oneCount= 0;
622 CFList l;
623 for (int i= 0; i < check; i++)
624 {
625 if (index[i] == 1)
626 {
627 iter=biFactors;
628 for (int j=1; j <= i-oneCount; j++)
629 iter++;
630 iter.remove (1);
631 for (int j= 0; j < lengthAeval2; j++)
632 {
633 l= leadingCoeffs2[j];
634 iter= l;
635 for (int k=1; k <= i-oneCount; k++)
636 iter++;
637 iter.remove (1);
638 leadingCoeffs2[j]=l;
639 }
640 oneCount++;
641 }
642 }
643 bufFactors= rationalFactors;
644 rationalFactors= CFList();
645 }
646 else if (!LCmultiplierIsConst && rationalFactors.length() == 0)
647 {
648 LCheuristic= true;
649 rationalFactors= oldFactors;
650 CFList contents, LCs;
651 bool foundTrueMultiplier= false;
652 LCHeuristic2 (LCmultiplier,rationalFactors,leadingCoeffs2[lengthAeval2-1],
653 contents, LCs, foundTrueMultiplier);
654 if (foundTrueMultiplier)
655 {
656 A= oldA;
657 leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
658 for (int i= lengthAeval2-1; i > -1; i--)
659 leadingCoeffs2[i]= CFList();
660 prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),
661 leadingCoeffs, biFactors, evaluation);
662 }
663 else
664 {
665 bool foundMultiplier= false;
666 LCHeuristic3 (LCmultiplier, rationalFactors, oldBiFactors, contents,
667 oldAeval,A,leadingCoeffs2, lengthAeval2, foundMultiplier);
668 // coming from above: divide out more LCmultiplier if possible
669 if (foundMultiplier)
670 {
671 foundMultiplier= false;
672 LCHeuristic4 (oldBiFactors, oldAeval, contents, rationalFactors,
673 testVars, lengthAeval2, leadingCoeffs2, A, LCmultiplier,
674 foundMultiplier);
675 }
676 else
677 {
678 LCHeuristicCheck (LCs, contents, A, oldA,
679 leadingCoeffs2[lengthAeval2-1], foundMultiplier);
680 if (!foundMultiplier && fdivides (getVars (LCmultiplier), testVars))
681 {
682 LCHeuristic (A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
683 lengthAeval2, evaluation, oldBiFactors);
684 }
685 }
686
687 // patch everything together again
688 leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
689 for (int i= lengthAeval2-1; i > -1; i--)
690 leadingCoeffs2[i]= CFList();
691 prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),leadingCoeffs,
692 biFactors, evaluation);
693 }
694 rationalFactors= CFList();
695 if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
696 {
697 LCheuristic= false;
698 A= bufA;
699 biFactors= bufBiFactors;
700 leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
701 LCmultiplier= bufLCmultiplier;
702 }
703 }
704 else
705 rationalFactors= CFList();
706 delete [] index;
707 }
708 TIMING_END_AND_PRINT (abs_fac_luckswang, "time for LucksWang in abs fact: ");
709
710 TIMING_START (abs_fac_lcheuristic);
711 if (!LCheuristic && !LCmultiplierIsConst && bufFactors.isEmpty()
712 && fdivides (getVars (LCmultiplier), testVars))
713 {
714 LCheuristic= true;
715 LCHeuristic (A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
716 lengthAeval2, evaluation, oldBiFactors);
717
718 leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
719 for (int i= lengthAeval2-1; i > -1; i--)
720 leadingCoeffs2[i]= CFList();
721 prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),leadingCoeffs,
722 biFactors, evaluation);
723
724 if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
725 {
726 LCheuristic= false;
727 A= bufA;
728 biFactors= bufBiFactors;
729 leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
730 LCmultiplier= bufLCmultiplier;
731 }
732 }
733 TIMING_END_AND_PRINT (abs_fac_lcheuristic,
734 "time for Lc heuristic in abs fact: ");
735
736tryAgainWithoutHeu:
737 //shifting to zero
738 TIMING_START (abs_fac_shift_to_zero);
739 CanonicalForm denA= bCommonDen (A);
740 A *= denA;
742 A /= denA;
743
744 for (iter= biFactors; iter.hasItem(); iter++)
745 iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
746
747 for (int i= 0; i < lengthAeval2-1; i++)
748 leadingCoeffs2[i]= CFList();
749 for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++)
750 {
752 for (int i= A.level() - 4; i > -1; i--)
753 {
754 if (i + 1 == lengthAeval2-1)
755 leadingCoeffs2[i].append (iter.getItem() (0, i + 4));
756 else
757 leadingCoeffs2[i].append (leadingCoeffs2[i+1].getLast() (0, i + 4));
758 }
759 }
760 TIMING_END_AND_PRINT (abs_fac_shift_to_zero,
761 "time to shift evaluation point to zero in abs fact: ");
762
763 CFArray Pi;
764 CFList diophant;
765 int* liftBounds= new int [A.level() - 1];
766 int liftBoundsLength= A.level() - 1;
767 for (int i= 0; i < liftBoundsLength; i++)
768 liftBounds [i]= degree (A, i + 2) + 1;
769
771 bool noOneToOne= false;
772
773 TIMING_START (abs_fac_cleardenom);
774 CFList commonDenominators;
775 for (iter=biFactors; iter.hasItem(); iter++)
776 commonDenominators.append (bCommonDen (iter.getItem()));
777 CanonicalForm tmp1, tmp2, tmp3=1;
778 CFListIterator iter2;
779 for (int i= 0; i < lengthAeval2; i++)
780 {
781 iter2= commonDenominators;
782 for (iter= leadingCoeffs2[i]; iter.hasItem(); iter++, iter2++)
783 {
786 iter2.getItem()= lcm (iter2.getItem(), tmp1);
787 On (SW_RATIONAL);
788 }
789 }
790 tmp1= prod (commonDenominators);
791 for (iter= Aeval; iter.hasItem(); iter++)
792 {
793 tmp2= bCommonDen (iter.getItem()/denA);
795 tmp3= lcm (tmp2,tmp3);
796 On (SW_RATIONAL);
797 }
798 CanonicalForm multiplier;
799 multiplier= tmp3/tmp1;
800 iter2= commonDenominators;
801 for (iter=biFactors; iter.hasItem(); iter++, iter2++)
802 iter.getItem() *= iter2.getItem()*multiplier;
803
804 for (iter= Aeval; iter.hasItem(); iter++)
805 iter.getItem() *= tmp3*power (multiplier, biFactors.length() - 1)/denA;
806
807 for (int i= 0; i < lengthAeval2; i++)
808 {
809 iter2= commonDenominators;
810 for (iter= leadingCoeffs2[i]; iter.hasItem(); iter++, iter2++)
811 iter.getItem() *= iter2.getItem()*multiplier;
812 }
813
814 TIMING_END_AND_PRINT (abs_fac_cleardenom,
815 "time to clear denominators in abs fact: ");
816
817 TIMING_START (abs_fac_hensel_lift);
818 rationalFactors= nonMonicHenselLift (Aeval, biFactors,leadingCoeffs2,diophant,
819 Pi, liftBounds, liftBoundsLength, noOneToOne);
820 TIMING_END_AND_PRINT (abs_fac_hensel_lift,
821 "time for non monic hensel lifting in abs fact: ");
822
823 if (!noOneToOne)
824 {
825 int check= rationalFactors.length();
826 A= oldA;
827 TIMING_START (abs_fac_recover_factors);
828 rationalFactors= recoverFactors (A, rationalFactors, evaluation);
829 TIMING_END_AND_PRINT (abs_fac_recover_factors,
830 "time to recover factors in abs fact: ");
831 if (check != rationalFactors.length())
832 noOneToOne= true;
833 else
834 rationalFactors= Union (rationalFactors, bufFactors);
835 }
836 if (noOneToOne)
837 {
838 if (!LCmultiplierIsConst && LCheuristic)
839 {
840 A= bufA;
841 biFactors= bufBiFactors;
842 leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
843 delete [] liftBounds;
844 LCheuristic= false;
845 goto tryAgainWithoutHeu;
846 //something probably went wrong in the heuristic
847 }
848
849 A= shift2Zero (oldA, Aeval, evaluation);
850 biFactors= oldBiFactors;
851 for (iter= biFactors; iter.hasItem(); iter++)
852 iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
853 CanonicalForm LCA= LC (Aeval.getFirst(), 1);
854 CanonicalForm yToLift= power (y, lift);
855 CFListIterator i= biFactors;
856 lift= degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1;
857 i++;
858
859 for (; i.hasItem(); i++)
860 lift= tmax (lift, degree (i.getItem(), 2)+degree (LC (i.getItem(), 1))+1);
861
862 lift= tmax (degree (Aeval.getFirst() , 2) + 1, lift);
863
864 i= biFactors;
865 yToLift= power (y, lift);
866 CanonicalForm dummy;
867 for (; i.hasItem(); i++)
868 {
869 LCA= LC (i.getItem(), 1);
870 extgcd (LCA, yToLift, LCA, dummy);
871 i.getItem()= mod (i.getItem()*LCA, yToLift);
872 }
873
874 liftBoundsLength= F.level() - 1;
875 liftBounds= liftingBounds (A, lift);
876
877 CFList MOD;
878 bool earlySuccess;
879 CFList earlyFactors;
881 CFList liftedFactors;
882 TIMING_START (abs_fac_hensel_lift);
883 liftedFactors= henselLiftAndEarly
884 (A, MOD, liftBounds, earlySuccess, earlyFactors,
885 Aeval, biFactors, evaluation, info);
886 TIMING_END_AND_PRINT (abs_fac_hensel_lift,
887 "time for hensel lifting in abs fact: ");
888
889 TIMING_START (abs_fac_factor_recombination);
890 rationalFactors= factorRecombination (A, liftedFactors, MOD);
891 TIMING_END_AND_PRINT (abs_fac_factor_recombination,
892 "time for factor recombination in abs fact: ");
893
894 if (earlySuccess)
895 rationalFactors= Union (rationalFactors, earlyFactors);
896
897 for (CFListIterator i= rationalFactors; i.hasItem(); i++)
898 {
899 int kk= Aeval.getLast().level();
900 for (CFListIterator j= evaluation; j.hasItem(); j++, kk--)
901 {
902 if (i.getItem().level() < kk)
903 continue;
904 i.getItem()= i.getItem() (Variable (kk) - j.getItem(), kk);
905 }
906 }
907 }
908
909 if (w.level() != 1)
910 {
911 for (CFListIterator iter= rationalFactors; iter.hasItem(); iter++)
912 iter.getItem()= swapvar (iter.getItem(), w, y);
913 }
914
915 for (CFListIterator iter= rationalFactors; iter.hasItem(); iter++)
916 {
918 {
919 factors= CFAFList (CFAFactor (iter.getItem(), getMipo (v), 1));
920 found= true;
921 break;
922 }
923 }
924
925 // necessary since extension may be too large
926 if (!found)
927 factors= RothsteinTrager (A, rationalFactors, v, evaluation);
928
929 decompress (factors, N);
930 if (isOn (SW_RATIONAL))
931 normalize (factors);
932
933 delete [] leadingCoeffs2;
934 delete [] oldAeval;
935 delete [] Aeval2;
936 delete[] liftBounds;
937
938 return factors;
939}
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
CanonicalForm getVars(const CanonicalForm &f)
CanonicalForm getVars ( const CanonicalForm & f )
Definition: cf_ops.cc:350
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
int degree(const CanonicalForm &f)
CanonicalForm FACTORY_PUBLIC swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition: cf_ops.cc:523
List< CanonicalForm > CFList
Variable mvar(const CanonicalForm &f)
CanonicalForm LC(const CanonicalForm &f)
List< CFAFactor > CFAFList
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:56
int l
Definition: cfEzgcd.cc:100
int k
Definition: cfEzgcd.cc:99
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:91
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
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:174
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
class CFMap
Definition: cf_map.h:85
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
bool inCoeffDomain() const
int level() const
level() returns the level of CO.
ExtensionInfo contains information about extension.
Definition: ExtensionInfo.h:51
generate random integers
Definition: cf_random.h:56
void remove(int moveright)
Definition: ftmpl_list.cc:526
T getFirst() const
Definition: ftmpl_list.cc:279
void removeFirst()
Definition: ftmpl_list.cc:287
int length() const
Definition: ftmpl_list.cc:273
void append(const T &)
Definition: ftmpl_list.cc:256
T getLast() const
Definition: ftmpl_list.cc:309
int isEmpty() const
Definition: ftmpl_list.cc:267
class to generate random evaluation points
Definition: cf_reval.h:26
void nextpoint()
Definition: cf_reval.cc:46
factory's class for variables
Definition: variable.h:33
CFAFList absBiFactorizeMain(const CanonicalForm &G, bool full)
main absolute factorization routine, expects bivariate poly which is irreducible over Q
CFAFList uniAbsFactorize(const CanonicalForm &F, bool full=false)
univariate absolute factorization over Q
const CanonicalForm int const CFList & evaluation
Definition: facAbsFact.cc:52
Variable x
Definition: facAbsFact.cc:58
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:53
REvaluation E(1, terms.length(), IntRandom(25))
CFList evalPoints4AbsFact(const CanonicalForm &F, CFList &eval, Evaluation &E, int &intervalSize)
Definition: facAbsFact.cc:132
if(degree(Feval, x) >=8||degree(H, x) >=8) res
const CanonicalForm & w
Definition: facAbsFact.cc:51
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:105
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:39
bool found
Definition: facFactorize.cc:55
void factorizationWRTDifferentSecondVars(const CanonicalForm &A, CFList *&Aeval, int &minFactorsLength, bool &irred, const Variable &w)
CFList int & minFactorsLength
[in,out] minimal length of bivariate factors
Definition: facFactorize.h:33
CFList *& Aeval
<[in] poly
Definition: facFactorize.h:31
CFList int bool & irred
[in,out] Is A irreducible?
Definition: facFactorize.h:34
else L getLast()(0
CFList tmp1
Definition: facFqBivar.cc:72
CFList tmp2
Definition: facFqBivar.cc:72
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:1152
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:586
CFList recoverFactors(const CanonicalForm &F, const CFList &factors)
divides factors by their content wrt. Variable(1) and checks if these polys divide F
CanonicalForm shift2Zero(const CanonicalForm &F, CFList &Feval, const CFList &evaluation, int l)
shift evaluation point to zero
int * liftingBounds(const CanonicalForm &A, const int &bivarLiftBound)
compute lifting bounds
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,...
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,...
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...
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...
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 ...
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...
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
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...
void getLeadingCoeffs(const CanonicalForm &A, CFList *&Aeval)
extract leading coefficients wrt Variable(1) from bivariate factors obtained from factorizations of A...
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 ...
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...
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
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....
CFList buildUniFactors(const CFList &biFactors, const CanonicalForm &evalPoint, const Variable &y)
plug in evalPoint for y in a list of polys
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:2855
int j
Definition: facHensel.cc:110
fq_nmod_poly_t prod
Definition: facHensel.cc:100
void sortList(CFList &list, const Variable &x)
sort a list of polynomials by their degree in x.
Definition: facHensel.cc:449
int LucksWangSparseHeuristic(const CanonicalForm &F, const CFList &factors, int level, const CFList &leadingCoeffs, CFList &result)
sparse heuristic lifting by Wang and Lucks
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...
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
#define info
Definition: libparse.cc:1256
VAR int check
Definition: libparse.cc:1106
ideal lift(const ideal J, const ring r, const ideal inI, const ring s)
Definition: lift.cc:26
number absValue(poly p)
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition: minpoly.cc:709
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
#define A
Definition: sirandom.c:24
#define TIMING_START(t)
Definition: timing.h:92
#define TIMING_END_AND_PRINT(t, msg)
Definition: timing.h:94
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207