47#if defined(HAVE_NTL) || defined(HAVE_FLINT)
223 if (uniFactors.
getFirst().factor().inCoeffDomain())
287 for (;
i.hasItem();
i++)
319 "time to compress poly in abs fact: ")
326 if (
result.getFirst().factor().inCoeffDomain())
346 CFAFList absBiFactors, absBufBiFactors;
348 int lift, bufLift, lengthAeval2=
A.level()-2;
352 int differentSecondVar= 0;
359 for (
int i= 0;
i < factorNums;
i++)
367 "time to find evaluation point in abs fact: ");
374 "time to eval wrt diff second vars in abs fact: ");
376 for (
int j= 0;
j < lengthAeval2;
j++)
378 if (!bufAeval2[
j].isEmpty())
387 "time for bivariate factorization in abs fact: ");
389 if (absBufBiFactors.
length() == 1)
404 absBiFactors= absBufBiFactors;
406 for (
int j= 0;
j < lengthAeval2;
j++)
407 Aeval2 [
j]= bufAeval2 [
j];
408 differentSecondVar= counter;
415 counter > differentSecondVar)
419 absBiFactors= absBufBiFactors;
421 for (
int j= 0;
j < lengthAeval2;
j++)
422 Aeval2 [
j]= bufAeval2 [
j];
423 differentSecondVar= counter;
428 evalPoly +=
j.getItem()*
power (
x,
k);
449 "time for bivariate factorization wrt diff second vars in abs fact: ");
452 "total time for eval and bivar factors in abs fact: ");
486 if (differentSecondVar == lengthAeval2)
488 bool zeroOccured=
false;
522 rationalFactors=
CFList();
528 for (
int i= 0;
i < lengthAeval2;
i++)
529 oldAeval[
i]= Aeval2[
i];
535 biFactorsLCs.
append (
LC (
i.getItem(), 1));
547 CFList oldBiFactors= biFactors;
553 if (!LCmultiplierIsConst)
563 CFList bufLeadingCoeffs2= leadingCoeffs2[lengthAeval2-1];
564 CFList bufBiFactors= biFactors;
567 if (!LCmultiplierIsConst)
570 for (
int i= 0;
i < lengthAeval2;
i++)
572 if (!oldAeval[
i].isEmpty())
577 "time to precompute LC in abs fact: ");
581 bool LCheuristic=
false;
587 CFList oldFactors= rationalFactors;
616 "time for successful LucksWang in abs fact: ");
619 else if (rationalFactors.
length() > 0)
628 for (
int j=1;
j <=
i-oneCount;
j++)
631 for (
int j= 0;
j < lengthAeval2;
j++)
633 l= leadingCoeffs2[
j];
635 for (
int k=1;
k <=
i-oneCount;
k++)
643 bufFactors= rationalFactors;
644 rationalFactors=
CFList();
646 else if (!LCmultiplierIsConst && rationalFactors.
length() == 0)
649 rationalFactors= oldFactors;
651 bool foundTrueMultiplier=
false;
652 LCHeuristic2 (LCmultiplier,rationalFactors,leadingCoeffs2[lengthAeval2-1],
653 contents, LCs, foundTrueMultiplier);
654 if (foundTrueMultiplier)
657 leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
658 for (
int i= lengthAeval2-1;
i > -1;
i--)
665 bool foundMultiplier=
false;
666 LCHeuristic3 (LCmultiplier, rationalFactors, oldBiFactors, contents,
667 oldAeval,
A,leadingCoeffs2, lengthAeval2, foundMultiplier);
671 foundMultiplier=
false;
672 LCHeuristic4 (oldBiFactors, oldAeval, contents, rationalFactors,
673 testVars, lengthAeval2, leadingCoeffs2,
A, LCmultiplier,
679 leadingCoeffs2[lengthAeval2-1], foundMultiplier);
682 LCHeuristic (
A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
688 leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
689 for (
int i= lengthAeval2-1;
i > -1;
i--)
694 rationalFactors=
CFList();
695 if (!
fdivides (
LC (oldA,1),
prod (leadingCoeffs2[lengthAeval2-1])))
699 biFactors= bufBiFactors;
700 leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
701 LCmultiplier= bufLCmultiplier;
705 rationalFactors=
CFList();
711 if (!LCheuristic && !LCmultiplierIsConst && bufFactors.
isEmpty()
715 LCHeuristic (
A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
718 leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
719 for (
int i= lengthAeval2-1;
i > -1;
i--)
724 if (!
fdivides (
LC (oldA,1),
prod (leadingCoeffs2[lengthAeval2-1])))
728 biFactors= bufBiFactors;
729 leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
730 LCmultiplier= bufLCmultiplier;
734 "time for Lc heuristic in abs fact: ");
747 for (
int i= 0;
i < lengthAeval2-1;
i++)
752 for (
int i=
A.level() - 4;
i > -1;
i--)
754 if (
i + 1 == lengthAeval2-1)
761 "time to shift evaluation point to zero in abs fact: ");
765 int* liftBounds=
new int [
A.level() - 1];
766 int liftBoundsLength=
A.level() - 1;
767 for (
int i= 0;
i < liftBoundsLength;
i++)
771 bool noOneToOne=
false;
774 CFList commonDenominators;
779 for (
int i= 0;
i < lengthAeval2;
i++)
781 iter2= commonDenominators;
799 multiplier= tmp3/
tmp1;
800 iter2= commonDenominators;
807 for (
int i= 0;
i < lengthAeval2;
i++)
809 iter2= commonDenominators;
815 "time to clear denominators in abs fact: ");
819 Pi, liftBounds, liftBoundsLength, noOneToOne);
821 "time for non monic hensel lifting in abs fact: ");
830 "time to recover factors in abs fact: ");
834 rationalFactors=
Union (rationalFactors, bufFactors);
838 if (!LCmultiplierIsConst && LCheuristic)
841 biFactors= bufBiFactors;
842 leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
843 delete [] liftBounds;
845 goto tryAgainWithoutHeu;
850 biFactors= oldBiFactors;
859 for (;
i.hasItem();
i++)
867 for (;
i.hasItem();
i++)
869 LCA=
LC (
i.getItem(), 1);
870 extgcd (LCA, yToLift, LCA, dummy);
871 i.getItem()=
mod (
i.getItem()*LCA, yToLift);
874 liftBoundsLength= F.
level() - 1;
884 (
A, MOD, liftBounds, earlySuccess, earlyFactors,
887 "time for hensel lifting in abs fact: ");
892 "time for factor recombination in abs fact: ");
895 rationalFactors=
Union (rationalFactors, earlyFactors);
902 if (
i.getItem().level() < kk)
904 i.getItem()=
i.getItem() (
Variable (kk) -
j.getItem(), kk);
933 delete [] leadingCoeffs2;
This file defines functions for conversion to FLINT (www.flintlib.org) and back.
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 resultantZ(const CanonicalForm &A, const CanonicalForm &B, const Variable &x, bool prob)
modular resultant algorihtm over Z
modular resultant algorithm as described by G.
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,...
univariate Gcd over finite fields and Z, extended GCD over finite fields and Q
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
declarations of higher level algorithms.
CFFList FACTORY_PUBLIC factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
CanonicalForm FACTORY_PUBLIC resultant(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
#define ASSERT(expression, message)
static const int SW_RATIONAL
set to 1 for computations over Q
generate random evaluation points
class to iterate through CanonicalForm's
class to evaluate a polynomial at points
ExtensionInfo contains information about extension.
void remove(int moveright)
class to generate random evaluation points
factory's class for variables
functions to print debug output
CFAFList absBiFactorizeMain(const CanonicalForm &G, bool full)
main absolute factorization routine, expects bivariate poly which is irreducible over Q
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 int const CFList & evaluation
CFAFList absFactorizeMain(const CanonicalForm &G)
main absolute factorization routine, expects poly which is irreducible over Q
CFAFList absFactorize(const CanonicalForm &G)
absolute factorization of a multivariate poly over Q
const CanonicalForm int s
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)
CanonicalForm sqrfPartRes
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".
absolute multivariate factorization over Q
const Variable & v
< [in] a sqrfree bivariate poly
void factorizationWRTDifferentSecondVars(const CanonicalForm &A, CFList *&Aeval, int &minFactorsLength, bool &irred, const Variable &w)
multivariate factorization over Q(a)
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
This file provides utility functions for multivariate factorization.
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
This file provides functions for factorizing a multivariate polynomial over , or GF.
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.
This file defines functions for Hensel lifting.
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...
This file provides functions for sparse heuristic Hensel lifting.
bool isZero(const CFArray &A)
checks if entries of A are zero
CanonicalForm sqrfPart(const CanonicalForm &F)
squarefree part of a poly
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
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)
int status int void size_t count
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
#define TIMING_DEFINE_PRINT(t)
#define TIMING_END_AND_PRINT(t, msg)
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Variable rootOf(const CanonicalForm &mipo, char name)
returns a symbolic root of polynomial with name name Use it to define algebraic variables