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 */