Changeset 7b5cb2 in git for factory/facSparseHensel.h

Timestamp:

Aug 8, 2012, 1:31:30 PM (12 years ago)

Author:

Martin Lee <martinlee84@…>

Branches:

(u'spielwiese', '17f1d200f27c5bd38f5dfc6e8a0879242279d1d8')

Children:

8267b8f9ab43170a4026e7e570df48db4601a748

Parents:

97686ecde8614d72ee9d26e96dc9344df8a7da32

git-author:

Martin Lee <martinlee84@web.de>2012-08-08 13:31:30+02:00

git-committer:

Martin Lee <martinlee84@web.de>2012-09-04 18:01:07+02:00

Message:

chg: faster retrieval of terms
chg: LucksWangSparseHeuristic now returns also partial factors

File:

• factory/facSparseHensel.h (modified) (8 diffs)

factory/facSparseHensel.h

@@ -18 +18 @@
 #include "cf_iter.h"
 #include "templates/ftmpl_functions.h"
+#include "cf_algorithm.h"
+#include "cf_map.h"
 
 /// compare polynomials
@@ -81 +83 @@
 /// quick sort helper function
 inline
-void quickSort (int lo, int hi, CFArray& A)
+void quickSort (int lo, int hi, CFArray& A, int l)
 {
   int i= lo, j= hi;
@@ -87 +89 @@
   while (i <= j)
   {
-    while (comp (A [i], tmp) < 0 && i < hi) i++;
-    while (comp (tmp, A[j]) < 0 && j > lo) j--;
+    if (l > 0)
+    {
+      while (comp (A [i], tmp, l) < 0 && i < hi) i++;
+      while (comp (tmp, A[j], l) < 0 && j > lo) j--;
+    }
+    else
+    {
+      while (comp (A [i], tmp) < 0 && i < hi) i++;
+      while (comp (tmp, A[j]) < 0 && j > lo) j--;
+    }
     if (i <= j)
     {
@@ -96 +106 @@
     }
   }
-  if (lo < j) quickSort (lo, j, A);
-  if (i < hi) quickSort (i, hi, A);
+  if (lo < j) quickSort (lo, j, A, l);
+  if (i < hi) quickSort (i, hi, A, l);
 }
 
 /// quick sort @a A
 inline
-void sort (CFArray& A)
-{
-  quickSort (0, A.size() - 1, A);
-}
+void sort (CFArray& A, int l= 0)
+{
+  quickSort (0, A.size() - 1, A, l);
+}
+
 
 /// find normalizing factors for @a biFactors and build monic univariate factors
@@ -187 +198 @@
 }
 
+/// helper function for getBiTerms
+inline CFArray
+getBiTerms_helper (const CanonicalForm& F, const CFMap& M)
+{
+  CFArray buf= CFArray (size (F));
+  int k= 0, level= F.level() - 1;
+  Variable x= F.mvar();
+  Variable y= Variable (F.level() - 1);
+  Variable one= Variable (1);
+  Variable two= Variable (2);
+  CFIterator j;
+  for (CFIterator i= F; i.hasTerms(); i++)
+  {
+    if (i.coeff().level() < level)
+    {
+      buf[k]= M (i.coeff())*power (one,i.exp());
+      k++;
+      continue;
+    }
+    j= i.coeff();
+    for (;j.hasTerms(); j++, k++)
+      buf[k]= power (one,i.exp())*power (two,j.exp())*M (j.coeff());
+  }
+  CFArray result= CFArray (k);
+  for (int i= 0; i < k; i++)
+    result[i]= buf[i];
+  return result;
+}
+
+/// get terms of @a F where F is considered a bivariate poly in Variable(1),
+/// Variable (2)
+inline CFArray
+getBiTerms (const CanonicalForm& F)
+{
+  if (F.inCoeffDomain())
+  {
+    CFArray result= CFArray (1);
+    result [0]= F;
+    return result;
+  }
+  if (F.isUnivariate())
+  {
+    CFArray result= CFArray (size(F));
+    int j= 0;
+    for (CFIterator i= F; i.hasTerms(); i++, j++)
+      result[j]= i.coeff()*power (F.mvar(), i.exp());
+    return result;
+  }
+
+  CanonicalForm G= F;
+
+  CFMap M;
+  M.newpair (Variable (1), F.mvar());
+  M.newpair (Variable (2), Variable (F.level() - 1));
+  G= swapvar (F, Variable (1), F.mvar());
+  G= swapvar (G, Variable (2), Variable (F.level() - 1));
+
+  CFArray result= getBiTerms_helper (G, M);
+  return result;
+}
+
 /// build a poly from entries in @a A
 inline CanonicalForm
@@ -197 +269 @@
 }
 
-/// group together elements in @a A, where entries in @a A are put put together
+/// group together elements in @a A, where entries in @a A are put together
 /// if they coincide up to level @a level
 inline void
@@ -213 +285 @@
     }
   }
+  if (A[n].isZero())
+    k--;
   CFArray B= CFArray (k);
   n++;
@@ -509 +583 @@
 ///
 /// @return @a LucksWangSparseHeuristic returns true if it was successful
-bool
+int
 LucksWangSparseHeuristic (const CanonicalForm& F,     ///<[in] polynomial to be
                                                       ///< factored