Loading...
Searching...
No Matches
facSparseHensel.h File Reference

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

## Detailed Description

This file provides functions for sparse heuristic Hensel lifting.

Author
  Martin Lee

Definition in file facSparseHensel.h.

## Function Documentation

## buildPolyFromArray()

CanonicalForm buildPolyFromArray | ( | const CFArray & | A | ) |

inline

build a poly from entries in A

Definition at line 267 of file facSparseHensel.h.

{
CanonicalForm result= 0;
for (int i= A.size() - 1; i > -1; i--)
result += A[i];
return result;
}
i
int i
Definition cfEzgcd.cc:132
CanonicalForm
factory's main class
Definition canonicalform.h:86
result
return result
Definition facAbsBiFact.cc:76
A
#define A
Definition sirandom.c:24

## comp() [1/2]

int comp | ( | const CanonicalForm & | A,
|  | const CanonicalForm & | B )

inline

compare polynomials

Definition at line 25 of file facSparseHensel.h.

{
if (A.inCoeffDomain() && !B.inCoeffDomain())
return -1;
else if (!A.inCoeffDomain() && B.inCoeffDomain())
return 1;
else if (A.inCoeffDomain() && B.inCoeffDomain())
return 0;
else if (degree (A, 1) > degree (B, 1))
return 1;
else if (degree (A, 1) < degree (B, 1))
return -1;
// here A and B are not in CoeffDomain
int n= tmax (A.level(), B.level());
for (int i= 2; i <= n; i++)
{
if (degree (A,i) > degree (B,i))
return 1;
else if (degree (A,i) < degree (B,i))
return -1;
}
return 0;
}
degree
int degree(const CanonicalForm &f)
Definition canonicalform.h:316
B
b *CanonicalForm B
Definition facBivar.cc:52
tmax
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)

## comp() [2/2]

int comp | ( | const CanonicalForm & | A,
|  | const CanonicalForm & | B,
|  | int | level )

inline

compare two polynomials up to level level

Definition at line 51 of file facSparseHensel.h.

{
if (A.inCoeffDomain() && !B.inCoeffDomain() && B.level() <= level)
return -1;
else if (!A.inCoeffDomain() && A.level() <= level && B.inCoeffDomain())
return 1;
else if (A.inCoeffDomain() && B.inCoeffDomain())
return 0;
else if (degree (A, 1) > degree (B, 1))
return 1;
else if (degree (A, 1) < degree (B, 1))
return -1;
// here A and B are not in coeffdomain
for (int i= 2; i <= level; i++)
{
if (degree (A,i) > degree (B,i))
return 1;
else if (degree (A,i) < degree (B,i))
return -1;
}
return 0;
}
level
int level(const CanonicalForm &f)
Definition canonicalform.h:331

## evaluate() [1/4]

void evaluate | ( | CFArray & | A,
|  | const CanonicalForm & | B,
|  | int | level )

inline

evaluate every entry of A at B and level level

Definition at line 362 of file facSparseHensel.h.

{
int n= A.size();
for (int i= 0; i < n; i++)
{
if (A[i].level() < level)
continue;
else
A[i]= A[i] (B, level);
}
}

## evaluate() [2/4]

void evaluate | ( | CFArray & | A,
|  | const CFArray & | B,
|  | int | level )

inline

evaluate every entry of A at every entry of B starting at level level

Definition at line 377 of file facSparseHensel.h.

{
int n= B.size();
for (int i= 0; i < n; i++)
{
if (!B[i].isZero())
evaluate (A, B[i], level + i);
}
}
isZero
bool isZero(const CFArray &A)
checks if entries of A are zero
Definition facSparseHensel.h:468
evaluate
void evaluate(CFArray &A, const CanonicalForm &B, int level)
evaluate every entry of A at B and level level
Definition facSparseHensel.h:362

## evaluate() [3/4]

CFArray * evaluate | ( | CFArray *const & | A,
|  | int | sizeA,
|  | const CanonicalForm & | eval,
|  | const Variable & | y )

inline

s.a.

Definition at line 544 of file facSparseHensel.h.

{
CFArray* result= new CFArray [sizeA];
for (int i= 0; i < sizeA; i++)
result[i]= evaluate (A[i], eval, y);
return result;
}
CFArray
Array< CanonicalForm > CFArray
Definition canonicalform.h:397
evaluate
CFArray evaluate(const CFArray &A, const CFList &evalPoints)
Definition cfModGcd.cc:2039
y
const CanonicalForm int const CFList const Variable & y
Definition facAbsFact.cc:53
eval
CFList & eval
Definition facFactorize.cc:47

## evaluate() [4/4]

CFArray evaluate | ( | const CFArray & | A,
|  | const CanonicalForm & | eval,
|  | const Variable & | y )

inline

evaluate entries in A at eval and y

Definition at line 533 of file facSparseHensel.h.

{
int j= A.size();
CFArray result= CFArray (j);
for (int i= 0; i < j; i++)
result [i]= A[i] (eval, y);
return result;
}
j
int j
Definition facHensel.cc:110

## findNormalizingFactor1()

CFList findNormalizingFactor1 | ( | const CFList & | biFactors,
|  | const CanonicalForm & | evalPoint,
|  | CFList & | uniFactors )

inline

find normalizing factors for biFactors and build monic univariate factors from biFactors

Definition at line 123 of file facSparseHensel.h.

{
CFList result;
CanonicalForm tmp;
for (CFListIterator i= biFactors; i.hasItem(); i++)
{
tmp= i.getItem() (evalPoint);
uniFactors.append (tmp /Lc (tmp));
result.append (Lc (tmp));
}
return result;
}
CFListIterator
ListIterator< CanonicalForm > CFListIterator
Definition canonicalform.h:396
Lc
CanonicalForm Lc(const CanonicalForm &f)
Definition canonicalform.h:307
CFList
List< CanonicalForm > CFList
Definition canonicalform.h:395
evalPoint
static void evalPoint(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &FEval, CanonicalForm &GEval, CFGenerator &evalPoint)
Definition cfModResultant.cc:311
List::append
void append(const T &)
Definition ftmpl_list.cc:256

## findNormalizingFactor2()

CFList findNormalizingFactor2 | ( | CFList & | biFactors,
|  | const CanonicalForm & | evalPoint,
|  | const CFList & | uniFactors )

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.

{
CFList result;
CFList uniBiFactors= biFactors;
CFList newBiFactors;
CFList l;
int pos;
CFListIterator iter;
for (iter= uniBiFactors; iter.hasItem(); iter++)
{
iter.getItem()= iter.getItem() (evalPoint);
l.append (Lc (iter.getItem()));
iter.getItem() /= Lc (iter.getItem());
}
for (CFListIterator i= uniFactors; i.hasItem(); i++)
{
pos= findItem (uniBiFactors, i.getItem());
newBiFactors.append (getItem (biFactors, pos));
result.append (getItem (l, pos));
}
biFactors= newBiFactors;
return result;
}
l
int l
Definition cfEzgcd.cc:100
findItem
int findItem(const CFList &list, const CanonicalForm &item)
helper function
Definition cf_map_ext.cc:42
getItem
CanonicalForm getItem(const CFList &list, const int &pos)
helper function
Definition cf_map_ext.cc:54
iter
CFFListIterator iter
Definition facAbsBiFact.cc:54

## getBiTerms()

CFArray getBiTerms | ( | const CanonicalForm & | F,
|  | int | threshold )

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.

{
if (F.inCoeffDomain())
{
CFArray result= CFArray (1);
result [0]= F;
return result;
}
if (F.isUnivariate())
{
CFArray result= CFArray (size(F));
int j= 0;
for (CFIterator i= F; i.hasTerms(); i++, j++)
result[j]= i.coeff()*power (F.mvar(), i.exp());
return result;
}
CanonicalForm G= F;
CFMap M;
M.newpair (Variable (1), F.mvar());
M.newpair (Variable (2), Variable (F.level() - 1));
G= swapvar (F, Variable (1), F.mvar());
G= swapvar (G, Variable (2), Variable (F.level() - 1));
CFArray result= getBiTerms_helper (G, M, threshold);
return result;
}
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition canonicalform.cc:1896
size
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition cf_ops.cc:600
swapvar
CanonicalForm FACTORY_PUBLIC swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition cf_ops.cc:168
CFIterator
class to iterate through CanonicalForm's
Definition cf_iter.h:44
CFMap
class CFMap
Definition cf_map.h:85
CanonicalForm::mvar
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
Definition canonicalform.cc:593
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition canonicalform.cc:122
CanonicalForm::level
int level() const
level() returns the level of CO.
Definition canonicalform.cc:576
CanonicalForm::isUnivariate
bool isUnivariate() const
Definition canonicalform.cc:155
Variable
factory's class for variables
Definition factory.h:127
getBiTerms_helper
CFArray getBiTerms_helper(const CanonicalForm &F, const CFMap &M, int threshold)
helper function for getBiTerms
Definition facSparseHensel.h:202
G
STATIC_VAR TreeM * G
Definition janet.cc:31
M
#define M
Definition sirandom.c:25

## getBiTerms_helper()

CFArray getBiTerms_helper | ( | const CanonicalForm & | F,
|  | const CFMap & | M,
|  | int | threshold )

inline

helper function for getBiTerms

Definition at line 202 of file facSparseHensel.h.

{
CFArray buf= CFArray (size (F));
int k= 0, level= F.level() - 1;
Variable x= F.mvar();
Variable y= Variable (F.level() - 1);
Variable one= Variable (1);
Variable two= Variable (2);
CFIterator j;
for (CFIterator i= F; i.hasTerms(); i++)
{
if (i.coeff().level() < level)
{
buf[k]= M (i.coeff())*power (one,i.exp());
k++;
if (k > threshold)
break;
continue;
}
j= i.coeff();
for (;j.hasTerms() && k <= threshold; j++, k++)
buf[k]= power (one,i.exp())*power (two,j.exp())*M (j.coeff());
if (k > threshold)
break;
}
CFArray result= CFArray (k);
for (int i= 0; i < k && k <= threshold; i++)
result[i]= buf[i];
return result;
}
k
int k
Definition cfEzgcd.cc:99
x
Variable x
Definition cfModGcd.cc:4090
buf
int status int void * buf
Definition si_signals.h:69

## getEquations()

CFArray getEquations | ( | const CFArray & | A,
|  | const CFArray & | B )

inline

get equations for LucksWangSparseHeuristic

Definition at line 350 of file facSparseHensel.h.

{
ASSERT (A.size() == B.size(), "size of A and B has to coincide");
CFArray result= CFArray (A.size());
int n= A.size();
for (int i= 0; i < n; i++)
result[i]= A[i]-B[i];
return result;
}
ASSERT
#define ASSERT(expression, message)
Definition cf_assert.h:99

## getTerms()

CFArray getTerms | ( | const CanonicalForm & | F | ) |

inline

get terms of F

Definition at line 167 of file facSparseHensel.h.

{
if (F.inCoeffDomain())
{
CFArray result= CFArray (1);
result [0]= F;
return result;
}
if (F.isUnivariate())
{
CFArray result= CFArray (size(F));
int j= 0;
for (CFIterator i= F; i.hasTerms(); i++, j++)
result[j]= i.coeff()*power (F.mvar(), i.exp());
return result;
}
int numMon= size (F);
CFArray result= CFArray (numMon);
int j= 0;
CFArray recResult;
Variable x= F.mvar();
CanonicalForm powX;
for (CFIterator i= F; i.hasTerms(); i++)
{
powX= power (x, i.exp());
recResult= getTerms (i.coeff());
for (int k= 0; k < recResult.size(); k++)
result[j+k]= powX*recResult[k];
j += recResult.size();
}
return result;
}
Array::size
int size() const
Definition ftmpl_array.cc:92
getTerms
CFArray getTerms(const CanonicalForm &F)
get terms of F
Definition facSparseHensel.h:167

## getTerms2() [1/2]

CFArray getTerms2 | ( | const CanonicalForm & | F | ) |

inline

get terms of F wrt. Variable (1)

Definition at line 492 of file facSparseHensel.h.

{
if (F.inCoeffDomain())
{
CFArray result= CFArray (1);
result[0]= F;
return result;
}
CFArray result= CFArray (size (F));
int j= 0;
Variable x= F.mvar();
Variable y= Variable (1);
CFIterator k;
for (CFIterator i= F; i.hasTerms(); i++)
{
if (i.coeff().inCoeffDomain())
{
result[j]= i.coeff()*power (x,i.exp());
j++;
}
else
{
for (k= i.coeff(); k.hasTerms(); k++, j++)
result[j]= k.coeff()*power (x,i.exp())*power (y,k.exp());
}
}
sort (result);
return result;
}
sort
void sort(CFArray &A, int l=0)
quick sort A
Definition facSparseHensel.h:114

## getTerms2() [2/2]

void getTerms2 | ( | const CFList & | F,
|  | CFArray * | result )

inline

get terms of entries in F and put them in result

Definition at line 524 of file facSparseHensel.h.

{
int j= 0;
for (CFListIterator i= F; i.hasItem(); i++, j++)
result[j]= getTerms2 (i.getItem());
}
getTerms2
CFArray getTerms2(const CanonicalForm &F)
get terms of F wrt. Variable (1)
Definition facSparseHensel.h:492

## 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.

{
int n= A.size() - 1;
int k= A.size();
for (int i= 0; i < n; i++)
{
if (comp (A[i],A[i+1], level) == 0)
{
A[i+1] += A[i];
A[i]= 0;
k--;
}
}
if (A[n].isZero())
k--;
CFArray B= CFArray (k);
n++;
k= 0;
for (int i= 0; i < n; i++)
{
if (!A[i].isZero())
{
B[k]= A[i];
k++;
}
}
A= B;
}
comp
int comp(const CanonicalForm &A, const CanonicalForm &B)
compare polynomials
Definition facSparseHensel.h:25

## isEqual()

bool isEqual | ( | const CFArray & | A,
|  | const CFArray & | B )

inline

checks if A equals B

Definition at line 479 of file facSparseHensel.h.

{
if (A.size() != B.size())
return false;
int i, n= B.size();
for (i= 0; i < n; i++)
if (A[i] != B[i])
return false;
return true;
}

## isZero()

bool isZero | ( | const CFArray & | A | ) |

inline

checks if entries of A are zero

Definition at line 468 of file facSparseHensel.h.

{
int n= A.size();
for (int i= 0; i < n; i++)
if (!A[i].isZero())
return false;
return true;
}

## LucksWangSparseHeuristic()

int LucksWangSparseHeuristic | ( | const CanonicalForm & | F,
|  | const CFList & | factors,
|  | int | level,
|  | const CFList & | leadingCoeffs,
|  | CFList & | result )

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.

{
int threshold= 450;
CFArray termsF= getBiTerms (F, threshold);
int si=termsF.size();
int fl=factors.length();
//printf("size:%d, length=%d, char=%d\n",si,fl,getCharacteristic());
if ((si > threshold)
|| (si <= fl)
)
return 0;
sort (termsF, level);
CFArray* monoms= new CFArray [factors.length()];
int i= 0;
int num= 0;
for (CFListIterator iter= factors; iter.hasItem(); iter++, i++)
{
monoms[i]= getTerms (iter.getItem());
num += monoms [i].size();
sort (monoms [i]);
}
i= 0;
CFArray* monomsLead= new CFArray [leadingCoeffs.length()];
for (CFListIterator iter= leadingCoeffs; iter.hasItem(); iter++, i++)
{
monomsLead[i]= getTerms (iter.getItem());
sort (monomsLead [i]);
groupTogether (monomsLead [i], level);
strip (monomsLead [i], level);
}
CFArray solution= CFArray (num);
int k, d, count, j= F.level() + 1;
num= 0;
i= 0;
for (CFListIterator iter= factors; iter.hasItem(); i++, iter++)
{
d= degree (iter.getItem(), 1);
count= 0;
for (k= 0; k < monoms[i].size(); k++, j++, num++)
{
monoms [i][k] *= Variable (j);
if (degree (monoms[i][k], 1) == d)
{
solution[num]= monomsLead [i] [count];
count++;
}
}
}
delete [] monomsLead;
CFList tmp;
CFArray* stripped2= new CFArray [factors.length()];
for (i= factors.length() - 1; i > -1; i--)
{
tmp.insert (buildPolyFromArray (monoms [i]));
strip (monoms[i], stripped2 [i], level);
}
delete [] monoms;
CanonicalForm H= prod (tmp);
CFArray monomsH= getMonoms (H);
sort (monomsH,F.level());
groupTogether (monomsH, F.level());
if (monomsH.size() != termsF.size())
{
delete [] stripped2;
return 0;
}
CFArray strippedH;
strip (monomsH, strippedH, level);
CFArray strippedF;
strip (termsF, strippedF, level);
if (!isEqual (strippedH, strippedF))
{
delete [] stripped2;
return 0;
}
CFArray A= getEquations (monomsH, termsF);
CFArray startingSolution= solution;
CFArray newSolution= CFArray (solution.size());
result= CFList();
do
{
evaluate (A, solution, F.level() + 1);
if (isZero (A))
break;
if (!simplify (A, newSolution, F.level() + 1))
{
delete [] stripped2;
return 0;
}
if (isZero (newSolution))
break;
if (!merge (solution, newSolution))
break;
} while (1);
if (isEqual (startingSolution, solution))
{
delete [] stripped2;
return 0;
}
CanonicalForm factor;
num= 0;
for (i= 0; i < factors.length(); i++)
{
k= stripped2[i].size();
factor= 0;
for (j= 0; j < k; j++, num++)
{
if (solution [num].isZero())
continue;
factor += solution [num]*stripped2[i][j];
}
result.append (factor);
}
delete [] stripped2;
if (result.length() > 0)
return 1;
return 0;
}
num
CanonicalForm num(const CanonicalForm &f)
Definition canonicalform.h:337
isEqual
bool isEqual(int *a, int *b, int lower, int upper)
Definition cfGcdAlgExt.cc:947
getMonoms
CFArray getMonoms(const CanonicalForm &F)
extract monomials of F, parts in algebraic variable are considered coefficients
Definition cfModGcd.cc:1965
sort
static void sort(int **points, int sizePoints)
Definition cfNewtonPolygon.cc:100
merge
int ** merge(int **points1, int sizePoints1, int **points2, int sizePoints2, int &sizeResult)
Definition cfNewtonPolygon.cc:230
getTerms
void getTerms(const CanonicalForm &f, const CanonicalForm &t, CFList &result)
get_Terms: Split the polynomial in the containing terms.
Definition cf_factor.cc:283
List::length
int length() const
Definition ftmpl_list.cc:273
List::insert
void insert(const T &)
Definition ftmpl_list.cc:193
factor
CanonicalForm factor
Definition facAbsFact.cc:97
H
CanonicalForm H
Definition facAbsFact.cc:60
prod
fq_nmod_poly_t prod
Definition facHensel.cc:100
buildPolyFromArray
CanonicalForm buildPolyFromArray(const CFArray &A)
build a poly from entries in A
Definition facSparseHensel.h:267
groupTogether
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
Definition facSparseHensel.h:278
getBiTerms
CFArray getBiTerms(const CanonicalForm &F, int threshold)
get terms of F where F is considered a bivariate poly in Variable(1), Variable (2)
Definition facSparseHensel.h:236
simplify
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...
Definition facSparseHensel.h:390
strip
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...
Definition facSparseHensel.h:310
getEquations
CFArray getEquations(const CFArray &A, const CFArray &B)
get equations for LucksWangSparseHeuristic
Definition facSparseHensel.h:350
count
int status int void size_t count
Definition si_signals.h:69

## merge()

bool merge | ( | CFArray & | A,
|  | CFArray & | B )

inline

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.

{
if (A.size() != B.size())
return false;
int n= A.size();
for (int i= 0; i < n; i++)
{
if (!B[i].isZero())
{
if (A[i].isZero())
{
A[i]= B[i];
B[i]= 0;
}
else if (A[i] == B[i])
B[i]= 0;
else
return false;
}
}
return true;
}

## normalize()

CFList normalize | ( | const CFList & | L,
|  | const CFList & | normalizingFactor )

inline

normalize entries in L with normalizingFactor

Definition at line 555 of file facSparseHensel.h.

{
CFList result;
CFListIterator j= normalizingFactor;
for (CFListIterator i= L; i.hasItem(); i++, j++)
result.append (i.getItem() / j.getItem());
return result;
}

## patch()

CanonicalForm patch | ( | const CanonicalForm & | F1,
|  | const CanonicalForm & | F2,
|  | const CanonicalForm & | eval )

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.

{
CanonicalForm result= F1;
if (F2.level() != 1 && !F2.inCoeffDomain())
{
int d= degree (F2);
result *= power (F2.mvar(), d);
result /= power (eval, d);
}
return result;
}

## quickSort()

void quickSort | ( | int | lo,
|  | int | hi,
|  | CFArray & | A,
|  | int | l )

inline

quick sort helper function

Definition at line 85 of file facSparseHensel.h.

{
int i= lo, j= hi;
CanonicalForm tmp= A[(lo+hi)/2];
while (i <= j)
{
if (l > 0)
{
while (comp (A [i], tmp, l) < 0 && i < hi) i++;
while (comp (tmp, A[j], l) < 0 && j > lo) j--;
}
else
{
while (comp (A [i], tmp) < 0 && i < hi) i++;
while (comp (tmp, A[j]) < 0 && j > lo) j--;
}
if (i <= j)
{
swap (A, i, j);
i++;
j--;
}
}
if (lo < j) quickSort (lo, j, A, l);
if (i < hi) quickSort (i, hi, A, l);
}
swap
#define swap(_i, _j)
quickSort
void quickSort(int lo, int hi, CFArray &A, int l)
quick sort helper function
Definition facSparseHensel.h:85

## search()

int search | ( | const CFArray & | A,
|  | const CanonicalForm & | F,
|  | int | i,
|  | int | j )

inline

search for F in A between index i and j

Definition at line 566 of file facSparseHensel.h.

{
for (; i < j; i++)
if (A[i] == F)
return i;
return -1;
}

## simplify() [1/2]

bool simplify | ( | CFArray & | A,
|  | CFArray & | B,
|  | int | level )

inline

if possible simplify A as described above and store result in B

Definition at line 412 of file facSparseHensel.h.

{
int n= A.size();
CanonicalForm f;
int index;
for (int i= 0; i < n; i++)
{
if (!A[i].isZero())
{
f= simplify (A[i], level);
if (!f.isZero())
{
index= A[i].level() - level;
if (index < 0 || index >= B.size())
return false;
if (!B[index].isZero() && B[index] != f)
return false;
else if (B[index].isZero())
{
B[index]= f;
A[i]= 0;
}
}
}
}
return true;
}
f
FILE * f
Definition checklibs.c:9
index
static int index(p_Length length, p_Ord ord)
Definition p_Procs_Impl.h:592

## simplify() [2/2]

CanonicalForm simplify | ( | const CanonicalForm & | A,
|  | int | level )

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.

{
CanonicalForm F= 0;
if (size (A, A.level()) == 2)
{
CanonicalForm C= getVars (A);
if ((C/C.mvar()).level() < level)
{
CanonicalForm B= LC (A);
if (B.level() < level)
{
CanonicalForm quot;
if (fdivides (B, A, quot))
F= -tailcoeff (quot);
}
}
}
return F;
}
getVars
CanonicalForm getVars(const CanonicalForm &f)
CanonicalForm getVars ( const CanonicalForm & f ).
Definition cf_ops.cc:350
tailcoeff
CanonicalForm tailcoeff(const CanonicalForm &f)
Definition canonicalform.h:325
LC
CanonicalForm LC(const CanonicalForm &f)
Definition canonicalform.h:310
fdivides
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)

## sort()

void sort | ( | CFArray & | A,
|  | int | l = 0 )

inline

quick sort A

Definition at line 114 of file facSparseHensel.h.

{
quickSort (0, A.size() - 1, A, l);
}

## sparseHeuristic()

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

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 160 of file facSparseHensel.cc.

{
int j= A.level() - 1;
int i;
//initialize storage
CFArray *** storeFactors= new CFArray** [j];
for (i= 0; i < j; i++)
storeFactors [i]= new CFArray* [2];
CFArray eval= CFArray (j);
i= j - 1;
for (CFListIterator iter= evaluation; iter.hasItem(); iter++,i--)
eval[i]= iter.getItem();
storeFactors [0] [0]= new CFArray [minFactorsLength];
storeFactors [0] [1]= new CFArray [minFactorsLength];
for (i= 1; i < j; i++)
{
storeFactors[i] [0]= new CFArray [minFactorsLength];
storeFactors[i] [1]= new CFArray [minFactorsLength];
}
//
CFList * normalizingFactors= new CFList [j];
CFList uniFactors;
normalizingFactors [0]= findNormalizingFactor1 (biFactors,
evaluation.getLast(), uniFactors);
for (i= j - 1; i > 0; i--)
{
if (moreBiFactors[i-1].length() != minFactorsLength)
{
moreBiFactors[i-1]=
recombination (moreBiFactors [i-1], uniFactors, 1,
moreBiFactors[i-1].length()-uniFactors.length()+1,
eval[i], Variable (i + 2)
);
}
normalizingFactors [i]= findNormalizingFactor2 (moreBiFactors [i - 1],
eval[i], uniFactors);
}
CFList tmp;
tmp= normalize (biFactors, normalizingFactors[0]);
getTerms2 (tmp, storeFactors [0] [0]);
storeFactors [0] [1]= evaluate (storeFactors [0] [0], minFactorsLength,
evaluation.getLast(), Variable (2));
for (i= j - 1; i > 0; i--)
{
tmp= normalize (moreBiFactors [i-1], normalizingFactors [i]);
getTerms2 (tmp, storeFactors [i] [0]);
storeFactors [i] [1]= evaluate (storeFactors [i] [0], minFactorsLength,
eval[i], Variable (i + 2));
}
int k, l, m, mm, count, sizeOfUniFactors= 0;
int*** seperator= new int** [j];
Variable x= Variable (1);
for (i= 0; i < j; i++)
seperator [i]= new int* [minFactorsLength];
for (k= 0; k < minFactorsLength; k++)
{
for (i= 0; i < j; i++)
{
count= 0;
for (l= 0; l < storeFactors [i][0][k].size() - 1; l++)
{
if (degree (storeFactors[i][0][k][l], x) <
degree (storeFactors[i][0][k][l+1], x))
count++;
}
if (i == 0)
sizeOfUniFactors= count;
else if (sizeOfUniFactors != count)
{
for (m= 0; m < j; m++)
{
delete [] storeFactors [m] [0];
delete [] storeFactors [m] [1];
delete [] storeFactors [m];
for (mm= 0; mm < k; mm++)
delete [] seperator [m][mm];
delete [] seperator [m];
}
delete [] storeFactors;
delete [] seperator;
delete [] normalizingFactors;
return CFList();
}
seperator [i][k]= new int [count + 3];
seperator [i][k][0]= count + 1;
seperator [i][k][1]= 0;
count= 2;
for (l= 0; l < storeFactors [i][0][k].size() - 1; l++)
{
if (degree (storeFactors[i][0][k][l], x) <
degree (storeFactors[i][0][k][l+1], x))
{
seperator[i][k][count]=l + 1;
count++;
}
}
seperator [i][k][count]= storeFactors[i][0][k].size();
}
}
CanonicalForm tmp1, factor, quot;
CanonicalForm B= A;
CFList result;
int maxTerms, n, index1, index2, mmm, found, columns, oneCount;
int ** mat;
for (k= 0; k < minFactorsLength; k++)
{
factor= 0;
sizeOfUniFactors= seperator [0][k][0];
for (n= 1; n <= sizeOfUniFactors; n++)
{
columns= 0;
maxTerms= 1;
index1= j - 1;
for (i= j - 1; i >= 0; i--)
{
if (maxTerms < seperator[i][k][n+1]-seperator[i][k][n])
{
maxTerms= seperator[i][k][n + 1]-seperator[i][k][n];
index1= i;
}
}
for (i= j - 1; i >= 0; i--)
{
if (i == index1)
continue;
columns += seperator [i][k][n+1]-seperator[i][k][n];
}
mat= new int *[maxTerms];
mm= 0;
for (m= seperator[index1][k][n]; m < seperator[index1][k][n+1]; m++, mm++)
{
tmp1= storeFactors [index1][1][k][m];
mat[mm]= new int [columns];
for (i= 0; i < columns; i++)
mat[mm][i]= 0;
index2= 0;
for (i= j - 1; i >= 0; i--)
{
if (i == index1)
continue;
found= -1;
if ((found= search (storeFactors[i][1][k], tmp1,
seperator[i][k][n], seperator[i][k][n+1])) >= 0)
mat[mm][index2 + found - seperator [i][k][n]]= 1;
index2 += seperator [i][k][n+1]-seperator[i][k][n];
}
}
index2= 0;
for (i= j - 1; i >= 0; i--)
{
if (i == index1)
continue;
oneCount= 0;
for (mm= 0; mm < seperator [i][k][n + 1] - seperator [i][k][n]; mm++)
{
for (m= 0; m < maxTerms; m++)
{
if (mat[m][mm+index2] == 1)
oneCount++;
}
}
if (oneCount == seperator [i][k][n+1]-seperator[i][k][n] - 1)
{
for (mm= 0; mm < seperator [i][k][n+1]-seperator[i][k][n]; mm++)
{
oneCount= 0;
for (m= 0; m < maxTerms; m++)
if (mat[m][mm+index2] == 1)
oneCount++;
if (oneCount > 0)
continue;
for (m= 0; m < maxTerms; m++)
{
oneCount= 0;
for (mmm= 0; mmm < seperator[i][k][n+1]-seperator[i][k][n]; mmm++)
{
if (mat[m][mmm+index2] == 1)
oneCount++;
}
if (oneCount > 0)
continue;
mat[m][mm+index2]= 1;
}
}
}
index2 += seperator [i][k][n+1] - seperator [i][k][n];
}
//read off solution
mm= 0;
for (m= seperator[index1][k][n]; m < seperator[index1][k][n+1]; m++, mm++)
{
tmp1= storeFactors [index1][0][k][m];
index2= 0;
for (i= j - 1; i > -1; i--)
{
if (i == index1)
continue;
for (mmm= 0; mmm < seperator [i][k][n+1]-seperator[i][k][n]; mmm++)
if (mat[mm][mmm+index2] == 1)
tmp1= patch (tmp1, storeFactors[i][0][k][seperator[i][k][n]+mmm],
eval[i]);
index2 += seperator [i][k][n+1]-seperator[i][k][n];
}
factor += tmp1;
}
for (m= 0; m < maxTerms; m++)
delete [] mat [m];
delete [] mat;
}
if (fdivides (factor, B, quot))
{
result.append (factor);
B= quot;
if (result.length() == biFactors.length() - 1)
{
result.append (quot);
break;
}
}
}
//delete
for (i= 0; i < j; i++)
{
delete [] storeFactors [i] [0];
delete [] storeFactors [i] [1];
delete [] storeFactors [i];
for (k= 0; k < minFactorsLength; k++)
delete [] seperator [i][k];
delete [] seperator [i];
}
delete [] seperator;
delete [] storeFactors;
delete [] normalizingFactors;
//
return result;
}
m
int m
Definition cfEzgcd.cc:128
evaluation
const CanonicalForm int const CFList & evaluation
Definition facAbsFact.cc:52
found
bool found
Definition facFactorize.cc:55
minFactorsLength
CFList int & minFactorsLength
[in,out] minimal length of bivariate factors
Definition facFactorize.h:33
tmp1
CFList tmp1
Definition facFqBivar.cc:75
recombination
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...
Definition facFqFactorize.cc:2114
findNormalizingFactor1
CFList findNormalizingFactor1(const CFList &biFactors, const CanonicalForm &evalPoint, CFList &uniFactors)
find normalizing factors for biFactors and build monic univariate factors from biFactors
Definition facSparseHensel.h:123
findNormalizingFactor2
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...
Definition facSparseHensel.h:140
search
int search(const CFArray &A, const CanonicalForm &F, int i, int j)
search for F in A between index i and j
Definition facSparseHensel.h:566
patch
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 ...
Definition facSparseHensel.h:577
length
static BOOLEAN length(leftv result, leftv arg)
Definition interval.cc:257
normalize
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition syz3.cc:1027

## strip() [1/2]

void strip | ( | CFArray & | F,
|  | CFArray & | G,
|  | int | level )

inline

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.

{
int n, m, i, j;
CanonicalForm g;
m= F.size();
G= CFArray (m);
for (j= 0; j < m; j++)
{
g= 1;
for (i= 1; i <= level; i++)
{
if ((n= degree (F[j],i)) > 0)
g *= power (Variable (i), n);
}
F[j] /= g;
G[j]= g;
}
}
g
g
Definition cfModGcd.cc:4098

## 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.

{
int n, m, i;
CanonicalForm g;
m= F.size();
for (int j= 0; j < m; j++)
{
g= 1;
for (i= 1; i <= level; i++)
{
if ((n= degree (F[j],i)) > 0)
g *= power (Variable (i), n);
}
F[j] /= g;
}
}

## swap()

void swap | ( | CFArray & | A,
|  | int | i,
|  | int | j )

inline

swap entry i and j in A

Definition at line 76 of file facSparseHensel.h.

{
CanonicalForm tmp= A[i];
A[i]= A[j];
A[j]= tmp;
}