 |
My Project
UNKNOWN_GIT_VERSION
|
Go to the source code of this file.
|
int | comp (const CanonicalForm &A, const CanonicalForm &B) |
| compare polynomials More...
|
|
int | comp (const CanonicalForm &A, const CanonicalForm &B, int level) |
| compare two polynomials up to level level More...
|
|
void | swap (CFArray &A, int i, int j) |
| swap entry i and j in A More...
|
|
void | quickSort (int lo, int hi, CFArray &A, int l) |
| quick sort helper function More...
|
|
void | sort (CFArray &A, int l=0) |
| quick sort A More...
|
|
CFList | findNormalizingFactor1 (const CFList &biFactors, const CanonicalForm &evalPoint, CFList &uniFactors) |
| find normalizing factors for biFactors and build monic univariate factors from biFactors More...
|
|
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 evalPoint coincide with uniFactors More...
|
|
CFArray | getTerms (const CanonicalForm &F) |
| get terms of F More...
|
|
CFArray | getBiTerms_helper (const CanonicalForm &F, const CFMap &M, int threshold) |
| helper function for getBiTerms More...
|
|
CFArray | getBiTerms (const CanonicalForm &F, int threshold) |
| get terms of F where F is considered a bivariate poly in Variable(1), Variable (2) More...
|
|
CanonicalForm | buildPolyFromArray (const CFArray &A) |
| build a poly from entries in A More...
|
|
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 More...
|
|
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 stripped off parts in G More...
|
|
void | strip (CFArray &F, int level) |
| s.a. stripped off parts are not returned More...
|
|
CFArray | getEquations (const CFArray &A, const CFArray &B) |
| get equations for LucksWangSparseHeuristic More...
|
|
void | evaluate (CFArray &A, const CanonicalForm &B, int level) |
| evaluate every entry of A at B and level level More...
|
|
void | evaluate (CFArray &A, const CFArray &B, int level) |
| evaluate every entry of A at every entry of B starting at level level More...
|
|
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 equal than level More...
|
|
bool | simplify (CFArray &A, CFArray &B, int level) |
| if possible simplify A as described above and store result in B More...
|
|
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 More...
|
|
bool | isZero (const CFArray &A) |
| checks if entries of A are zero More...
|
|
bool | isEqual (const CFArray &A, const CFArray &B) |
| checks if A equals B More...
|
|
CFArray | getTerms2 (const CanonicalForm &F) |
| get terms of F wrt. Variable (1) More...
|
|
void | getTerms2 (const CFList &F, CFArray *result) |
| get terms of entries in F and put them in result More...
|
|
CFArray | evaluate (const CFArray &A, const CanonicalForm &eval, const Variable &y) |
| evaluate entries in A at eval and y More...
|
|
CFArray * | evaluate (CFArray *const &A, int sizeA, const CanonicalForm &eval, const Variable &y) |
| s.a. More...
|
|
CFList | normalize (const CFList &L, const CFList &normalizingFactor) |
| normalize entries in L with normalizingFactor More...
|
|
int | search (const CFArray &A, const CanonicalForm &F, int i, int j) |
| search for F in A between index i and j More...
|
|
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 one variable having level 1 More...
|
|
int | LucksWangSparseHeuristic (const CanonicalForm &F, const CFList &factors, int level, const CFList &leadingCoeffs, CFList &result) |
| sparse heuristic lifting by Wang and Lucks More...
|
|
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 their univariate images More...
|
|
This file provides functions for sparse heuristic Hensel lifting
- Author
- Martin Lee
Definition in file facSparseHensel.h.
◆ buildPolyFromArray()
build a poly from entries in A
Definition at line 267 of file facSparseHensel.h.
270 for (
int i=
A.size() - 1;
i > -1;
i--)
◆ comp() [1/2]
◆ comp() [2/2]
◆ evaluate() [1/4]
evaluate every entry of A at B and level level
Definition at line 362 of file facSparseHensel.h.
365 for (
int i= 0;
i < n;
i++)
◆ evaluate() [2/4]
evaluate every entry of A at every entry of B starting at level level
Definition at line 377 of file facSparseHensel.h.
380 for (
int i= 0;
i < n;
i++)
◆ evaluate() [3/4]
◆ evaluate() [4/4]
◆ findNormalizingFactor1()
find normalizing factors for biFactors and build monic univariate factors from biFactors
Definition at line 123 of file facSparseHensel.h.
◆ findNormalizingFactor2()
find normalizing factors for biFactors and sort biFactors s.t. the returned biFactors evaluated at evalPoint coincide with uniFactors
Definition at line 140 of file facSparseHensel.h.
144 CFList uniBiFactors= biFactors;
157 pos=
findItem (uniBiFactors,
i.getItem());
161 biFactors= newBiFactors;
◆ getBiTerms()
◆ getBiTerms_helper()
helper function for getBiTerms
Definition at line 202 of file facSparseHensel.h.
213 if (
i.coeff().level() <
level)
222 for (;
j.hasTerms() &&
k <= threshold;
j++,
k++)
228 for (
int i= 0;
i <
k &&
k <= threshold;
i++)
◆ getEquations()
get equations for LucksWangSparseHeuristic
Definition at line 350 of file facSparseHensel.h.
352 ASSERT (
A.size() ==
B.size(),
"size of A and B has to coincide");
355 for (
int i= 0;
i < n;
i++)
◆ getTerms()
get terms of F
Definition at line 167 of file facSparseHensel.h.
183 int numMon=
size (F);
193 for (
int k= 0;
k < recResult.size();
k++)
195 j += recResult.size();
◆ getTerms2() [1/2]
◆ getTerms2() [2/2]
◆ groupTogether()
void groupTogether |
( |
CFArray & |
A, |
|
|
int |
level |
|
) |
| |
|
inline |
group together elements in A, where entries in A are put together if they coincide up to level level
Definition at line 278 of file facSparseHensel.h.
282 for (
int i= 0;
i < n;
i++)
296 for (
int i= 0;
i < n;
i++)
◆ isEqual()
checks if A equals B
Definition at line 479 of file facSparseHensel.h.
481 if (
A.size() !=
B.size())
484 for (
i= 0;
i < n;
i++)
◆ isZero()
◆ LucksWangSparseHeuristic()
sparse heuristic lifting by Wang and Lucks
- Returns
- LucksWangSparseHeuristic returns true if it was successful
- Parameters
-
[in] | F | polynomial to be factored |
[in] | factors | factors of F lifted to level |
[in] | level | level of lifted factors |
[in] | leadingCoeffs | leading coefficients of factors |
[in,out] | result | result |
Definition at line 26 of file facSparseHensel.cc.
31 if (termsF.
size() > threshold)
50 sort (monomsLead [
i]);
78 for (
i= factors.
length() - 1;
i > -1;
i--)
102 if (!
isEqual (strippedH, strippedF))
109 CFArray startingSolution= solution;
124 if (!
merge (solution, newSolution))
128 if (
isEqual (startingSolution, solution))
◆ merge()
merge B into A if possible, i.e. every non-zero entry in A should be zero in B
Definition at line 443 of file facSparseHensel.h.
445 if (
A.size() !=
B.size())
448 for (
int i= 0;
i < n;
i++)
457 else if (
A[
i] ==
B[
i])
◆ normalize()
normalize entries in L with normalizingFactor
Definition at line 555 of file facSparseHensel.h.
560 result.append (
i.getItem() /
j.getItem());
◆ patch()
patch together F1 and F2 and normalize by a power of eval F1 and F2 are assumed to be bivariate with one variable having level 1
Definition at line 577 of file facSparseHensel.h.
◆ quickSort()
void quickSort |
( |
int |
lo, |
|
|
int |
hi, |
|
|
CFArray & |
A, |
|
|
int |
l |
|
) |
| |
|
inline |
quick sort helper function
Definition at line 85 of file facSparseHensel.h.
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--;
◆ search()
◆ simplify() [1/2]
if possible simplify A as described above and store result in B
Definition at line 412 of file facSparseHensel.h.
417 for (
int i= 0;
i < n;
i++)
425 if (index < 0 || index >=
B.size())
◆ simplify() [2/2]
simplify A if possible, i.e. A consists of 2 terms and contains only one variable of level greater or equal than level
Definition at line 390 of file facSparseHensel.h.
393 if (
size (
A,
A.level()) == 2)
◆ sort()
void sort |
( |
CFArray & |
A, |
|
|
int |
l = 0 |
|
) |
| |
|
inline |
◆ sparseHeuristic()
sparse heuristic which patches together bivariate factors of A wrt. different second variables by their univariate images
- Returns
- sparseHeuristic returns a list of found factors of A
- Parameters
-
[in] | A | polynomial to be factored |
[in] | biFactors | bivariate factors of A where the second variable has level 2 |
[in] | moreBiFactors | more bivariate factorizations wrt. different second variables |
[in] | evaluation | evaluation point |
[in] | minFactorsLength | minimal length of bivariate factorizations |
Definition at line 155 of file facSparseHensel.cc.
159 int j=
A.level() - 1;
164 for (
i= 0;
i <
j;
i++)
173 for (
i= 1;
i <
j;
i++)
184 for (
i=
j - 1;
i > 0;
i--)
195 eval[
i], uniFactors);
199 tmp=
normalize (biFactors, normalizingFactors[0]);
203 for (
i=
j - 1;
i > 0;
i--)
205 tmp=
normalize (moreBiFactors [
i-1], normalizingFactors [
i]);
212 int k,
l,
m, mm,
count, sizeOfUniFactors= 0;
213 int*** seperator=
new int** [
j];
216 for (
i= 0;
i <
j;
i++)
220 for (
i= 0;
i <
j;
i++)
223 for (
l= 0;
l < storeFactors [
i][0][
k].
size() - 1;
l++)
230 sizeOfUniFactors=
count;
231 else if (sizeOfUniFactors !=
count)
233 for (
m= 0;
m <
j;
m++)
235 delete [] storeFactors [
m] [0];
236 delete [] storeFactors [
m] [1];
237 delete [] storeFactors [
m];
238 for (mm= 0; mm <
k; mm++)
239 delete [] seperator [
m][mm];
240 delete [] seperator [
m];
242 delete [] storeFactors;
244 delete [] normalizingFactors;
247 seperator [
i][
k]=
new int [
count + 3];
248 seperator [
i][
k][0]=
count + 1;
249 seperator [
i][
k][1]= 0;
251 for (
l= 0;
l < storeFactors [
i][0][
k].
size() - 1;
l++)
267 int maxTerms, n, index1, index2, mmm,
found, columns, oneCount;
273 sizeOfUniFactors= seperator [0][
k][0];
274 for (n= 1; n <= sizeOfUniFactors; n++)
279 for (
i=
j - 1;
i >= 0;
i--)
281 if (maxTerms < seperator[
i][
k][n+1]-seperator[
i][
k][n])
283 maxTerms= seperator[
i][
k][n + 1]-seperator[
i][
k][n];
287 for (
i=
j - 1;
i >= 0;
i--)
291 columns += seperator [
i][
k][n+1]-seperator[
i][
k][n];
293 mat=
new int *[maxTerms];
295 for (
m= seperator[index1][
k][n];
m < seperator[index1][
k][n+1];
m++, mm++)
297 tmp1= storeFactors [index1][1][
k][
m];
298 mat[mm]=
new int [columns];
299 for (
i= 0;
i < columns;
i++)
302 for (
i=
j - 1;
i >= 0;
i--)
308 seperator[
i][
k][n], seperator[
i][
k][n+1])) >= 0)
309 mat[mm][index2 +
found - seperator [
i][
k][n]]= 1;
310 index2 += seperator [
i][
k][n+1]-seperator[
i][
k][n];
315 for (
i=
j - 1;
i >= 0;
i--)
320 for (mm= 0; mm < seperator [
i][
k][n + 1] - seperator [
i][
k][n]; mm++)
322 for (
m= 0;
m < maxTerms;
m++)
324 if (mat[
m][mm+index2] == 1)
328 if (oneCount == seperator [
i][
k][n+1]-seperator[
i][
k][n] - 1)
330 for (mm= 0; mm < seperator [
i][
k][n+1]-seperator[
i][
k][n]; mm++)
333 for (
m= 0;
m < maxTerms;
m++)
334 if (mat[
m][mm+index2] == 1)
338 for (
m= 0;
m < maxTerms;
m++)
341 for (mmm= 0; mmm < seperator[
i][
k][n+1]-seperator[
i][
k][n]; mmm++)
343 if (mat[
m][mmm+index2] == 1)
348 mat[
m][mm+index2]= 1;
352 index2 += seperator [
i][
k][n+1] - seperator [
i][
k][n];
357 for (
m= seperator[index1][
k][n];
m < seperator[index1][
k][n+1];
m++, mm++)
359 tmp1= storeFactors [index1][0][
k][
m];
361 for (
i=
j - 1;
i > -1;
i--)
365 for (mmm= 0; mmm < seperator [
i][
k][n+1]-seperator[
i][
k][n]; mmm++)
366 if (mat[mm][mmm+index2] == 1)
369 index2 += seperator [
i][
k][n+1]-seperator[
i][
k][n];
374 for (
m= 0;
m < maxTerms;
m++)
392 for (
i= 0;
i <
j;
i++)
394 delete [] storeFactors [
i] [0];
395 delete [] storeFactors [
i] [1];
396 delete [] storeFactors [
i];
398 delete [] seperator [
i][
k];
399 delete [] seperator [
i];
402 delete [] storeFactors;
403 delete [] normalizingFactors;
◆ strip() [1/2]
strip off those parts of entries in F whose level is less than or equal than level and store the stripped off parts in G
Definition at line 310 of file facSparseHensel.h.
316 for (
j= 0;
j <
m;
j++)
◆ strip() [2/2]
void strip |
( |
CFArray & |
F, |
|
|
int |
level |
|
) |
| |
|
inline |
s.a. stripped off parts are not returned
Definition at line 331 of file facSparseHensel.h.
336 for (
int j= 0;
j <
m;
j++)
◆ swap()
void swap |
( |
CFArray & |
A, |
|
|
int |
i, |
|
|
int |
j |
|
) |
| |
|
inline |
CFArray evaluate(const CFArray &A, const CFList &evalPoints)
bool isZero(const CFArray &A)
checks if entries of A are zero
CFArray getBiTerms(const CanonicalForm &F, int threshold)
get terms of F where F is considered a bivariate poly in Variable(1), Variable (2)
class to iterate through CanonicalForm's
CFArray getBiTerms_helper(const CanonicalForm &F, const CFMap &M, int threshold)
helper function for getBiTerms
const CanonicalForm int const CFList const Variable & y
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...
int search(const CFArray &A, const CanonicalForm &F, int i, int j)
search for F in A between index i and j
bool isEqual(int *a, int *b, int lower, int upper)
static BOOLEAN length(leftv result, leftv arg)
CFArray getEquations(const CFArray &A, const CFArray &B)
get equations for LucksWangSparseHeuristic
CFArray getTerms2(const CanonicalForm &F)
get terms of F wrt. Variable (1)
CanonicalForm getItem(const CFList &list, const int &pos)
helper function
CFList int & minFactorsLength
[in,out] minimal length of bivariate factors
const CanonicalForm int const CFList & evaluation
CFArray getMonoms(const CanonicalForm &F)
extract monomials of F, parts in algebraic variable are considered coefficients
#define ASSERT(expression, message)
int status int void * buf
CFArray getTerms(const CanonicalForm &F)
get terms of F
static void evalPoint(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &FEval, CanonicalForm &GEval, CFGenerator &evalPoint)
void swap(CFArray &A, int i, int j)
swap entry i and j in A
void sort(CFArray &A, int l=0)
quick sort A
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
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 ...
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
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...
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...
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
CanonicalForm buildPolyFromArray(const CFArray &A)
build a poly from entries in A
factory's class for variables
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
void quickSort(int lo, int hi, CFArray &A, int l)
quick sort helper function
int findItem(const CFList &list, const CanonicalForm &item)
helper function
int status int void size_t count
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...
int comp(const CanonicalForm &A, const CanonicalForm &B)
compare polynomials
void getTerms(const CanonicalForm &f, const CanonicalForm &t, CFList &result)
get_Terms: Split the polynomial in the containing terms.
static int index(p_Length length, p_Ord ord)
void evaluate(CFArray &A, const CanonicalForm &B, int level)
evaluate every entry of A at B and level level
int ** merge(int **points1, int sizePoints1, int **points2, int sizePoints2, int &sizeResult)
CFList findNormalizingFactor1(const CFList &biFactors, const CanonicalForm &evalPoint, CFList &uniFactors)
find normalizing factors for biFactors and build monic univariate factors from biFactors