304{
306
310
313
314
319 "time to compress poly in abs fact: ")
320
321
322 if (F.isUnivariate())
323 {
326 if (
result.getFirst().factor().inCoeffDomain())
329 }
330
331
333 {
337 }
338
341
351 int counter;
354
355
360 {
361 counter= 0;
367 "time to find evaluation point in abs fact: ");
370
374 "time to eval wrt diff second vars in abs fact: ");
375
377 {
379 counter++;
380 }
381
383
387 "time for bivariate factorization in abs fact: ");
388
390 {
398 }
399
401 {
409 }
410 else
411 {
416 {
424 }
425 }
430 }
431
433
436
440
442
445
449 "time for bivariate factorization wrt diff second vars in abs fact: ");
450
452 "total time for eval and bivar factors in abs fact: ");
454 {
461 }
462
468
470
472
474
476 {
483 }
484
487 {
490 {
492 {
494 break;
495 }
496 }
498 {
502 {
504 {
506 {
509 break;
510 }
511 }
512
515
520 }
521 else
523
524 }
525 }
526
530
532
536
541
545
548
552
556
557
561
568 {
571 {
574 }
575 }
577 "time to precompute LC in abs fact: ");
578
584 {
589
591 {
593 {
596 }
597
599 {
601 {
604 break;
605 }
606 }
607
610
616 "time for successful LucksWang in abs fact: ");
618 }
620 {
624 {
626 {
632 {
639 }
641 }
642 }
645 }
647 {
655 {
662 }
663 else
664 {
668
670 {
675 }
676 else
677 {
681 {
684 }
685 }
686
687
693 }
696 {
702 }
703 }
704 else
707 }
709
713 {
717
723
725 {
731 }
732 }
734 "time for Lc heuristic in abs fact: ");
735
737
743
746
750 {
752 for (
int i=
A.level() - 4;
i > -1;
i--)
753 {
756 else
758 }
759 }
761 "time to shift evaluation point to zero in abs fact: ");
762
769
772
780 {
783 {
788 }
789 }
792 {
797 }
803
806
808 {
812 }
813
815 "time to clear denominators in abs fact: ");
816
821 "time for non monic hensel lifting in abs fact: ");
822
824 {
830 "time to recover factors in abs fact: ");
833 else
835 }
837 {
839 {
846
847 }
848
858
859 for (;
i.hasItem();
i++)
861
863
867 for (;
i.hasItem();
i++)
868 {
872 }
873
876
887 "time for hensel lifting in abs fact: ");
888
892 "time for factor recombination in abs fact: ");
893
896
898 {
901 {
902 if (
i.getItem().level() <
kk)
903 continue;
905 }
906 }
907 }
908
910 {
913 }
914
916 {
918 {
921 break;
922 }
923 }
924
925
928
932
937
939}
const CanonicalForm CFMap CFMap & N
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
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,...
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
ExtensionInfo contains information about extension.
void remove(int moveright)
class to generate random evaluation points
factory's class for variables
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
const CanonicalForm int const CFList const Variable & y
REvaluation E(1, terms.length(), IntRandom(25))
CFList evalPoints4AbsFact(const CanonicalForm &F, CFList &eval, Evaluation &E, int &intervalSize)
if(degree(Feval, x) >=8||degree(H, x) >=8) res
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".
const Variable & v
< [in] a sqrfree bivariate poly
void factorizationWRTDifferentSecondVars(const CanonicalForm &A, CFList *&Aeval, int &minFactorsLength, bool &irred, const Variable &w)
CFList int & minFactorsLength
[in,out] minimal length of bivariate factors
CFList *& Aeval
<[in] poly
CFList int bool & irred
[in,out] Is A irreducible?
CFList henselLiftAndEarly(CanonicalForm &A, bool &earlySuccess, CFList &earlyFactors, DegreePattern °s, int &liftBound, const CFList &uniFactors, const ExtensionInfo &info, const CanonicalForm &eval, modpk &b, CanonicalForm &den)
hensel Lifting and early factor detection
CFList factorRecombination(CFList &factors, CanonicalForm &F, const CanonicalForm &N, DegreePattern °s, 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...
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)
void sortList(CFList &list, const Variable &x)
sort a list of polynomials by their degree in x.
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...
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
ideal lift(const ideal J, const ring r, const ideal inI, const ring s)
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
static int index(p_Length length, p_Ord ord)
#define TIMING_END_AND_PRINT(t, msg)