Loading...
Searching...
No Matches
facAbsFact.cc File Reference
`#include "config.h"`
`#include "timing.h"`
`#include "debug.h"`
`#include "facAbsBiFact.h"`
`#include "facAbsFact.h"`
`#include "facFqFactorize.h"`
`#include "facFqFactorizeUtil.h"`
`#include "facHensel.h"`
`#include "facSparseHensel.h"`
`#include "facFactorize.h"`
`#include "cf_reval.h"`
`#include "cf_primes.h"`
`#include "cf_algorithm.h"`
`#include "cfModResultant.h"`
`#include "cfUnivarGcd.h"`
`#include "FLINTconvert.h"`

Go to the source code of this file.

## Functions

TIMING_DEFINE_PRINT (abs_fac_bi_factorizer) TIMING_DEFINE_PRINT(abs_fac_hensel_lift) TIMING_DEFINE_PRINT(abs_fac_factor_recombination) TIMING_DEFINE_PRINT(abs_fac_shift_to_zero) TIMING_DEFINE_PRINT(abs_fac_precompute_leadcoeff) TIMING_DEFINE_PRINT(abs_fac_evaluation) TIMING_DEFINE_PRINT(abs_fac_recover_factors) TIMING_DEFINE_PRINT(abs_fac_bifactor_total) TIMING_DEFINE_PRINT(abs_fac_luckswang) TIMING_DEFINE_PRINT(abs_fac_lcheuristic) TIMING_DEFINE_PRINT(abs_fac_cleardenom) TIMING_DEFINE_PRINT(abs_fac_compress) CFAFList RothsteinTragerResultant(const CanonicalForm &F

| steps 4)-8) of Algorithm B.7.8. from Greuel, Pfister "A Singular Introduction to Commutative Algebra"
| for (CFIterator i=w;i.hasTerms();i++) terms.append(i.coeff())
| for (int i=terms.length();i >=1;i--, iter++) g+
| for (int i=F.level();i >=2;iter++, i--)
| if (degree(Feval, x) >=8||degree(H, x) >=8) res
| while (degree(sqrfPartRes) !=s)
return | CFAFList (CFAFactor(factor, getMipo(beta), 1))
CFAFList | RothsteinTrager (const CanonicalForm &F, const CFList &factors, const Variable &alpha, const CFList &evaluation)
| Algorithm B.7.8 from Greuel, Pfister "A Singular Introduction to Commutative Algebra".
CFList | evalPoints4AbsFact (const CanonicalForm &F, CFList &eval, Evaluation &E, int &intervalSize)
CFAFList | absFactorize (const CanonicalForm &G)
| absolute factorization of a multivariate poly over Q
CFAFList | absFactorizeMain (const CanonicalForm &G)
| main absolute factorization routine, expects poly which is irreducible over Q

## Variables

const CanonicalForm & | w
const CanonicalForm int | s
const CanonicalForm int const CFList & | evaluation
const CanonicalForm int const CFList const Variable & | y
Variable | x = Variable (1)
CanonicalForm | derivF = deriv (F, x)
CanonicalForm | g = 0
CanonicalForm | geval = g
CanonicalForm | derivFeval = derivF
CanonicalForm | Feval = F
CanonicalForm | H = y*derivFeval-geval
CanonicalForm | res = resultant (Feval, H, x)
CanonicalForm | sqrfPartRes = sqrfPart (res)
CFListIterator | iter = terms
REvaluation | E (1, terms.length(), IntRandom(25))
| do
Variable | beta = rootOf (sqrfPartRes)
CanonicalForm | factor = gcd (F, beta*derivF-g)

## Detailed Description

Author
  Martin Lee

Definition in file facAbsFact.cc.

## Function Documentation

## absFactorize()

CFAFList absFactorize | ( | const CanonicalForm & | G | ) |

absolute factorization of a multivariate poly over Q

Returns
  absFactorize returns a list whose entries contain three entities: an absolute irreducible factor, an irreducible univariate polynomial that defines the minimal field extension over which the irreducible factor is defined (note: in case the factor is already defined over Q[t]/(t), 1 is returned), and the multiplicity of the absolute irreducible factor

Parameters

  [in] | G | poly over Q

Definition at line 262 of file facAbsFact.cc.

{
//TODO handle homogeneous input, is already done in LIB interface but still...
ASSERT (getCharacteristic() == 0, "expected poly over Q");
CanonicalForm F= G;
CanonicalForm LcF= Lc (F);
bool isRat= isOn (SW_RATIONAL);
if (isRat)
F *= bCommonDen (F);
Off (SW_RATIONAL);
F /= icontent (F);
if (isRat)
On (SW_RATIONAL);
CFFList rationalFactors= factorize (F);
CFAFList result, resultBuf;
CFAFListIterator iter;
CFFListIterator i= rationalFactors;
i++;
for (; i.hasItem(); i++)
{
resultBuf= absFactorizeMain (i.getItem().factor());
for (iter= resultBuf; iter.hasItem(); iter++)
iter.getItem()= CFAFactor (iter.getItem().factor(),
iter.getItem().minpoly(), i.getItem().exp());
result= Union (result, resultBuf);
}
if (isRat)
normalize (result);
result.insert (CFAFactor (LcF, 1, 1));
return result;
}
isOn
bool isOn(int sw)
switches
Definition canonicalform.cc:1971
On
void On(int sw)
switches
Definition canonicalform.cc:1957
Off
void Off(int sw)
switches
Definition canonicalform.cc:1964
CFAFactor
AFactor< CanonicalForm > CFAFactor
Definition canonicalform.h:389
icontent
CanonicalForm FACTORY_PUBLIC icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f ).
Definition cf_gcd.cc:74
CFAFListIterator
ListIterator< CFAFactor > CFAFListIterator
Definition canonicalform.h:391
CFFListIterator
ListIterator< CFFactor > CFFListIterator
Definition canonicalform.h:394
CFFList
List< CFFactor > CFFList
Definition canonicalform.h:393
Lc
CanonicalForm Lc(const CanonicalForm &f)
Definition canonicalform.h:307
CFAFList
List< CFAFactor > CFAFList
Definition canonicalform.h:390
getCharacteristic
int FACTORY_PUBLIC getCharacteristic()
Definition cf_char.cc:70
i
int i
Definition cfEzgcd.cc:132
bCommonDen
CanonicalForm bCommonDen(const CanonicalForm &f)
void psqr ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & q, CanonicalForm & r,...
Definition cf_algorithm.cc:293
factorize
CFFList FACTORY_PUBLIC factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition cf_factor.cc:409
ASSERT
#define ASSERT(expression, message)
Definition cf_assert.h:99
SW_RATIONAL
static const int SW_RATIONAL
set to 1 for computations over Q
Definition cf_defs.h:31
CanonicalForm
factory's main class
Definition canonicalform.h:86
iter
CFFListIterator iter
Definition facAbsBiFact.cc:54
LcF
CanonicalForm LcF
Definition facAbsBiFact.cc:51
result
return result
Definition facAbsBiFact.cc:76
absFactorizeMain
CFAFList absFactorizeMain(const CanonicalForm &G)
main absolute factorization routine, expects poly which is irreducible over Q
Definition facAbsFact.cc:303
Union
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
G
STATIC_VAR TreeM * G
Definition janet.cc:31
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

## absFactorizeMain()

CFAFList absFactorizeMain | ( | const CanonicalForm & | F | ) |

main absolute factorization routine, expects poly which is irreducible over Q

Returns
  absFactorizeMain returns a list whose entries contain three entities: an absolute irreducible factor, an irreducible univariate polynomial that defines the minimal field extension over which the irreducible factor is defined (note: in case the factor is already defined over Q[t]/(t), 1 is returned as defining poly), and the multiplicity of the absolute irreducible factor

Parameters

  [in] | G | irred poly over Q

Definition at line 303 of file facAbsFact.cc.

{
CanonicalForm F= bCommonDen (G)*G;
Off (SW_RATIONAL);
F /= icontent (F);
On (SW_RATIONAL);
if (F.inCoeffDomain())
return CFAFList (CFAFactor (F, 1, 1));
// compress and find main Variable
CFMap N;
TIMING_START (abs_fac_compress)
CanonicalForm A= myCompress (F, N);
TIMING_END_AND_PRINT (abs_fac_compress,
"time to compress poly in abs fact: ")
//univariate case
if (F.isUnivariate())
{
CFAFList result;
result= uniAbsFactorize (F);
if (result.getFirst().factor().inCoeffDomain())
result.removeFirst();
return result;
}
//bivariate case
if (A.level() == 2)
{
CFAFList result= absBiFactorizeMain (A);
decompress (result, N);
return result; //needs compressed input
}
Variable x= Variable (1);
Variable y= Variable (2);
CFAFList factors;
A *= bCommonDen (A);
CFList Aeval, list, evaluation, bufEvaluation, bufAeval;
int factorNums= 1;
CFAFList absBiFactors, absBufBiFactors;
CanonicalForm evalPoly;
int lift, bufLift, lengthAeval2= A.level()-2;
CFList* bufAeval2= new CFList [lengthAeval2];
CFList* Aeval2= new CFList [lengthAeval2];
int counter;
int differentSecondVar= 0;
CanonicalForm bufA;
// several bivariate factorizations
TIMING_START (abs_fac_bifactor_total);
int absValue= 2;
REvaluation E (2, A.level(), IntRandom (absValue));
for (int i= 0; i < factorNums; i++)
{
counter= 0;
bufA= A;
bufAeval= CFList();
TIMING_START (abs_fac_evaluation);
bufEvaluation= evalPoints4AbsFact (bufA, bufAeval, E, absValue);
TIMING_END_AND_PRINT (abs_fac_evaluation,
"time to find evaluation point in abs fact: ");
E.nextpoint();
evalPoly= 0;
TIMING_START (abs_fac_evaluation);
evaluationWRTDifferentSecondVars (bufAeval2, bufEvaluation, A);
TIMING_END_AND_PRINT (abs_fac_evaluation,
"time to eval wrt diff second vars in abs fact: ");
for (int j= 0; j < lengthAeval2; j++)
{
if (!bufAeval2[j].isEmpty())
counter++;
}
bufLift= degree (A, y) + 1 + degree (LC(A, x), y);
TIMING_START (abs_fac_bi_factorizer);
absBufBiFactors= absBiFactorizeMain (bufAeval.getFirst(), true);
TIMING_END_AND_PRINT (abs_fac_bi_factorizer,
"time for bivariate factorization in abs fact: ");
if (absBufBiFactors.length() == 1)
{
factors.append (CFAFactor (A, 1, 1));
decompress (factors, N);
if (isOn (SW_RATIONAL))
normalize (factors);
delete [] bufAeval2;
delete [] Aeval2;
return factors;
}
if (i == 0)
{
Aeval= bufAeval;
evaluation= bufEvaluation;
absBiFactors= absBufBiFactors;
lift= bufLift;
for (int j= 0; j < lengthAeval2; j++)
Aeval2 [j]= bufAeval2 [j];
differentSecondVar= counter;
}
else
{
if (absBufBiFactors.length() < absBiFactors.length() ||
((bufLift < lift) &&
(absBufBiFactors.length() == absBiFactors.length())) ||
counter > differentSecondVar)
{
Aeval= bufAeval;
evaluation= bufEvaluation;
absBiFactors= absBufBiFactors;
lift= bufLift;
for (int j= 0; j < lengthAeval2; j++)
Aeval2 [j]= bufAeval2 [j];
differentSecondVar= counter;
}
}
int k= 0;
for (CFListIterator j= bufEvaluation; j.hasItem(); j++, k++)
evalPoly += j.getItem()*power (x, k);
list.append (evalPoly);
}
delete [] bufAeval2;
CFList rationalFactors;
Variable v= mvar (absBiFactors.getFirst().minpoly());
CFList biFactors;
for (CFAFListIterator iter= absBiFactors; iter.hasItem(); iter++)
biFactors.append (iter.getItem().factor());
sortList (biFactors, x);
int minFactorsLength;
bool irred= false;
TIMING_START (abs_fac_bi_factorizer);
factorizationWRTDifferentSecondVars (A, Aeval2, minFactorsLength, irred, v);
TIMING_END_AND_PRINT (abs_fac_bi_factorizer,
"time for bivariate factorization wrt diff second vars in abs fact: ");
TIMING_END_AND_PRINT (abs_fac_bifactor_total,
"total time for eval and bivar factors in abs fact: ");
if (irred)
{
factors.append (CFAFactor (A, 1, 1));
decompress (factors, N);
if (isOn (SW_RATIONAL))
normalize (factors);
delete [] Aeval2;
return factors;
}
if (minFactorsLength == 0)
minFactorsLength= biFactors.length();
else if (biFactors.length() > minFactorsLength)
refineBiFactors (A, biFactors, Aeval2, evaluation, minFactorsLength);
minFactorsLength= tmin (minFactorsLength, biFactors.length());
CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
sortByUniFactors (Aeval2, lengthAeval2, uniFactors, biFactors, evaluation);
minFactorsLength= tmin (minFactorsLength, biFactors.length());
if (minFactorsLength == 1)
{
factors.append (CFAFactor (A, 1, 1));
decompress (factors, N);
if (isOn (SW_RATIONAL))
normalize (factors);
delete [] Aeval2;
return factors;
}
bool found= false;
if (differentSecondVar == lengthAeval2)
{
bool zeroOccured= false;
for (CFListIterator iter= evaluation; iter.hasItem(); iter++)
{
if (iter.getItem().isZero())
{
zeroOccured= true;
break;
}
}
if (!zeroOccured)
{
rationalFactors= sparseHeuristic (A, biFactors, Aeval2, evaluation,
minFactorsLength);
if (rationalFactors.length() == biFactors.length())
{
for (CFListIterator iter= rationalFactors; iter.hasItem(); iter++)
{
if (totaldegree(iter.getItem())*degree(getMipo(v)) == totaldegree (G))
{
factors= CFAFList (CFAFactor (iter.getItem(), getMipo (v), 1));
found= true;
break;
}
}
// necessary since extension may be too large
if (!found)
factors= RothsteinTrager (A, rationalFactors, v, evaluation);
decompress (factors, N);
normalize (factors);
delete [] Aeval2;
return factors;
}
else
rationalFactors= CFList();
//TODO case where factors.length() > 0
}
}
CFList * oldAeval= new CFList [lengthAeval2];
for (int i= 0; i < lengthAeval2; i++)
oldAeval[i]= Aeval2[i];
getLeadingCoeffs (A, Aeval2);
CFList biFactorsLCs;
for (CFListIterator i= biFactors; i.hasItem(); i++)
biFactorsLCs.append (LC (i.getItem(), 1));
Variable w;
TIMING_START (abs_fac_precompute_leadcoeff);
CFList leadingCoeffs= precomputeLeadingCoeff (LC (A, 1), biFactorsLCs, x,
evaluation, Aeval2, lengthAeval2, w);
if (w.level() != 1)
changeSecondVariable (A, biFactors, evaluation, oldAeval, lengthAeval2,
uniFactors, w);
CanonicalForm oldA= A;
CFList oldBiFactors= biFactors;
CanonicalForm LCmultiplier= leadingCoeffs.getFirst();
bool LCmultiplierIsConst= LCmultiplier.inCoeffDomain();
leadingCoeffs.removeFirst();
if (!LCmultiplierIsConst)
distributeLCmultiplier (A, leadingCoeffs, biFactors, evaluation,
LCmultiplier);
//prepare leading coefficients
CFList* leadingCoeffs2= new CFList [lengthAeval2];
prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(), leadingCoeffs,
biFactors, evaluation);
CFListIterator iter;
CFList bufLeadingCoeffs2= leadingCoeffs2[lengthAeval2-1];
CFList bufBiFactors= biFactors;
bufA= A;
CanonicalForm testVars, bufLCmultiplier= LCmultiplier;
if (!LCmultiplierIsConst)
{
testVars= Variable (2);
for (int i= 0; i < lengthAeval2; i++)
{
if (!oldAeval[i].isEmpty())
testVars *= oldAeval[i].getFirst().mvar();
}
}
TIMING_END_AND_PRINT(abs_fac_precompute_leadcoeff,
"time to precompute LC in abs fact: ");
TIMING_START (abs_fac_luckswang);
CFList bufFactors= CFList();
bool LCheuristic= false;
if (LucksWangSparseHeuristic (A, biFactors, 2, leadingCoeffs2[lengthAeval2-1],
rationalFactors))
{
int check= biFactors.length();
int * index= new int [factors.length()];
CFList oldFactors= rationalFactors;
rationalFactors= recoverFactors (A, rationalFactors, index);
if (check == rationalFactors.length())
{
if (w.level() != 1)
{
for (iter= rationalFactors; iter.hasItem(); iter++)
iter.getItem()= swapvar (iter.getItem(), w, y);
}
for (CFListIterator iter= rationalFactors; iter.hasItem(); iter++)
{
if (totaldegree(iter.getItem())*degree (getMipo (v)) == totaldegree (G))
{
factors= CFAFList (CFAFactor (iter.getItem(), getMipo (v), 1));
found=true;
break;
}
}
// necessary since extension may be too large
if (!found)
factors= RothsteinTrager (A, rationalFactors, v, evaluation);
decompress (factors, N);
normalize (factors);
delete [] index;
delete [] Aeval2;
TIMING_END_AND_PRINT (abs_fac_luckswang,
"time for successful LucksWang in abs fact: ");
return factors;
}
else if (rationalFactors.length() > 0)
{
int oneCount= 0;
CFList l;
for (int i= 0; i < check; i++)
{
if (index[i] == 1)
{
iter=biFactors;
for (int j=1; j <= i-oneCount; j++)
iter++;
iter.remove (1);
for (int j= 0; j < lengthAeval2; j++)
{
l= leadingCoeffs2[j];
iter= l;
for (int k=1; k <= i-oneCount; k++)
iter++;
iter.remove (1);
leadingCoeffs2[j]=l;
}
oneCount++;
}
}
bufFactors= rationalFactors;
rationalFactors= CFList();
}
else if (!LCmultiplierIsConst && rationalFactors.length() == 0)
{
LCheuristic= true;
rationalFactors= oldFactors;
CFList contents, LCs;
bool foundTrueMultiplier= false;
LCHeuristic2 (LCmultiplier,rationalFactors,leadingCoeffs2[lengthAeval2-1],
contents, LCs, foundTrueMultiplier);
if (foundTrueMultiplier)
{
A= oldA;
leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
for (int i= lengthAeval2-1; i > -1; i--)
leadingCoeffs2[i]= CFList();
prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),
leadingCoeffs, biFactors, evaluation);
}
else
{
bool foundMultiplier= false;
LCHeuristic3 (LCmultiplier, rationalFactors, oldBiFactors, contents,
oldAeval,A,leadingCoeffs2, lengthAeval2, foundMultiplier);
// coming from above: divide out more LCmultiplier if possible
if (foundMultiplier)
{
foundMultiplier= false;
LCHeuristic4 (oldBiFactors, oldAeval, contents, rationalFactors,
testVars, lengthAeval2, leadingCoeffs2, A, LCmultiplier,
foundMultiplier);
}
else
{
LCHeuristicCheck (LCs, contents, A, oldA,
leadingCoeffs2[lengthAeval2-1], foundMultiplier);
if (!foundMultiplier && fdivides (getVars (LCmultiplier), testVars))
{
LCHeuristic (A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
lengthAeval2, evaluation, oldBiFactors);
}
}
// patch everything together again
leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
for (int i= lengthAeval2-1; i > -1; i--)
leadingCoeffs2[i]= CFList();
prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),leadingCoeffs,
biFactors, evaluation);
}
rationalFactors= CFList();
if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
{
LCheuristic= false;
A= bufA;
biFactors= bufBiFactors;
leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
LCmultiplier= bufLCmultiplier;
}
}
else
rationalFactors= CFList();
delete [] index;
}
TIMING_END_AND_PRINT (abs_fac_luckswang, "time for LucksWang in abs fact: ");
TIMING_START (abs_fac_lcheuristic);
if (!LCheuristic && !LCmultiplierIsConst && bufFactors.isEmpty()
&& fdivides (getVars (LCmultiplier), testVars))
{
LCheuristic= true;
LCHeuristic (A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
lengthAeval2, evaluation, oldBiFactors);
leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
for (int i= lengthAeval2-1; i > -1; i--)
leadingCoeffs2[i]= CFList();
prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),leadingCoeffs,
biFactors, evaluation);
if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
{
LCheuristic= false;
A= bufA;
biFactors= bufBiFactors;
leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
LCmultiplier= bufLCmultiplier;
}
}
TIMING_END_AND_PRINT (abs_fac_lcheuristic,
"time for Lc heuristic in abs fact: ");
tryAgainWithoutHeu:
//shifting to zero
TIMING_START (abs_fac_shift_to_zero);
CanonicalForm denA= bCommonDen (A);
A *= denA;
A= shift2Zero (A, Aeval, evaluation);
A /= denA;
for (iter= biFactors; iter.hasItem(); iter++)
iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
for (int i= 0; i < lengthAeval2-1; i++)
leadingCoeffs2[i]= CFList();
for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++)
{
iter.getItem()= shift2Zero (iter.getItem(), list, evaluation);
for (int i= A.level() - 4; i > -1; i--)
{
if (i + 1 == lengthAeval2-1)
leadingCoeffs2[i].append (iter.getItem() (0, i + 4));
else
leadingCoeffs2[i].append (leadingCoeffs2[i+1].getLast() (0, i + 4));
}
}
TIMING_END_AND_PRINT (abs_fac_shift_to_zero,
"time to shift evaluation point to zero in abs fact: ");
CFArray Pi;
CFList diophant;
int* liftBounds= new int [A.level() - 1];
int liftBoundsLength= A.level() - 1;
for (int i= 0; i < liftBoundsLength; i++)
liftBounds [i]= degree (A, i + 2) + 1;
Aeval.removeFirst();
bool noOneToOne= false;
TIMING_START (abs_fac_cleardenom);
CFList commonDenominators;
for (iter=biFactors; iter.hasItem(); iter++)
commonDenominators.append (bCommonDen (iter.getItem()));
CanonicalForm tmp1, tmp2, tmp3=1;
CFListIterator iter2;
for (int i= 0; i < lengthAeval2; i++)
{
iter2= commonDenominators;
for (iter= leadingCoeffs2[i]; iter.hasItem(); iter++, iter2++)
{
tmp1= bCommonDen (iter.getItem());
Off (SW_RATIONAL);
iter2.getItem()= lcm (iter2.getItem(), tmp1);
On (SW_RATIONAL);
}
}
tmp1= prod (commonDenominators);
for (iter= Aeval; iter.hasItem(); iter++)
{
tmp2= bCommonDen (iter.getItem()/denA);
Off (SW_RATIONAL);
tmp3= lcm (tmp2,tmp3);
On (SW_RATIONAL);
}
CanonicalForm multiplier;
multiplier= tmp3/tmp1;
iter2= commonDenominators;
for (iter=biFactors; iter.hasItem(); iter++, iter2++)
iter.getItem() *= iter2.getItem()*multiplier;
for (iter= Aeval; iter.hasItem(); iter++)
iter.getItem() *= tmp3*power (multiplier, biFactors.length() - 1)/denA;
for (int i= 0; i < lengthAeval2; i++)
{
iter2= commonDenominators;
for (iter= leadingCoeffs2[i]; iter.hasItem(); iter++, iter2++)
iter.getItem() *= iter2.getItem()*multiplier;
}
TIMING_END_AND_PRINT (abs_fac_cleardenom,
"time to clear denominators in abs fact: ");
TIMING_START (abs_fac_hensel_lift);
rationalFactors= nonMonicHenselLift (Aeval, biFactors,leadingCoeffs2,diophant,
Pi, liftBounds, liftBoundsLength, noOneToOne);
TIMING_END_AND_PRINT (abs_fac_hensel_lift,
"time for non monic hensel lifting in abs fact: ");
if (!noOneToOne)
{
int check= rationalFactors.length();
A= oldA;
TIMING_START (abs_fac_recover_factors);
rationalFactors= recoverFactors (A, rationalFactors, evaluation);
TIMING_END_AND_PRINT (abs_fac_recover_factors,
"time to recover factors in abs fact: ");
if (check != rationalFactors.length())
noOneToOne= true;
else
rationalFactors= Union (rationalFactors, bufFactors);
}
if (noOneToOne)
{
if (!LCmultiplierIsConst && LCheuristic)
{
A= bufA;
biFactors= bufBiFactors;
leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
delete [] liftBounds;
LCheuristic= false;
goto tryAgainWithoutHeu;
//something probably went wrong in the heuristic
}
A= shift2Zero (oldA, Aeval, evaluation);
biFactors= oldBiFactors;
for (iter= biFactors; iter.hasItem(); iter++)
iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
CanonicalForm LCA= LC (Aeval.getFirst(), 1);
CanonicalForm yToLift= power (y, lift);
CFListIterator i= biFactors;
lift= degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1;
i++;
for (; i.hasItem(); i++)
lift= tmax (lift, degree (i.getItem(), 2)+degree (LC (i.getItem(), 1))+1);
lift= tmax (degree (Aeval.getFirst() , 2) + 1, lift);
i= biFactors;
yToLift= power (y, lift);
CanonicalForm dummy;
for (; i.hasItem(); i++)
{
LCA= LC (i.getItem(), 1);
extgcd (LCA, yToLift, LCA, dummy);
i.getItem()= mod (i.getItem()*LCA, yToLift);
}
liftBoundsLength= F.level() - 1;
liftBounds= liftingBounds (A, lift);
CFList MOD;
bool earlySuccess;
CFList earlyFactors;
ExtensionInfo info= ExtensionInfo (false);
CFList liftedFactors;
TIMING_START (abs_fac_hensel_lift);
liftedFactors= henselLiftAndEarly
(A, MOD, liftBounds, earlySuccess, earlyFactors,
Aeval, biFactors, evaluation, info);
TIMING_END_AND_PRINT (abs_fac_hensel_lift,
"time for hensel lifting in abs fact: ");
TIMING_START (abs_fac_factor_recombination);
rationalFactors= factorRecombination (A, liftedFactors, MOD);
TIMING_END_AND_PRINT (abs_fac_factor_recombination,
"time for factor recombination in abs fact: ");
if (earlySuccess)
rationalFactors= Union (rationalFactors, earlyFactors);
for (CFListIterator i= rationalFactors; i.hasItem(); i++)
{
int kk= Aeval.getLast().level();
for (CFListIterator j= evaluation; j.hasItem(); j++, kk--)
{
if (i.getItem().level() < kk)
continue;
i.getItem()= i.getItem() (Variable (kk) - j.getItem(), kk);
}
}
}
if (w.level() != 1)
{
for (CFListIterator iter= rationalFactors; iter.hasItem(); iter++)
iter.getItem()= swapvar (iter.getItem(), w, y);
}
for (CFListIterator iter= rationalFactors; iter.hasItem(); iter++)
{
if (totaldegree (iter.getItem())*degree (getMipo (v)) == totaldegree (G))
{
factors= CFAFList (CFAFactor (iter.getItem(), getMipo (v), 1));
found= true;
break;
}
}
// necessary since extension may be too large
if (!found)
factors= RothsteinTrager (A, rationalFactors, v, evaluation);
decompress (factors, N);
if (isOn (SW_RATIONAL))
normalize (factors);
delete [] leadingCoeffs2;
delete [] oldAeval;
delete [] Aeval2;
delete[] liftBounds;
return factors;
}
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition canonicalform.cc:1896
getVars
CanonicalForm getVars(const CanonicalForm &f)
CanonicalForm getVars ( const CanonicalForm & f ).
Definition cf_ops.cc:350
mod
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
degree
int degree(const CanonicalForm &f)
Definition canonicalform.h:316
CFArray
Array< CanonicalForm > CFArray
Definition canonicalform.h:397
swapvar
CanonicalForm FACTORY_PUBLIC swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition cf_ops.cc:168
CFListIterator
ListIterator< CanonicalForm > CFListIterator
Definition canonicalform.h:396
totaldegree
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition cf_ops.cc:523
CFList
List< CanonicalForm > CFList
Definition canonicalform.h:395
mvar
Variable mvar(const CanonicalForm &f)
Definition canonicalform.h:334
LC
CanonicalForm LC(const CanonicalForm &f)
Definition canonicalform.h:310
N
const CanonicalForm CFMap CFMap & N
Definition cfEzgcd.cc:56
l
int l
Definition cfEzgcd.cc:100
k
int k
Definition cfEzgcd.cc:99
myCompress
int myCompress(const CanonicalForm &F, const CanonicalForm &G, CFMap &M, CFMap &N, bool topLevel)
compressing two polynomials F and G, M is used for compressing, N to reverse the compression
Definition cfModGcd.cc:92
x
Variable x
Definition cfModGcd.cc:4090
decompress
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
Definition cfNewtonPolygon.cc:853
extgcd
CanonicalForm extgcd(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b)
CanonicalForm extgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a,...
Definition cfUnivarGcd.cc:174
fdivides
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
AFactor::minpoly
T minpoly() const
Definition ftmpl_afactor.h:30
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
ExtensionInfo
ExtensionInfo contains information about extension.
Definition ExtensionInfo.h:51
IntRandom
generate random integers
Definition cf_random.h:56
ListIterator::getItem
T & getItem() const
Definition ftmpl_list.cc:431
List::getFirst
T getFirst() const
Definition ftmpl_list.cc:279
List::removeFirst
void removeFirst()
Definition ftmpl_list.cc:287
List::length
int length() const
Definition ftmpl_list.cc:273
List::append
void append(const T &)
Definition ftmpl_list.cc:256
List::isEmpty
int isEmpty() const
Definition ftmpl_list.cc:267
REvaluation
class to generate random evaluation points
Definition cf_reval.h:26
Variable
factory's class for variables
Definition factory.h:127
absBiFactorizeMain
CFAFList absBiFactorizeMain(const CanonicalForm &G, bool full)
main absolute factorization routine, expects bivariate poly which is irreducible over Q
Definition facAbsBiFact.cc:212
uniAbsFactorize
CFAFList uniAbsFactorize(const CanonicalForm &F, bool full=false)
univariate absolute factorization over Q
evaluation
const CanonicalForm int const CFList & evaluation
Definition facAbsFact.cc:52
y
const CanonicalForm int const CFList const Variable & y
Definition facAbsFact.cc:53
E
REvaluation E(1, terms.length(), IntRandom(25))
evalPoints4AbsFact
CFList evalPoints4AbsFact(const CanonicalForm &F, CFList &eval, Evaluation &E, int &intervalSize)
Definition facAbsFact.cc:132
w
const CanonicalForm & w
Definition facAbsFact.cc:51
RothsteinTrager
CFAFList RothsteinTrager(const CanonicalForm &F, const CFList &factors, const Variable &alpha, const CFList &evaluation)
Algorithm B.7.8 from Greuel, Pfister "A Singular Introduction to CommutativeAlgebra".
Definition facAbsFact.cc:105
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition facBivar.h:39
found
bool found
Definition facFactorize.cc:55
factorizationWRTDifferentSecondVars
void factorizationWRTDifferentSecondVars(const CanonicalForm &A, CFList *&Aeval, int &minFactorsLength, bool &irred, const Variable &w)
Definition facFactorize.cc:158
minFactorsLength
CFList int & minFactorsLength
[in,out] minimal length of bivariate factors
Definition facFactorize.h:33
Aeval
CFList *& Aeval
<[in] poly
Definition facFactorize.h:31
irred
CFList int bool & irred
[in,out] Is A irreducible?
Definition facFactorize.h:34
getLast
else L getLast()(0
tmp1
CFList tmp1
Definition facFqBivar.cc:75
tmp2
CFList tmp2
Definition facFqBivar.cc:75
henselLiftAndEarly
CFList henselLiftAndEarly(CanonicalForm &A, bool &earlySuccess, CFList &earlyFactors, DegreePattern &degs, int &liftBound, const CFList &uniFactors, const ExtensionInfo &info, const CanonicalForm &eval, modpk &b, CanonicalForm &den)
hensel Lifting and early factor detection
Definition facFqBivar.cc:1155
factorRecombination
CFList factorRecombination(CFList &factors, CanonicalForm &F, const CanonicalForm &N, DegreePattern &degs, const CanonicalForm &eval, int s, int thres, const modpk &b, const CanonicalForm &den)
naive factor recombination as decribed in "Factoringmultivariate polynomials over a finite field" by ...
Definition facFqBivar.cc:589
recoverFactors
CFList recoverFactors(const CanonicalForm &F, const CFList &factors)
divides factors by their content wrt. Variable(1) and checks if these polys divide F
Definition facFqFactorizeUtil.cc:238
shift2Zero
CanonicalForm shift2Zero(const CanonicalForm &F, CFList &Feval, const CFList &evaluation, int l)
shift evaluation point to zero
Definition facFqFactorizeUtil.cc:131
liftingBounds
int * liftingBounds(const CanonicalForm &A, const int &bivarLiftBound)
compute lifting bounds
Definition facFqFactorizeUtil.cc:118
precomputeLeadingCoeff
CFList precomputeLeadingCoeff(const CanonicalForm &LCF, const CFList &LCFFactors, const Variable &alpha, const CFList &evaluation, CFList *&differentSecondVarLCs, int lSecondVarLCs, Variable &y)
computes a list l of length length(LCFFactors)+1 of polynomials such that prod (l)=LCF,...
Definition facFqFactorize.cc:1479
LCHeuristicCheck
void LCHeuristicCheck(const CFList &LCs, const CFList &contents, CanonicalForm &A, const CanonicalForm &oldA, CFList &leadingCoeffs, bool &foundTrueMultiplier)
checks if prod(LCs)==LC (oldA,1) and if so divides elements of leadingCoeffs by elements in contents,...
Definition facFqFactorize.cc:2763
distributeLCmultiplier
void distributeLCmultiplier(CanonicalForm &A, CFList &leadingCoeffs, CFList &biFactors, const CFList &evaluation, const CanonicalForm &LCmultipler)
distributes a divisor LCmultiplier of LC(A,1) on the bivariate factors and the precomputed leading co...
Definition facFqFactorize.cc:2591
evaluationWRTDifferentSecondVars
void evaluationWRTDifferentSecondVars(CFList *&Aeval, const CFList &evaluation, const CanonicalForm &A)
evaluate a poly A with main variable at level 1 at an evaluation point in K^(n-1) wrt different secon...
Definition facFqFactorize.cc:1966
prepareLeadingCoeffs
void prepareLeadingCoeffs(CFList *&LCs, CanonicalForm &A, CFList &Aeval, int n, const CFList &leadingCoeffs, const CFList &biFactors, const CFList &evaluation)
normalize precomputed leading coefficients such that leading coefficients evaluated at evaluation in ...
Definition facFqFactorize.cc:2382
LCHeuristic4
void LCHeuristic4(const CFList &oldBiFactors, const CFList *oldAeval, const CFList &contents, const CFList &factors, const CanonicalForm &testVars, int lengthAeval, CFList *&leadingCoeffs, CanonicalForm &A, CanonicalForm &LCmultiplier, bool &foundMultiplier)
heuristic to remove factors of LCmultiplier from factors. More precisely checks if elements of conten...
Definition facFqFactorize.cc:2857
changeSecondVariable
void changeSecondVariable(CanonicalForm &A, CFList &biFactors, CFList &evaluation, CFList *&oldAeval, int lengthAeval2, const CFList &uniFactors, const Variable &w)
changes the second variable to be w and updates all relevant data
Definition facFqFactorize.cc:2544
sortByUniFactors
void sortByUniFactors(CFList *&Aeval, int AevalLength, CFList &uniFactors, CFList &biFactors, const CFList &evaluation)
sort bivariate factors in Aeval such that their corresponding univariate factors coincide with uniFac...
Definition facFqFactorize.cc:2251
getLeadingCoeffs
void getLeadingCoeffs(const CanonicalForm &A, CFList *&Aeval)
extract leading coefficients wrt Variable(1) from bivariate factors obtained from factorizations of A...
Definition facFqFactorize.cc:2233
LCHeuristic3
void LCHeuristic3(const CanonicalForm &LCmultiplier, const CFList &factors, const CFList &oldBiFactors, const CFList &contents, const CFList *oldAeval, CanonicalForm &A, CFList *&leadingCoeffs, int lengthAeval, bool &foundMultiplier)
heuristic to remove LCmultiplier from a factor based on the contents of factors. factors are assumed ...
Definition facFqFactorize.cc:2809
LCHeuristic
void LCHeuristic(CanonicalForm &A, const CanonicalForm &LCmultiplier, CFList &biFactors, CFList *&leadingCoeffs, const CFList *oldAeval, int lengthAeval, const CFList &evaluation, const CFList &oldBiFactors)
heuristic to distribute LCmultiplier onto factors based on the variables that occur in LCmultiplier a...
Definition facFqFactorize.cc:2615
refineBiFactors
void refineBiFactors(const CanonicalForm &A, CFList &biFactors, CFList *const &Aeval, const CFList &evaluation, int minFactorsLength)
refine a bivariate factorization of A with l factors to one with minFactorsLength if possible
Definition facFqFactorize.cc:2335
LCHeuristic2
void LCHeuristic2(const CanonicalForm &LCmultiplier, const CFList &factors, CFList &leadingCoeffs, CFList &contents, CFList &LCs, bool &foundTrueMultiplier)
heuristic to distribute LCmultiplier onto factors based on the contents of factors....
Definition facFqFactorize.cc:2779
buildUniFactors
CFList buildUniFactors(const CFList &biFactors, const CanonicalForm &evalPoint, const Variable &y)
plug in evalPoint for y in a list of polys
Definition facFqFactorize.cc:2321
nonMonicHenselLift
CFList nonMonicHenselLift(const CFList &F, const CFList &factors, const CFList &LCs, CFList &diophant, CFArray &Pi, CFMatrix &M, int lOld, int &lNew, const CFList &MOD, bool &noOneToOne)
Definition facHensel.cc:2856
j
int j
Definition facHensel.cc:110
prod
fq_nmod_poly_t prod
Definition facHensel.cc:100
sortList
void sortList(CFList &list, const Variable &x)
sort a list of polynomials by their degree in x.
Definition facHensel.cc:449
LucksWangSparseHeuristic
int LucksWangSparseHeuristic(const CanonicalForm &F, const CFList &factors, int level, const CFList &leadingCoeffs, CFList &result)
sparse heuristic lifting by Wang and Lucks
Definition facSparseHensel.cc:26
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 the...
Definition facSparseHensel.cc:160
getMipo
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition variable.cc:207
if
if(!FE_OPT_NO_SHELL_FLAG)
Definition fehelp.cc:1000
tmax
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
tmin
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
info
#define info
Definition libparse.cc:1256
check
VAR int check
Definition libparse.cc:1106
lift
ideal lift(const ideal J, const ring r, const ideal inI, const ring s)
Definition lift.cc:26
absValue
number absValue(poly p)
Definition linearAlgebra.cc:734
lcm
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition minpoly.cc:709
index
static int index(p_Length length, p_Ord ord)
Definition p_Procs_Impl.h:592
A
#define A
Definition sirandom.c:24
TIMING_START
#define TIMING_START(t)
Definition timing.h:92
TIMING_END_AND_PRINT
#define TIMING_END_AND_PRINT(t, msg)
Definition timing.h:94

## CFAFList()

return CFAFList | ( | CFAFactor(factor, getMipo(beta), 1) |  | ) |

## evalPoints4AbsFact()

CFList evalPoints4AbsFact | ( | const CanonicalForm & | F,
|  | CFList & | eval,
|  | Evaluation & | E,
|  | int & | intervalSize )

Definition at line 132 of file facAbsFact.cc.

{
CFList result;
Variable x= Variable (1);
CanonicalForm LCF= LC (F, x);
CFList LCFeval= CFList();
bool found= false;
bool allZero= true;
bool foundZero= false;
CanonicalForm deriv_x, gcd_deriv;
CFFList uniFactors;
CFListIterator iter;
int count= 0;
do
{
count++;
if (count==E.max() - E.min() + 1)
{
count= 1;
intervalSize++;
E= REvaluation (E.min(), E.max(), IntRandom (intervalSize));
E.nextpoint();
}
eval.insert (F);
LCFeval.insert (LCF);
bool bad= false;
for (int i= E.max(); i >= E.min(); i--)
{
eval.insert (eval.getFirst()( E [i], i));
LCFeval.insert (LCFeval.getFirst()( E [i], i));
result.append (E[i]);
if (!E[i].isZero())
allZero= false;
else
foundZero= true;
if (!allZero && foundZero)
{
result= CFList();
eval= CFList();
LCFeval= CFList();
bad= true;
foundZero= false;
break;
}
if (degree (eval.getFirst(), i - 1) != degree (F, i - 1))
{
result= CFList();
LCFeval= CFList();
eval= CFList();
bad= true;
break;
}
if ((i != 2) && (degree (LCFeval.getFirst(), i-1) != degree (LCF, i-1)))
{
result= CFList();
LCFeval= CFList();
eval= CFList();
bad= true;
break;
}
}
if (bad)
{
E.nextpoint();
continue;
}
if (degree (eval.getFirst()) != degree (F, 1))
{
result= CFList();
eval= CFList();
LCFeval= CFList();
E.nextpoint();
continue;
}
deriv_x= deriv (eval.getFirst(), x);
gcd_deriv= gcd (eval.getFirst(), deriv_x);
if (degree (gcd_deriv) > 0)
{
result= CFList();
eval= CFList();
LCFeval= CFList();
E.nextpoint();
continue;
}
uniFactors= factorize (eval.getFirst());
if (uniFactors.getFirst().factor().inCoeffDomain())
uniFactors.removeFirst();
if (uniFactors.length() > 1 || uniFactors.getFirst().exp() > 1)
{
result= CFList();
eval= CFList();
LCFeval= CFList();
E.nextpoint();
continue;
}
iter= eval;
iter++;
CanonicalForm contentx= content (iter.getItem(), x);
if (degree (contentx) > 0)
{
result= CFList();
eval= CFList();
LCFeval= CFList();
E.nextpoint();
continue;
}
contentx= content (iter.getItem());
if (degree (contentx) > 0)
{
result= CFList();
eval= CFList();
LCFeval= CFList();
E.nextpoint();
continue;
}
found= true;
}
while (!found);
if (!eval.isEmpty())
eval.removeFirst();
return result;
}
content
CanonicalForm FACTORY_PUBLIC content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f ).
Definition cf_gcd.cc:603
deriv
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
Definition canonicalform.h:346
Factor::exp
int exp() const
Definition ftmpl_factor.h:31
Factor::factor
T factor() const
Definition ftmpl_factor.h:30
contentx
CanonicalForm contentx
Definition facFactorize.cc:128
gcd_deriv
CanonicalForm gcd_deriv
Definition facFactorize.cc:58
LCFeval
CFList LCFeval
Definition facFactorize.cc:53
LCF
CanonicalForm LCF
Definition facFactorize.cc:52
deriv_x
CanonicalForm deriv_x
Definition facFactorize.cc:58
bad
bool bad
Definition facFactorize.cc:64
allZero
bool allZero
Definition facFactorize.cc:56
eval
CFList & eval
Definition facFactorize.cc:47
foundZero
bool foundZero
Definition facFactorize.cc:57
isZero
bool isZero(const CFArray &A)
checks if entries of A are zero
Definition facSparseHensel.h:468
count
int status int void size_t count
Definition si_signals.h:69
gcd
int gcd(int a, int b)
Definition walkSupport.cc:836

## for() [1/3]

for | ( | CFIterator | i = w;i.hasTerms();i++ | ) |

## for() [2/3]

for | ( | int | i = F.level(); i >= 2; iter++,
|  | i-- | )

Definition at line 77 of file facAbsFact.cc.

{
Feval= Feval (iter.getItem(), i);
geval= geval (iter.getItem(), i);
derivFeval= derivFeval (iter.getItem(), i);
}
geval
CanonicalForm geval
Definition facAbsFact.cc:60
Feval
CanonicalForm Feval
Definition facAbsFact.cc:60
derivFeval
CanonicalForm derivFeval
Definition facAbsFact.cc:60

## for() [3/3]

for | ( | int | i = terms.length();i >=1;i--,
|  | iter++ | )

## if()

if | ( | degree(Feval, x) >=8||degree(H, x) >= | 8 | ) |

## RothsteinTrager()

CFAFList RothsteinTrager | ( | const CanonicalForm & | F,
|  | const CFList & | factors,
|  | const Variable & | alpha,
|  | const CFList & | evaluation )

Algorithm B.7.8 from Greuel, Pfister "A Singular Introduction to Commutative Algebra".

Definition at line 105 of file facAbsFact.cc.

{
Variable x= Variable (1);
ASSERT (factors.length() == 2, "expected two factors");
CanonicalForm G, H;
if (totaldegree (factors.getFirst()) > totaldegree (factors.getLast()))
{
H= factors.getLast();
G= factors.getFirst();
}
else
{
H= factors.getFirst();
G= factors.getLast();
}
CanonicalForm derivH= deriv (H, x);
CanonicalForm w= G*derivH;
Variable y= Variable (F.level()+1);
w= replacevar (w, alpha, y);
int s= totaldegree (F)/totaldegree (H);
return RothsteinTragerResultant (F, w, s, evaluation, y);
}
replacevar
CanonicalForm FACTORY_PUBLIC replacevar(const CanonicalForm &, const Variable &, const Variable &)
CanonicalForm replacevar ( const CanonicalForm & f, const Variable & x1, const Variable & x2 ).
Definition cf_ops.cc:271
List::getLast
T getLast() const
Definition ftmpl_list.cc:309
alpha
Variable alpha
Definition facAbsBiFact.cc:52
s
const CanonicalForm int s
Definition facAbsFact.cc:51
H
CanonicalForm H
Definition facAbsFact.cc:60

## TIMING_DEFINE_PRINT()

TIMING_DEFINE_PRINT | ( | abs_fac_bi_factorizer |  | ) | const &

steps 4)-8) of Algorithm B.7.8. from Greuel, Pfister "A Singular Introduction to Commutative Algebra"

## while()

while | ( | degree(sqrfPartRes) ! | = s | ) |

## Variable Documentation

## beta

Variable beta = rootOf (sqrfPartRes)

Definition at line 95 of file facAbsFact.cc.

## derivF

CanonicalForm derivF = deriv (F, x)

Definition at line 59 of file facAbsFact.cc.

## derivFeval

derivFeval = derivF

Definition at line 60 of file facAbsFact.cc.

## do

do

Initial value:
{
E.nextpoint()

Definition at line 65 of file facAbsFact.cc.

## E

REvaluation E(1, terms.length(), IntRandom(25)) | ( | 1 | ,
|  | terms. | length(),
|  | IntRandom(25) | )

## evaluation

const CanonicalForm int const CFList& evaluation

Definition at line 52 of file facAbsFact.cc.

## factor

CanonicalForm factor = gcd (F, beta*derivF-g)

Definition at line 97 of file facAbsFact.cc.

## Feval

Feval = F

Definition at line 60 of file facAbsFact.cc.

## g

g = 0

Definition at line 60 of file facAbsFact.cc.

## geval

geval = g

Definition at line 60 of file facAbsFact.cc.

## H

H = y*derivFeval-geval

Definition at line 60 of file facAbsFact.cc.

## iter

iter = terms

Definition at line 61 of file facAbsFact.cc.

## res

else res = resultant (Feval, H, x)

Definition at line 60 of file facAbsFact.cc.

## s

const CanonicalForm int s

Definition at line 51 of file facAbsFact.cc.

## sqrfPartRes

sqrfPartRes = sqrfPart (res)

Definition at line 60 of file facAbsFact.cc.

## w

const CanonicalForm& w

Definition at line 51 of file facAbsFact.cc.

## x

Variable x = Variable (1)

Definition at line 58 of file facAbsFact.cc.

## y

const CanonicalForm int const CFList const Variable& y

Initial value:
{
CFList terms

Definition at line 52 of file facAbsFact.cc.