Changeset 69076c in git

Timestamp:

Jan 23, 2012, 10:56:15 PM (12 years ago)

Author:

Martin Lee <martinlee84@…>

Branches:

(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')

Children:

db65ada582680024acbac9836a6e6efb6100c8a9

Parents:

a541144c391fb958d4c9ea1ac173dc1c117fb51f

git-author:

Martin Lee <martinlee84@web.de>2012-01-23 22:56:15+01:00

git-committer:

Oleksandr Motsak <motsak@mathematik.uni-kl.de>2012-02-10 14:16:44+01:00

Message:

chg: use shape of Newton polygon for factor detection and
     use lower lift bound

File:

• factory/facFqBivar.cc (modified) (2 diffs)

factory/facFqBivar.cc

@@ -853 +853 @@
   bool extension= info.isInExtension();
 
+  int sizeOfLiftPre;
+  int * liftPre= getLiftPrecisions (A, sizeOfLiftPre, degree (LC (A, 1), 2));
+
   Variable x= Variable (1);
   Variable y= Variable (2);
@@ -862 +865 @@
   earlySuccess= false;
   int newLiftBound= 0;
-  int smallFactorDeg= 11; //this is a tunable parameter
-  if (smallFactorDeg >= liftBound)
+
+  int smallFactorDeg= tmin (11, liftPre [sizeOfLiftPre- 1] + 1);//this is a tunable parameter
+  int dummy;
+  if (smallFactorDeg >= liftBound || degree (A,y) <= 4)
     henselLift12 (A, bufUniFactors, liftBound, Pi, diophant, M);
-  else if (smallFactorDeg >= degree (A, y) + 1)
-  {
-    henselLift12 (A, bufUniFactors, degree (A, y) + 1, Pi, diophant, M);
+  else if (sizeOfLiftPre > 1 && sizeOfLiftPre < 30)
+  {
+    henselLift12 (A, bufUniFactors, smallFactorDeg, Pi, diophant, M);
     if (!extension)
       earlyFactors= earlyFactorDetection (A, bufUniFactors, newLiftBound,
-                     degs, earlySuccess, degree (A, y) + 1);
+                     degs, earlySuccess, smallFactorDeg);
     else
       earlyFactors= extEarlyFactorDetection (A, bufUniFactors,
                      newLiftBound, degs, earlySuccess, info, eval,
-                     degree (A, y) + 1);
-    if (degs.getLength() > 1 && !earlySuccess)
-    {
-      if (newLiftBound > degree (A, y) + 1)
-      {
-        liftBound= newLiftBound;
-        bufUniFactors.insert (LC(A, x));
-        henselLiftResume12 (A, bufUniFactors, degree (A, y) + 1, liftBound,
-                            Pi, diophant, M);
+                     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);
+        if (!extension)
+          earlyFactors= earlyFactorDetection (A, bufUniFactors, newLiftBound,
+                        degs, earlySuccess, liftPre[sizeOfLiftPre-1] + 1);
+        else
+          earlyFactors= extEarlyFactorDetection (A, bufUniFactors,
+                        newLiftBound, degs, earlySuccess, info, eval,
+                        liftPre[sizeOfLiftPre-1] + 1);
       }
     }
     else if (earlySuccess)
       liftBound= newLiftBound;
-  }
-  else if (smallFactorDeg < degree (A, y) + 1)
+
+    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);
+        if (!extension)
+          earlyFactors= earlyFactorDetection (A, bufUniFactors, newLiftBound,
+                        degs, earlySuccess, liftPre[i-1] + 1);
+        else
+          earlyFactors= extEarlyFactorDetection (A, bufUniFactors,
+                        newLiftBound, degs, earlySuccess, info, eval,
+                        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);
     if (!extension)
       earlyFactors= earlyFactorDetection (A, bufUniFactors, newLiftBound,
-                                           degs, earlySuccess,
-                                           smallFactorDeg);
+                     degs, earlySuccess, smallFactorDeg);
     else
       earlyFactors= extEarlyFactorDetection (A, bufUniFactors,
-                     newLiftBound, degs, earlySuccess,
-                     info, eval, smallFactorDeg);
-    if (degs.getLength() > 1 && !earlySuccess)
+                     newLiftBound, degs, earlySuccess, info, eval,
+                     smallFactorDeg);
+    int i= 1;
+    while ((degree (A,y)/4)*i + 4 <= smallFactorDeg)
+      i++;
+    dummy= tmin (degree (A,y)+1, (degree (A,y)/4)*i+4);
+    if (degs.getLength() > 1 && !earlySuccess && dummy > smallFactorDeg)
     {
       bufUniFactors.insert (LC (A, x));
-      henselLiftResume12 (A, bufUniFactors, smallFactorDeg, degree (A, y)
-                          + 1, Pi, diophant, M);
+      henselLiftResume12 (A, bufUniFactors, smallFactorDeg,
+                          dummy, Pi, diophant, M);
       if (!extension)
         earlyFactors= earlyFactorDetection (A, bufUniFactors, newLiftBound,
-                       degs, earlySuccess, degree (A, y) + 1);
+                      degs, earlySuccess, dummy);
       else
         earlyFactors= extEarlyFactorDetection (A, bufUniFactors,
-                       newLiftBound, degs, earlySuccess,
-                       info, eval, degree(A,y) + 1);
-      if (degs.getLength() > 1 && !earlySuccess)
-      {
-        if (newLiftBound > degree (A, y) + 1)
-        {
-          bufUniFactors.insert (LC(A, x));
-          henselLiftResume12 (A, bufUniFactors, degree (A, y) + 1, liftBound,
-                              Pi, diophant, M);
-        }
-      }
-      else if (earlySuccess)
+                      newLiftBound, degs, earlySuccess, info, eval,
+                      dummy);
+    }
+    while (degs.getLength() > 1 && !earlySuccess && i < 4)
+    {
+      if (newLiftBound >= dummy)
+      {
+        bufUniFactors.insert (LC (A, x));
+        dummy= tmin (degree (A,y)+1, (degree (A,y)/4)*(i+1)+4);
+        henselLiftResume12 (A, bufUniFactors, (degree (A,y)/4)*i + 4,
+                            dummy, Pi, diophant, M);
+        if (!extension)
+          earlyFactors= earlyFactorDetection (A, bufUniFactors, newLiftBound,
+                        degs, earlySuccess, dummy);
+        else
+          earlyFactors= extEarlyFactorDetection (A, bufUniFactors,
+                        newLiftBound, degs, earlySuccess, info, eval,
+                        dummy);
+      }
+      else
+      {
         liftBound= newLiftBound;
-    }
-    else if (earlySuccess)
+        break;
+      }
+      i++;
+    }
+    if (earlySuccess)
       liftBound= newLiftBound;
   }
-  if (newLiftBound > 0)
-    liftBound= newLiftBound;
+
+  if (!earlySuccess)
+    liftBound= degree (A,y) + 1;
+
+  delete [] liftPre;
+
   return bufUniFactors;
 }