Loading...
Searching...
No Matches
facFactorize.h
Go to the documentation of this file.
/*****************************************************************************\
* Computer Algebra System SINGULAR
\*****************************************************************************/
/** @file facFactorize.h
*
* multivariate factorization over Q(a)
*
* @author Martin Lee
*
**/
/*****************************************************************************/
#ifndef FAC_FACTORIZE_H
#define FAC_FACTORIZE_H
// #include "config.h"
#include "timing.h"
#include "facBivar.h"
#include "facFqBivarUtil.h"
TIMING_DEFINE_PRINT (fac_squarefree)
TIMING_DEFINE_PRINT (fac_factor_squarefree)
/// Factorization of A wrt. to different second vars
void
factorizationWRTDifferentSecondVars (
const CanonicalForm& A, ///<[in] poly
CFList*& Aeval, ///<[in,out] A evaluated wrt.
///< different second vars
///< returns bivariate factors
int& minFactorsLength, ///<[in,out] minimal length of
///< bivariate factors
bool& irred, ///<[in,out] Is A irreducible?
const Variable& w ///<[in] alg. variable
);
/// Factorization over Q (a)
///
/// @return @a multiFactorize returns a factorization of F
CFList
multiFactorize (const CanonicalForm& F, ///< [in] sqrfree poly
const Variable& v ///< [in] some algebraic variable
);
#if defined(HAVE_NTL) || defined(HAVE_FLINT) // ratBiSqrfFactorize
/// factorize a squarefree multivariate polynomial over \f$ Q(\alpha) \f$
///
/// @return @a ratSqrfFactorize returns a list of monic factors, the first
/// element is the leading coefficient.
inline
CFList
ratSqrfFactorize (const CanonicalForm & G, ///<[in] a multivariate poly
const Variable& v= Variable (1) ///<[in] algebraic variable
)
{
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;
}
#endif
#if defined(HAVE_NTL) || defined(HAVE_FLINT) // multiFactorize, henselLiftAndEarly, nonMonicHenselLift
/// factorize a multivariate polynomial over \f$ Q(\alpha) \f$
///
/// @return @a ratFactorize returns a list of monic factors with
/// multiplicity, the first element is the leading coefficient.
inline
CFFList
ratFactorize (const CanonicalForm& G, ///<[in] a multivariate poly
const Variable& v= Variable (1), ///<[in] algebraic variable
bool substCheck= true ///<[in] enables substitute check
)
{
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;
}
#endif
#endif
isOn
bool isOn(int sw)
switches
Definition canonicalform.cc:1971
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition canonicalform.cc:1896
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
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
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
sqrFree
CFFList FACTORY_PUBLIC sqrFree(const CanonicalForm &f, bool sort=false)
squarefree factorization
Definition cf_factor.cc:961
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
CanonicalForm::level
int level() const
level() returns the level of CO.
Definition canonicalform.cc:576
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
LcF
CanonicalForm LcF
Definition facAbsBiFact.cc:51
result
return result
Definition facAbsBiFact.cc:76
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
facBivar.h
bivariate factorization over Q(a)
ratBiSqrfFactorize
CFList ratBiSqrfFactorize(const CanonicalForm &G, const Variable &v=Variable(1))
factorize a squarefree bivariate polynomial over .
Definition facBivar.h:47
ratBiFactorize
CFFList ratBiFactorize(const CanonicalForm &G, const Variable &v=Variable(1), bool substCheck=true)
factorize a bivariate polynomial over
Definition facBivar.h:129
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition facBivar.h:39
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
ratFactorize
CFFList ratFactorize(const CanonicalForm &G, const Variable &v=Variable(1), bool substCheck=true)
factorize a multivariate polynomial over
Definition facFactorize.h:79
multiFactorize
CFList multiFactorize(const CanonicalForm &F, const Variable &v)
Factorization over Q (a).
Definition facFactorize.cc:198
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
facFqBivarUtil.h
This file provides utility functions for bivariate factorization.
tmp2
CFList tmp2
Definition facFqBivar.cc:75
j
int j
Definition facHensel.cc:110
G
STATIC_VAR TreeM * G
Definition janet.cc:31
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.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