 |
My Project
UNKNOWN_GIT_VERSION
|
Go to the documentation of this file.
228 if (uniFactors.
getFirst().factor().inCoeffDomain())
292 for (;
i.hasItem();
i++)
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)
409 absBiFactors= absBufBiFactors;
411 for (
int j= 0;
j < lengthAeval2;
j++)
412 Aeval2 [
j]= bufAeval2 [
j];
413 differentSecondVar= counter;
420 counter > differentSecondVar)
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: ");
491 if (differentSecondVar == lengthAeval2)
493 bool zeroOccured=
false;
527 rationalFactors=
CFList();
533 for (
int i= 0;
i < lengthAeval2;
i++)
534 oldAeval[
i]= Aeval2[
i];
540 biFactorsLCs.
append (
LC (
i.getItem(), 1));
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;
592 CFList oldFactors= rationalFactors;
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,
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,
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: ");
752 for (
int i= 0;
i < lengthAeval2-1;
i++)
757 for (
int i=
A.level() - 4;
i > -1;
i--)
759 if (
i + 1 == lengthAeval2-1)
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;
784 for (
int i= 0;
i < lengthAeval2;
i++)
786 iter2= commonDenominators;
804 multiplier= tmp3/
tmp1;
805 iter2= commonDenominators;
812 for (
int i= 0;
i < lengthAeval2;
i++)
814 iter2= commonDenominators;
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: ");
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;
864 for (;
i.hasItem();
i++)
872 for (;
i.hasItem();
i++)
874 LCA=
LC (
i.getItem(), 1);
875 extgcd (LCA, yToLift, LCA, dummy);
876 i.getItem()=
mod (
i.getItem()*LCA, yToLift);
879 liftBoundsLength= F.
level() - 1;
889 (
A, MOD, liftBounds, earlySuccess, earlyFactors,
892 "time for hensel lifting in abs fact: ");
897 "time for factor recombination in abs fact: ");
900 rationalFactors=
Union (rationalFactors, earlyFactors);
907 if (
i.getItem().level() < kk)
909 i.getItem()=
i.getItem() (
Variable (kk) -
j.getItem(), kk);
938 delete [] leadingCoeffs2;
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)
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".
static const int SW_RATIONAL
set to 1 for computations over Q
CFList evalPoints4AbsFact(const CanonicalForm &F, CFList &eval, Evaluation &E, int &intervalSize)
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...
bool isZero(const CFArray &A)
checks if entries of A are zero
class to iterate through CanonicalForm's
const CanonicalForm int const CFList const Variable & y
CFAFList uniAbsFactorize(const CanonicalForm &F, bool full=false)
univariate absolute factorization over Q
CFList recoverFactors(const CanonicalForm &F, const CFList &factors)
divides factors by their content wrt. Variable(1) and checks if these polys divide F
generate random evaluation points
CanonicalForm resultantZ(const CanonicalForm &A, const CanonicalForm &B, const Variable &x, bool prob)
modular resultant algorihtm over Z
ideal lift(const ideal J, const ring r, const ideal inI, const ring s)
CFAFList absBiFactorizeMain(const CanonicalForm &G, bool full)
main absolute factorization routine, expects bivariate poly which is irreducible over Q
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...
CFList int bool & irred
[in,out] Is A irreducible?
void sortList(CFList &list, const Variable &x)
sort a list of polynomials by their degree in x.
CFAFList absFactorize(const CanonicalForm &G)
absolute factorization of a multivariate poly over Q
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 ...
class to evaluate a polynomial at points
REvaluation E(1, terms.length(), IntRandom(25))
Variable rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables
return CFAFList(CFAFactor(factor, getMipo(beta), 1))
const CanonicalForm CFMap CFMap & N
void getLeadingCoeffs(const CanonicalForm &A, CFList *&Aeval)
extract leading coefficients wrt Variable(1) from bivariate factors obtained from factorizations of A...
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 extgcd(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b)
CanonicalForm extgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a,...
This file provides functions for sparse heuristic Hensel lifting.
univariate Gcd over finite fields and Z, extended GCD over finite fields and Q
This file provides utility functions for multivariate factorization.
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,...
modular resultant algorithm as described by G.
CFList int & minFactorsLength
[in,out] minimal length of bivariate factors
const CanonicalForm int const CFList & evaluation
CanonicalForm sqrfPart(const CanonicalForm &F)
squarefree part of a poly
CFList buildUniFactors(const CFList &biFactors, const CanonicalForm &evalPoint, const Variable &y)
plug in evalPoint for y in a list of polys
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
absolute multivariate factorization over Q
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
#define ASSERT(expression, message)
CFAFList absFactorizeMain(const CanonicalForm &G)
main absolute factorization routine, expects poly which is irreducible over Q
TIMING_START(fac_alg_resultant)
CFList *& Aeval
<[in] poly
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...
Conversion to and from NTL.
int LucksWangSparseHeuristic(const CanonicalForm &F, const CFList &factors, int level, const CFList &leadingCoeffs, CFList &result)
sparse heuristic lifting by Wang and Lucks
declarations of higher level algorithms.
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
class to generate random evaluation points
bivariate absolute factorization over Q described in "Modular Las Vegas Algorithms for Polynomial Abs...
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...
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
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 factorizationWRTDifferentSecondVars(const CanonicalForm &A, CFList *&Aeval, int &minFactorsLength, bool &irred, const Variable &w)
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...
This file defines functions for conversion to FLINT (www.flintlib.org) and back.
CanonicalForm sqrfPartRes
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
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....
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
void remove(int moveright)
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
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"
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
factory's class for variables
ExtensionInfo contains information about extension.
This file defines functions for Hensel lifting.
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
multivariate factorization over Q(a)
CanonicalForm resultant(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
int * liftingBounds(const CanonicalForm &A, const int &bivarLiftBound)
compute lifting bounds
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
const Variable & v
< [in] a sqrfree bivariate poly
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...
const CanonicalForm int s
int status int void size_t count
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,...
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
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
static int index(p_Length length, p_Ord ord)
const ExtensionInfo & info
< [in] sqrfree poly
CanonicalForm shift2Zero(const CanonicalForm &F, CFList &Feval, const CFList &evaluation, int l)
shift evaluation point to zero
functions to print debug output
This file provides functions for factorizing a multivariate polynomial over , or GF.