Loading...
Searching...
No Matches
facFqFactorizeUtil.cc
Go to the documentation of this file.
/*****************************************************************************\
* Computer Algebra System SINGULAR
\*****************************************************************************/
/** @file facFqFactorizeUtil.cc
*
* This file provides utility functions for multivariate factorization
*
* @author Martin Lee
*
**/
/*****************************************************************************/
#include "config.h"
#include "canonicalform.h"
#include "cf_map.h"
#include "cf_algorithm.h"
static inline
void appendSwap (CFList& factors1, const CFList& factors2, const int
swapLevel1, const int swapLevel2, const Variable& x)
{
for (CFListIterator i= factors2; i.hasItem(); i++)
{
if (swapLevel1)
{
if (swapLevel2)
factors1.append (swapvar (swapvar (i.getItem(), x,
Variable (swapLevel2)), Variable (swapLevel1), x));
else
factors1.append (swapvar (i.getItem(), Variable (swapLevel1), x));
}
else
{
if (swapLevel2)
factors1.append (swapvar (i.getItem(), x, Variable (swapLevel2)));
else
factors1.append (i.getItem());
}
}
return;
}
void swap (CFList& factors, const int swapLevel1, const int swapLevel2, const
Variable& x)
{
for (CFListIterator i= factors; i.hasItem(); i++)
{
if (swapLevel1)
{
if (swapLevel2)
i.getItem()= swapvar (swapvar (i.getItem(), x, Variable (swapLevel2)),
Variable (swapLevel1), x);
else
i.getItem()= swapvar (i.getItem(), Variable (swapLevel1), x);
}
else
{
if (swapLevel2)
i.getItem()= swapvar (i.getItem(), x, Variable (swapLevel2));
}
}
return;
}
void appendSwapDecompress (CFList& factors1, const CFList& factors2,
const CFMap& N, const int swapLevel, const
Variable& x)
{
for (CFListIterator i= factors1; i.hasItem(); i++)
{
if (swapLevel)
i.getItem()= swapvar (i.getItem(), Variable (swapLevel), x);
i.getItem()= N(i.getItem());
}
for (CFListIterator i= factors2; i.hasItem(); i++)
{
if (!i.getItem().inCoeffDomain())
factors1.append (N (i.getItem()));
}
return;
}
void appendSwapDecompress (CFList& factors1, const CFList& factors2,
const CFMap& N, const int swapLevel1,
const int swapLevel2, const Variable& x)
{
for (CFListIterator i= factors1; i.hasItem(); i++)
{
if (swapLevel1)
{
if (swapLevel2)
i.getItem()=
N (swapvar (swapvar (i.getItem(), Variable (swapLevel2), x), x,
Variable (swapLevel1)));
else
i.getItem()= N (swapvar (i.getItem(), x, Variable (swapLevel1)));
}
else
{
if (swapLevel2)
i.getItem()= N (swapvar (i.getItem(), Variable (swapLevel2), x));
else
i.getItem()= N (i.getItem());
}
}
for (CFListIterator i= factors2; i.hasItem(); i++)
{
if (!i.getItem().inCoeffDomain())
factors1.append (N (i.getItem()));
}
return;
}
int* liftingBounds (const CanonicalForm& A, const int& bivarLiftBound)
{
int j= A.level() - 1;
int* liftBounds= new int [j];
liftBounds[0]= bivarLiftBound;
for (int i= 1; i < j; i++)
{
liftBounds[i]= degree (A, Variable (i + 2)) + 1 +
degree (LC (A, 1), Variable (i + 2));
}
return liftBounds;
}
CanonicalForm shift2Zero (const CanonicalForm& F, CFList& Feval, const CFList& evaluation, int l)
{
CanonicalForm A= F;
int k= evaluation.length() + l - 1;
for (CFListIterator i= evaluation; i.hasItem(); i++, k--)
A= A (Variable (k) + i.getItem(), k);
CanonicalForm buf= A;
Feval= CFList();
Feval.append (buf);
for (k= A.level(); k > 2; k--)
{
buf= mod (buf, Variable (k));
Feval.insert (buf);
}
return A;
}
CanonicalForm reverseShift (const CanonicalForm& F, const CFList& evaluation, int l)
{
int k= evaluation.length() + l - 1;
CanonicalForm result= F;
CFListIterator j= evaluation;
for (int i= k; j.hasItem() && (i > l - 1); i--, j++)
{
if (F.level() < i)
continue;
result= result (Variable (i) - j.getItem(), i);
}
return result;
}
bool isOnlyLeadingCoeff (const CanonicalForm& F)
{
return (F-LC (F,1)*power (Variable(1),degree (F,1))).isZero();
}
/// like getVars but including multiplicities
CanonicalForm myGetVars (const CanonicalForm& F)
{
CanonicalForm result= 1;
int deg;
for (int i= 1; i <= F.level(); i++)
{
if ((deg= degree (F, i)) > 0)
result *= power (Variable (i), deg);
}
return result;
}
int compareByNumberOfVars (const CFFactor& F, const CFFactor& G)
{
return getNumVars (F.factor()) < getNumVars (G.factor());
}
CFFList
sortCFFListByNumOfVars (CFFList& F)
{
F.sort (compareByNumberOfVars);
CFFList result= F;
return result;
}
CFList evaluateAtZero (const CanonicalForm& F)
{
CFList result;
CanonicalForm buf= F;
result.insert (buf);
for (int i= F.level(); i > 2; i--)
{
buf= buf (0, i);
result.insert (buf);
}
return result;
}
CFList evaluateAtEval (const CanonicalForm& F, const CFArray& eval)
{
CFList result;
CanonicalForm buf= F;
result.insert (buf);
int k= eval.size();
for (int i= 1; i < k; i++)
{
buf= buf (eval[i], i + 2);
result.insert (buf);
}
return result;
}
CFList evaluateAtEval (const CanonicalForm& F, const CFList& evaluation, int l)
{
CFList result;
CanonicalForm buf= F;
result.insert (buf);
int k= evaluation.length() + l - 1;
CFListIterator j= evaluation;
for (int i= k; j.hasItem() && i > l; i--, j++)
{
if (F.level() < i)
continue;
buf= buf (j.getItem(), i);
result.insert (buf);
}
return result;
}
CFList recoverFactors (const CanonicalForm& F, const CFList& factors)
{
CFList result;
CanonicalForm tmp, tmp2;
CanonicalForm G= F;
for (CFListIterator i= factors; i.hasItem(); i++)
{
tmp= i.getItem()/content (i.getItem(), 1);
if (fdivides (tmp, G, tmp2))
{
G= tmp2;
result.append (tmp);
}
}
if (result.length() + 1 == factors.length())
result.append (G/content (G,1));
return result;
}
CFList recoverFactors (const CanonicalForm& F, const CFList& factors,
const CFList& evaluation)
{
CFList result;
CanonicalForm tmp, tmp2;
CanonicalForm G= F;
for (CFListIterator i= factors; i.hasItem(); i++)
{
tmp= reverseShift (i.getItem(), evaluation, 2);
tmp /= content (tmp, 1);
if (fdivides (tmp, G, tmp2))
{
G= tmp2;
result.append (tmp);
}
}
if (result.length() + 1 == factors.length())
result.append (G/content (G,1));
return result;
}
CFList recoverFactors (CanonicalForm& F, const CFList& factors, int* index)
{
CFList result;
CanonicalForm tmp, tmp2;
CanonicalForm G= F;
int j= 0;
for (CFListIterator i= factors; i.hasItem(); i++, j++)
{
if (i.getItem().isZero())
{
index[j]= 0;
continue;
}
tmp= i.getItem();
if (fdivides (tmp, G, tmp2))
{
G= tmp2;
tmp /=content (tmp, 1);
result.append (tmp);
index[j]= 1;
}
else
index[j]= 0;
}
if (result.length() + 1 == factors.length())
{
result.append (G/content (G,1));
F= G/content (G,1);
}
else
F= G;
return result;
}
swap
#define swap(_i, _j)
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition canonicalform.cc:1896
canonicalform.h
Header for factory's main class CanonicalForm.
content
CanonicalForm FACTORY_PUBLIC content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f ).
Definition cf_gcd.cc:603
getNumVars
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition cf_ops.cc:314
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
CFFList
List< CFFactor > CFFList
Definition canonicalform.h:393
CFFactor
Factor< CanonicalForm > CFFactor
Definition canonicalform.h:392
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
x
Variable x
Definition cfModGcd.cc:4090
cf_algorithm.h
declarations of higher level algorithms.
fdivides
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
cf_map.h
map polynomials
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
Factor::factor
T factor() const
Definition ftmpl_factor.h:30
List::sort
void sort(int(*)(const T &, const T &))
Definition ftmpl_list.cc:339
List::length
int length() const
Definition ftmpl_list.cc:273
List::append
void append(const T &)
Definition ftmpl_list.cc:256
Variable
factory's class for variables
Definition factory.h:127
result
return result
Definition facAbsBiFact.cc:76
evaluation
const CanonicalForm int const CFList & evaluation
Definition facAbsFact.cc:52
Feval
CanonicalForm Feval
Definition facAbsFact.cc:60
eval
CFList & eval
Definition facFactorize.cc:47
factors2
const CFList & factors2
Definition facFqBivarUtil.cc:42
tmp2
CFList tmp2
Definition facFqBivar.cc:75
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
reverseShift
CanonicalForm reverseShift(const CanonicalForm &F, const CFList &evaluation, int l)
reverse shifting the evaluation point to zero
Definition facFqFactorizeUtil.cc:148
shift2Zero
CanonicalForm shift2Zero(const CanonicalForm &F, CFList &Feval, const CFList &evaluation, int l)
shift evaluation point to zero
Definition facFqFactorizeUtil.cc:131
appendSwapDecompress
void appendSwapDecompress(CFList &factors1, const CFList &factors2, const CFMap &N, const int swapLevel, const Variable &x)
swap elements of factors2, append them to factors1 and decompress
Definition facFqFactorizeUtil.cc:69
appendSwap
static void appendSwap(CFList &factors1, const CFList &factors2, const int swapLevel1, const int swapLevel2, const Variable &x)
Definition facFqFactorizeUtil.cc:22
liftingBounds
int * liftingBounds(const CanonicalForm &A, const int &bivarLiftBound)
compute lifting bounds
Definition facFqFactorizeUtil.cc:118
evaluateAtZero
CFList evaluateAtZero(const CanonicalForm &F)
evaluate F successively n-2 at 0
Definition facFqFactorizeUtil.cc:193
isOnlyLeadingCoeff
bool isOnlyLeadingCoeff(const CanonicalForm &F)
check if F consists of more than just the leading coeff wrt. Variable (1)
Definition facFqFactorizeUtil.cc:162
compareByNumberOfVars
int compareByNumberOfVars(const CFFactor &F, const CFFactor &G)
Definition facFqFactorizeUtil.cc:180
sortCFFListByNumOfVars
CFFList sortCFFListByNumOfVars(CFFList &F)
sort CFFList by the number variables in a factor
Definition facFqFactorizeUtil.cc:186
myGetVars
CanonicalForm myGetVars(const CanonicalForm &F)
like getVars but including multiplicities
Definition facFqFactorizeUtil.cc:168
evaluateAtEval
CFList evaluateAtEval(const CanonicalForm &F, const CFArray &eval)
evaluate F at evaluation
Definition facFqFactorizeUtil.cc:206
j
int j
Definition facHensel.cc:110
G
STATIC_VAR TreeM * G
Definition janet.cc:31
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