Changeset 1130ffc in git for factory/facBivar.cc

Timestamp:

Oct 25, 2012, 2:25:59 PM (11 years ago)

Author:

Oleksandr Motsak <motsak@…>

Branches:

(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')

Children:

139f6f800b915490dfaa914ef7676d29a3236b92186df6b3fe891f605e0e3e7324333e7713165436

Parents:

becbea965e6c5de8e8ab195c7f480cabc295ac0cd91423947d67c2ab2eaf1aae4a61f9f2988e9510

Message:

Merge pull request #198 from mmklee/factory_clean_sw

Factory clean sw

File:

• factory/facBivar.cc (modified) (6 diffs)

factory/facBivar.cc

@@ -13 +13 @@
 #include "config.h"
 
-#include "assert.h"
+#include "cf_assert.h"
 #include "debug.h"
 #include "timing.h"
@@ -28 +28 @@
 TIMING_DEFINE_PRINT(fac_bi_hensel_lift)
 TIMING_DEFINE_PRINT(fac_bi_factor_recombination)
+TIMING_DEFINE_PRINT(fac_bi_evaluation)
+TIMING_DEFINE_PRINT(fac_bi_shift_to_zero)
 
 // bound on coeffs of f (cf. Musser: Multivariate Polynomial Factorization,
@@ -186 +188 @@
 }
 
-CFList
-earlyFactorDetection0 (CanonicalForm& F, CFList& factors,int& adaptedLiftBound,
-                      DegreePattern& degs, bool& success, int deg)
-{
-  DegreePattern bufDegs1= degs;
-  DegreePattern bufDegs2;
-  CFList result;
-  CFList T= factors;
-  CanonicalForm buf= F;
-  CanonicalForm LCBuf= LC (buf, Variable (1));
-  CanonicalForm g, quot;
-  CanonicalForm M= power (F.mvar(), deg);
-  adaptedLiftBound= 0;
-  int d= degree (F) + degree (LCBuf, F.mvar());
-  for (CFListIterator i= factors; i.hasItem(); i++)
-  {
-    if (!bufDegs1.find (degree (i.getItem(), 1)))
-      continue;
-    else
-    {
-      g= i.getItem() (0, 1);
-      g *= LCBuf;
-      g= mod (g, M);
-      if (fdivides (LC (g), LCBuf))
-      {
-        g= mulMod2 (i.getItem(), LCBuf, M);
-        g /= content (g, Variable (1));
-        if (fdivides (g, buf, quot))
-        {
-          result.append (g);
-          buf= quot;
-          d -= degree (g) + degree (LC (g, Variable (1)), F.mvar());
-          LCBuf= LC (buf, Variable (1));
-          T= Difference (T, CFList (i.getItem()));
-
-          // compute new possible degree pattern
-          bufDegs2= DegreePattern (T);
-          bufDegs1.intersect (bufDegs2);
-          bufDegs1.refine ();
-          if (bufDegs1.getLength() <= 1)
-          {
-            result.append (buf);
-            break;
-          }
-        }
-      }
-    }
-  }
-  adaptedLiftBound= d + 1;
-  if (d < deg)
-  {
-    factors= T;
-    degs= bufDegs1;
-    F= buf;
-    success= true;
-  }
-  if (bufDegs1.getLength() <= 1)
-    degs= bufDegs1;
-  return result;
-}
-
-
-CFList
-henselLiftAndEarly0 (CanonicalForm& A, bool& earlySuccess, CFList&
-                    earlyFactors, DegreePattern& degs, int& liftBound,
-                    const CFList& uniFactors, const CanonicalForm& eval)
-{
-  int sizeOfLiftPre;
-  int * liftPre= getLiftPrecisions (A, sizeOfLiftPre, degree (LC (A, 1), 2));
-
-  Variable x= Variable (1);
-  Variable y= Variable (2);
-  CFArray Pi;
-  CFList diophant;
-  CFList bufUniFactors= uniFactors;
-  bufUniFactors.insert (LC (A, x));
-  CFMatrix M= CFMatrix (liftBound, bufUniFactors.length() - 1);
-  earlySuccess= false;
-  int newLiftBound= 0;
-  int smallFactorDeg= tmin (11, liftPre [sizeOfLiftPre- 1] + 1);//this is a tunable parameter
-  if (smallFactorDeg >= liftBound || degree (A,y) <= 4)
-    henselLift12 (A, bufUniFactors, liftBound, Pi, diophant, M);
-  else if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
-  {
-    henselLift12 (A, bufUniFactors, smallFactorDeg, Pi, diophant, M);
-    earlyFactors= earlyFactorDetection0 (A, bufUniFactors, newLiftBound,
-                                        degs, earlySuccess,
-                                        smallFactorDeg);
-    if (degs.getLength() > 1 && !earlySuccess &&
-        smallFactorDeg != liftPre [sizeOfLiftPre-1] + 1)
-    {
-      if (newLiftBound > liftPre[sizeOfLiftPre-1]+1)
-      {
-        bufUniFactors.insert (LC (A, x));
-        henselLiftResume12 (A, bufUniFactors, smallFactorDeg,
-                            liftPre[sizeOfLiftPre-1] + 1, Pi, diophant, M);
-        earlyFactors= earlyFactorDetection0 (A, bufUniFactors, newLiftBound,
-                      degs, earlySuccess, liftPre[sizeOfLiftPre-1] + 1);
-      }
-    }
-    else if (earlySuccess)
-      liftBound= newLiftBound;
-    int i= sizeOfLiftPre - 1;
-    while (degs.getLength() > 1 && !earlySuccess && i - 1 >= 0)
-    {
-      if (newLiftBound > liftPre[i] + 1)
-      {
-        bufUniFactors.insert (LC (A, x));
-        henselLiftResume12 (A, bufUniFactors, liftPre[i] + 1,
-                            liftPre[i-1] + 1, Pi, diophant, M);
-        earlyFactors= earlyFactorDetection0 (A, bufUniFactors, newLiftBound,
-                      degs, earlySuccess, liftPre[i-1] + 1);
-      }
-      else
-      {
-        liftBound= newLiftBound;
-        break;
-      }
-      i--;
-    }
-    if (earlySuccess)
-      liftBound= newLiftBound;
-    //after here all factors are lifted to liftPre[sizeOfLiftPre-1]
-  }
-  else
-  {
-    henselLift12 (A, bufUniFactors, smallFactorDeg, Pi, diophant, M);
-    earlyFactors= earlyFactorDetection0 (A, bufUniFactors, newLiftBound,
-                                        degs, earlySuccess,
-                                        smallFactorDeg);
-    int i= 1;
-    while ((degree (A,y)/4)*i + 4 <= smallFactorDeg)
-      i++;
-    if (degs.getLength() > 1 && !earlySuccess)
-    {
-      bufUniFactors.insert (LC (A, x));
-      henselLiftResume12 (A, bufUniFactors, smallFactorDeg,
-                          (degree (A, y)/4)*i + 4, Pi, diophant, M);
-      earlyFactors= earlyFactorDetection0 (A, bufUniFactors, newLiftBound,
-                    degs, earlySuccess, (degree (A, y)/4)*i + 4);
-    }
-    while (degs.getLength() > 1 && !earlySuccess && i < 4)
-    {
-      if (newLiftBound > (degree (A, y)/4)*i + 4)
-      {
-        bufUniFactors.insert (LC (A, x));
-        henselLiftResume12 (A, bufUniFactors, (degree (A,y)/4)*i + 4,
-                            (degree (A, y)/4)*(i+1) + 4, Pi, diophant, M);
-        earlyFactors= earlyFactorDetection0 (A, bufUniFactors, newLiftBound,
-                      degs, earlySuccess, (degree (A, y)/4)*(i+1) + 4);
-      }
-      else
-      {
-        liftBound= newLiftBound;
-        break;
-      }
-      i++;
-    }
-    if (earlySuccess)
-      liftBound= newLiftBound;
-  }
-
-  return bufUniFactors;
-}
-
 CFList biFactorize (const CanonicalForm& F, const Variable& v)
 {
@@ -499 +336 @@
   {
     bufAeval= A;
+    TIMING_START (fac_bi_evaluation);
     bufAeval= evalPoint (A, bufEvaluation);
+    TIMING_END_AND_PRINT (fac_bi_evaluation, "time for eval point over Q: ");
 
     bufAeval2= buf;
+    TIMING_START (fac_bi_evaluation);
     bufAeval2= evalPoint (buf, bufEvaluation2);
+    TIMING_END_AND_PRINT (fac_bi_evaluation,
+                          "time for eval point over Q in y: ");
 
     // univariate factorization
-    TIMING_START (uni_factorize);
-
+    TIMING_START (fac_uni_factorizer);
     if (extension)
       bufUniFactors= conv (factorize (bufAeval, v));
     else
       bufUniFactors= conv (factorize (bufAeval, true));
-    TIMING_END_AND_PRINT (uni_factorize,
-                          "time for univariate factorization: ");
+    TIMING_END_AND_PRINT (fac_uni_factorizer,
+                          "time for univariate factorization over Q: ");
     DEBOUTLN (cerr, "prod (bufUniFactors)== bufAeval " <<
               (prod (bufUniFactors) == bufAeval));
 
-    TIMING_START (uni_factorize);
+    TIMING_START (fac_uni_factorizer);
     if (extension)
       bufUniFactors2= conv (factorize (bufAeval2, v));
     else
       bufUniFactors2= conv (factorize (bufAeval2, true));
-    TIMING_END_AND_PRINT (uni_factorize,
-                          "time for univariate factorization in y: ");
+    TIMING_END_AND_PRINT (fac_uni_factorizer,
+                          "time for univariate factorization in y over Q: ");
     DEBOUTLN (cerr, "prod (bufuniFactors2)== bufAeval2 " <<
               (prod (bufUniFactors2) == bufAeval2));
@@ -709 +550 @@
               (A, earlySuccess, earlyFactors, degs, liftBound,
                uniFactors, dummy, evaluation, b);
-  TIMING_END_AND_PRINT (fac_bi_hensel_lift, "time for hensel lifting: ");
+  TIMING_END_AND_PRINT (fac_bi_hensel_lift,
+                        "time for bivariate hensel lifting over Q: ");
   DEBOUTLN (cerr, "lifted factors= " << uniFactors);
 
@@ -728 +570 @@
   Off (SW_RATIONAL);
 
+  TIMING_START (fac_bi_factor_recombination);
   factors= factorRecombination (uniFactors, A, MODl, degs, 1,
                                 uniFactors.length()/2, b);
+  TIMING_END_AND_PRINT (fac_bi_factor_recombination,
+                        "time for bivariate factor recombination over Q: ");
 
   On (SW_RATIONAL);