Changeset 9e2029c in git

Timestamp:

Jun 5, 2014, 5:11:56 PM (10 years ago)

Author:

Martin Lee <martinlee84@…>

Branches:

(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')

Children:

0bd659380ba176abcaad091e0fdef5817cb9954d

Parents:

f8df35286530f57c88ffeb98595d16aa5edd60f4

git-author:

Martin Lee <martinlee84@web.de>2014-06-05 17:11:56+02:00

git-committer:

Martin Lee <martinlee84@web.de>2014-06-17 14:08:30+02:00

Message:

chg: more checks for one to one correspondence of bi. factors and multi. factors

Location:

factory

Files:

• facAbsFact.cc (modified) (2 diffs)
• facFactorize.cc (modified) (2 diffs)
• facFqFactorize.cc (modified) (12 diffs)
• facFqFactorize.h (modified) (2 diffs)

factory/facAbsFact.cc

@@ -460 +460 @@
   else if (biFactors.length() > minFactorsLength)
     refineBiFactors (A, biFactors, Aeval2, evaluation, minFactorsLength);
+  minFactorsLength= tmin (minFactorsLength, biFactors.length());
+
+  CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
+
+  sortByUniFactors (Aeval2, lengthAeval2, uniFactors, biFactors, evaluation);
+
+  minFactorsLength= tmin (minFactorsLength, biFactors.length());
+
+  if (minFactorsLength == 1)
+  {
+    factors.append (CFAFactor (A, 1, 1));
+    decompress (factors, N);
+    if (isOn (SW_RATIONAL))
+      normalize (factors);
+    delete [] Aeval2;
+    return factors;
+  }
 
   bool found= false;
@@ -502 +519 @@
     }
   }
-
-  CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
-
-  sortByUniFactors (Aeval2, lengthAeval2, uniFactors, evaluation);
 
   CFList * oldAeval= new CFList [lengthAeval2];

factory/facFactorize.cc

@@ -394 +394 @@
   minFactorsLength= tmin (minFactorsLength, biFactors.length());
 
+  CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
+
+  sortByUniFactors (Aeval2, lengthAeval2, uniFactors, biFactors, evaluation);
+
+  minFactorsLength= tmin (minFactorsLength, biFactors.length());
+
+  if (minFactorsLength == 1)
+  {
+    factors.append (A);
+    appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
+    if (isOn (SW_RATIONAL))
+      normalize (factors);
+    delete [] Aeval2;
+    return factors;
+  }
+
   if (differentSecondVar == lengthAeval2)
   {
@@ -421 +437 @@
     }
   }
-
-  CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
-
-  sortByUniFactors (Aeval2, lengthAeval2, uniFactors, evaluation);
 
   CFList * oldAeval= new CFList [lengthAeval2];

factory/facFqFactorize.cc

@@ -2004 +2004 @@
 }
 
+void
+checkHelper (const CanonicalForm& f1, CFList& factors1, CFList& factors2,
+             CFList& l1, CFList& l2)
+{
+  CanonicalForm g1= f1, g2;
+  CFListIterator iter1= factors1, iter2= factors2;
+  for (; iter1.hasItem(); iter1++, iter2++)
+  {
+    g2= gcd (g1, iter1.getItem());
+    if (!g2.inCoeffDomain())
+    {
+      l1.append (iter1.getItem());
+      l2.append (iter2.getItem());
+      g1 /= g2;
+    }
+  }
+  factors1= Difference (factors1, l1);
+  factors2= Difference (factors2, l2);
+}
+
+/// check if univariate factors @a factors2 of @a factors3 coincide with
+/// univariate factors of @a factors1 and recombine if necessary.
+/// The recombined factors of @a factors1 are returned and @a factors3 is
+/// recombined accordingly.
+CFList
+checkOneToOne (const CFList& factors1, const CFList& factors2, CFList& factors3,
+               const CanonicalForm& evalPoint, const Variable& x)
+{
+  CFList uniFactorsOfFactors1;
+  CFList result, result2;
+  CFList bad1= factors2;
+  CFListIterator iter, iter2, iter3;
+  CanonicalForm tmp;
+  int pos;
+
+  for (iter= factors1; iter.hasItem(); iter++)
+  {
+    tmp= iter.getItem() (evalPoint, x);
+    tmp /= Lc (tmp);
+    if (pos= findItem (factors2, tmp))
+    {
+      result2.append (getItem (factors3, pos));
+      result.append (iter.getItem());
+      bad1= Difference (bad1, CFList (tmp));
+    }
+    else
+      uniFactorsOfFactors1.append (tmp);
+  }
+
+  CFList bad2, bad3;
+  bad2= Difference (factors1, result);
+  bad3= Difference (factors3, result2);
+  CFList tmp2, tmp3;
+  CanonicalForm g1, g2, g3, g4;
+
+  while (!uniFactorsOfFactors1.isEmpty())
+  {
+    tmp= uniFactorsOfFactors1.getFirst();
+    checkHelper (tmp, bad1, bad3, tmp2, tmp3);
+    g1= prod (tmp2);
+    g2= prod (tmp3);
+    tmp2= CFList();
+    tmp3= CFList();
+    checkHelper (g1, uniFactorsOfFactors1, bad2, tmp2, tmp3);
+    g3= prod (tmp2);
+    g4= prod (tmp3);
+    tmp2= CFList();
+    tmp3= CFList();
+    do
+    {
+      checkHelper (g3, bad1, bad3, tmp2, tmp3);
+      g1 *= prod (tmp2);
+      g2 *= prod (tmp3);
+      tmp2= CFList();
+      tmp3= CFList();
+      checkHelper (g1, uniFactorsOfFactors1, bad2, tmp2, tmp3);
+      g3 *= prod (tmp2);
+      g4 *= prod (tmp3);
+      tmp2= CFList();
+      tmp3= CFList();
+    } while (!bad2.isEmpty() && !bad3.isEmpty());
+    result.append (g4);
+    result2.append (g2);
+  }
+
+  factors3= result2;
+  return result;
+}
+
 //recombine bivariate factors in case one bivariate factorization yields less
 // factors than the other
@@ -2021 +2110 @@
   CFArray TT;
   TT= copy (factors1);
+  int recombinations= 0;
   while (T.length() >= 2*s && s <= thres)
   {
@@ -2028 +2118 @@
       {
         delete [] v;
-        result.append (prod (T));
+        if (recombinations == factors2.length() - 1)
+          result.append (prod (T));
+        else
+          result= Union (result, T);
         return result;
       }
@@ -2037 +2130 @@
       if (find (factors2, buf))
       {
+        recombinations++;
         T= Difference (T, S);
         result.append (prod (S));
@@ -2047 +2141 @@
     if (T.length() < 2*s || T.length() == s)
     {
+      if (recombinations == factors2.length() - 1)
+        result.append (prod (T));
+      else
+        result= Union (result, T);
       delete [] v;
-      result.append (prod (T));
       return result;
     }
@@ -2059 +2156 @@
   if (T.length() < 2*s)
   {
-    result.append (prod (T));
+    result= Union (result, T);
     return result;
   }
@@ -2134 +2231 @@
 
 void sortByUniFactors (CFList*& Aeval, int AevalLength,
-                       const CFList& uniFactors, const CFList& evaluation
+                       CFList& uniFactors, CFList& biFactors,
+                       const CFList& evaluation
                       )
 {
@@ -2143 +2241 @@
   CFList LCs, buf;
   CFArray l;
-  int pos, index;
+  int pos, index, checklength;
   bool leaveLoop=false;
+recurse:
   for (int j= 0; j < AevalLength; j++)
   {
@@ -2173 +2272 @@
                                  Aeval[j].length() - uniFactors.length() + 1,
                                  evalPoint, v);
+
+      checklength= biFactors.length();
+      Aeval[j]= checkOneToOne (Aeval[j], uniFactors, biFactors, evalPoint, v);
+      if (checklength > biFactors.length())
+      {
+        uniFactors= buildUniFactors (biFactors, evaluation.getLast(),
+                                     Variable (2));
+        goto recurse;
+      }
 
       buf= buildUniFactors (Aeval[j], evalPoint, v);
@@ -2776 +2884 @@
 multiFactorize (const CanonicalForm& F, const ExtensionInfo& info)
 {
-
   if (F.inCoeffDomain())
     return CFList (F);
@@ -3091 +3198 @@
   minFactorsLength= tmin (minFactorsLength, biFactors.length());
 
+  CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
+
+  sortByUniFactors (Aeval2, lengthAeval2, uniFactors, biFactors, evaluation);
+
+  minFactorsLength= tmin (minFactorsLength, biFactors.length());
+
+  if (minFactorsLength == 1)
+  {
+    if (extension)
+    {
+      CFList source, dest;
+      A= mapDown (A, info, source, dest);
+    }
+    factors.append (A);
+    appendSwapDecompress (factors, contentAFactors, N, swapLevel,
+                          swapLevel2, x);
+    if (!extension)
+      normalize (factors);
+    delete [] Aeval2;
+    return factors;
+  }
+
   if (differentSecondVar == lengthAeval2)
   {
@@ -3123 +3252 @@
     }
   }
-
-  CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
-
-  sortByUniFactors (Aeval2, lengthAeval2, uniFactors, evaluation);
 
   CFList * oldAeval= new CFList [lengthAeval2]; //TODO use bufAeval2 for this

factory/facFqFactorize.h

@@ -565 +565 @@
 
 /// refine a bivariate factorization of A with l factors to one with
-/// minFactorsLength
+/// minFactorsLength if possible
 void
 refineBiFactors (const CanonicalForm& A,  ///< [in] some poly
@@ -589 +589 @@
 
 /// sort bivariate factors in Aeval such that their corresponding univariate
-/// factors coincide with uniFactors
+/// factors coincide with uniFactors, uniFactors and biFactors may get
+/// recombined if necessary
 void sortByUniFactors (CFList*& Aeval,          ///< [in,out] array of bivariate
                                                 ///< factors
                        int AevalLength,         ///< [in] length of Aeval
-                       const CFList& uniFactors,///< [in] univariate factors
+                       CFList& uniFactors,      ///< [in,out] univariate factors
+                       CFList& biFactors,       ///< [in,out] bivariate factors
                        const CFList& evaluation ///< [in] evaluation point
                       );