Changeset 69c882 in git

Timestamp:

Feb 1, 2012, 5:19:00 PM (12 years ago)

Author:

Martin Lee <martinlee84@…>

Branches:

(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')

Children:

fdae2dc8d40153cbd857c71de2961e22d3f0a252

Parents:

1a3011e587832b2682cb4978c6d117754eaa2572

git-author:

Martin Lee <martinlee84@web.de>2012-02-01 17:19:00+01:00

git-committer:

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

Message:

chg: delete factors already found by early factor detection
chg: use "smaller" polynomial for factor recombination

File:

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

factory/facFqBivar.cc

@@ -651 +651 @@
         LCBuf= LC (buf, x);
         T= Difference (T, CFList (i.getItem()));
+        F= buf;
 
         // compute new possible degree pattern
@@ -667 +668 @@
   if (adaptedLiftBound < deg)
   {
+    degs= bufDegs1;
     success= true;
-    factors= T;
-    degs= bufDegs1;
-    F= buf;
   }
   if (bufDegs1.getLength() <= 1)
@@ -743 +742 @@
         {
           T= Difference (T, CFList (i.getItem()));
+          F= buf;
 
           // compute new possible degree pattern
@@ -763 +763 @@
   if (adaptedLiftBound < deg)
   {
+    degs= bufDegs1;
     success= true;
-    factors= T;
-    degs= bufDegs1;
-    F= buf;
   }
   if (bufDegs1.getLength() <= 1)
@@ -828 +826 @@
 
 void
-deleteFactors (const CFList& L, CFList& factors, const CanonicalForm& eval, bool
-               extension)
+deleteFactors (CFList& factors, int* factorsFoundIndex)
 {
-  int index;
-  CanonicalForm tmp1, tmp2;
-  CFListIterator j;
-  Variable y= Variable (2);
-  for (CFListIterator i= L; i.hasItem(); i++)
-  {
-    index= 1;
-    if (extension)
-      tmp1= mod (i.getItem(), y-eval);
+  CFList result;
+  int i= 0;
+  for (CFListIterator iter= factors; iter.hasItem(); iter++, i++)
+  {
+    if (factorsFoundIndex[i] == 1)
+      continue;
     else
-      tmp1= mod (i.getItem(), y);
-    tmp1 /= Lc (tmp1);
-    for (j= factors; j.hasItem(); j++, index++)
-    {
-      tmp2= mod (j.getItem(), y);
-      tmp2 /= Lc (tmp2);
-      if (tmp1 == tmp2)
-      {
-        index++;
-        j.remove(index);
-        break;
-      }
-    }
-  }
+      result.append (iter.getItem());
+  }
+  factors= result;
 }
 
@@ -887 +870 @@
   for (int i= 0; i < uniFactors.length(); i++)
     factorsFoundIndex [i]= 0;
+  CanonicalForm bufA= A;
 
   if (smallFactorDeg >= liftBound || degree (A,y) <= 4)
@@ -894 +878 @@
     henselLift12 (A, bufUniFactors, smallFactorDeg, Pi, diophant, M);
     if (!extension)
-      earlyFactorDetection (earlyFactors, A, bufUniFactors, newLiftBound,
+      earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
                             factorsFoundIndex, degs, earlySuccess,
                             smallFactorDeg);
     else
-      extEarlyFactorDetection (earlyFactors, A, bufUniFactors, newLiftBound,
+      extEarlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
                                factorsFoundIndex, degs, earlySuccess, info,
                                eval, smallFactorDeg);
@@ -910 +894 @@
                             liftPre[sizeOfLiftPre-1] + 1, Pi, diophant, M);
         if (!extension)
-          earlyFactorDetection (earlyFactors, A, bufUniFactors, newLiftBound,
+          earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
                                 factorsFoundIndex, degs, earlySuccess,
                                 liftPre[sizeOfLiftPre-1] + 1);
         else
-          extEarlyFactorDetection (earlyFactors, A, bufUniFactors, newLiftBound,
+          extEarlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
                                    factorsFoundIndex, degs, earlySuccess, info,
                                    eval, liftPre[sizeOfLiftPre-1] + 1);
@@ -931 +915 @@
                             liftPre[i-1] + 1, Pi, diophant, M);
         if (!extension)
-          earlyFactorDetection (earlyFactors, A, bufUniFactors, newLiftBound,
+          earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
                                 factorsFoundIndex, degs, earlySuccess,
                                 liftPre[i-1] + 1);
         else
-          extEarlyFactorDetection (earlyFactors, A, bufUniFactors, newLiftBound,
+          extEarlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
                                    factorsFoundIndex, degs, earlySuccess, info,
                                    eval, liftPre[i-1] + 1);
@@ -954 +938 @@
     henselLift12 (A, bufUniFactors, smallFactorDeg, Pi, diophant, M);
     if (!extension)
-      earlyFactorDetection (earlyFactors, A, bufUniFactors, newLiftBound,
+      earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
                             factorsFoundIndex, degs, earlySuccess,
                             smallFactorDeg);
     else
-      extEarlyFactorDetection (earlyFactors, A, bufUniFactors, newLiftBound,
+      extEarlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
                                factorsFoundIndex, degs, earlySuccess, info,
                                eval, smallFactorDeg);
@@ -971 +955 @@
                           dummy, Pi, diophant, M);
       if (!extension)
-        earlyFactorDetection (earlyFactors, A, bufUniFactors, newLiftBound,
+        earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
                               factorsFoundIndex, degs, earlySuccess, dummy);
       else
-        extEarlyFactorDetection (earlyFactors, A, bufUniFactors, newLiftBound,
+        extEarlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
                                  factorsFoundIndex, degs, earlySuccess, info,
                                  eval, dummy);
@@ -987 +971 @@
                             dummy, Pi, diophant, M);
         if (!extension)
-          earlyFactorDetection (earlyFactors, A, bufUniFactors, newLiftBound,
+          earlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
                                 factorsFoundIndex, degs, earlySuccess, dummy);
         else
-          extEarlyFactorDetection (earlyFactors, A, bufUniFactors, newLiftBound,
+          extEarlyFactorDetection (earlyFactors, bufA, bufUniFactors, newLiftBound,
                                    factorsFoundIndex, degs, earlySuccess, info,
                                    eval, dummy);
@@ -1003 +987 @@
     if (earlySuccess)
       liftBound= newLiftBound;
+  }
+
+  A= bufA;
+  if (earlyFactors.length() > 0 && degs.getLength() > 1)
+  {
+    liftBound= degree (A,y) + 1;
+    earlySuccess= true;
+    deleteFactors (bufUniFactors, factorsFoundIndex);
   }
 
@@ -4253 +4245 @@
     return earlyFactors;
   }
-  int sizeOldF= size (F);
-  CFList result;
-  CanonicalForm bufF= F;
-  if (earlyFactors.length() > 0)
-  {
-    for (CFListIterator i= earlyFactors; i.hasItem(); i++)
-      bufF /= i.getItem();
-  }
-
-  if (size (bufF) < sizeOldF)
-  {
-    H= bufF;
+  int sizeOldF= size (G);
+  if (size (F) < sizeOldF)
+  {
+    H= F;
     success= true;
     return earlyFactors;
@@ -4309 +4293 @@
   }
   Variable y= F.mvar();
-  CanonicalForm shiftedF= F (y - evaluation, y);
+  CanonicalForm shiftedF= G (y - evaluation, y);
   int sizeOldF= size (shiftedF);
-  CFList result;
-  CanonicalForm bufF= shiftedF;
-  if (earlyFactors.length() > 0)
-  {
-    for (CFListIterator i= earlyFactors; i.hasItem(); i++)
-    {
-      bufF /= i.getItem();
-      result.append (i.getItem());
-    }
-  }
-
-  if (size (bufF) < sizeOldF)
-  {
-    H= bufF (y + evaluation, y); //shift back to zero
+  if (size (F) < sizeOldF)
+  {
+    H= F (y + evaluation, y); //shift back to zero
     success= true;
-    return result;
+    return earlyFactors;
   }
   else