13 #ifndef FAC_SPARSE_HENSEL_H
14 #define FAC_SPARSE_HENSEL_H
39 for (
int i= 2;
i <=
n;
i++)
93 while (
comp (A [i], tmp, l) < 0 && i < hi) i++;
94 while (
comp (tmp, A[j], l) < 0 && j > lo) j--;
98 while (
comp (A [i], tmp) < 0 && i < hi) i++;
99 while (
comp (tmp, A[j]) < 0 && j > lo) j--;
144 CFList uniBiFactors= biFactors;
149 for (iter= uniBiFactors; iter.
hasItem(); iter++)
157 pos=
findItem (uniBiFactors,
i.getItem());
161 biFactors= newBiFactors;
183 int numMon=
size (F);
193 for (
int k= 0;
k < recResult.size();
k++)
194 result[j+
k]= powX*recResult[
k];
195 j += recResult.size();
213 if (
i.coeff().level() <
level)
215 buf[
k]=
M (
i.coeff())*
power (one,
i.exp());
222 for (;j.
hasTerms() && k <= threshold; j++, k++)
228 for (
int i= 0;
i < k && k <= threshold;
i++)
270 for (
int i= A.
size() - 1;
i > -1;
i--)
282 for (
int i= 0;
i <
n;
i++)
284 if (
comp (A[
i],A[i+1], level) == 0)
296 for (
int i= 0;
i <
n;
i++)
316 for (j= 0; j <
m; j++)
319 for (i= 1; i <=
level; i++)
321 if ((n=
degree (F[j],i)) > 0)
336 for (
int j= 0;
j <
m;
j++)
339 for (i= 1; i <=
level; i++)
355 for (
int i= 0;
i <
n;
i++)
356 result[
i]= A[
i]-B[
i];
365 for (
int i= 0;
i <
n;
i++)
380 for (
int i= 0;
i <
n;
i++)
417 for (
int i= 0;
i <
n;
i++)
424 index= A[
i].level() -
level;
425 if (index < 0 || index >= B.
size())
429 else if (B[index].
isZero())
448 for (
int i= 0;
i <
n;
i++)
457 else if (A[
i] == B[
i])
471 for (
int i= 0;
i <
n;
i++)
484 for (i= 0; i <
n; i++)
507 if (
i.coeff().inCoeffDomain())
509 result[
j]=
i.coeff()*
power (x,
i.exp());
514 for (k=
i.coeff(); k.
hasTerms(); k++, j++)
537 for (
int i= 0;
i <
j;
i++)
538 result [
i]= A[
i] (eval, y);
548 for (
int i= 0;
i < sizeA;
i++)
585 result /=
power (eval, d);
600 const CFList& leadingCoeffs,
CFList findNormalizingFactor1(const CFList &biFactors, const CanonicalForm &evalPoint, CFList &uniFactors)
find normalizing factors for biFactors and build monic univariate factors from biFactors ...
bool isEqual(const CFArray &A, const CFArray &B)
checks if A equals B
const CanonicalForm int const CFList const Variable & y
CFArray getBiTerms(const CanonicalForm &F, int threshold)
get terms of F where F is considered a bivariate poly in Variable(1), Variable (2) ...
some useful template functions.
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
CanonicalForm getItem(const CFList &list, const int &pos)
helper function
factory's class for variables
const CanonicalForm CFMap CFMap int &both_non_zero int n
bool merge(CFArray &A, CFArray &B)
merge B into A if possible, i.e. every non-zero entry in A should be zero in B
CFList int & minFactorsLength
[in,out] minimal length of < bivariate factors
CanonicalForm buildPolyFromArray(const CFArray &A)
build a poly from entries in A
const CanonicalForm int const CFList & evaluation
CanonicalForm simplify(const CanonicalForm &A, int level)
simplify A if possible, i.e. A consists of 2 terms and contains only one variable of level greater or...
CFArray getBiTerms_helper(const CanonicalForm &F, const CFMap &M, int threshold)
helper function for getBiTerms
This file implements functions to map between extensions of finite fields.
CF_NO_INLINE int hasTerms() const
check if iterator has reached < the end of CanonicalForm
int comp(const CanonicalForm &A, const CanonicalForm &B)
compare polynomials
CanonicalForm patch(const CanonicalForm &F1, const CanonicalForm &F2, const CanonicalForm &eval)
patch together F1 and F2 and normalize by a power of eval F1 and F2 are assumed to be bivariate with ...
CF_NO_INLINE CanonicalForm coeff() const
get the current coefficient
int LucksWangSparseHeuristic(const CanonicalForm &F, const CFList &factors, int level, const CFList &leadingCoeffs, CFList &result)
sparse heuristic lifting by Wang and Lucks
CFArray getTerms(const CanonicalForm &F)
get terms of F
void groupTogether(CFArray &A, int level)
group together elements in A, where entries in A are put together if they coincide up to level level ...
int search(const CFArray &A, const CanonicalForm &F, int i, int j)
search for F in A between index i and j
void quickSort(int lo, int hi, CFArray &A, int l)
quick sort helper function
int status int void * buf
void swap(CFArray &A, int i, int j)
swap entry i and j in A
Iterators for CanonicalForm's.
declarations of higher level algorithms.
void strip(CFArray &F, CFArray &G, int level)
strip off those parts of entries in F whose level is less than or equal than level and store the stri...
CFArray getEquations(const CFArray &A, const CFArray &B)
get equations for LucksWangSparseHeuristic
CFArray getTerms2(const CanonicalForm &F)
get terms of F wrt. Variable (1)
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 newpair(const Variable &v, const CanonicalForm &s)
void CFMap::newpair ( const Variable & v, const CanonicalForm & s )
CF_NO_INLINE int exp() const
get the current exponent
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...
CFList normalize(const CFList &L, const CFList &normalizingFactor)
normalize entries in L with normalizingFactor
bool isZero(const CFArray &A)
checks if entries of A are zero
void sort(CFArray &A, int l=0)
quick sort A
#define ASSERT(expression, message)
void evaluate(CFArray &A, const CanonicalForm &B, int level)
evaluate every entry of A at B and level level
CFList findNormalizingFactor2(CFList &biFactors, const CanonicalForm &evalPoint, const CFList &uniFactors)
find normalizing factors for biFactors and sort biFactors s.t. the returned biFactors evaluated at ev...
int findItem(const CFList &list, const CanonicalForm &item)
helper function
static void evalPoint(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &FEval, CanonicalForm &GEval, CFGenerator &evalPoint)