Changeset 1e9197 in git

Timestamp:

Nov 27, 2020, 11:06:46 AM (3 years ago)

Author:

Hans Schoenemann <hannes@…>

Branches:

(u'fieker-DuVal', '117eb8c30fc9e991c4decca4832b1d19036c4c65')(u'spielwiese', '38077648e7239f98078663eb941c3c979511150a')

Children:

815e701a9eb465a5c6526483632b99b0dd38db32

Parents:

a0efc838470abff6a0d11126dd9350fd43451088

Message:

factorization (multivariate) over Zp(a) via FLINT 2.7.0

Location:

factory

Files:

• FLINTconvert.cc (modified) (3 diffs)
• FLINTconvert.h (modified) (5 diffs)
• cf_factor.cc (modified) (3 diffs)
• facBivar.h (modified) (3 diffs)
• facFactorize.h (modified) (1 diff)

factory/FLINTconvert.cc

@@ -734 +734 @@
 }
 
+#if __FLINT_RELEASE >= 20700
+static void convFlint_RecPP ( const CanonicalForm & f, ulong * exp, fq_nmod_mpoly_t result, const fq_nmod_mpoly_ctx_t ctx, int N, const fq_nmod_ctx_t fq_ctx )
+{
+  // assume f!=0
+  if ( ! f.inCoeffDomain() )
+  {
+    int l = f.level();
+    for ( CFIterator i = f; i.hasTerms(); i++ )
+    {
+      exp[N-l] = i.exp();
+      convFlint_RecPP( i.coeff(), exp, result, ctx, N, fq_ctx );
+    }
+    exp[N-l] = 0;
+  }
+  else
+  {
+    fq_nmod_t c;
+    convertFacCF2Fq_nmod_t (c, f, fq_ctx);
+    fq_nmod_mpoly_push_term_fq_nmod_ui(result,c,exp,ctx);
+  }
+}
+#endif
+
 void convFactoryPFlintMP ( const CanonicalForm & f, nmod_mpoly_t res, nmod_mpoly_ctx_t ctx, int N )
 {
@@ -765 +788 @@
   Free(exp,N*sizeof(ulong));
 }
+
+#if __FLINT_RELEASE >= 20700
+void convFactoryPFlintMP ( const CanonicalForm & f, fq_nmod_mpoly_t res, fq_nmod_mpoly_ctx_t ctx, int N, fq_nmod_ctx_t fq_ctx )
+{
+  if (f.isZero()) return;
+  ulong * exp = (ulong*)Alloc(N*sizeof(ulong));
+  memset(exp,0,N*sizeof(ulong));
+  bool save_sym_ff= isOn (SW_SYMMETRIC_FF);
+  if (save_sym_ff) Off (SW_SYMMETRIC_FF);
+  convFlint_RecPP( f, exp, res, ctx, N, fq_ctx );
+  if (save_sym_ff) On(SW_SYMMETRIC_FF);
+  Free(exp,N*sizeof(ulong));
+}
+#endif
 
 CanonicalForm convFlintMPFactoryP(nmod_mpoly_t f, nmod_mpoly_ctx_t ctx, int N)
@@ -953 +990 @@
 }
 
-#endif
-
-#endif
-
-
+#endif // FLINT 2.5.3
+
+#if __FLINT_RELEASE >= 20700
+CFFList
+convertFLINTFq_nmod_mpoly_factor2FacCFFList (
+                   fq_nmod_mpoly_factor_t fac, 
+                   const fq_nmod_mpoly_ctx_t& ctx,
+                   const int N,
+                   const fq_nmod_ctx_t& fq_ctx,
+                   const Variable alpha)
+{
+  CFFList result;
+
+  long i;
+
+  fq_nmod_t c;
+  fq_nmod_init(c,fq_ctx);
+  fq_nmod_mpoly_factor_get_constant_fq_nmod(c,fac,ctx);
+  result.append(CFFactor(convertFq_nmod_t2FacCF(c,alpha,fq_ctx),1));
+  fq_nmod_clear(c,fq_ctx);
+
+  fq_nmod_mpoly_t p;
+  fq_nmod_mpoly_init(p,ctx);
+  long exp;
+  for (i = 0; i < fac->num; i++)
+  {
+    fq_nmod_mpoly_factor_get_base(p,fac,i,ctx);
+    exp=fq_nmod_mpoly_factor_get_exp_si(fac,i,ctx);
+    result.append (CFFactor (convertFq_nmod_mpoly_t2FacCF (
+                             p,ctx,N,fq_ctx,alpha), exp));
+  }
+  fq_nmod_mpoly_clear(p,ctx);
+  return result;
+}
+
+void
+convertFacCF2Fq_nmod_mpoly_t (fq_nmod_mpoly_t result,
+                        const CanonicalForm& f,
+                        const fq_nmod_mpoly_ctx_t ctx,
+                        const int N,
+                        const fq_nmod_ctx_t fq_ctx
+                       )
+{
+  if (f.isZero()) return;
+  ulong * exp = (ulong*)Alloc(N*sizeof(ulong));
+  memset(exp,0,N*sizeof(ulong));
+  convFlint_RecPP( f, exp, result, ctx, N, fq_ctx );
+  Free(exp,N*sizeof(ulong));
+}
+
+CanonicalForm
+convertFq_nmod_mpoly_t2FacCF (const fq_nmod_mpoly_t f,
+                              const fq_nmod_mpoly_ctx_t& ctx,
+                              const int N,
+                              const fq_nmod_ctx_t& fq_ctx,
+                              const Variable alpha)
+{
+  CanonicalForm result;
+  int d=fq_nmod_mpoly_length(f,ctx)-1;
+  ulong* exp=(ulong*)Alloc(N*sizeof(ulong));
+  fq_nmod_t c;
+  fq_nmod_init(c,fq_ctx);
+  for(int i=d; i>=0; i--)
+  {
+    fq_nmod_mpoly_get_term_coeff_fq_nmod(c,f,i,ctx);
+    fq_nmod_mpoly_get_term_exp_ui(exp,f,i,ctx);
+    CanonicalForm term=convertFq_nmod_t2FacCF(c,alpha,fq_ctx);
+    for ( int i = 0; i <N; i++ )
+    {
+      if (exp[i]!=0) term*=CanonicalForm( Variable( N-i ), exp[i] );
+    }
+    result+=term;
+  }
+  Free(exp,N*sizeof(ulong));
+  return result;
+}
+
+#endif
+#endif // FLINT
+
+

factory/FLINTconvert.h

@@ -43 +43 @@
 #if ( __FLINT_RELEASE >= 20503)
 #include <flint/fmpq_mpoly.h>
+#include <flint/fq_nmod_mpoly_factor.h>
 #endif
 #endif
@@ -137 +138 @@
                                         );
 
+/// conversion of a FLINT factorization over Zp(a) to a CFFList
+CFFList
+convertFLINTFq_nmod_mpoly_factor2FacCFFList (
+                   fq_nmod_mpoly_factor_t fac,    ///< [in] a fq_nmod_mpoly_factor_t
+                   const fq_nmod_mpoly_ctx_t& ctx,///< [in] context
+                   const int N,                   ///< [in] #vars
+                   const fq_nmod_ctx_t& fq_ctx,   ///< [in] fq context
+                   const Variable alpha           ///< [in] alpha
+                                        );
+
 /// conversion of a factory univariate poly over Z to a FLINT poly over
 /// Z/p (for non word size p)
@@ -164 +175 @@
 convertFq_nmod_t2FacCF (const fq_nmod_t poly, ///< [in] fq_nmod_t
                         const Variable& alpha, ///< [in] algebraic variable
-                        const fq_nmod_ctx_t ctx ///<[in] context
+                        const fq_nmod_ctx_t ctx ///<[in] context
                        );
 
@@ -180 +191 @@
                         const CanonicalForm& f, ///< [in] element of Fq
                         const fq_nmod_ctx_t ctx ///< [in] Fq context
+                       );
+
+/// conversion of a factory polynomial over of F_q to a FLINT fq_nmod_mpoly_t, does not do any
+/// memory allocation for poly
+void
+convertFacCF2Fq_nmod_mpoly_t (fq_nmod_mpoly_t result, ///< [in,out] fq_nmod_mpoly__t
+                        const CanonicalForm& f,       ///< [in] poly over Fq
+                        const fq_nmod_mpoly_ctx_t ctx,///< [in] context
+                        const int N,                  ///< [in] #vars
+                        const fq_nmod_ctx_t fq_ctx    ///< [in] fq context
                        );
 
@@ -279 +300 @@
 CanonicalForm convFlintMPFactoryP(fmpq_mpoly_t f, fmpq_mpoly_ctx_t ctx, int N);
 CanonicalForm convFlintMPFactoryP(fmpz_mpoly_t f, fmpz_mpoly_ctx_t ctx, int N);
-#endif
-#endif
-#endif
+#endif // FLINT 2.5.3
+#if __FLINT_RELEASE >= 20700
+CanonicalForm
+convertFq_nmod_mpoly_t2FacCF (const fq_nmod_mpoly_t poly,    ///< [in] 
+                              const fq_nmod_mpoly_ctx_t& ctx,///< [in] context
+                              const int N,                   ///< [in] #vars
+                              const fq_nmod_ctx_t& fq_ctx,   ///< [in] fq context
+                              const Variable alpha           ///< [in] alpha
+                         );
+#endif // FLINT2.7.0
+#endif // FLINT
+#endif

factory/cf_factor.cc

@@ -47 +47 @@
 #include <flint/nmod_mpoly_factor.h>
 #include <flint/fmpq_mpoly_factor.h>
+#include <flint/fq_nmod_mpoly_factor.h>
 #endif
 #endif
@@ -880 +881 @@
     else // char p, multivariate
     {
-      #ifdef HAVE_NTL
+      #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
+        // use FLINT
+        nmod_poly_t FLINTmipo, leadingCoeff;
+        fq_nmod_ctx_t fq_con;
+        fq_nmod_mpoly_ctx_t fq_mpoly_ctx;
+
+        nmod_poly_init (FLINTmipo, ch);
+        convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
+
+        fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
+        fq_nmod_mpoly_ctx_init(fq_mpoly_ctx,f.level(),ORD_LEX,fq_con);
+
+        fq_nmod_mpoly_t FLINTF;
+        fq_nmod_mpoly_init(FLINTF,ctx);
+        convertFacCF2Fq_nmod_mpoly_t(FLINTF,f,fq_mpoly_ctx,f.level(),fq_con);
+        fq_nmod_mpoly_factor_t res;
+        fq_nmod_mpoly_factor_init (res, fq_mpoly_ctx);
+        fq_nmod_mpoly_factor (res, FLINTF, fq_mpoly_ctx);
+        F= convertFLINTFq_nmod_mpoly_factor2FacCFFList (res, fq_mpoly_ctx,f.level(),fq_con,alpha);
+        //F.insert (CFFactor (Lc (f), 1));
+
+        fq_nmod_mpoly_factor_clear (res, fq_mpoly_ctx);
+        fq_nmod_mpoly_clear (FLINTF, fq_mpoly_ctx);
+        nmod_poly_clear (FLINTmipo);
+        fq_nmod_mpoly_ctx_clear (fq_mpoly_ctx);
+        fq_nmod_ctx_clear (fq_con);
+        if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
+        return F;
+      #elif defined(HAVE_NTL)
       F= FqFactorize (f, alpha);
       #else
-      factoryError ("multivariate factorization over Z/pZ(alpha) depends on NTL(missing)");
+      factoryError ("multivariate factorization over Z/pZ(alpha) depends on NTL/Flint(missing)");
       return CFFList (CFFactor (f, 1));
       #endif
@@ -896 +925 @@
     else //Q(a)[x1,...,xn]
     {
-      #ifdef HAVE_NTL
       F= ratFactorize (f, alpha);
-      #else
-      factoryError ("multivariate factorization over Q(alpha) depends on NTL(missing)");
-      return CFFList (CFFactor (f, 1));
-      #endif
     }
   }

factory/facBivar.h

@@ -27 +27 @@
 #include "cfNewtonPolygon.h"
 #include "fac_util.h"
+#include "cf_algorithm.h"
 
 TIMING_DEFINE_PRINT(fac_bi_sqrf)
@@ -42 +43 @@
 /// @ return @a ratBiSqrfFactorize returns a list of monic factors, the first
 ///         element is the leading coefficient.
-#ifdef HAVE_NTL
 inline
 CFList
@@ -276 +276 @@
 }
 
-#endif
-
 /// convert a CFFList to a CFList by dropping the multiplicity
 CFList conv (const CFFList& L ///< [in] a CFFList

factory/facFactorize.h

@@ -173 +173 @@
 }
 #endif
-#endif