 |
My Project
UNKNOWN_GIT_VERSION
|
#include "config.h"
#include "timing.h"
#include "debug.h"
#include "facAbsBiFact.h"
#include "facAbsFact.h"
#include "facFqFactorize.h"
#include "facFqFactorizeUtil.h"
#include "facHensel.h"
#include "facSparseHensel.h"
#include "facFactorize.h"
#include "cf_reval.h"
#include "cf_primes.h"
#include "cf_algorithm.h"
#include "cfModResultant.h"
#include "cfUnivarGcd.h"
#include "FLINTconvert.h"
#include "NTLconvert.h"
#include <NTL/LLL.h>
Go to the source code of this file.
|
| 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" More...
|
|
| for (CFIterator i=w;i.hasTerms();i++) terms.append(i.coeff()) |
|
| for (int i=terms.length();i >=1;i--, iter++) g+ |
|
| for (int i=F.level();i >=2;iter++, i--) |
|
| if (degree(Feval, x) >=8||degree(H, x) >=8) res |
|
| while (degree(sqrfPartRes) !=s) |
|
return | CFAFList (CFAFactor(factor, getMipo(beta), 1)) |
|
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". More...
|
|
CFList | evalPoints4AbsFact (const CanonicalForm &F, CFList &eval, Evaluation &E, int &intervalSize) |
|
CFAFList | absFactorize (const CanonicalForm &G) |
| absolute factorization of a multivariate poly over Q More...
|
|
CFAFList | absFactorizeMain (const CanonicalForm &G) |
| main absolute factorization routine, expects poly which is irreducible over Q More...
|
|
- Author
- Martin Lee
Definition in file facAbsFact.cc.
◆ absFactorize()
absolute factorization of a multivariate poly over Q
- Returns
- absFactorize returns a list whose entries contain three entities: an absolute irreducible factor, an irreducible univariate polynomial that defines the minimal field extension over which the irreducible factor is defined (note: in case the factor is already defined over Q[t]/(t), 1 is returned), and the multiplicity of the absolute irreducible factor
- Parameters
-
Definition at line 267 of file facAbsFact.cc.
292 for (;
i.hasItem();
i++)
◆ absFactorizeMain()
main absolute factorization routine, expects poly which is irreducible over Q
- Returns
- absFactorizeMain returns a list whose entries contain three entities: an absolute irreducible factor, an irreducible univariate polynomial that defines the minimal field extension over which the irreducible factor is defined (note: in case the factor is already defined over Q[t]/(t), 1 is returned as defining poly), and the multiplicity of the absolute irreducible factor
- Parameters
-
Definition at line 308 of file facAbsFact.cc.
324 "time to compress poly in abs fact: ")
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)
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())
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;
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;
◆ CFAFList()
◆ evalPoints4AbsFact()
◆ for() [1/3]
◆ for() [2/3]
◆ for() [3/3]
◆ if()
◆ RothsteinTrager()
Algorithm B.7.8 from Greuel, Pfister "A Singular Introduction to Commutative
Algebra".
Definition at line 110 of file facAbsFact.cc.
◆ TIMING_DEFINE_PRINT()
TIMING_DEFINE_PRINT |
( |
abs_fac_bi_factorizer |
| ) |
const & |
steps 4)-8) of Algorithm B.7.8. from Greuel, Pfister "A Singular
Introduction to Commutative Algebra"
◆ while()
◆ beta
◆ derivF
◆ derivFeval
◆ do
◆ evaluation
◆ factor
◆ Feval
◆ geval
◆ iter
◆ res
◆ sqrfPartRes
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
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
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.
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))
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
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
if(degree(Feval, x) >=8||degree(H, x) >=8) res
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...
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_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
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