74 for (
int i= terms.
length();
i >= 1;
i--, iter++)
88 H= y*derivFeval-
geval;
97 while (
degree (sqrfPartRes) != s);
133 return RothsteinTragerResultant (F, w, s, evaluation, y);
156 if (count==E.
max() - E.
min() + 1)
175 if (!allZero && foundZero)
219 if (
degree (gcd_deriv) > 0)
228 if (uniFactors.
getFirst().factor().inCoeffDomain())
241 if (
degree (contentx) > 0)
250 if (
degree (contentx) > 0)
295 for (iter= resultBuf; iter.
hasItem(); iter++)
298 result=
Union (result, resultBuf);
324 "time to compress poly in abs fact: ")
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())
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++)
773 liftBounds [
i]=
degree (A,
i + 2) + 1;
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: ");
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);
916 for (
CFListIterator iter= rationalFactors; iter.hasItem(); iter++)
917 iter.getItem()=
swapvar (iter.getItem(),
w,
y);
920 for (
CFListIterator iter= rationalFactors; iter.hasItem(); iter++)
938 delete [] leadingCoeffs2;
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
int status int void size_t count
CanonicalForm shift2Zero(const CanonicalForm &F, CFList &Feval, const CFList &evaluation, int l)
shift evaluation point to zero
const CanonicalForm int s
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 ...
Conversion to and from NTL.
This file defines functions for Hensel lifting.
CFAFList absFactorizeMain(const CanonicalForm &G)
main absolute factorization routine, expects poly which is irreducible over Q
This file provides utility functions for multivariate factorization.
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)
This file defines functions for conversion to FLINT (www.flintlib.org) and back.
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 ...
functions to print debug output
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
generate random evaluation points
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
This file provides functions for factorizing a multivariate polynomial over , or GF...
CanonicalForm sqrfPart(const CanonicalForm &F)
squarefree part of a poly
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)
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 > &)
Variable rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables ...
ideal lift(const ideal J, const ring r, const ideal inI, const ring s)
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
TIMING_DEFINE_PRINT(abs_fac_bi_factorizer) TIMING_DEFINE_PRINT(abs_fac_hensel_lift) TIMING_DEFINE_PRINT(abs_fac_factor_recombination) TIMING_DEFINE_PRINT(abs_fac_shift_to_zero) TIMING_DEFINE_PRINT(abs_fac_precompute_leadcoeff) TIMING_DEFINE_PRINT(abs_fac_evaluation) TIMING_DEFINE_PRINT(abs_fac_recover_factors) TIMING_DEFINE_PRINT(abs_fac_bifactor_total) TIMING_DEFINE_PRINT(abs_fac_luckswang) TIMING_DEFINE_PRINT(abs_fac_lcheuristic) TIMING_DEFINE_PRINT(abs_fac_cleardenom) TIMING_DEFINE_PRINT(abs_fac_compress) CFAFList RothsteinTragerResultant(const CanonicalForm &F
steps 4)-8) of Algorithm B.7.8. from Greuel, Pfister "A Singular Introduction to Commutative Algebra"...
This file provides functions for sparse heuristic Hensel lifting.
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 ...
bivariate absolute factorization over Q described in "Modular Las Vegas Algorithms for Polynomial Abs...
CFAFList uniAbsFactorize(const CanonicalForm &F, bool full=false)
univariate absolute factorization over Q
const CanonicalForm CFMap CFMap & N
univariate Gcd over finite fields and Z, extended GCD over finite fields and Q
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.
multivariate factorization over Q(a)
declarations of higher level algorithms.
void factorizationWRTDifferentSecondVars(const CanonicalForm &A, CFList *&Aeval, int &minFactorsLength, bool &irred, const Variable &w)
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
CanonicalForm resultantZ(const CanonicalForm &A, const CanonicalForm &B, const Variable &x, bool prob)
modular resultant algorihtm over Z
static int index(p_Length length, p_Ord ord)
class to iterate through CanonicalForm's
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...
modular resultant algorithm as described by G.
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))
class to evaluate a polynomial at points
bool isZero(const CFArray &A)
checks if entries of A are zero
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...
#define ASSERT(expression, message)
CanonicalForm sqrfPartRes
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 ...
CFAFList absFactorize(const CanonicalForm &G)
absolute factorization of a multivariate poly over Q
absolute multivariate factorization over Q
CanonicalForm resultant(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x ) ...
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 &)