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

multivariate factorization over Q(a) More...

`#include "timing.h"`
`#include "facBivar.h"`
`#include "facFqBivarUtil.h"`

Go to the source code of this file.

## Functions

| TIMING_DEFINE_PRINT (fac_squarefree) TIMING_DEFINE_PRINT(fac_factor_squarefree) void factorizationWRTDifferentSecondVars(const CanonicalForm &A
| Factorization of A wrt. to different second vars.
CFList | multiFactorize (const CanonicalForm &F, const Variable &v)
| Factorization over Q (a).
CFList | ratSqrfFactorize (const CanonicalForm &G, const Variable &v=Variable(1))
| factorize a squarefree multivariate polynomial over
CFFList | ratFactorize (const CanonicalForm &G, const Variable &v=Variable(1), bool substCheck=true)
| factorize a multivariate polynomial over

## Variables

CFList *& | Aeval
| <[in] poly
CFList int & | minFactorsLength
| [in,out] minimal length of bivariate factors
CFList int bool & | irred
| [in,out] Is A irreducible?
CFList int bool const Variable & | w
| <[in] alg. variable

## Detailed Description

multivariate factorization over Q(a)

Author
  Martin Lee

Definition in file facFactorize.h.

## Function Documentation

## multiFactorize()

CFList multiFactorize | ( | const CanonicalForm & | F,
|  | const Variable & | v )

Factorization over Q (a).

Returns
  multiFactorize returns a factorization of F

Parameters

  [in] | F | sqrfree poly
  [in] | v | some algebraic variable

Definition at line 198 of file facFactorize.cc.

{
if (F.inCoeffDomain())
return CFList (F);
TIMING_START (fac_preprocess_and_content);
// compress and find main Variable
CFMap N;
TIMING_START (fac_compress)
CanonicalForm A= myCompress (F, N);
TIMING_END_AND_PRINT (fac_compress, "time to compress poly over Q: ")
//univariate case
if (F.isUnivariate())
{
CFList result;
if (v.level() != 1)
result= conv (factorize (F, v));
else
result= conv (factorize (F,true));
if (result.getFirst().inCoeffDomain())
result.removeFirst();
return result;
}
//bivariate case
if (A.level() == 2)
{
CFList buf= ratBiSqrfFactorize (F, v);
if (buf.getFirst().inCoeffDomain())
buf.removeFirst();
return buf;
}
Variable x= Variable (1);
Variable y= Variable (2);
// remove content
TIMING_START (fac_content);
CFList contentAi;
CanonicalForm lcmCont= lcmContent (A, contentAi);
A /= lcmCont;
TIMING_END_AND_PRINT (fac_content, "time to extract content over Q: ");
// trivial after content removal
CFList contentAFactors;
if (A.inCoeffDomain())
{
for (CFListIterator i= contentAi; i.hasItem(); i++)
{
if (i.getItem().inCoeffDomain())
continue;
else
{
lcmCont /= i.getItem();
contentAFactors=
Union (multiFactorize (lcmCont, v),
multiFactorize (i.getItem(), v));
break;
}
}
decompress (contentAFactors, N);
if (isOn (SW_RATIONAL))
normalize (contentAFactors);
return contentAFactors;
}
// factorize content
TIMING_START (fac_content);
contentAFactors= multiFactorize (lcmCont, v);
TIMING_END_AND_PRINT (fac_content, "time to factor content over Q: ");
// univariate after content removal
CFList factors;
if (A.isUnivariate ())
{
if (v.level() != 1)
factors= conv (factorize (A, v));
else
factors= conv (factorize (A,true));
append (factors, contentAFactors);
decompress (factors, N);
return factors;
}
A *= bCommonDen (A);
CFList Aeval, list, evaluation, bufEvaluation, bufAeval;
int factorNums= 2;
//p is irreducible. But factorize does not recognizes this. However, if you
//change factorNums to 2 at line 281 in facFactorize.cc it will. That change
//might impair performance in some cases since you do twice as many
//bivariate factorizations as before. Otherwise you need to change
//precomputeLeadingCoeff to detect these cases and trigger more bivariate
// factorizations.
// (http://www.singular.uni-kl.de:8002/trac/ticket/666)
CFList biFactors, bufBiFactors;
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;
TIMING_END_AND_PRINT (fac_preprocess_and_content,
"time to preprocess poly and extract content over Q: ");
// several bivariate factorizations
TIMING_START (fac_bifactor_total);
REvaluation E (2, A.level(), IntRandom (25));
for (int i= 0; i < factorNums; i++)
{
counter= 0;
bufA= A;
bufAeval= CFList();
TIMING_START (fac_evaluation);
bufEvaluation= evalPoints (bufA, bufAeval, E);
TIMING_END_AND_PRINT (fac_evaluation,
"time to find evaluation point over Q: ");
E.nextpoint();
evalPoly= 0;
TIMING_START (fac_evaluation);
evaluationWRTDifferentSecondVars (bufAeval2, bufEvaluation, A);
TIMING_END_AND_PRINT (fac_evaluation,
"time to eval wrt diff second vars over Q: ");
for (int j= 0; j < lengthAeval2; j++)
{
if (!bufAeval2[j].isEmpty())
counter++;
}
bufLift= degree (A, y) + 1 + degree (LC(A, x), y);
TIMING_START (fac_bi_factorizer);
bufBiFactors= ratBiSqrfFactorize (bufAeval.getFirst(), v);
TIMING_END_AND_PRINT (fac_bi_factorizer,
"time for bivariate factorization: ");
bufBiFactors.removeFirst();
if (bufBiFactors.length() == 1)
{
factors.append (A);
appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
if (isOn (SW_RATIONAL))
normalize (factors);
delete [] bufAeval2;
delete [] Aeval2;
return factors;
}
if (i == 0)
{
Aeval= bufAeval;
evaluation= bufEvaluation;
biFactors= bufBiFactors;
lift= bufLift;
for (int j= 0; j < lengthAeval2; j++)
Aeval2 [j]= bufAeval2 [j];
differentSecondVar= counter;
}
else
{
if (bufBiFactors.length() < biFactors.length() ||
((bufLift < lift) && (bufBiFactors.length() == biFactors.length())) ||
counter > differentSecondVar)
{
Aeval= bufAeval;
evaluation= bufEvaluation;
biFactors= bufBiFactors;
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;
sortList (biFactors, x);
int minFactorsLength;
bool irred= false;
TIMING_START (fac_bi_factorizer);
factorizationWRTDifferentSecondVars (A, Aeval2, minFactorsLength, irred, v);
TIMING_END_AND_PRINT (fac_bi_factorizer,
"time for bivariate factorization wrt diff second vars over Q: ");
TIMING_END_AND_PRINT (fac_bifactor_total,
"total time for eval and bivar factors over Q: ");
if (irred)
{
factors.append (A);
appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
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 (A);
appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
if (isOn (SW_RATIONAL))
normalize (factors);
delete [] Aeval2;
return factors;
}
if (differentSecondVar == lengthAeval2)
{
bool zeroOccured= false;
for (CFListIterator iter= evaluation; iter.hasItem(); iter++)
{
if (iter.getItem().isZero())
{
zeroOccured= true;
break;
}
}
if (!zeroOccured)
{
factors= sparseHeuristic (A, biFactors, Aeval2, evaluation,
minFactorsLength);
if (factors.length() == biFactors.length())
{
appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
normalize (factors);
delete [] Aeval2;
return factors;
}
else
factors= 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 (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];
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(fac_precompute_leadcoeff,
"time to precompute LC over Q: ");
TIMING_START (fac_luckswang);
CFList bufFactors= CFList();
bool LCheuristic= false;
if (LucksWangSparseHeuristic (A, biFactors, 2, leadingCoeffs2[lengthAeval2-1],
factors))
{
int check= biFactors.length();
int * index= new int [factors.length()];
CFList oldFactors= factors;
factors= recoverFactors (A, factors, index);
if (check == factors.length())
{
if (w.level() != 1)
{
for (iter= factors; iter.hasItem(); iter++)
iter.getItem()= swapvar (iter.getItem(), w, y);
}
appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
normalize (factors);
delete [] index;
delete [] Aeval2;
TIMING_END_AND_PRINT (fac_luckswang,
"time for successful LucksWang over Q: ");
return factors;
}
else if (factors.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= factors;
factors= CFList();
}
else if (!LCmultiplierIsConst && factors.length() == 0)
{
LCheuristic= true;
factors= oldFactors;
CFList contents, LCs;
bool foundTrueMultiplier= false;
LCHeuristic2 (LCmultiplier, factors, 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, factors, oldBiFactors, contents, oldAeval,
A, leadingCoeffs2, lengthAeval2, foundMultiplier);
// coming from above: divide out more LCmultiplier if possible
if (foundMultiplier)
{
foundMultiplier= false;
LCHeuristic4 (oldBiFactors, oldAeval, contents, factors, 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);
}
factors= CFList();
if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
{
LCheuristic= false;
A= bufA;
biFactors= bufBiFactors;
leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
LCmultiplier= bufLCmultiplier;
}
}
else
factors= CFList();
delete [] index;
}
TIMING_END_AND_PRINT (fac_luckswang, "time for LucksWang over Q: ");
TIMING_START (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 (fac_lcheuristic, "time for Lc heuristic over Q: ");
tryAgainWithoutHeu:
//shifting to zero
TIMING_START (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 (fac_shift_to_zero,
"time to shift evaluation point to zero: ");
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 (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 (fac_cleardenom, "time to clear denominators: ");
TIMING_START (fac_hensel_lift);
factors= nonMonicHenselLift (Aeval, biFactors, leadingCoeffs2, diophant,
Pi, liftBounds, liftBoundsLength, noOneToOne);
TIMING_END_AND_PRINT (fac_hensel_lift,
"time for non monic hensel lifting over Q: ");
if (!noOneToOne)
{
int check= factors.length();
A= oldA;
TIMING_START (fac_recover_factors);
factors= recoverFactors (A, factors, evaluation);
TIMING_END_AND_PRINT (fac_recover_factors,
"time to recover factors over Q: ");
if (check != factors.length())
noOneToOne= true;
else
factors= Union (factors, 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 (fac_hensel_lift);
liftedFactors= henselLiftAndEarly
(A, MOD, liftBounds, earlySuccess, earlyFactors,
Aeval, biFactors, evaluation, info);
TIMING_END_AND_PRINT (fac_hensel_lift, "time for hensel lifting: ");
TIMING_START (fac_factor_recombination);
factors= factorRecombination (A, liftedFactors, MOD);
TIMING_END_AND_PRINT (fac_factor_recombination,
"time for factor recombination: ");
if (earlySuccess)
factors= Union (factors, earlyFactors);
for (CFListIterator i= factors; 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= factors; iter.hasItem(); iter++)
iter.getItem()= swapvar (iter.getItem(), w, y);
}
append (factors, contentAFactors);
decompress (factors, N);
if (isOn (SW_RATIONAL))
normalize (factors);
delete [] leadingCoeffs2;
delete [] oldAeval;
delete [] Aeval2;
delete[] liftBounds;
return factors;
}
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
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
CFList
List< CanonicalForm > CFList
Definition canonicalform.h:395
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
i
int i
Definition cfEzgcd.cc:132
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
bCommonDen
CanonicalForm bCommonDen(const CanonicalForm &f)
void psqr ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & q, CanonicalForm & r,...
Definition cf_algorithm.cc:293
fdivides
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
factorize
CFFList FACTORY_PUBLIC factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition cf_factor.cc:409
SW_RATIONAL
static const int SW_RATIONAL
set to 1 for computations over Q
Definition cf_defs.h:31
CFMap
class CFMap
Definition cf_map.h:85
CanonicalForm
factory's main class
Definition canonicalform.h:86
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
iter
CFFListIterator iter
Definition facAbsBiFact.cc:54
result
return result
Definition facAbsBiFact.cc:76
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))
w
const CanonicalForm & w
Definition facAbsFact.cc:51
append
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
Definition facAlgFuncUtil.cc:32
conv
CFList conv(const CFFList &L)
convert a CFFList to a CFList by dropping the multiplicity
Definition facBivar.cc:126
ratBiSqrfFactorize
CFList ratBiSqrfFactorize(const CanonicalForm &G, const Variable &v=Variable(1))
factorize a squarefree bivariate polynomial over .
Definition facBivar.h:47
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition facBivar.h:39
E
CFList Evaluation & E
Definition facFactorize.cc:48
multiFactorize
CFList multiFactorize(const CanonicalForm &F, const Variable &v)
Factorization over Q (a).
Definition facFactorize.cc:198
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
appendSwapDecompress
void appendSwapDecompress(CFList &factors1, const CFList &factors2, const CFList &factors3, const bool swap1, const bool swap2, const CFMap &N)
first swap Variables in factors1 if necessary, then append factors2 and factors3 on factors1 and fina...
Definition facFqBivarUtil.cc:70
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
lcmContent
CanonicalForm lcmContent(const CanonicalForm &A, CFList &contentAi)
compute the LCM of the contents of A wrt to each variable occuring in A.
Definition facFqFactorize.cc:966
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
evalPoints
CFList evalPoints(const CanonicalForm &F, CFList &eval, const Variable &alpha, CFList &list, const bool &GF, bool &fail)
evaluation point search for multivariate factorization, looks for a (F.level() - 1)-tuple such that t...
Definition facFqFactorize.cc:751
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
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 &)
Union
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
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
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
buf
int status int void * buf
Definition si_signals.h:69
A
#define A
Definition sirandom.c:24
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
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

## ratFactorize()

CFFList ratFactorize | ( | const CanonicalForm & | G,
|  | const Variable & | v = Variable (1),
|  | bool | substCheck = true )

inline

factorize a multivariate polynomial over

Returns
  ratFactorize returns a list of monic factors with multiplicity, the first element is the leading coefficient.

Parameters

  [in] | G | a multivariate poly
  [in] | v | algebraic variable
  [in] | substCheck | enables substitute check

Definition at line 79 of file facFactorize.h.

{
if (getNumVars (G) == 2)
{
CFFList result= ratBiFactorize (G,v);
return result;
}
CanonicalForm F= G;
if (substCheck)
{
bool foundOne= false;
int * substDegree= new int [F.level()];
for (int i= 1; i <= F.level(); i++)
{
if (degree (F, i) > 0)
{
substDegree[i-1]= substituteCheck (F, Variable (i));
if (substDegree [i-1] > 1)
{
foundOne= true;
subst (F, F, substDegree[i-1], Variable (i));
}
}
else
substDegree[i-1]= -1;
}
if (foundOne)
{
CFFList result= ratFactorize (F, v, false);
CFFList newResult, tmp;
CanonicalForm tmp2;
newResult.insert (result.getFirst());
result.removeFirst();
for (CFFListIterator i= result; i.hasItem(); i++)
{
tmp2= i.getItem().factor();
for (int j= 1; j <= G.level(); j++)
{
if (substDegree[j-1] > 1)
tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
}
tmp= ratFactorize (tmp2, v, false);
tmp.removeFirst();
for (CFFListIterator j= tmp; j.hasItem(); j++)
newResult.append (CFFactor (j.getItem().factor(),
j.getItem().exp()*i.getItem().exp()));
}
delete [] substDegree;
return newResult;
}
delete [] substDegree;
}
CanonicalForm LcF= Lc (F);
if (isOn (SW_RATIONAL))
F *= bCommonDen (F);
CFFList result;
TIMING_START (fac_squarefree);
CFFList sqrfFactors= sqrFree (F);
TIMING_END_AND_PRINT (fac_squarefree,
"time for squarefree factorization over Q: ");
CFList tmp;
for (CFFListIterator i= sqrfFactors; i.hasItem(); i++)
{
TIMING_START (fac_factor_squarefree);
tmp= ratSqrfFactorize (i.getItem().factor(), v);
TIMING_END_AND_PRINT (fac_factor_squarefree,
"time to factorize sqrfree factor over Q: ");
for (CFListIterator j= tmp; j.hasItem(); j++)
{
if (j.getItem().inCoeffDomain()) continue;
result.append (CFFactor (j.getItem(), i.getItem().exp()));
}
}
if (isOn (SW_RATIONAL))
{
normalize (result);
if (v.level() == 1)
{
for (CFFListIterator i= result; i.hasItem(); i++)
{
LcF /= power (bCommonDen (i.getItem().factor()), i.getItem().exp());
i.getItem()= CFFactor (i.getItem().factor()*
bCommonDen(i.getItem().factor()), i.getItem().exp());
}
}
result.insert (CFFactor (LcF, 1));
}
return result;
}
getNumVars
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition cf_ops.cc:314
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
CFFactor
Factor< CanonicalForm > CFFactor
Definition canonicalform.h:392
sqrFree
CFFList FACTORY_PUBLIC sqrFree(const CanonicalForm &f, bool sort=false)
squarefree factorization
Definition cf_factor.cc:961
List::insert
void insert(const T &)
Definition ftmpl_list.cc:193
LcF
CanonicalForm LcF
Definition facAbsBiFact.cc:51
subst
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
Definition facAlgFuncUtil.cc:120
ratBiFactorize
CFFList ratBiFactorize(const CanonicalForm &G, const Variable &v=Variable(1), bool substCheck=true)
factorize a bivariate polynomial over
Definition facBivar.h:129
ratFactorize
CFFList ratFactorize(const CanonicalForm &G, const Variable &v=Variable(1), bool substCheck=true)
factorize a multivariate polynomial over
Definition facFactorize.h:79
ratSqrfFactorize
CFList ratSqrfFactorize(const CanonicalForm &G, const Variable &v=Variable(1))
factorize a squarefree multivariate polynomial over
Definition facFactorize.h:53
reverseSubst
CanonicalForm reverseSubst(const CanonicalForm &F, const int d, const Variable &x)
reverse a substitution x^d->x
Definition facFqBivarUtil.cc:1295
substituteCheck
int substituteCheck(const CanonicalForm &F, const Variable &x)
check if a substitution x^n->x is possible
Definition facFqBivarUtil.cc:1089
G
STATIC_VAR TreeM * G
Definition janet.cc:31

## ratSqrfFactorize()

CFList ratSqrfFactorize | ( | const CanonicalForm & | G,
|  | const Variable & | v = Variable (1) )

inline

factorize a squarefree multivariate polynomial over

Returns
  ratSqrfFactorize returns a list of monic factors, the first element is the leading coefficient.

Parameters

  [in] | G | a multivariate poly
  [in] | v | algebraic variable

Definition at line 53 of file facFactorize.h.

{
if (getNumVars (G) == 2)
return ratBiSqrfFactorize (G, v);
CanonicalForm F= G;
if (isOn (SW_RATIONAL))
F *= bCommonDen (F);
CFList result= multiFactorize (F, v);
if (isOn (SW_RATIONAL))
{
normalize (result);
result.insert (Lc(F));
}
return result;
}
multiFactorize
CFList multiFactorize(const CanonicalForm &F, const Variable &v)
Factorization over Q (a).
Definition facFactorize.cc:198

## TIMING_DEFINE_PRINT()

TIMING_DEFINE_PRINT | ( | fac_squarefree |  | ) | const &

Factorization of A wrt. to different second vars.

## Variable Documentation

## Aeval

CFList*& Aeval

<[in] poly

[in,out] A evaluated wrt. different second vars returns bivariate factors

Definition at line 29 of file facFactorize.h.

## irred

CFList int bool& irred

[in,out] Is A irreducible?

Definition at line 34 of file facFactorize.h.

## minFactorsLength

CFList int& minFactorsLength

[in,out] minimal length of bivariate factors

Definition at line 32 of file facFactorize.h.

## w

CFList int bool const Variable& w

<[in] alg. variable

Definition at line 35 of file facFactorize.h.