327 if (F.isUnivariate())
331 if (result.
getFirst().factor().inCoeffDomain())
351 CFAFList absBiFactors, absBufBiFactors;
353 int lift, bufLift, lengthAeval2=
A.level()-2;
357 int differentSecondVar= 0;
364 for (
int i= 0;
i < factorNums;
i++)
372 "time to find evaluation point in abs fact: ");
379 "time to eval wrt diff second vars in abs fact: ");
381 for (
int j= 0;
j < lengthAeval2;
j++)
383 if (!bufAeval2[
j].isEmpty())
392 "time for bivariate factorization in abs fact: ");
394 if (absBufBiFactors.
length() == 1)
408 evaluation= bufEvaluation;
409 absBiFactors= absBufBiFactors;
411 for (
int j= 0;
j < lengthAeval2;
j++)
412 Aeval2 [
j]= bufAeval2 [
j];
413 differentSecondVar= counter;
420 counter > differentSecondVar)
423 evaluation= bufEvaluation;
424 absBiFactors= absBufBiFactors;
426 for (
int j= 0;
j < lengthAeval2;
j++)
427 Aeval2 [
j]= bufAeval2 [
j];
428 differentSecondVar= counter;
433 evalPoly +=
j.getItem()*
power (x, k);
454 "time for bivariate factorization wrt diff second vars in abs fact: ");
457 "total time for eval and bivar factors in abs fact: ");
468 if (minFactorsLength == 0)
469 minFactorsLength= biFactors.
length();
472 minFactorsLength=
tmin (minFactorsLength, biFactors.length());
478 minFactorsLength=
tmin (minFactorsLength, biFactors.length());
480 if (minFactorsLength == 1)
491 if (differentSecondVar == lengthAeval2)
493 bool zeroOccured=
false;
506 if (rationalFactors.
length() == biFactors.length())
527 rationalFactors=
CFList();
533 for (
int i= 0;
i < lengthAeval2;
i++)
534 oldAeval[
i]= Aeval2[
i];
540 biFactorsLCs.
append (
LC (
i.getItem(), 1));
545 evaluation, Aeval2, lengthAeval2, w);
552 CFList oldBiFactors= biFactors;
558 if (!LCmultiplierIsConst)
568 CFList bufLeadingCoeffs2= leadingCoeffs2[lengthAeval2-1];
569 CFList bufBiFactors= biFactors;
572 if (!LCmultiplierIsConst)
575 for (
int i= 0;
i < lengthAeval2;
i++)
577 if (!oldAeval[
i].isEmpty())
578 testVars *= oldAeval[
i].
getFirst().mvar();
582 "time to precompute LC in abs fact: ");
586 bool LCheuristic=
false;
590 int check= biFactors.length();
592 CFList oldFactors= rationalFactors;
595 if (check == rationalFactors.
length())
599 for (iter= rationalFactors; iter.hasItem(); iter++)
600 iter.getItem()=
swapvar (iter.getItem(),
w,
y);
603 for (
CFListIterator iter= rationalFactors; iter.hasItem(); iter++)
621 "time for successful LucksWang in abs fact: ");
624 else if (rationalFactors.
length() > 0)
633 for (
int j=1;
j <=
i-oneCount;
j++)
636 for (
int j= 0;
j < lengthAeval2;
j++)
638 l= leadingCoeffs2[
j];
640 for (
int k=1; k <=
i-oneCount; k++)
648 bufFactors= rationalFactors;
649 rationalFactors=
CFList();
651 else if (!LCmultiplierIsConst && rationalFactors.
length() == 0)
654 rationalFactors= oldFactors;
656 bool foundTrueMultiplier=
false;
657 LCHeuristic2 (LCmultiplier,rationalFactors,leadingCoeffs2[lengthAeval2-1],
658 contents, LCs, foundTrueMultiplier);
659 if (foundTrueMultiplier)
662 leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
663 for (
int i= lengthAeval2-1;
i > -1;
i--)
670 bool foundMultiplier=
false;
671 LCHeuristic3 (LCmultiplier, rationalFactors, oldBiFactors, contents,
672 oldAeval,
A,leadingCoeffs2, lengthAeval2, foundMultiplier);
676 foundMultiplier=
false;
677 LCHeuristic4 (oldBiFactors, oldAeval, contents, rationalFactors,
678 testVars, lengthAeval2, leadingCoeffs2,
A, LCmultiplier,
684 leadingCoeffs2[lengthAeval2-1], foundMultiplier);
687 LCHeuristic (
A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
688 lengthAeval2, evaluation, oldBiFactors);
693 leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
694 for (
int i= lengthAeval2-1;
i > -1;
i--)
699 rationalFactors=
CFList();
700 if (!
fdivides (
LC (oldA,1),
prod (leadingCoeffs2[lengthAeval2-1])))
704 biFactors= bufBiFactors;
705 leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
706 LCmultiplier= bufLCmultiplier;
710 rationalFactors=
CFList();
716 if (!LCheuristic && !LCmultiplierIsConst && bufFactors.
isEmpty()
720 LCHeuristic (
A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
721 lengthAeval2, evaluation, oldBiFactors);
723 leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
724 for (
int i= lengthAeval2-1;
i > -1;
i--)
729 if (!
fdivides (
LC (oldA,1),
prod (leadingCoeffs2[lengthAeval2-1])))
733 biFactors= bufBiFactors;
734 leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
735 LCmultiplier= bufLCmultiplier;
739 "time for Lc heuristic in abs fact: ");
749 for (iter= biFactors; iter.hasItem(); iter++)
750 iter.getItem()= iter.getItem () (y + evaluation.
getLast(),
y);
752 for (
int i= 0;
i < lengthAeval2-1;
i++)
754 for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++)
757 for (
int i=
A.level() - 4;
i > -1;
i--)
759 if (
i + 1 == lengthAeval2-1)
760 leadingCoeffs2[
i].
append (iter.getItem() (0,
i + 4));
766 "time to shift evaluation point to zero in abs fact: ");
770 int* liftBounds=
new int [
A.level() - 1];
771 int liftBoundsLength=
A.level() - 1;
772 for (
int i= 0;
i < liftBoundsLength;
i++)
776 bool noOneToOne=
false;
779 CFList commonDenominators;
780 for (iter=biFactors; iter.hasItem(); iter++)
784 for (
int i= 0;
i < lengthAeval2;
i++)
786 iter2= commonDenominators;
787 for (iter= leadingCoeffs2[
i]; iter.hasItem(); iter++, iter2++)
795 tmp1=
prod (commonDenominators);
796 for (iter= Aeval; iter.hasItem(); iter++)
800 tmp3=
lcm (tmp2,tmp3);
804 multiplier= tmp3/
tmp1;
805 iter2= commonDenominators;
806 for (iter=biFactors; iter.hasItem(); iter++, iter2++)
807 iter.getItem() *= iter2.
getItem()*multiplier;
809 for (iter= Aeval; iter.hasItem(); iter++)
810 iter.getItem() *= tmp3*
power (multiplier, biFactors.length() - 1)/denA;
812 for (
int i= 0;
i < lengthAeval2;
i++)
814 iter2= commonDenominators;
815 for (iter= leadingCoeffs2[
i]; iter.hasItem(); iter++, iter2++)
816 iter.getItem() *= iter2.
getItem()*multiplier;
820 "time to clear denominators in abs fact: ");
824 Pi, liftBounds, liftBoundsLength, noOneToOne);
826 "time for non monic hensel lifting in abs fact: ");
830 int check= rationalFactors.length();
835 "time to recover factors in abs fact: ");
836 if (check != rationalFactors.length())
839 rationalFactors=
Union (rationalFactors, bufFactors);
843 if (!LCmultiplierIsConst && LCheuristic)
846 biFactors= bufBiFactors;
847 leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
848 delete [] liftBounds;
850 goto tryAgainWithoutHeu;
855 biFactors= oldBiFactors;
856 for (iter= biFactors; iter.hasItem(); iter++)
857 iter.getItem()= iter.getItem () (y + evaluation.
getLast(),
y);
870 yToLift=
power (y, lift);
875 extgcd (LCA, yToLift, LCA, dummy);
879 liftBoundsLength= F.
level() - 1;
889 (
A, MOD, liftBounds, earlySuccess, earlyFactors,
890 Aeval, biFactors, evaluation, info);
892 "time for hensel lifting in abs fact: ");
897 "time for factor recombination in abs fact: ");
900 rationalFactors=
Union (rationalFactors, earlyFactors);
904 int kk= Aeval.
getLast().level();
917 iter.getItem()=
swapvar (iter.getItem(),
w,
y);
938 delete [] leadingCoeffs2;
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
const CanonicalForm int const CFList const Variable & y
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)
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
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
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...
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's class for variables
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 *& Aeval
<[in] poly
CFList evalPoints4AbsFact(const CanonicalForm &F, CFList &eval, Evaluation &E, int &intervalSize)
CFList int & minFactorsLength
[in,out] minimal length of < bivariate factors
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...
class to generate random evaluation points
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 ...
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...
const CanonicalForm int const CFList & evaluation
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)
return CFAFList(CFAFactor(factor, getMipo(beta), 1))
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
Rational abs(const Rational &a)
void sortList(CFList &list, const Variable &x)
sort a list of polynomials by their degree in x.
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...
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
ideal lift(const ideal J, const ring r, const ideal inI, const ring s)
ExtensionInfo contains information about extension.
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
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
const ExtensionInfo & info
< [in] sqrfree poly
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
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
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)
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
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 ...
REvaluation E(1, terms.length(), IntRandom(25))
CFList int bool & irred
[in,out] Is A irreducible?
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 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 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
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".
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)