Loading...
Searching...
No Matches
facFqFactorize.h
Go to the documentation of this file.
/*****************************************************************************\
* Computer Algebra System SINGULAR
\*****************************************************************************/
/** @file facFqFactorize.h
*
* This file provides functions for factorizing a multivariate polynomial over
* \f$ F_{p} \f$ , \f$ F_{p}(\alpha ) \f$ or GF.
*
* @author Martin Lee
*
**/
/*****************************************************************************/
#ifndef FAC_FQ_FACTORIZE_H
#define FAC_FQ_FACTORIZE_H
// #include "config.h"
#include "timing.h"
#include "facFqBivar.h"
#include "DegreePattern.h"
#include "ExtensionInfo.h"
#include "cf_util.h"
#include "facFqSquarefree.h"
#include "facFqBivarUtil.h"
TIMING_DEFINE_PRINT (fac_fq_squarefree)
TIMING_DEFINE_PRINT (fac_fq_factor_squarefree)
/// Factorization over a finite field
///
/// @return @a multiFactorize returns a factorization of F
/// @sa biFactorize(), extFactorize()
CFList
multiFactorize (const CanonicalForm& F, ///< [in] sqrfree poly
const ExtensionInfo& info ///< [in] info about extension
);
/// factorize a squarefree multivariate polynomial over \f$ F_{p} \f$
///
/// @return @a FpSqrfFactorize returns a list of monic factors, the first
/// element is the leading coefficient.
/// @sa FqSqrfFactorize(), GFSqrfFactorize()
#ifdef HAVE_NTL
inline
CFList FpSqrfFactorize (const CanonicalForm & F ///< [in] a multivariate poly
)
{
if (getNumVars (F) == 2)
return FpBiSqrfFactorize (F);
ExtensionInfo info= ExtensionInfo (false);
CFList result= multiFactorize (F, info);
result.insert (Lc(F));
return result;
}
/// factorize a squarefree multivariate polynomial over \f$ F_{p} (\alpha ) \f$
///
/// @return @a FqSqrfFactorize returns a list of monic factors, the first
/// element is the leading coefficient.
/// @sa FpSqrfFactorize(), GFSqrfFactorize()
inline
CFList FqSqrfFactorize (const CanonicalForm & F, ///< [in] a multivariate poly
const Variable& alpha ///< [in] algebraic variable
)
{
if (getNumVars (F) == 2)
return FqBiSqrfFactorize (F, alpha);
ExtensionInfo info= ExtensionInfo (alpha, false);
CFList result= multiFactorize (F, info);
result.insert (Lc(F));
return result;
}
/// factorize a squarefree multivariate polynomial over GF
///
/// @return @a GFSqrfFactorize returns a list of monic factors, the first
/// element is the leading coefficient.
/// @sa FpSqrfFactorize(), FqSqrfFactorize()
inline
CFList GFSqrfFactorize (const CanonicalForm & F ///< [in] a multivariate poly
)
{
ASSERT (CFFactory::gettype() == GaloisFieldDomain,
"GF as base field expected");
if (getNumVars (F) == 2)
return GFBiSqrfFactorize (F);
ExtensionInfo info= ExtensionInfo (getGFDegree(), gf_name, false);
CFList result= multiFactorize (F, info);
result.insert (Lc(F));
return result;
}
/// factorize a multivariate polynomial over \f$ F_{p} \f$
///
/// @return @a FpFactorize returns a list of monic factors with
/// multiplicity, the first element is the leading coefficient.
/// @sa FqFactorize(), GFFactorize()
inline
CFFList FpFactorize (const CanonicalForm& G,///< [in] a multivariate poly
bool substCheck= true ///< [in] enables substitute check
)
{
if (getNumVars (G) == 2)
return FpBiFactorize (G, substCheck);
CanonicalForm F= G;
if (substCheck)
{
bool foundOne= false;
int * substDegree= NEW_ARRAY(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= FpFactorize (F, 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= FpFactorize (tmp2, false);
tmp.removeFirst();
for (CFFListIterator j= tmp; j.hasItem(); j++)
newResult.append (CFFactor (j.getItem().factor(),
j.getItem().exp()*i.getItem().exp()));
}
DELETE_ARRAY(substDegree);
return newResult;
}
DELETE_ARRAY(substDegree);
}
ExtensionInfo info= ExtensionInfo (false);
Variable a= Variable (1);
CanonicalForm LcF= Lc (F);
TIMING_START (fac_fq_squarefree);
CFFList sqrf= FpSqrf (F, false);
TIMING_END_AND_PRINT (fac_fq_squarefree,
"time for squarefree factorization over Fq: ");
CFFList result;
CFList bufResult;
sqrf.removeFirst();
CFListIterator i;
for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
{
TIMING_START (fac_fq_factor_squarefree);
bufResult= multiFactorize (iter.getItem().factor(), info);
TIMING_END_AND_PRINT (fac_fq_factor_squarefree,
"time to factorize sqrfree factor over Fq: ");
for (i= bufResult; i.hasItem(); i++)
result.append (CFFactor (i.getItem(), iter.getItem().exp()));
}
result.insert (CFFactor (LcF, 1));
return result;
}
/// factorize a multivariate polynomial over \f$ F_{p} (\alpha ) \f$
///
/// @return @a FqFactorize returns a list of monic factors with
/// multiplicity, the first element is the leading coefficient.
/// @sa FpFactorize(), GFFactorize()
inline
CFFList FqFactorize (const CanonicalForm& G, ///< [in] a multivariate poly
const Variable& alpha, ///< [in] algebraic variable
bool substCheck= true ///< [in] enables substitute check
)
{
if (getNumVars (G) == 2)
return FqBiFactorize (G, alpha, substCheck);
CanonicalForm F= G;
if (substCheck)
{
bool foundOne= false;
int * substDegree= NEW_ARRAY(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= FqFactorize (F, alpha, 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= FqFactorize (tmp2, alpha, false);
tmp.removeFirst();
for (CFFListIterator j= tmp; j.hasItem(); j++)
newResult.append (CFFactor (j.getItem().factor(),
j.getItem().exp()*i.getItem().exp()));
}
DELETE_ARRAY(substDegree);
return newResult;
}
DELETE_ARRAY(substDegree);
}
ExtensionInfo info= ExtensionInfo (alpha, false);
CanonicalForm LcF= Lc (F);
TIMING_START (fac_fq_squarefree);
CFFList sqrf= FqSqrf (F, alpha, false);
TIMING_END_AND_PRINT (fac_fq_squarefree,
"time for squarefree factorization over Fq: ");
CFFList result;
CFList bufResult;
sqrf.removeFirst();
CFListIterator i;
for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
{
TIMING_START (fac_fq_factor_squarefree);
bufResult= multiFactorize (iter.getItem().factor(), info);
TIMING_END_AND_PRINT (fac_fq_factor_squarefree,
"time to factorize sqrfree factor over Fq: ");
for (i= bufResult; i.hasItem(); i++)
result.append (CFFactor (i.getItem(), iter.getItem().exp()));
}
result.insert (CFFactor (LcF, 1));
return result;
}
/// factorize a multivariate polynomial over GF
///
/// @return @a GFFactorize returns a list of monic factors with
/// multiplicity, the first element is the leading coefficient.
/// @sa FpFactorize(), FqFactorize()
inline
CFFList GFFactorize (const CanonicalForm& G, ///< [in] a multivariate poly
bool substCheck= true ///< [in] enables substitute check
)
{
ASSERT (CFFactory::gettype() == GaloisFieldDomain,
"GF as base field expected");
if (getNumVars (G) == 2)
return GFBiFactorize (G, substCheck);
CanonicalForm F= G;
if (substCheck)
{
bool foundOne= false;
int * substDegree= NEW_ARRAY(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= GFFactorize (F, 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= GFFactorize (tmp2, false);
tmp.removeFirst();
for (CFFListIterator j= tmp; j.hasItem(); j++)
newResult.append (CFFactor (j.getItem().factor(),
j.getItem().exp()*i.getItem().exp()));
}
DELETE_ARRAY(substDegree);
return newResult;
}
DELETE_ARRAY(substDegree);
}
Variable a= Variable (1);
ExtensionInfo info= ExtensionInfo (getGFDegree(), gf_name, false);
CanonicalForm LcF= Lc (F);
CFFList sqrf= GFSqrf (F, false);
CFFList result;
CFList bufResult;
sqrf.removeFirst();
CFListIterator i;
for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
{
bufResult= multiFactorize (iter.getItem().factor(), info);
for (i= bufResult; i.hasItem(); i++)
result.append (CFFactor (i.getItem(), iter.getItem().exp()));
}
result.insert (CFFactor (LcF, 1));
return result;
}
#endif
/// Naive factor recombination for multivariate factorization over an extension
/// of the initial field. No precomputed is used to exclude combinations.
///
/// @return @a extFactorRecombination returns a list of factors of @a F, whose
/// shift to zero is reversed.
/// @sa factorRecombination()
CFList
extFactorRecombination (
const CFList& factors, ///< [in] list of lifted factors
///< that are monic wrt Variable (1)
const CanonicalForm& F, ///< [in] poly to be factored
const CFList& M, ///< [in] a list of powers of
///< Variables
const ExtensionInfo& info, ///< [in] info about extension
const CFList& evaluation ///< [in] evaluation point
);
/// Naive factor recombination for multivariate factorization.
/// No precomputed is used to exclude combinations.
///
/// @return @a factorRecombination returns a list of factors of @a F
/// @sa extFactorRecombination()
CFList
factorRecombination (const CanonicalForm& F,///< [in] poly to be factored
const CFList& factors, ///< [in] list of lifted factors
///< that are monic wrt Variable (1)
const CFList& M ///< [in] a list of powers of
///< Variables
);
/// recombination of bivariate factors @a factors1 s. t. the result evaluated
/// at @a evalPoint coincides with @a factors2
CFList
recombination (const CFList& factors1, ///<[in] list of bivariate factors
const CFList& factors2, ///<[in] list univariate factors
int s, ///<[in] algorithm starts checking
///< subsets of size s
int thres, ///<[in] threshold for the size of
///< subsets which are checked
const CanonicalForm& evalPoint,///<[in] evaluation point
const Variable& x ///<[in] second variable of
///< bivariate factors
);
/// Lift bound adaption. Essentially an early factor detection but only the lift
/// bound is adapted.
///
/// @return @a liftBoundAdaption returns an adapted lift bound.
/// @sa earlyFactorDetect(), earlyFactorDetection()
int
liftBoundAdaption (const CanonicalForm& F, ///< [in] a poly
const CFList& factors, ///< [in] list of list of lifted
///< factors that are monic wrt
///< Variable (1)
bool& success, ///< [in,out] indicates that no
///< further lifting is necessary
const int deg, ///< [in] stage of Hensel lifting
const CFList& MOD, ///< [in] a list of powers of
///< Variables
const int bound ///< [in] initial lift bound
);
/// Lift bound adaption over an extension of the initial field. Essentially an
///early factor detection but only the lift bound is adapted.
///
/// @return @a liftBoundAdaption returns an adapted lift bound.
/// @sa earlyFactorDetect(), earlyFactorDetection()
int
extLiftBoundAdaption (
const CanonicalForm& F, ///< [in] a poly
const CFList& factors, ///< [in] list of list of lifted
///< factors that are monic wrt
bool& success, ///< [in,out] indicates that no further
///< lifting is necessary
const ExtensionInfo& info, ///< [in] info about extension
const CFList& eval, ///< [in] evaluation point
const int deg, ///< [in] stage of Hensel lifting
const CFList& MOD, ///< [in] a list of powers of
///< Variables
const int bound ///< [in] initial lift bound
);
/// detects factors of @a F at stage @a deg of Hensel lifting.
/// No combinations of more than one factor are tested. Lift bound is adapted.
///
/// @return @a earlyFactorDetect returns a list of factors of F (possibly
/// incomplete), in case of success. Otherwise an empty list.
/// @sa factorRecombination(), extEarlyFactorDetect()
CFList
earlyFactorDetect (
CanonicalForm& F, ///< [in,out] poly to be factored,
///< returns poly divided by detected
///< factors in case of success
CFList& factors, ///< [in,out] list of factors lifted up
///< to @a deg, returns a list of factors
///< without detected factors
int& adaptedLiftBound, ///< [in,out] adapted lift bound
bool& success, ///< [in,out] indicating success
const int deg, ///< [in] stage of Hensel lifting
const CFList& MOD, ///< [in] a list of powers of
///< Variables
const int bound ///< [in] initial lift bound
);
/// detects factors of @a F at stage @a deg of Hensel lifting.
/// No combinations of more than one factor are tested. Lift bound is adapted.
///
/// @return @a extEarlyFactorDetect returns a list of factors of F (possibly
/// incomplete), whose shift to zero is reversed, in case of success.
/// Otherwise an empty list.
/// @sa factorRecombination(), earlyFactorDetection()
CFList
extEarlyFactorDetect (
CanonicalForm& F, ///< [in,out] poly to be factored,
///< returns poly divided by detected
///< factors in case of success
CFList& factors, ///< [in,out] list of factors lifted up
///< to @a deg, returns a list of factors
///< without detected factors
int& adaptedLiftBound, ///< [in,out] adapted lift bound
bool& success, ///< [in,out] indicating succes
const ExtensionInfo& info, ///< [in] info about extension
const CFList& eval, ///< [in] evaluation point
const int deg, ///< [in] stage of Hensel lifting
const CFList& MOD, ///< [in] a list of powers of Variables
const int bound ///< [in] initial lift bound
);
/// evaluation point search for multivariate factorization,
/// looks for a (F.level() - 1)-tuple such that the resulting univariate
/// polynomial has main variable Variable (1), is squarefree and its degree
/// coincides with degree(F) and the bivariate one is primitive wrt.
/// Variable(1), and successively evaluated polynomials have the same degree in
/// their main variable as F has, fails if there are no valid evaluation points,
/// eval contains the intermediate evaluated polynomials.
///
/// @return @a evalPoints returns an evaluation point, which is valid if and
/// only if fail == false.
CFList
evalPoints (const CanonicalForm& F, ///< [in] a compressed poly
CFList & eval, ///< [in,out] an empty list, returns @a F
///< successive evaluated
const Variable& alpha, ///< [in] algebraic variable
CFList& list, ///< [in,out] a list of points already
///< considered, a point is encoded as a
///< poly of degree F.level()-1 in
///< Variable(1)
const bool& GF, ///< [in] GF?
bool& fail ///< [in,out] indicates failure
);
/// hensel Lifting and early factor detection
///
/// @return @a henselLiftAndEarly returns monic (wrt Variable (1)) lifted
/// factors without factors which have been detected at an early stage
/// of Hensel lifting
/// @sa earlyFactorDetectn(), extEarlyFactorDetect()
CFList
henselLiftAndEarly (
CanonicalForm& A, ///< [in,out] poly to be factored,
///< returns poly divided by detected
///< factors, in case of success
CFList& MOD, ///< [in,out] a list of powers of
///< Variables
int*& liftBounds, ///< [in,out] initial lift bounds, returns
///< adapted lift bounds
bool& earlySuccess, ///< [in,out] indicating success
CFList& earlyFactors, ///< [in,out] early factors
const CFList& Aeval, ///< [in] @a A successively evaluated at
///< elements of @a evaluation
const CFList& biFactors, ///< [in] bivariate factors
const CFList& evaluation, ///< [in] evaluation point
const ExtensionInfo& info ///< [in] info about extension
);
/// Factorization over an extension of initial field
///
/// @return @a extFactorize returns factorization of F over initial field
/// @sa extBiFactorize(), multiFactorize()
CFList
extFactorize (const CanonicalForm& F, ///< [in] poly to be factored
const ExtensionInfo& info ///< [in] info about extension
);
/// compute the LCM of the contents of @a A wrt to each variable occuring in @a
/// A.
///
/// @return @a lcmContent returns the LCM of the contents of @a A wrt to each
/// variable occuring in @a A.
CanonicalForm
lcmContent (const CanonicalForm& A, ///< [in] a compressed multivariate poly
CFList& contentAi ///< [in,out] an empty list, returns a list
///< of the contents of @a A wrt to each
///< variable occuring in @a A starting from
///< @a A.mvar().
);
/// compress a polynomial s.t. \f$ deg_{x_{i}} (F) >= deg_{x_{i+1}} (F) \f$ and
/// no gaps between the variables occur
///
/// @return a compressed poly with the above properties
CanonicalForm myCompress (const CanonicalForm& F, ///< [in] a poly
CFMap& N ///< [in,out] a map to
///< decompress
);
/// evaluate a poly A with main variable at level 1 at an evaluation point in
/// K^(n-1) wrt different second variables. If this evaluation is valid (see
/// evalPoints) then Aeval contains A successively evaluated at this point,
/// otherwise this entry is empty
void
evaluationWRTDifferentSecondVars (
CFList*& Aeval, ///<[in,out] an array of length n-2
///< if variable at level i > 2
///< admits a valid evaluation
///< this entry contains A
///< successively evaluated at this
///< point otherwise an empty list
const CFList& evaluation,///<[in] a valid evaluation point
///< for main variable at level 1
///< and second variable at level 2
const CanonicalForm& A ///<[in] some poly
);
/// refine a bivariate factorization of A with l factors to one with
/// minFactorsLength if possible
void
refineBiFactors (const CanonicalForm& A, ///< [in] some poly
CFList& biFactors, ///< [in,out] list of bivariate to be
///< refined, returns refined factors
CFList* const& factors, ///< [in] list of bivariate
///< factorizations of A wrt different
///< second variables
const CFList& evaluation,///< [in] the evaluation point
int minFactorsLength ///< [in] the minimal number of factors
);
/// plug in evalPoint for y in a list of polys
///
/// @return returns a list of the evaluated polys, these evaluated polys are
/// made monic
CFList
buildUniFactors (const CFList& biFactors, ///< [in] a list of polys
const CanonicalForm& evalPoint,///< [in] some evaluation point
const Variable& y ///< [in] some variable
);
/// sort bivariate factors in Aeval such that their corresponding univariate
/// factors coincide with uniFactors, uniFactors and biFactors may get
/// recombined if necessary
void sortByUniFactors (CFList*& Aeval, ///< [in,out] array of bivariate
///< factors
int AevalLength, ///< [in] length of Aeval
CFList& uniFactors, ///< [in,out] univariate factors
CFList& biFactors, ///< [in,out] bivariate factors
const CFList& evaluation ///< [in] evaluation point
);
/// extract leading coefficients wrt Variable(1) from bivariate factors obtained
/// from factorizations of A wrt different second variables
void
getLeadingCoeffs (const CanonicalForm& A, ///< [in] some poly
CFList*& Aeval ///< [in,out] array of bivariate
///< factors, returns the leading
///< coefficients of these factors
);
/// normalize precomputed leading coefficients such that leading coefficients
/// evaluated at @a evaluation in K^(n-2) equal the leading coeffs wrt
/// Variable(1) of bivariate factors and change @a A and @a Aeval accordingly
void
prepareLeadingCoeffs (CFList*& LCs, ///<[in,out]
CanonicalForm& A, ///<[in,out]
CFList& Aeval, ///<[in,out]
int n, ///<[in] level of poly to be
///< factored
const CFList& leadingCoeffs,///<[in] precomputed leading
///< coeffs
const CFList& biFactors, ///<[in] bivariate factors
const CFList& evaluation ///<[in] evaluation point
);
/// obtain factors of F by reconstructing their leading coeffs
///
/// @return returns the reconstructed factors
/// @sa factorRecombination()
CFList
leadingCoeffReconstruction (const CanonicalForm& F,///<[in] poly to be factored
const CFList& factors, ///<[in] factors of f monic
///< wrt Variable (1)
const CFList& M ///<[in] a list of powers of
///< Variables
);
/// distribute content
///
/// @return returns a list result of polys such that prod (result)= prod (L)
/// but the first entry of L may be (partially) factorized and these factors
/// are distributed onto other entries in L
CFList
distributeContent (
const CFList& L, ///<[in] list of polys, first
///< entry the content to be
///< distributed
const CFList* differentSecondVarFactors,///<[in] factorization wrt
///< different second vars
int length ///<[in] length of
///<differentSecondVarFactors
);
/// gcd free basis of two lists of factors
void
gcdFreeBasis (CFFList& factors1, ///< [in,out] list of factors, returns gcd free
///< factors
CFFList& factors2 ///< [in,out] list of factors, returns gcd free
///< factors
);
/// computes a list l of length length(LCFFactors)+1 of polynomials such that
/// prod (l)=LCF, note that the first entry of l may be non constant. Intended
/// to be used to precompute coefficients of a polynomial f from its bivariate
/// factorizations.
///
/// @return see above
CFList
precomputeLeadingCoeff (const CanonicalForm& LCF, ///<[in] a multivariate
///< poly
const CFList& LCFFactors, ///<[in] a list of
///< univariate factors
///< of LCF of level 2
const Variable& alpha, ///<[in] algebraic var.
const CFList& evaluation, ///<[in] an evaluation
///< point having
///< lSecondVarLCs+1
///< components
CFList* & differentSecondVarLCs,///<[in] LCs of factors
///< of f wrt different
///< second variables
int lSecondVarLCs, ///<[in] length of the
///< above
Variable& y ///<[in,out] if y.level()
///< is not 1 on output
///< the second variable
///< has been changed to
///< y
);
/// changes the second variable to be @a w and updates all relevant data
void
changeSecondVariable (CanonicalForm& A, ///<[in,out] a multivariate poly
CFList& biFactors, ///<[in,out] bivariate factors
CFList& evaluation, ///<[in,out] evaluation point
CFList*& oldAeval, ///<[in,out] old bivariate factors
///< wrt. different second vars
int lengthAeval2, ///<[in] length of oldAeval
const CFList& uniFactors,///<[in] univariate factors
const Variable& w ///<[in] some variable
);
/// distributes a divisor LCmultiplier of LC(A,1) on the bivariate factors and
/// the precomputed leading coefficients
void
distributeLCmultiplier (CanonicalForm& A, ///<[in,out] some poly
CFList& leadingCoeffs, ///<[in,out] leading
///< coefficients
CFList& biFactors, ///<[in,out] bivariate
///< factors
const CFList& evaluation, ///<[in] eval. point
const CanonicalForm& LCmultipler///<[in] multiplier
);
/// heuristic to distribute @a LCmultiplier onto factors based on the variables
/// that occur in @a LCmultiplier and in the leading coeffs of bivariate factors
void
LCHeuristic (CanonicalForm& A, ///<[in,out] a poly
const CanonicalForm& LCmultiplier,///<[in,out] divisor of LC (A,1)
CFList& biFactors, ///<[in,out] bivariate factors
CFList*& leadingCoeffs, ///<[in,out] leading coeffs
const CFList* oldAeval, ///<[in] bivariate factors wrt.
///< different second vars
int lengthAeval, ///<[in] length of oldAeval
const CFList& evaluation, ///<[in] evaluation point
const CFList& oldBiFactors ///<[in] bivariate factors
///< without LCmultiplier
///< distributed on them
);
/// checks if prod(LCs)==LC (oldA,1) and if so divides elements of leadingCoeffs
/// by elements in contents, sets A to oldA and sets foundTrueMultiplier to true
void
LCHeuristicCheck (const CFList& LCs, ///<[in] leading coeffs computed
const CFList& contents, ///<[in] content of factors
CanonicalForm& A, ///<[in,out] oldA*LCmultiplier^m
const CanonicalForm& oldA,///<[in] some poly
CFList& leadingCoeffs, ///<[in,out] leading coefficients
bool& foundTrueMultiplier ///<[in,out] success?
);
/// heuristic to distribute @a LCmultiplier onto factors based on the contents
/// of @a factors. @a factors are assumed to come from LucksWangSparseHeuristic.
/// If not successful @a contents will contain the content of each element of @a
/// factors and @a LCs will contain the LC of each element of @a factors divided
/// by its content
void
LCHeuristic2 (const CanonicalForm& LCmultiplier,///<[in] divisor of LC (A,1)
const CFList& factors, ///<[in] result of
///< LucksWangSparseHeuristic
CFList& leadingCoeffs, ///<[in,out] leading coeffs
CFList& contents, ///<[in,out] content of factors
CFList& LCs, ///<[in,out] LC of factors
///< divided by content of
///< factors
bool& foundTrueMultiplier ///<[in,out] success?
);
/// heuristic to remove @a LCmultiplier from a factor based on the contents
/// of @a factors. @a factors are assumed to come from LucksWangSparseHeuristic.
void
LCHeuristic3 (const CanonicalForm& LCmultiplier,///<[in] divisor of LC (A,1)
const CFList& factors, ///<[in] result of
///< LucksWangSparseHeuristic
const CFList& oldBiFactors, ///<[in] bivariate factors
///< without LCmultiplier
///< distributed on them
const CFList& contents, ///<[in] content of factors
const CFList* oldAeval, ///<[in] bivariate factors wrt.
///< different second vars
CanonicalForm& A, ///<[in,out] poly
CFList*& leadingCoeffs, ///<[in,out] leading coeffs
int lengthAeval, ///<[in] length of oldAeval
bool& foundMultiplier ///<[in,out] success?
);
/// heuristic to remove factors of @a LCmultiplier from @a factors.
/// More precisely checks if elements of @a contents divide @a LCmultiplier.
/// Assumes LCHeuristic3 is run before it and was successful.
void
LCHeuristic4 (const CFList& oldBiFactors, ///<[in] bivariate factors
///< without LCmultiplier
///< distributed on them
const CFList* oldAeval, ///<[in] bivariate factors wrt.
///< different second vars
const CFList& contents, ///<[in] content of factors
const CFList& factors, ///<[in] result of
///< LucksWangSparseHeuristic
const CanonicalForm& testVars,///<[in] product of second vars that
///< occur among oldAeval
int lengthAeval, ///<[in] length of oldAeval
CFList*& leadingCoeffs, ///<[in,out] leading coeffs
CanonicalForm& A, ///<[in,out] poly
CanonicalForm& LCmultiplier, ///<[in,out] divisor of LC (A,1)
bool& foundMultiplier ///<[in] success?
);
#endif
/* FAC_FQ_FACTORIZE_H */
DegreePattern.h
This file provides a class to handle degree patterns.
ExtensionInfo.h
This file provides a class to store information about finite fields and extensions thereof.
getNumVars
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition cf_ops.cc:314
degree
int degree(const CanonicalForm &f)
Definition canonicalform.h:316
getGFDegree
int getGFDegree()
Definition cf_char.cc:75
CFFListIterator
ListIterator< CFFactor > CFFListIterator
Definition canonicalform.h:394
CFListIterator
ListIterator< CanonicalForm > CFListIterator
Definition canonicalform.h:396
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
CFList
List< CanonicalForm > CFList
Definition canonicalform.h:395
N
const CanonicalForm CFMap CFMap & N
Definition cfEzgcd.cc:56
i
int i
Definition cfEzgcd.cc:132
x
Variable x
Definition cfModGcd.cc:4090
evalPoint
static void evalPoint(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &FEval, CanonicalForm &GEval, CFGenerator &evalPoint)
Definition cfModResultant.cc:311
ASSERT
#define ASSERT(expression, message)
Definition cf_assert.h:99
DELETE_ARRAY
#define DELETE_ARRAY(P)
Definition cf_defs.h:65
NEW_ARRAY
#define NEW_ARRAY(T, N)
Definition cf_defs.h:64
GaloisFieldDomain
#define GaloisFieldDomain
Definition cf_defs.h:18
bound
static CanonicalForm bound(const CFMatrix &M)
Definition cf_linsys.cc:460
cf_util.h
CFFactory::gettype
static int gettype()
Definition cf_factory.h:28
CFMap
class CFMap
Definition cf_map.h:85
CanonicalForm
factory's main class
Definition canonicalform.h:86
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
List::removeFirst
void removeFirst()
Definition ftmpl_list.cc:287
List::append
void append(const T &)
Definition ftmpl_list.cc:256
List::insert
void insert(const T &)
Definition ftmpl_list.cc:193
Variable
factory's class for variables
Definition factory.h:127
iter
CFFListIterator iter
Definition facAbsBiFact.cc:54
alpha
Variable alpha
Definition facAbsBiFact.cc:52
LcF
CanonicalForm LcF
Definition facAbsBiFact.cc:51
result
return result
Definition facAbsBiFact.cc:76
evaluation
const CanonicalForm int const CFList & evaluation
Definition facAbsFact.cc:52
s
const CanonicalForm int s
Definition facAbsFact.cc:51
y
const CanonicalForm int const CFList const Variable & y
Definition facAbsFact.cc:53
w
const CanonicalForm & w
Definition facAbsFact.cc:51
subst
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
Definition facAlgFuncUtil.cc:120
LCF
CanonicalForm LCF
Definition facFactorize.cc:52
eval
CFList & eval
Definition facFactorize.cc:47
multiFactorize
CFList multiFactorize(const CanonicalForm &F, const Variable &v)
Factorization over Q (a).
Definition facFactorize.cc:198
minFactorsLength
CFList int & minFactorsLength
[in,out] minimal length of bivariate factors
Definition facFactorize.h:33
Aeval
CFList *& Aeval
<[in] poly
Definition facFactorize.h:31
factors2
const CFList & factors2
Definition facFqBivarUtil.cc:42
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
facFqBivarUtil.h
This file provides utility functions for bivariate factorization.
tmp2
CFList tmp2
Definition facFqBivar.cc:75
facFqBivar.h
This file provides functions for factorizing a bivariate polynomial over , or GF.
FqBiFactorize
CFFList FqBiFactorize(const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
factorize a bivariate polynomial over
Definition facFqBivar.h:317
FpBiFactorize
CFFList FpBiFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a bivariate polynomial over
Definition facFqBivar.h:190
GFBiFactorize
CFFList GFBiFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a bivariate polynomial over GF
Definition facFqBivar.h:446
FqBiSqrfFactorize
CFList FqBiSqrfFactorize(const CanonicalForm &G, const Variable &alpha)
factorize a squarefree bivariate polynomial over .
Definition facFqBivar.h:156
FpBiSqrfFactorize
CFList FpBiSqrfFactorize(const CanonicalForm &G)
factorize a squarefree bivariate polynomial over .
Definition facFqBivar.h:141
GFBiSqrfFactorize
CFList GFBiSqrfFactorize(const CanonicalForm &G)
factorize a squarefree bivariate polynomial over GF
Definition facFqBivar.h:172
FpSqrfFactorize
CFList FpSqrfFactorize(const CanonicalForm &F)
factorize a squarefree multivariate polynomial over
Definition facFqFactorize.h:47
factorRecombination
CFList factorRecombination(const CanonicalForm &F, const CFList &factors, const CFList &M)
Naive factor recombination for multivariate factorization. No precomputed is used to exclude combinat...
Definition facFqFactorize.cc:361
FpFactorize
CFFList FpFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a multivariate polynomial over
Definition facFqFactorize.h:101
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
liftBoundAdaption
int liftBoundAdaption(const CanonicalForm &F, const CFList &factors, bool &success, const int deg, const CFList &MOD, const int bound)
Lift bound adaption. Essentially an early factor detection but only the lift bound is adapted.
Definition facFqFactorize.cc:448
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
refineBiFactors
void refineBiFactors(const CanonicalForm &A, CFList &biFactors, CFList *const &factors, const CFList &evaluation, int minFactorsLength)
refine a bivariate factorization of A with l factors to one with minFactorsLength if possible
Definition facFqFactorize.cc:2335
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
extFactorRecombination
CFList extFactorRecombination(const CFList &factors, const CanonicalForm &F, const CFList &M, const ExtensionInfo &info, const CFList &evaluation)
Naive factor recombination for multivariate factorization over an extension of the initial field....
Definition facFqFactorize.cc:216
extEarlyFactorDetect
CFList extEarlyFactorDetect(CanonicalForm &F, CFList &factors, int &adaptedLiftBound, bool &success, const ExtensionInfo &info, const CFList &eval, const int deg, const CFList &MOD, const int bound)
detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are test...
Definition facFqFactorize.cc:665
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
myCompress
CanonicalForm myCompress(const CanonicalForm &F, CFMap &N)
compress a polynomial s.t. and no gaps between the variables occur
Definition facFqFactorize.cc:134
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
distributeContent
CFList distributeContent(const CFList &L, const CFList *differentSecondVarFactors, int length)
distribute content
Definition facFqFactorize.cc:1295
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
GFFactorize
CFFList GFFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a multivariate polynomial over GF
Definition facFqFactorize.h:267
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
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
gcdFreeBasis
void gcdFreeBasis(CFFList &factors1, CFFList &factors2)
gcd free basis of two lists of factors
Definition facFqFactorize.cc:1269
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
GFSqrfFactorize
CFList GFSqrfFactorize(const CanonicalForm &F)
factorize a squarefree multivariate polynomial over GF
Definition facFqFactorize.h:82
extFactorize
CFList extFactorize(const CanonicalForm &F, const ExtensionInfo &info)
Factorization over an extension of initial field.
Definition facFqFactorize.cc:3661
extLiftBoundAdaption
int extLiftBoundAdaption(const CanonicalForm &F, const CFList &factors, bool &success, const ExtensionInfo &info, const CFList &eval, const int deg, const CFList &MOD, const int bound)
Lift bound adaption over an extension of the initial field. Essentially an early factor detection but...
Definition facFqFactorize.cc:514
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
FqFactorize
CFFList FqFactorize(const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
factorize a multivariate polynomial over
Definition facFqFactorize.h:184
FqSqrfFactorize
CFList FqSqrfFactorize(const CanonicalForm &F, const Variable &alpha)
factorize a squarefree multivariate polynomial over
Definition facFqFactorize.h:64
henselLiftAndEarly
CFList henselLiftAndEarly(CanonicalForm &A, CFList &MOD, int *&liftBounds, bool &earlySuccess, CFList &earlyFactors, const CFList &Aeval, const CFList &biFactors, const CFList &evaluation, const ExtensionInfo &info)
hensel Lifting and early factor detection
Definition facFqFactorize.cc:985
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
leadingCoeffReconstruction
CFList leadingCoeffReconstruction(const CanonicalForm &F, const CFList &factors, const CFList &M)
obtain factors of F by reconstructing their leading coeffs
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
earlyFactorDetect
CFList earlyFactorDetect(CanonicalForm &F, CFList &factors, int &adaptedLiftBound, bool &success, const int deg, const CFList &MOD, const int bound)
detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are test...
Definition facFqFactorize.cc:612
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
facFqSquarefree.h
This file provides functions for squarefrees factorizing over , or GF.
GFSqrf
CFFList GFSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over GF. If input is not monic, the leading coefficient is dropped
Definition facFqSquarefree.h:116
FqSqrf
CFFList FqSqrf(const CanonicalForm &F, const Variable &alpha, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped
Definition facFqSquarefree.h:77
FpSqrf
CFFList FpSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped
Definition facFqSquarefree.h:38
j
int j
Definition facHensel.cc:110
gf_name
VAR char gf_name
Definition gfops.cc:52
length
static BOOLEAN length(leftv result, leftv arg)
Definition interval.cc:257
G
STATIC_VAR TreeM * G
Definition janet.cc:31
info
#define info
Definition libparse.cc:1256
A
#define A
Definition sirandom.c:24
M
#define M
Definition sirandom.c:25
timing.h
TIMING_DEFINE_PRINT
#define TIMING_DEFINE_PRINT(t)
Definition timing.h:95
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