55 sort (monomsLead [
i]);
83 for (
i= factors.
length() - 1;
i > -1;
i--)
107 if (!
isEqual (strippedH, strippedF))
114 CFArray startingSolution= solution;
129 if (!
merge (solution, newSolution))
133 if (
isEqual (startingSolution, solution))
164 int j=
A.level() - 1;
169 for (
i= 0;
i <
j;
i++)
178 for (
i= 1;
i <
j;
i++)
189 for (
i=
j - 1;
i > 0;
i--)
200 eval[
i], uniFactors);
204 tmp=
normalize (biFactors, normalizingFactors[0]);
208 for (
i=
j - 1;
i > 0;
i--)
210 tmp=
normalize (moreBiFactors [
i-1], normalizingFactors [
i]);
217 int k,
l,
m, mm,
count, sizeOfUniFactors= 0;
218 int*** seperator=
new int** [
j];
221 for (
i= 0;
i <
j;
i++)
225 for (
i= 0;
i <
j;
i++)
228 for (
l= 0;
l < storeFactors [
i][0][
k].
size() - 1;
l++)
235 sizeOfUniFactors=
count;
236 else if (sizeOfUniFactors !=
count)
238 for (
m= 0;
m <
j;
m++)
240 delete [] storeFactors [
m] [0];
241 delete [] storeFactors [
m] [1];
242 delete [] storeFactors [
m];
243 for (mm= 0; mm <
k; mm++)
244 delete [] seperator [
m][mm];
245 delete [] seperator [
m];
247 delete [] storeFactors;
249 delete [] normalizingFactors;
252 seperator [
i][
k]=
new int [
count + 3];
253 seperator [
i][
k][0]=
count + 1;
254 seperator [
i][
k][1]= 0;
256 for (
l= 0;
l < storeFactors [
i][0][
k].
size() - 1;
l++)
272 int maxTerms, n, index1, index2, mmm,
found, columns, oneCount;
278 sizeOfUniFactors= seperator [0][
k][0];
279 for (n= 1; n <= sizeOfUniFactors; n++)
284 for (
i=
j - 1;
i >= 0;
i--)
286 if (maxTerms < seperator[
i][
k][n+1]-seperator[
i][
k][n])
288 maxTerms= seperator[
i][
k][n + 1]-seperator[
i][
k][n];
292 for (
i=
j - 1;
i >= 0;
i--)
296 columns += seperator [
i][
k][n+1]-seperator[
i][
k][n];
298 mat=
new int *[maxTerms];
300 for (
m= seperator[index1][
k][n];
m < seperator[index1][
k][n+1];
m++, mm++)
302 tmp1= storeFactors [index1][1][
k][
m];
303 mat[mm]=
new int [columns];
304 for (
i= 0;
i < columns;
i++)
307 for (
i=
j - 1;
i >= 0;
i--)
313 seperator[
i][
k][n], seperator[
i][
k][n+1])) >= 0)
314 mat[mm][index2 +
found - seperator [
i][
k][n]]= 1;
315 index2 += seperator [
i][
k][n+1]-seperator[
i][
k][n];
320 for (
i=
j - 1;
i >= 0;
i--)
325 for (mm= 0; mm < seperator [
i][
k][n + 1] - seperator [
i][
k][n]; mm++)
327 for (
m= 0;
m < maxTerms;
m++)
329 if (mat[
m][mm+index2] == 1)
333 if (oneCount == seperator [
i][
k][n+1]-seperator[
i][
k][n] - 1)
335 for (mm= 0; mm < seperator [
i][
k][n+1]-seperator[
i][
k][n]; mm++)
338 for (
m= 0;
m < maxTerms;
m++)
339 if (mat[
m][mm+index2] == 1)
343 for (
m= 0;
m < maxTerms;
m++)
346 for (mmm= 0; mmm < seperator[
i][
k][n+1]-seperator[
i][
k][n]; mmm++)
348 if (mat[
m][mmm+index2] == 1)
353 mat[
m][mm+index2]= 1;
357 index2 += seperator [
i][
k][n+1] - seperator [
i][
k][n];
362 for (
m= seperator[index1][
k][n];
m < seperator[index1][
k][n+1];
m++, mm++)
364 tmp1= storeFactors [index1][0][
k][
m];
366 for (
i=
j - 1;
i > -1;
i--)
370 for (mmm= 0; mmm < seperator [
i][
k][n+1]-seperator[
i][
k][n]; mmm++)
371 if (mat[mm][mmm+index2] == 1)
374 index2 += seperator [
i][
k][n+1]-seperator[
i][
k][n];
379 for (
m= 0;
m < maxTerms;
m++)
397 for (
i= 0;
i <
j;
i++)
399 delete [] storeFactors [
i] [0];
400 delete [] storeFactors [
i] [1];
401 delete [] storeFactors [
i];
403 delete [] seperator [
i][
k];
404 delete [] seperator [
i];
407 delete [] storeFactors;
408 delete [] normalizingFactors;
bool isEqual(int *a, int *b, int lower, int upper)
CFArray getMonoms(const CanonicalForm &F)
extract monomials of F, parts in algebraic variable are considered coefficients
CFArray evaluate(const CFArray &A, const CFList &evalPoints)
modular and sparse modular GCD algorithms over finite fields and Z.
static void sort(int **points, int sizePoints)
int ** merge(int **points1, int sizePoints1, int **points2, int sizePoints2, int &sizeResult)
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
declarations of higher level algorithms.
void getTerms(const CanonicalForm &f, const CanonicalForm &t, CFList &result)
get_Terms: Split the polynomial in the containing terms.
factory's class for variables
const CanonicalForm int const CFList & evaluation
CFList int & minFactorsLength
[in,out] minimal length of bivariate factors
CFList recombination(const CFList &factors1, const CFList &factors2, int s, int thres, const CanonicalForm &evalPoint, const Variable &x)
recombination of bivariate factors factors1 s. t. the result evaluated at evalPoint coincides with fa...
This file provides functions for factorizing a multivariate polynomial over , or GF.
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.
CanonicalForm buildPolyFromArray(const CFArray &A)
build a poly from entries in A
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
CFArray getTerms2(const CanonicalForm &F)
get terms of F wrt. Variable (1)
CFArray getBiTerms(const CanonicalForm &F, int threshold)
get terms of F where F is considered a bivariate poly in Variable(1), Variable (2)
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...
bool isZero(const CFArray &A)
checks if entries of A are zero
CFList findNormalizingFactor1(const CFList &biFactors, const CanonicalForm &evalPoint, CFList &uniFactors)
find normalizing factors for biFactors and build monic univariate factors from biFactors
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 search(const CFArray &A, const CanonicalForm &F, int i, int j)
search for F in A between index i and j
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 ...
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
static BOOLEAN length(leftv result, leftv arg)
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)