 |
My Project
debian-1:4.1.2-p1+ds-2
|
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;
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));
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;
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
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,...
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,...
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
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...
int LucksWangSparseHeuristic(const CanonicalForm &F, const CFList &factors, int level, const CFList &leadingCoeffs, CFList &result)
sparse heuristic lifting by Wang and Lucks
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
class to generate random evaluation points
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...
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
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
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