![]() |
My Project
|
This file provides functions for sparse heuristic Hensel lifting. More...
#include "canonicalform.h"
#include "cf_map_ext.h"
#include "cf_iter.h"
#include "templates/ftmpl_functions.h"
#include "cf_algorithm.h"
#include "cf_map.h"
Go to the source code of this file.
Functions | |
int | comp (const CanonicalForm &A, const CanonicalForm &B) |
compare polynomials | |
int | comp (const CanonicalForm &A, const CanonicalForm &B, int level) |
compare two polynomials up to level level | |
void | swap (CFArray &A, int i, int j) |
swap entry i and j in A | |
void | quickSort (int lo, int hi, CFArray &A, int l) |
quick sort helper function | |
void | sort (CFArray &A, int l=0) |
quick sort A | |
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 evalPoint coincide with uniFactors | |
CFArray | getTerms (const CanonicalForm &F) |
get terms of F | |
CFArray | getBiTerms_helper (const CanonicalForm &F, const CFMap &M, int threshold) |
helper function for getBiTerms | |
CFArray | getBiTerms (const CanonicalForm &F, int threshold) |
get terms of F where F is considered a bivariate poly in Variable(1), Variable (2) | |
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 | |
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 | |
void | strip (CFArray &F, int level) |
s.a. stripped off parts are not returned | |
CFArray | getEquations (const CFArray &A, const CFArray &B) |
get equations for LucksWangSparseHeuristic | |
void | evaluate (CFArray &A, const CanonicalForm &B, int level) |
evaluate every entry of A at B and level level | |
void | evaluate (CFArray &A, const CFArray &B, int level) |
evaluate every entry of A at every entry of B starting at level level | |
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 | |
bool | simplify (CFArray &A, CFArray &B, int level) |
if possible simplify A as described above and store result in B | |
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 | |
bool | isZero (const CFArray &A) |
checks if entries of A are zero | |
bool | isEqual (const CFArray &A, const CFArray &B) |
checks if A equals B | |
CFArray | getTerms2 (const CanonicalForm &F) |
get terms of F wrt. Variable (1) | |
void | getTerms2 (const CFList &F, CFArray *result) |
get terms of entries in F and put them in result | |
CFArray | evaluate (const CFArray &A, const CanonicalForm &eval, const Variable &y) |
evaluate entries in A at eval and y | |
CFArray * | evaluate (CFArray *const &A, int sizeA, const CanonicalForm &eval, const Variable &y) |
s.a. | |
CFList | normalize (const CFList &L, const CFList &normalizingFactor) |
normalize entries in L with normalizingFactor | |
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 one variable having level 1 | |
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 their univariate images | |
This file provides functions for sparse heuristic Hensel lifting.
Definition in file facSparseHensel.h.
|
inline |
|
inline |
compare polynomials
Definition at line 25 of file facSparseHensel.h.
|
inline |
compare two polynomials up to level level
Definition at line 51 of file facSparseHensel.h.
|
inline |
evaluate every entry of A at every entry of B starting at level level
Definition at line 377 of file facSparseHensel.h.
|
inline |
evaluate entries in A at eval and y
Definition at line 533 of file facSparseHensel.h.
|
inline |
find normalizing factors for biFactors and build monic univariate factors from biFactors
Definition at line 123 of file facSparseHensel.h.
|
inline |
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.
|
inline |
get terms of F where F is considered a bivariate poly in Variable(1), Variable (2)
Definition at line 236 of file facSparseHensel.h.
helper function for getBiTerms
Definition at line 202 of file facSparseHensel.h.
get equations for LucksWangSparseHeuristic
Definition at line 350 of file facSparseHensel.h.
|
inline |
get terms of F
Definition at line 167 of file facSparseHensel.h.
|
inline |
get terms of F wrt. Variable (1)
Definition at line 492 of file facSparseHensel.h.
get terms of entries in F and put them in result
Definition at line 524 of file facSparseHensel.h.
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.
int LucksWangSparseHeuristic | ( | const CanonicalForm & | F, |
const CFList & | factors, | ||
int | level, | ||
const CFList & | leadingCoeffs, | ||
CFList & | result ) |
sparse heuristic lifting by Wang and Lucks
[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.
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.
normalize entries in L with normalizingFactor
Definition at line 555 of file facSparseHensel.h.
|
inline |
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.
quick sort helper function
Definition at line 85 of file facSparseHensel.h.
if possible simplify A as described above and store result in B
Definition at line 412 of file facSparseHensel.h.
|
inline |
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.
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
[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 160 of file facSparseHensel.cc.
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.
s.a. stripped off parts are not returned
Definition at line 331 of file facSparseHensel.h.