Changeset f8ac2df in git for factory/facBivar.cc

Timestamp:

Jan 9, 2012, 2:01:10 PM (12 years ago)

Author:

Martin Lee <martinlee84@…>

Branches:

(u'spielwiese', 'd0474371d8c5d8068ab70bfb42719c97936b18a6')

Children:

97a0599a2c91cf3fd4b1b2efcdf9d0a40caf5746

Parents:

4bafa67969ab030397c6410e512aadf5574be0dc

git-author:

Martin Lee <martinlee84@web.de>2012-01-09 14:01:10+01:00

git-committer:

Martin Lee <martinlee84@web.de>2012-04-04 14:42:24+02:00

Message:

chg: replaced Hensel lifting and early factor detection by a
     faster version

File:

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

factory/facBivar.cc

@@ -22 +22 @@
 #include "facFqBivar.h"
 #include "facBivar.h"
+#include "facHensel.h"
 
 #ifdef HAVE_NTL
@@ -81 +82 @@
     i++;
   } while (1);
+}
+
+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;
 }
 
@@ -365 +531 @@
   int liftBound= degree (A, y) + 1;
 
-  ExtensionInfo dummy= ExtensionInfo (false);
   bool earlySuccess= false;
   CFList earlyFactors;
-  TIMING_START (hensel_lift12);
-  uniFactors= henselLiftAndEarly 
+  TIMING_START (fac_hensel_lift);
+  uniFactors= henselLiftAndEarly0
              (A, earlySuccess, earlyFactors, degs, liftBound,
-              uniFactors, dummy, evaluation);
-  TIMING_END_AND_PRINT (hensel_lift12, "time for hensel lifting: ");
+              uniFactors, evaluation);
+  TIMING_END_AND_PRINT (fac_hensel_lift, "time for hensel lifting: ");
   DEBOUTLN (cerr, "lifted factors= " << uniFactors);