Loading...
Searching...
No Matches
facFqBivarUtil.h
Go to the documentation of this file.
/*****************************************************************************\
* Computer Algebra System SINGULAR
\*****************************************************************************/
/** @file facFqBivarUtil.h
*
* This file provides utility functions for bivariate factorization
*
* @author Martin Lee
*
**/
/*****************************************************************************/
#ifndef FAC_FQ_BIVAR_UTIL_H
#define FAC_FQ_BIVAR_UTIL_H
// #include "config.h"
#include "cf_map.h"
#include "ExtensionInfo.h"
#ifdef HAVE_NTL
#include "NTLconvert.h"
#endif
#ifdef HAVE_FLINT
#include "FLINTconvert.h"
#endif
/// append @a factors2 on @a factors1
void append (CFList& factors1, ///< [in,out] a list of polys
const CFList& factors2 ///< [in] a list of polys
);
/// decompress a list of polys @a factors using the map @a N
void decompress (CFList& factors, ///< [in,out] a list of polys
const CFMap& N ///< [in] a map
);
/// as above
void decompress (CFFList& factors, ///< [in,out] a list of factors
const CFMap& N ///< [in] a map
);
/// as above
void decompress (CFAFList& factors, ///< [in,out] a list of factors
const CFMap& N ///< [in] a map
);
/// first swap Variables in @a factors1 if necessary, then append @a factors2
/// and @a factors3 on @a factors1 and finally decompress @a factors1
void appendSwapDecompress (CFList& factors1, ///< [in,out] a list of polys
const CFList& factors2, ///< [in] a list of polys
const CFList& factors3, ///< [in] a list of polys
const bool swap1, ///< [in] indicates the need
///< to swap
const bool swap2, ///< [in] indicates the need
///< to swap
const CFMap& N ///< [in] a map
);
/// swap Variables in @a factors, then decompress @a factors
void swapDecompress (CFList& factors, ///< [in,out] a list of polys
const bool swap, ///< [in] indicates the need to swap
const CFMap& N ///< [in] a map
);
/// tests if F is not contained in a subfield defined by @a gamma (Fq case) or
/// @a k (GF case)
///
/// @return @a isInExtension returns true if @a F is not contained in a subfield
/// defined by @a gamma (Fq case) or @a k (GF case), false else
/// @sa appendTestMapDown()
bool isInExtension (const CanonicalForm& F, ///< [in] a poly over
///< F_p (alpha)=Fq or GF(p^l)
const CanonicalForm& gamma, ///< [in] a primitive element
///< defining a subfield of
///< Fq if we are not over some
///< GF
const int k, ///< some int k such that k
///< divides l if we are not
///< over some Fq
const CanonicalForm& delta, ///< [in] image of gamma
CFList& source, ///< [in,out] list of preimages
CFList& dest ///< [in,out] list of images
);
/// map a poly into a subfield of the current field, no testing is performed!
///
/// @return @a mapDown returns @a F mapped into a subfield of the current field
/// @sa appendTestMapDown(), appendMapDown()
CanonicalForm
mapDown (const CanonicalForm& F, ///< [in] a poly
const ExtensionInfo& info, ///< [in] information about the sub- and
///< current field
CFList& source, ///< [in,out] in case we are over some
///< F_p (alpha) and want to map down into
///< F_p (beta) source contains powers of
///< the primitive element of F_p (alpha)
CFList& dest ///< [in,out] as source but contains
///< the corresponding powers of the
///< primitive element of F_p (beta)
);
/// test if @a g is in a subfield of the current field, if so map it down and
/// append it to @a factors
///
/// @sa mapDown(), isInExtension()
void appendTestMapDown (CFList& factors, ///< [in,out] a list of polys
const CanonicalForm& f, ///< [in] a poly
const ExtensionInfo& info,///< [in] information about
///< extension
CFList& source, ///< [in,out] @sa mapDown()
CFList& dest ///< [in,out] @sa mapDown()
);
/// map @a g down into a subfield of the current field and append it to @a
/// factors
///
/// @sa mapDown(), appendTestMapDown()
void
appendMapDown (CFList& factors, ///< [in,out] a list of polys
const CanonicalForm& g, ///< [in] a poly
const ExtensionInfo& info,///< [in] information about extension
CFList& source, ///< [in,out] @sa mapDown()
CFList& dest ///< [in,out] @sa mapDown()
);
/// normalize factors, i.e. make factors monic
void normalize (CFList& factors ///< [in,out] a list of polys
);
/// as above
void normalize (CFFList& factors ///< [in,out] a list of factors
);
/// extract a subset given by @a index of size @a s from @a elements, if there
/// is no subset we have not yet considered noSubset is set to true. @a index
/// encodes the next subset, e.g. if s= 3, elements= {a,b,c,d},
/// index= {1, 2, 4, 0}, then subset= {a,c,d}. @a index is of size
/// @a elements.size().
///
/// @return @a subset returns a list of polys of length @a s if there is a
/// subset we have not yet considered.
CFList subset (int index [], ///< [in,out] an array encoding the next
///< subset
const int& s, ///< [in] size of the subset
const CFArray& elements, ///< [in] an array of polys
bool& noSubset ///< [in,out] if there is no subset we
///< have not yet considered @a noSubset
///< is true
);
/// write elements of @a list into an array
///
/// @return an array of polys
CFArray copy (const CFList& list ///< [in] a list of polys
);
/// update @a index
void indexUpdate (int index [], ///< [in,out] an array encoding a
///< subset of size subsetSize
const int& subsetSize, ///< [in] size of the subset
const int& setSize, ///< [in] size of the given set
bool& noSubset ///< [in,out] if there is no subset we
///< have not yet considered @a
///< noSubset is true
);
/// compute the sum of degrees in Variable(1) of elements in S
///
/// @return @a subsetDegree returns the sum of degrees in Variable(1) of
/// elements in S
int subsetDegree (const CFList& S ///< [in] a list of polys
);
/// determine multiplicity of the factors
///
/// @return a list of factors of F with their multiplicity
CFFList multiplicity (CanonicalForm& F, ///< [in] a poly
const CFList& factors ///< [in] a list of factors of F
);
/// compute the coefficients of the logarithmic derivative of G mod
/// Variable (2)^l over Fq
///
/// @return an array of coefficients of the logarithmic derivative of G mod
/// Variable (2)^l
CFArray logarithmicDerivative (const CanonicalForm& F,///<[in] a bivariate poly
const CanonicalForm& G, ///<[in] a factor of F
int l, ///<[in] lifting precision
CanonicalForm& Q ///<[in,out] F/G
);
/// compute the coefficients of the logarithmic derivative of G mod
/// Variable (2)^l over Fq with oldQ= F/G mod Variable (2)^oldL
///
/// @return an array of coefficients of the logarithmic derivative of G mod
/// Variable (2)^l
CFArray
logarithmicDerivative (const CanonicalForm& F, ///< [in] bivariate poly
///< truncated at Variable(2)^l
const CanonicalForm& G, ///< [in] a factor of F
int l, ///< [in] lifting precision
int oldL, ///< [in] old precision
const CanonicalForm& oldQ,///< [in] F/G mod
///< Variable(2)^oldL
CanonicalForm& Q ///< [in, out] F/G
);
/// compute bounds for logarithmic derivative as described in K. Belabas,
/// M. van Hoeij, J. Klüners, and A. Steel, Factoring polynomials over global
/// fields
///
/// @return @a computeBounds returns bounds as described above
int *
computeBounds (const CanonicalForm& F,///< [in] compressed bivariate polynomial
int& n, ///< [in,out] length of output
bool& isIrreducible ///< [in,out] check if poly is irreducible
);
/// as above just wrt to the other variable
///
/// @return @a computeBounds returns bounds as described above
int *
computeBoundsWrtDiffMainvar
(const CanonicalForm& F,///< [in] compressed bivariate polynomial
int& n, ///< [in,out] length of output
bool& isIrreducible ///< [in,out] check if poly is irreducible
);
/// extract coefficients of \f$ x^i \f$ for \f$i\geq k\f$ where \f$ x \f$ is
/// a variable of level 1
///
/// @return coefficients of \f$ x^i \f$ for \f$i\geq k\f$
/// @sa {getCoeffs (const CanonicalForm&, const int, const Variable&),
/// getCoeffs (const CanonicalForm&, const int, const int, const int,
/// const Variable&, const CanonicalForm&, const mat_zz_p&)}
CFArray
getCoeffs (const CanonicalForm& F,///< [in] compressed bivariate poly over F_p
const int k ///< [in] some int
);
/// extract coefficients of \f$ x^i \f$ for \f$i\geq k\f$ where \f$ x \f$ is
/// a variable of level 1
///
/// @return coefficients of \f$ x^i \f$ for \f$i\geq k\f$
/// @sa {getCoeffs (const CanonicalForm&, const int),
/// getCoeffs (const CanonicalForm&, const int, const int, const int,
/// const Variable&, const CanonicalForm&, const mat_zz_p&)}
CFArray
getCoeffs (const CanonicalForm& F,///< [in] compressed bivariate poly over
///< F_p(alpha)
const int k, ///< [in] some int
const Variable& alpha ///< [in] algebraic variable
);
#ifdef HAVE_NTL
/// extract coefficients of \f$ x^i \f$ for \f$i\geq k\f$ where \f$ x \f$ is
/// a variable of level 1
///
/// @return coefficients of \f$ x^i \f$ for \f$i\geq k\f$
/// @sa {getCoeffs (const CanonicalForm&, const int, const Variable& alpha),
/// getCoeffs (const CanonicalForm&, const int)}
CFArray
getCoeffs (const CanonicalForm& F, ///< [in] compressed bivariate poly
const int k, ///< [in] some int
const int l, ///< [in] precision
const int degMipo, ///< [in] degree of minimal poly
const Variable& alpha, ///< [in] algebraic variable
const CanonicalForm& evaluation,///< [in] evaluation point
const mat_zz_p& M ///< [in] bases change matrix
);
#endif
#ifdef HAVE_FLINT
/// extract coefficients of \f$ x^i \f$ for \f$i\geq k\f$ where \f$ x \f$ is
/// a variable of level 1
///
/// @return coefficients of \f$ x^i \f$ for \f$i\geq k\f$
/// @sa {getCoeffs (const CanonicalForm&, const int, const Variable& alpha),
/// getCoeffs (const CanonicalForm&, const int)}
CFArray
getCoeffs (const CanonicalForm& F, ///< [in] compressed bivariate poly
const int k, ///< [in] some int
const int l, ///< [in] precision
const int degMipo, ///< [in] degree of minimal poly
const Variable& alpha, ///< [in] algebraic variable
const CanonicalForm& evaluation,///< [in] evaluation point
const nmod_mat_t M ///< [in] bases change matrix
);
#endif
/// write A into M starting at row startIndex
void
writeInMatrix (CFMatrix& M, ///< [in,out] some matrix
const CFArray& A, ///< [in] array of polys
const int column, ///< [in] column in which A is written
const int startIndex///< [in] row in which to start
);
/// checks if a substitution x^n->x is possible
///
/// @return an integer n > 1, if a substitution described as above is possible
/// else n <= 1
int substituteCheck (const CFList& L ///< [in] a list of univariate polys
);
/// substitute x^d by x in F
void
subst (const CanonicalForm& F, ///< [in] a polynomial
CanonicalForm& A, ///< [in,out] returns F with x^d replaced by x
const int d, ///< d > 1 such that a substitution x^d -> x
///< [in] is possible
const Variable& x ///< [in] a Variable
);
/// reverse a substitution x^d->x
///
/// @return a poly with x replaced by x^d
CanonicalForm
reverseSubst (const CanonicalForm& F, ///< [in] a poly
const int d, ///< [in] an integer > 0
const Variable& x ///< [in] a Variable
);
/// reverse a substitution x^d->x
void
reverseSubst (CFList& L, ///< [in,out] a list of polys, returns the
///< given list with x replaced by x^d
const int d, ///< [in] an integer > 0
const Variable& x ///< [in] a Variable
);
/// check if a substitution x^n->x is possible
///
/// @return an integer n > 1, if a substitution described as above is possible
/// else n <= 1
int
substituteCheck (const CanonicalForm& F, ///<[in] a polynomial
const Variable& x ///<[in] some variable
);
#endif
/* FAC_FQ_BIVAR_UTIL_H */
ExtensionInfo.h
This file provides a class to store information about finite fields and extensions thereof.
FLINTconvert.h
This file defines functions for conversion to FLINT (www.flintlib.org) and back.
NTLconvert.h
Conversion to and from NTL.
swap
#define swap(_i, _j)
CFArray
Array< CanonicalForm > CFArray
Definition canonicalform.h:397
CFMatrix
Matrix< CanonicalForm > CFMatrix
Definition canonicalform.h:398
CFFList
List< CFFactor > CFFList
Definition canonicalform.h:393
CFList
List< CanonicalForm > CFList
Definition canonicalform.h:395
CFAFList
List< CFAFactor > CFAFList
Definition canonicalform.h:390
N
const CanonicalForm CFMap CFMap & N
Definition cfEzgcd.cc:56
l
int l
Definition cfEzgcd.cc:100
k
int k
Definition cfEzgcd.cc:99
x
Variable x
Definition cfModGcd.cc:4090
g
g
Definition cfModGcd.cc:4098
cf_map.h
map polynomials
f
FILE * f
Definition checklibs.c:9
CFMap
class CFMap
Definition cf_map.h:85
CanonicalForm
factory's main class
Definition canonicalform.h:86
ExtensionInfo
ExtensionInfo contains information about extension.
Definition ExtensionInfo.h:51
Variable
factory's class for variables
Definition factory.h:127
alpha
Variable alpha
Definition facAbsBiFact.cc:52
evaluation
const CanonicalForm int const CFList & evaluation
Definition facAbsFact.cc:52
s
const CanonicalForm int s
Definition facAbsFact.cc:51
factors2
const CFList & factors2
Definition facFqBivarUtil.cc:42
append
void append(CFList &factors1, const CFList &factors2)
append factors2 on factors1
subsetDegree
int subsetDegree(const CFList &S)
compute the sum of degrees in Variable(1) of elements in S
Definition facFqBivarUtil.cc:428
logarithmicDerivative
CFArray logarithmicDerivative(const CanonicalForm &F, const CanonicalForm &G, int l, CanonicalForm &Q)
compute the coefficients of the logarithmic derivative of G mod Variable (2)^l over Fq
Definition facFqBivarUtil.cc:459
computeBounds
int * computeBounds(const CanonicalForm &F, int &n, bool &isIrreducible)
compute bounds for logarithmic derivative as described in K. Belabas, M. van Hoeij,...
Definition facFqBivarUtil.cc:768
appendTestMapDown
void appendTestMapDown(CFList &factors, const CanonicalForm &f, const ExtensionInfo &info, CFList &source, CFList &dest)
test if g is in a subfield of the current field, if so map it down and append it to factors
Definition facFqBivarUtil.cc:223
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
mapDown
CanonicalForm mapDown(const CanonicalForm &F, const ExtensionInfo &info, CFList &source, CFList &dest)
map a poly into a subfield of the current field, no testing is performed!
Definition facFqBivarUtil.cc:206
normalize
void normalize(CFList &factors)
normalize factors, i.e. make factors monic
Definition facFqBivarUtil.cc:286
indexUpdate
void indexUpdate(int index[], const int &subsetSize, const int &setSize, bool &noSubset)
update index
Definition facFqBivarUtil.cc:373
appendMapDown
void appendMapDown(CFList &factors, const CanonicalForm &g, const ExtensionInfo &info, CFList &source, CFList &dest)
map g down into a subfield of the current field and append it to factors
Definition facFqBivarUtil.cc:267
reverseSubst
CanonicalForm reverseSubst(const CanonicalForm &F, const int d, const Variable &x)
reverse a substitution x^d->x
Definition facFqBivarUtil.cc:1295
subst
void subst(const CanonicalForm &F, CanonicalForm &A, const int d, const Variable &x)
substitute x^d by x in F
Definition facFqBivarUtil.cc:1275
getCoeffs
CFArray getCoeffs(const CanonicalForm &F, const int k)
extract coefficients of for where is a variable of level 1
Definition facFqBivarUtil.cc:599
copy
CFArray copy(const CFList &list)
write elements of list into an array
Definition facFqBivarUtil.cc:364
swapDecompress
void swapDecompress(CFList &factors, const bool swap, const CFMap &N)
swap Variables in factors, then decompress factors
Definition facFqBivarUtil.cc:97
substituteCheck
int substituteCheck(const CFList &L)
checks if a substitution x^n->x is possible
Definition facFqBivarUtil.cc:1254
subset
CFList subset(int index[], const int &s, const CFArray &elements, bool &noSubset)
extract a subset given by index of size s from elements, if there is no subset we have not yet consid...
Definition facFqBivarUtil.cc:309
isInExtension
bool isInExtension(const CanonicalForm &F, const CanonicalForm &gamma, const int k, const CanonicalForm &delta, CFList &source, CFList &dest)
tests if F is not contained in a subfield defined by gamma (Fq case) or k (GF case)
Definition facFqBivarUtil.cc:184
writeInMatrix
void writeInMatrix(CFMatrix &M, const CFArray &A, const int column, const int startIndex)
write A into M starting at row startIndex
Definition facFqBivarUtil.cc:586
computeBoundsWrtDiffMainvar
int * computeBoundsWrtDiffMainvar(const CanonicalForm &F, int &n, bool &isIrreducible)
as above just wrt to the other variable
Definition facFqBivarUtil.cc:922
decompress
void decompress(CFList &factors, const CFMap &N)
decompress a list of polys factors using the map N
Definition facFqBivarUtil.cc:51
isIrreducible
bool isIrreducible(const CanonicalForm &f)
bool isIrreducible ( const CanonicalForm & f )
Definition gengftables-conway.cc:77
multiplicity
STATIC_VAR int * multiplicity
Definition interpolation.cc:86
G
STATIC_VAR TreeM * G
Definition janet.cc:31
info
#define info
Definition libparse.cc:1256
index
static int index(p_Length length, p_Ord ord)
Definition p_Procs_Impl.h:592
A
#define A
Definition sirandom.c:24
M
#define M
Definition sirandom.c:25
Q
#define Q
Definition sirandom.c:26