Changeset 8256fd in git

Timestamp:

Jul 16, 2012, 11:15:58 AM (12 years ago)

Author:

Martin Lee <martinlee84@…>

Branches:

(u'fieker-DuVal', '117eb8c30fc9e991c4decca4832b1d19036c4c65')(u'spielwiese', 'b4f17ed1d25f93d46dbe29e4b499baecc2fd51bb')

Children:

faa1b8d6e411251ef4c85b56aefa21b74f5db582

Parents:

67a39b21729f20cbd2a5d3b6e61a60d67aa387d9

git-author:

Martin Lee <martinlee84@web.de>2012-07-16 11:15:58+02:00

git-committer:

Martin Lee <martinlee84@web.de>2012-09-04 17:25:37+02:00

Message:

fix: possible hang in multivariate factorization

Location:

factory

Files:

• facFactorize.cc (modified) (10 diffs)
• facFqFactorize.cc (modified) (9 diffs)

factory/facFactorize.cc

@@ -267 +267 @@
   }
 
-  CFMap N;
-  CanonicalForm F= compress (LCF, N);
+  CFMap N, M;
+  CFArray dummy= CFArray (1);
+  dummy [0]= LCF;
+  compress (dummy, M, N);
+  CanonicalForm F= M (LCF);
   if (LCF.isUnivariate())
   {
@@ -311 +314 @@
   CFList factors= LCFFactors;
 
-  CFMap dummy;
   for (CFListIterator i= factors; i.hasItem(); i++)
-    i.getItem()= compress (i.getItem(), dummy);
+    i.getItem()= M (i.getItem());
 
   CanonicalForm sqrfPartF;
@@ -333 +335 @@
   {
     int lev= 0;
-    for (int i= 1; i <= LCF.level(); i++)
-    {
-      if(degree (LCF, i) > 0)
-      {
-        lev= i - 1;
-        break;
-      }
-    }
     for (int i= 0; i < length; i++)
     {
@@ -355 +349 @@
             allConstant= false;
             y= Variable (iter.getItem().level());
+            lev= M(y).level();
           }
         }
@@ -364 +359 @@
           iter.getItem()= swapvar (iter.getItem(), x, y);
         bufF= F;
-        z= Variable (y.level() - lev);
+        z= Variable (lev);
         bufF= swapvar (bufF, x, z);
         bufBufFactors= bufFactors;
@@ -536 +531 @@
   else
   {
-    factors= CFList (oldSqrfPartF);
+    CanonicalForm contF=content (oldSqrfPartF,1);
+    factors= CFList (oldSqrfPartF/contF);
     interMedResult= recoverFactors (oldSqrfPartF, factors);
   }
@@ -799 +795 @@
     if (!zeroOccured)
     {
-      factors= sparseHeuristic (A, biFactors, Aeval2, evaluation, minFactorsLength);
+      factors= sparseHeuristic (A, biFactors, Aeval2, evaluation,
+                                minFactorsLength);
       if (factors.length() == biFactors.length())
       {
@@ -832 +829 @@
   {
     A= swapvar (A, y, w);
-    for (int i= 0; i < A.level() - 2; i++)
-    {
-      if (oldAeval[i].isEmpty())
-        continue;
-      if (oldAeval[i].getFirst().level() == w.level())
-      {
-        biFactors= CFList();
-        for (CFListIterator iter= oldAeval [i]; iter.hasItem(); iter++)
-          biFactors.append (swapvar (iter.getItem(), w, y));
-      }
-    }
     int i= A.level();
     CanonicalForm evalPoint;
@@ -854 +840 @@
         evaluation.append (evalPoint);
         break;
+      }
+    }
+    for (i= 0; i < A.level() - 2; i++)
+    {
+      if (oldAeval[i].isEmpty())
+        continue;
+      if (oldAeval[i].getFirst().level() == w.level())
+      {
+        CFArray tmp= copy (oldAeval[i]);
+        for (int ii= 0; ii < tmp.size(); ii++)
+          tmp[ii]= swapvar (tmp[ii], w, y);
+        CFArray tmp2= CFArray (tmp.size());
+        CanonicalForm buf;
+        for (int ii= 0; ii < tmp.size(); ii++)
+        {
+          buf= tmp[ii] (evaluation.getLast(),y);
+          buf /= Lc (buf);
+          tmp2[findItem (uniFactors, buf)-1]=tmp[ii];
+        }
+        biFactors= CFList();
+        for (int j= 0; j < tmp2.size(); j++)
+          biFactors.append (tmp2[j]);
       }
     }
@@ -906 +914 @@
     if (check == factors.length())
     {
+
+      if (w.level() != 1)
+      {
+        for (CFListIterator iter= factors; iter.hasItem(); iter++)
+          iter.getItem()= swapvar (iter.getItem(), w, y);
+      }
+
       appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
       normalize (factors);

factory/facFqFactorize.cc

@@ -1182 +1182 @@
     {
       g= gcd (i.getItem().factor(), j.getItem().factor());
-      if (degree (g) > 0)
+      if (degree (g,1) > 0)
       {
         j.getItem()= CFFactor (j.getItem().factor()/g, j.getItem().exp());
@@ -1432 +1432 @@
   }
 
-  CFMap N;
-  CanonicalForm F= compress (LCF, N);
+  CFMap N, M;
+  CFArray dummy= CFArray (1);
+  dummy [0]= LCF;
+  compress (dummy, M, N);
+  CanonicalForm F= M (LCF);
   if (LCF.isUnivariate())
   {
@@ -1476 +1479 @@
   CFList factors= LCFFactors;
 
-  CFMap dummy;
   for (CFListIterator i= factors; i.hasItem(); i++)
-    i.getItem()= compress (i.getItem(), dummy);
+    i.getItem()= M (i.getItem());
 
   CanonicalForm sqrfPartF;
@@ -1498 +1500 @@
     int lev= 0;
     // LCF is non-constant here
-    for (int i= 1; i <= LCF.level(); i++)
-    {
-      if(degree (LCF, i) > 0)
-      {
-        lev= i - 1;
-        break;
-      }
-    }
     CFList bufBufFactors;
     CanonicalForm bufF, swap;
@@ -1520 +1514 @@
             allConstant= false;
             y= Variable (iter.getItem().level());
+            lev= M(y).level();
           }
         }
@@ -1529 +1524 @@
           iter.getItem()= swapvar (iter.getItem(), x, y);
         bufF= F;
-        z= Variable (y.level() - lev);
+        z= Variable (lev);
         bufF= swapvar (bufF, x, z);
         bufBufFactors= bufFactors;
@@ -1700 +1695 @@
   else
   {
-    factors= CFList (oldSqrfPartF);
+    CanonicalForm contF=content (oldSqrfPartF,1);
+    factors= CFList (oldSqrfPartF/contF);
     interMedResult= recoverFactors (oldSqrfPartF, factors);
   }
@@ -2547 +2543 @@
   {
     A= swapvar (A, y, v);
-    for (int i= 0; i < A.level() - 2; i++)
-    {
-      if (oldAeval[i].isEmpty())
-        continue;
-      if (oldAeval[i].getFirst().level() == v.level())
-      {
-        biFactors= CFList();
-        for (CFListIterator iter= oldAeval [i]; iter.hasItem(); iter++)
-          biFactors.append (swapvar (iter.getItem(), v, y));
-      }
-    }
     int i= A.level();
     CanonicalForm evalPoint;
@@ -2569 +2554 @@
         evaluation.append (evalPoint);
         break;
+      }
+    }
+    for (i= 0; i < A.level() - 2; i++)
+    {
+      if (oldAeval[i].isEmpty())
+        continue;
+      if (oldAeval[i].getFirst().level() == v.level())
+      {
+        CFArray tmp= copy (oldAeval[i]);
+        for (int ii= 0; ii < tmp.size(); ii++)
+          tmp[ii]= swapvar (tmp[ii], v, y);
+        CFArray tmp2= CFArray (tmp.size());
+        CanonicalForm buf;
+        for (int ii= 0; ii < tmp.size(); ii++)
+        {
+          buf= tmp[ii] (evaluation.getLast(),y);
+          buf /= Lc (buf);
+          tmp2[findItem (uniFactors, buf)-1]=tmp[ii];
+        }
+        biFactors= CFList();
+        for (int j= 0; j < tmp2.size(); j++)
+          biFactors.append (tmp2[j]);
       }
     }