Index: factory/Makefile.am
===================================================================
--- factory/Makefile.am	(revision 6deedd6650206f3f5a123f8dfbd41e449fd35f93)
+++ factory/Makefile.am	(revision 91788c087460478b3feb0c0461c30cb0383129fe)
@@ -69,4 +69,5 @@
 		facHensel.cc \
 		facIrredTest.cc \
+		facSparseHensel.cc \
 		fieldGCD.cc \
 		ffops.cc \
@@ -152,4 +153,5 @@
 		facHensel.h \
 		facIrredTest.h \
+		facSparseHensel.h \
 		fieldGCD.h \
 		ffops.h \
Index: factory/facFactorize.cc
===================================================================
--- factory/facFactorize.cc	(revision 6deedd6650206f3f5a123f8dfbd41e449fd35f93)
+++ factory/facFactorize.cc	(revision 91788c087460478b3feb0c0461c30cb0383129fe)
@@ -29,4 +29,5 @@
 #include "algext.h"
 #include "cf_reval.h"
+#include "facSparseHensel.h"
 
 #ifdef HAVE_NTL
Index: factory/facFqFactorize.cc
===================================================================
--- factory/facFqFactorize.cc	(revision 6deedd6650206f3f5a123f8dfbd41e449fd35f93)
+++ factory/facFqFactorize.cc	(revision 91788c087460478b3feb0c0461c30cb0383129fe)
@@ -31,4 +31,5 @@
 #include "cf_map_ext.h"
 #include "algext.h"
+#include "facSparseHensel.h"
 
 #ifdef HAVE_NTL
@@ -39,433 +40,4 @@
 TIMING_DEFINE_PRINT(fac_hensel_lift)
 TIMING_DEFINE_PRINT(fac_factor_recombination)
-
-CFList
-recombination (const CFList& factors1, const CFList& factors2, int s, int thres,
-               const CanonicalForm& evalPoint, const Variable& x);
-
-static
-int comp (const CanonicalForm& A, const CanonicalForm& B)
-{
-  if (A.inCoeffDomain() && !B.inCoeffDomain())
-    return -1;
-  else if (!A.inCoeffDomain() && B.inCoeffDomain())
-    return 1;
-  else if (A.inCoeffDomain() && B.inCoeffDomain())
-    return 0;
-  else if (degree (A, 1) > degree (B, 1))
-    return 1;
-  else if (degree (A, 1) < degree (B, 1))
-    return -1;
-  // here A and B are not in CoeffDomain
-  if (degree (A) > degree (B))
-    return 1;
-  else if (degree (A) < degree (B))
-    return -1;
-  return 0;
-}
-
-static
-void swap (CFArray& A, int i, int j)
-{
-  CanonicalForm tmp= A[i];
-  A[i]= A[j];
-  A[j]= tmp;
-}
-
-static
-void quickSort (int lo, int hi, CFArray& A)
-{
-  int i= lo, j= hi;
-  CanonicalForm tmp= A[(lo+hi)/2];
-  while (i <= j)
-  {
-    while (comp (A [i], tmp) < 0 && i < hi) i++;
-    while (comp (tmp, A[j]) < 0 && j > lo) j--;
-    if (i <= j)
-    {
-      swap (A, i, j);
-      i++;
-      j--;
-    }
-  }
-  if (lo < j) quickSort (lo, j, A);
-  if (i < hi) quickSort (i, hi, A);
-}
-
-static
-void sort (CFArray& A)
-{
-  quickSort (0, A.size() - 1, A);
-}
-
-CFList
-findNormalizingFactor1 (const CFList& biFactors, const CanonicalForm& evalPoint,
-                        CFList& uniFactors)
-{
-  CFList result;
-  CanonicalForm tmp;
-  for (CFListIterator i= biFactors; i.hasItem(); i++)
-  {
-    tmp= i.getItem() (evalPoint);
-    uniFactors.append (tmp /Lc (tmp));
-    result.append (Lc (tmp));
-  }
-  return result;
-}
-
-CFList
-findNormalizingFactor2 (CFList& biFactors, const CanonicalForm& evalPoint,
-                        const CFList& uniFactors)
-{
-  CFList result;
-  CFList uniBiFactors= biFactors;
-  CFList newBiFactors;
-  CFList l;
-  int pos;
-  CFListIterator iter;
-  for (iter= uniBiFactors; iter.hasItem(); iter++)
-  {
-    iter.getItem()= iter.getItem() (evalPoint);
-    l.append (Lc (iter.getItem()));
-    iter.getItem() /= Lc (iter.getItem());
-  }
-  for (CFListIterator i= uniFactors; i.hasItem(); i++)
-  {
-    pos= findItem (uniBiFactors, i.getItem());
-    newBiFactors.append (getItem (biFactors, pos));
-    result.append (getItem (l, pos));
-  }
-  biFactors= newBiFactors;
-  return result;
-}
-
-CFArray
-getTerms (const CanonicalForm& F)
-{
-  CFArray result= CFArray (size (F));
-  int j= 0;
-  Variable x= F.mvar();
-  Variable y= Variable (1);
-  CFIterator k;
-  for (CFIterator i= F; i.hasTerms(); i++)
-  {
-    for (k= i.coeff(); k.hasTerms(); k++, j++)
-      result[j]= k.coeff()*power (x,i.exp())*power (y,k.exp());
-  }
-  sort (result);
-  return result;
-}
-
-void getTerms (const CFList& F, CFArray* result)
-{
-  int j= 0;
-  for (CFListIterator i= F; i.hasItem(); i++, j++)
-    result[j]= getTerms (i.getItem());
-}
-
-CFArray
-evaluate (const CFArray& A, const CanonicalForm& eval, const Variable& y)
-{
-  int j= A.size();
-  CFArray result= CFArray (j);
-  for (int i= 0; i < j; i++)
-    result [i]= A[i] (eval, y);
-  return result;
-}
-
-CFArray*
-evaluate (CFArray* const& A, int sizeA, const CanonicalForm& eval,
-          const Variable& y)
-{
-  CFArray* result= new CFArray [sizeA];
-  for (int i= 0; i < sizeA; i++)
-    result[i]= evaluate (A[i], eval, y);
-  return result;
-}
-
-CFList normalize (const CFList& L, const CFList& normalizingFactor)
-{
-  CFList result;
-  CFListIterator j= normalizingFactor;
-  for (CFListIterator i= L; i.hasItem(); i++, j++)
-    result.append (i.getItem() / j.getItem());
-  return result;
-}
-
-int search (const CFArray& A, const CanonicalForm& F, int i, int j)
-{
-  for (; i < j; i++)
-    if (A[i] == F)
-      return i;
-  return -1;
-}
-
-CanonicalForm patch (const CanonicalForm& F1, const CanonicalForm& F2,
-                     const CanonicalForm& eval)
-{
-  CanonicalForm result= F1;
-  if (F2.level() != 1)
-  {
-    int d= degree (F2);
-    result *= power (F2.mvar(), d);
-    result /= power (eval, d);
-  }
-  return result;
-}
-
-CFList
-sparseHeuristic (const CanonicalForm& A, const CFList& biFactors,
-                 CFList*& moreBiFactors, const CFList& evaluation,
-                 int minFactorsLength)
-{
-  int j= A.level() - 1;
-  int i;
-
-  //initialize storage
-  CFArray *** storeFactors= new CFArray** [j];
-  for (i= 0; i < j; i++)
-    storeFactors [i]= new CFArray* [2];
-
-  CFArray eval= CFArray (j);
-  i= j - 1;
-  for (CFListIterator iter= evaluation; iter.hasItem(); iter++,i--)
-    eval[i]= iter.getItem();
-  storeFactors [0] [0]= new CFArray [minFactorsLength];
-  storeFactors [0] [1]= new CFArray [minFactorsLength];
-  for (i= 1; i < j; i++)
-  {
-    storeFactors[i] [0]= new CFArray [minFactorsLength];
-    storeFactors[i] [1]= new CFArray [minFactorsLength];
-  }
-  //
-
-  CFList * normalizingFactors= new CFList [j];
-  CFList uniFactors;
-  normalizingFactors [0]= findNormalizingFactor1 (biFactors,
-                                              evaluation.getLast(), uniFactors);
-  for (i= j - 1; i > 0; i--)
-  {
-    if (moreBiFactors[i-1].length() != minFactorsLength)
-    {
-      moreBiFactors[i-1]= 
-        recombination (moreBiFactors [i-1], uniFactors, 1,
-                       moreBiFactors[i-1].length()-uniFactors.length()+1,
-                       eval[i], Variable (i + 2)
-                      );
-    }
-    normalizingFactors [i]= findNormalizingFactor2 (moreBiFactors [i - 1],
-                                                    eval[i], uniFactors);
-  }
-
-  CFList tmp;
-  tmp= normalize (biFactors, normalizingFactors[0]);
-  getTerms (tmp, storeFactors [0] [0]);
-  storeFactors [0] [1]= evaluate (storeFactors [0] [0], minFactorsLength,
-                                  evaluation.getLast(), Variable (2));
-  for (i= j - 1; i > 0; i--)
-  {
-    tmp= normalize (moreBiFactors [i-1], normalizingFactors [i]);
-    getTerms (tmp, storeFactors [i] [0]);
-    storeFactors [i] [1]= evaluate (storeFactors [i] [0], minFactorsLength,
-                                    eval[i], Variable (i + 2));
-  }
-
-
-  int k, l, m, mm, count, sizeOfUniFactors= 0;
-  int*** seperator= new int** [j];
-  Variable x= Variable (1);
-
-  for (i= 0; i < j; i++)
-    seperator [i]= new int* [minFactorsLength];
-  for (k= 0; k < minFactorsLength; k++)
-  {
-    for (i= 0; i < j; i++)
-    {
-      count= 0;
-      for (l= 0; l < storeFactors [i][0][k].size() - 1; l++)
-      {
-        if (degree (storeFactors[i][0][k][l], x) <
-            degree (storeFactors[i][0][k][l+1], x))
-          count++;
-      }
-      if (i == 0)
-        sizeOfUniFactors= count;
-      else if (sizeOfUniFactors != count)
-      {
-        for (m= 0; m < j; m++)
-        {
-          delete [] storeFactors [m] [0];
-          delete [] storeFactors [m] [1];
-          delete [] storeFactors [m];
-          for (mm= 0; mm < k; mm++)
-            delete [] seperator [m][mm];
-          delete [] seperator [m];
-        }
-        delete [] storeFactors;
-        for (m= 0; m < i; m++)
-          delete [] seperator [m][k];
-        delete [] seperator;
-        return CFList();
-      }
-      seperator [i][k]= new int [count + 3];
-      seperator [i][k][0]= count + 1;
-      seperator [i][k][1]= 0;
-      count= 2;
-      for (l= 0; l < storeFactors [i][0][k].size() - 1; l++)
-      {
-        if (degree (storeFactors[i][0][k][l], x) <
-            degree (storeFactors[i][0][k][l+1], x))
-        {
-          seperator[i][k][count]=l + 1;
-          count++;
-        }
-      }
-      seperator [i][k][count]= storeFactors[i][0][k].size();
-    }
-  }
-
-  CanonicalForm tmp1, factor, quot;
-  CanonicalForm B= A;
-  CFList result;
-  int maxTerms, n, index1, index2, mmm, found, columns, oneCount;
-  int ** mat;
-
-  for (k= 0; k < minFactorsLength; k++)
-  {
-    factor= 0;
-    sizeOfUniFactors= seperator [0][k][0];
-    for (n= 1; n <= sizeOfUniFactors; n++)
-    {
-      columns= 0;
-      maxTerms= 1;
-      index1= j - 1;
-      for (i= j - 1; i >= 0; i--)
-      {
-        if (maxTerms < seperator[i][k][n+1]-seperator[i][k][n])
-        {
-          maxTerms= seperator[i][k][n + 1]-seperator[i][k][n];
-          index1= i;
-        }
-      }
-      for (i= j - 1; i >= 0; i--)
-      {
-        if (i == index1)
-          continue;
-        columns += seperator [i][k][n+1]-seperator[i][k][n];
-      }
-      mat= new int *[maxTerms];
-      mm= 0;
-      for (m= seperator[index1][k][n]; m < seperator[index1][k][n+1]; m++, mm++)
-      {
-        tmp1= storeFactors [index1][1][k][m];
-        mat[mm]= new int [columns];
-        for (i= 0; i < columns; i++)
-          mat[mm][i]= 0;
-        index2= 0;
-        for (i= j - 1; i >= 0; i--)
-        {
-          if (i == index1)
-            continue;
-          found= -1;
-          if ((found= search (storeFactors[i][1][k], tmp1, 
-                              seperator[i][k][n], seperator[i][k][n+1])) >= 0)
-            mat[mm][index2 + found - seperator [i][k][n]]= 1;
-          index2 += seperator [i][k][n+1]-seperator[i][k][n];
-        }
-      }
-
-      index2= 0;
-      for (i= j - 1; i >= 0; i--)
-      {
-        if (i == index1)
-          continue;
-        oneCount= 0;
-        for (mm= 0; mm < seperator [i][k][n + 1] - seperator [i][k][n]; mm++)
-        {
-          for (m= 0; m < maxTerms; m++)
-          {
-            if (mat[m][mm+index2] == 1)
-              oneCount++;
-          }
-        }
-        if (oneCount == seperator [i][k][n+1]-seperator[i][k][n] - 1)
-        {
-          for (mm= 0; mm < seperator [i][k][n+1]-seperator[i][k][n]; mm++)
-          {
-            oneCount= 0;
-            for (m= 0; m < maxTerms; m++)
-              if (mat[m][mm+index2] == 1)
-                oneCount++;
-            if (oneCount > 0)
-              continue;
-            for (m= 0; m < maxTerms; m++)
-            {
-              oneCount= 0;
-              for (mmm= 0; mmm < seperator[i][k][n+1]-seperator[i][k][n]; mmm++)
-              {
-                if (mat[m][mmm+index2] == 1)
-                  oneCount++;
-              }
-              if (oneCount > 0)
-                continue;
-              mat[m][mm+index2]= 1;
-            }
-          }
-        }
-        index2 += seperator [i][k][n+1] - seperator [i][k][n];
-      }
-
-      //read off solution
-      mm= 0;
-      for (m= seperator[index1][k][n]; m < seperator[index1][k][n+1]; m++, mm++)
-      {
-        tmp1= storeFactors [index1][0][k][m];
-        index2= 0;
-        for (i= j - 1; i > -1; i--)
-        {
-          if (i == index1)
-            continue;
-          for (mmm= 0; mmm < seperator [i][k][n+1]-seperator[i][k][n]; mmm++)
-            if (mat[mm][mmm+index2] == 1)
-              tmp1= patch (tmp1, storeFactors[i][0][k][seperator[i][k][n]+mmm],
-                           eval[i]);
-          index2 += seperator [i][k][n+1]-seperator[i][k][n];
-        }
-        factor += tmp1;
-      }
-
-      for (m= 0; m < maxTerms; m++)
-        delete [] mat [m];
-      delete [] mat;
-    }
-
-    if (fdivides (factor, B, quot))
-    {
-      result.append (factor);
-      B= quot;
-      if (result.length() == biFactors.length() - 1)
-      {
-        result.append (quot);
-        break;
-      }
-    }
-  }
-
-  //delete
-  for (i= 0; i < j; i++)
-  {
-    delete [] storeFactors [i] [0];
-    delete [] storeFactors [i] [1];
-    delete [] storeFactors [i];
-    for (k= 0; k < minFactorsLength; k++)
-      delete [] seperator [i][k];
-    delete [] seperator [i];
-  }
-  delete [] seperator;
-  delete [] storeFactors;
-  //
-
-  return result;
-}
 
 static inline
@@ -1591,32 +1163,4 @@
 }
 
-CFList
-leadingCoeffReconstruction (const CanonicalForm& F, const CFList& factors,
-                            const CFList& M)
-{
-  CanonicalForm quot, buf= F;
-  CanonicalForm LCBuf= LC (buf, 1);
-
-  CFList result;
-
-  CanonicalForm tmp;
-  for (CFListIterator i= factors; i.hasItem(); i++)
-  {
-    tmp= i.getItem();
-    tmp= mulMod (tmp, LCBuf, M);
-    tmp= tmp/content (tmp, 1);
-    if (fdivides (tmp, buf, quot))
-    {
-      buf= quot;
-      result.append (tmp);
-      LCBuf= LC (buf, 1);
-    }
-    else //no one-to-one correspondence
-      return CFList();
-  }
-
-  return result;
-}
-
 void
 gcdFreeBasis (CFFList& factors1, CFFList& factors2)
Index: factory/facFqFactorize.h
===================================================================
--- factory/facFqFactorize.h	(revision 6deedd6650206f3f5a123f8dfbd41e449fd35f93)
+++ factory/facFqFactorize.h	(revision 91788c087460478b3feb0c0461c30cb0383129fe)
@@ -264,4 +264,18 @@
                     );
 
+/// recombination of bivariate factors @a factors1 s. t. the result evaluated
+/// at @a evalPoint coincides with @a factors2
+CFList
+recombination (const CFList& factors1,        ///<[in] list of bivariate factors
+               const CFList& factors2,        ///<[in] list univariate factors
+               int s,                         ///<[in] algorithm starts checking
+                                              ///<  subsets of size s
+               int thres,                     ///<[in] threshold for the size of
+                                              ///<  subsets which are checked
+               const CanonicalForm& evalPoint,///<[in] evaluation point
+               const Variable& x              ///<[in] second variable of
+                                              ///< bivariate factors
+              );
+
 /// Lift bound adaption. Essentially an early factor detection but only the lift
 /// bound is adapted.
Index: factory/facSparseHensel.cc
===================================================================
--- factory/facSparseHensel.cc	(revision 91788c087460478b3feb0c0461c30cb0383129fe)
+++ factory/facSparseHensel.cc	(revision 91788c087460478b3feb0c0461c30cb0383129fe)
@@ -0,0 +1,398 @@
+/*****************************************************************************\
+ * Computer Algebra System SINGULAR
+\*****************************************************************************/
+/** @file facSparseHensel.cc
+ *
+ * This file implements functions for sparse heuristic Hensel lifting
+ *
+ * ABSTRACT: "A fast implementation of polynomial factorization" by M. Lucks and
+ * "Effective polynomial computation" by R. Zippel
+ *
+ * @author Martin Lee
+ *
+ * @internal @version \$Id$
+ *
+ **/
+/*****************************************************************************/
+
+#include "facSparseHensel.h"
+#include "cf_algorithm.h"
+#include "cf_gcd_smallp.h"
+#include "facFqFactorize.h"
+
+bool
+LucksWangSparseHeuristic (const CanonicalForm& F, const CFList& factors,
+                          int level, const CFList& leadingCoeffs, CFList& result)
+{
+  CFArray* monoms= new CFArray [factors.length()];
+  int i= 0;
+  int num= 0;
+  for (CFListIterator iter= factors; iter.hasItem(); iter++, i++)
+  {
+    monoms[i]= getTerms (iter.getItem());
+    num += monoms [i].size();
+    sort (monoms [i]);
+  }
+
+  i= 0;
+  CFArray* monomsLead= new CFArray [leadingCoeffs.length()];
+  for (CFListIterator iter= leadingCoeffs; iter.hasItem(); iter++, i++)
+  {
+    monomsLead[i]= getTerms (iter.getItem());
+    sort (monomsLead [i]);
+    groupTogether (monomsLead [i], level);
+    strip (monomsLead [i], level);
+  }
+
+  CFArray solution= CFArray (num);
+  int k, d, count, j= F.level() + 1;
+  num= 0;
+  i= 0;
+  for (CFListIterator iter= factors; iter.hasItem(); i++, iter++)
+  {
+    d= degree (iter.getItem(), 1);
+    count= 0;
+    for (k= 0; k < monoms[i].size(); k++, j++, num++)
+    {
+      monoms [i][k] *= Variable (j);
+      if (degree (monoms[i][k], 1) == d)
+      {
+        solution[num]= monomsLead [i] [count];
+        count++;
+      }
+    }
+  }
+
+  delete [] monomsLead;
+
+  CFArray termsF= getTerms (F);
+  sort (termsF);
+
+  CFList tmp;
+  CFArray* stripped2= new CFArray [factors.length()];
+  for (i= factors.length() - 1; i > -1; i--)
+  {
+    tmp.insert (buildPolyFromArray (monoms [i]));
+    strip (monoms[i], stripped2 [i], level);
+  }
+  delete [] monoms;
+
+  CanonicalForm H= prod (tmp);
+  CFArray monomsH= getMonoms (H);
+  sort (monomsH);
+
+  groupTogether (termsF, level);
+  groupTogether (monomsH, F.level());
+
+  if (monomsH.size() != termsF.size())
+  {
+    delete [] stripped2;
+    return false;
+  }
+
+  CFArray strippedH;
+  strip (monomsH, strippedH, level);
+  CFArray strippedF;
+  strip (termsF, strippedF, level);
+
+  if (!isEqual (strippedH, strippedF))
+  {
+    delete [] stripped2;
+    return false;
+  }
+
+  CFArray A= getEquations (monomsH, termsF);
+  CFArray newSolution= CFArray (solution.size());
+  do
+  {
+    evaluate (A, solution, F.level() + 1);
+    if (isZero (A))
+      break;
+    if (!simplify (A, newSolution, F.level() + 1))
+    {
+      delete [] stripped2;
+      return false;
+    }
+    if (isZero (newSolution))
+    {
+      delete [] stripped2;
+      return false;
+    }
+    if (!merge (solution, newSolution))
+    {
+      delete [] stripped2;
+      return false;
+    }
+  } while (1);
+
+
+  result= CFList();
+  CanonicalForm factor;
+  num= 0;
+  for (i= 0; i < factors.length(); i++)
+  {
+    k= stripped2[i].size();
+    factor= 0;
+    for (j= 0; j < k; j++, num++)
+      factor += solution [num]*stripped2[i][j];
+    result.append (factor);
+  }
+
+  delete [] stripped2;
+  return true;
+}
+
+CFList
+sparseHeuristic (const CanonicalForm& A, const CFList& biFactors,
+                 CFList*& moreBiFactors, const CFList& evaluation,
+                 int minFactorsLength)
+{
+  int j= A.level() - 1;
+  int i;
+
+  //initialize storage
+  CFArray *** storeFactors= new CFArray** [j];
+  for (i= 0; i < j; i++)
+    storeFactors [i]= new CFArray* [2];
+
+  CFArray eval= CFArray (j);
+  i= j - 1;
+  for (CFListIterator iter= evaluation; iter.hasItem(); iter++,i--)
+    eval[i]= iter.getItem();
+  storeFactors [0] [0]= new CFArray [minFactorsLength];
+  storeFactors [0] [1]= new CFArray [minFactorsLength];
+  for (i= 1; i < j; i++)
+  {
+    storeFactors[i] [0]= new CFArray [minFactorsLength];
+    storeFactors[i] [1]= new CFArray [minFactorsLength];
+  }
+  //
+
+  CFList * normalizingFactors= new CFList [j];
+  CFList uniFactors;
+  normalizingFactors [0]= findNormalizingFactor1 (biFactors,
+                                              evaluation.getLast(), uniFactors);
+  for (i= j - 1; i > 0; i--)
+  {
+    if (moreBiFactors[i-1].length() != minFactorsLength)
+    {
+      moreBiFactors[i-1]= 
+        recombination (moreBiFactors [i-1], uniFactors, 1,
+                       moreBiFactors[i-1].length()-uniFactors.length()+1,
+                       eval[i], Variable (i + 2)
+                      );
+    }
+    normalizingFactors [i]= findNormalizingFactor2 (moreBiFactors [i - 1],
+                                                    eval[i], uniFactors);
+  }
+
+  CFList tmp;
+  tmp= normalize (biFactors, normalizingFactors[0]);
+  getTerms2 (tmp, storeFactors [0] [0]);
+  storeFactors [0] [1]= evaluate (storeFactors [0] [0], minFactorsLength,
+                                  evaluation.getLast(), Variable (2));
+  for (i= j - 1; i > 0; i--)
+  {
+    tmp= normalize (moreBiFactors [i-1], normalizingFactors [i]);
+    getTerms2 (tmp, storeFactors [i] [0]);
+    storeFactors [i] [1]= evaluate (storeFactors [i] [0], minFactorsLength,
+                                    eval[i], Variable (i + 2));
+  }
+
+
+  int k, l, m, mm, count, sizeOfUniFactors= 0;
+  int*** seperator= new int** [j];
+  Variable x= Variable (1);
+
+  for (i= 0; i < j; i++)
+    seperator [i]= new int* [minFactorsLength];
+  for (k= 0; k < minFactorsLength; k++)
+  {
+    for (i= 0; i < j; i++)
+    {
+      count= 0;
+      for (l= 0; l < storeFactors [i][0][k].size() - 1; l++)
+      {
+        if (degree (storeFactors[i][0][k][l], x) <
+            degree (storeFactors[i][0][k][l+1], x))
+          count++;
+      }
+      if (i == 0)
+        sizeOfUniFactors= count;
+      else if (sizeOfUniFactors != count)
+      {
+        for (m= 0; m < j; m++)
+        {
+          delete [] storeFactors [m] [0];
+          delete [] storeFactors [m] [1];
+          delete [] storeFactors [m];
+          for (mm= 0; mm < k; mm++)
+            delete [] seperator [m][mm];
+          delete [] seperator [m];
+        }
+        delete [] storeFactors;
+        for (m= 0; m < i; m++)
+          delete [] seperator [m][k];
+        delete [] seperator;
+        return CFList();
+      }
+      seperator [i][k]= new int [count + 3];
+      seperator [i][k][0]= count + 1;
+      seperator [i][k][1]= 0;
+      count= 2;
+      for (l= 0; l < storeFactors [i][0][k].size() - 1; l++)
+      {
+        if (degree (storeFactors[i][0][k][l], x) <
+            degree (storeFactors[i][0][k][l+1], x))
+        {
+          seperator[i][k][count]=l + 1;
+          count++;
+        }
+      }
+      seperator [i][k][count]= storeFactors[i][0][k].size();
+    }
+  }
+
+  CanonicalForm tmp1, factor, quot;
+  CanonicalForm B= A;
+  CFList result;
+  int maxTerms, n, index1, index2, mmm, found, columns, oneCount;
+  int ** mat;
+
+  for (k= 0; k < minFactorsLength; k++)
+  {
+    factor= 0;
+    sizeOfUniFactors= seperator [0][k][0];
+    for (n= 1; n <= sizeOfUniFactors; n++)
+    {
+      columns= 0;
+      maxTerms= 1;
+      index1= j - 1;
+      for (i= j - 1; i >= 0; i--)
+      {
+        if (maxTerms < seperator[i][k][n+1]-seperator[i][k][n])
+        {
+          maxTerms= seperator[i][k][n + 1]-seperator[i][k][n];
+          index1= i;
+        }
+      }
+      for (i= j - 1; i >= 0; i--)
+      {
+        if (i == index1)
+          continue;
+        columns += seperator [i][k][n+1]-seperator[i][k][n];
+      }
+      mat= new int *[maxTerms];
+      mm= 0;
+      for (m= seperator[index1][k][n]; m < seperator[index1][k][n+1]; m++, mm++)
+      {
+        tmp1= storeFactors [index1][1][k][m];
+        mat[mm]= new int [columns];
+        for (i= 0; i < columns; i++)
+          mat[mm][i]= 0;
+        index2= 0;
+        for (i= j - 1; i >= 0; i--)
+        {
+          if (i == index1)
+            continue;
+          found= -1;
+          if ((found= search (storeFactors[i][1][k], tmp1, 
+                              seperator[i][k][n], seperator[i][k][n+1])) >= 0)
+            mat[mm][index2 + found - seperator [i][k][n]]= 1;
+          index2 += seperator [i][k][n+1]-seperator[i][k][n];
+        }
+      }
+
+      index2= 0;
+      for (i= j - 1; i >= 0; i--)
+      {
+        if (i == index1)
+          continue;
+        oneCount= 0;
+        for (mm= 0; mm < seperator [i][k][n + 1] - seperator [i][k][n]; mm++)
+        {
+          for (m= 0; m < maxTerms; m++)
+          {
+            if (mat[m][mm+index2] == 1)
+              oneCount++;
+          }
+        }
+        if (oneCount == seperator [i][k][n+1]-seperator[i][k][n] - 1)
+        {
+          for (mm= 0; mm < seperator [i][k][n+1]-seperator[i][k][n]; mm++)
+          {
+            oneCount= 0;
+            for (m= 0; m < maxTerms; m++)
+              if (mat[m][mm+index2] == 1)
+                oneCount++;
+            if (oneCount > 0)
+              continue;
+            for (m= 0; m < maxTerms; m++)
+            {
+              oneCount= 0;
+              for (mmm= 0; mmm < seperator[i][k][n+1]-seperator[i][k][n]; mmm++)
+              {
+                if (mat[m][mmm+index2] == 1)
+                  oneCount++;
+              }
+              if (oneCount > 0)
+                continue;
+              mat[m][mm+index2]= 1;
+            }
+          }
+        }
+        index2 += seperator [i][k][n+1] - seperator [i][k][n];
+      }
+
+      //read off solution
+      mm= 0;
+      for (m= seperator[index1][k][n]; m < seperator[index1][k][n+1]; m++, mm++)
+      {
+        tmp1= storeFactors [index1][0][k][m];
+        index2= 0;
+        for (i= j - 1; i > -1; i--)
+        {
+          if (i == index1)
+            continue;
+          for (mmm= 0; mmm < seperator [i][k][n+1]-seperator[i][k][n]; mmm++)
+            if (mat[mm][mmm+index2] == 1)
+              tmp1= patch (tmp1, storeFactors[i][0][k][seperator[i][k][n]+mmm],
+                           eval[i]);
+          index2 += seperator [i][k][n+1]-seperator[i][k][n];
+        }
+        factor += tmp1;
+      }
+
+      for (m= 0; m < maxTerms; m++)
+        delete [] mat [m];
+      delete [] mat;
+    }
+
+    if (fdivides (factor, B, quot))
+    {
+      result.append (factor);
+      B= quot;
+      if (result.length() == biFactors.length() - 1)
+      {
+        result.append (quot);
+        break;
+      }
+    }
+  }
+
+  //delete
+  for (i= 0; i < j; i++)
+  {
+    delete [] storeFactors [i] [0];
+    delete [] storeFactors [i] [1];
+    delete [] storeFactors [i];
+    for (k= 0; k < minFactorsLength; k++)
+      delete [] seperator [i][k];
+    delete [] seperator [i];
+  }
+  delete [] seperator;
+  delete [] storeFactors;
+  //
+
+  return result;
+}
Index: factory/facSparseHensel.h
===================================================================
--- factory/facSparseHensel.h	(revision 91788c087460478b3feb0c0461c30cb0383129fe)
+++ factory/facSparseHensel.h	(revision 91788c087460478b3feb0c0461c30cb0383129fe)
@@ -0,0 +1,527 @@
+/*****************************************************************************\
+ * Computer Algebra System SINGULAR
+\*****************************************************************************/
+/** @file facFqFactorize.h
+ *
+ * This file provides functions for sparse heuristic Hensel lifting
+ *
+ * @author Martin Lee
+ *
+ * @internal @version \$Id$
+ *
+ **/
+/*****************************************************************************/
+
+#ifndef FAC_SPARSE_HENSEL_H
+#define FAC_SPARSE_HENSEL_H
+
+#include "canonicalform.h"
+#include "cf_map_ext.h"
+#include "cf_iter.h"
+#include "templates/ftmpl_functions.h"
+
+/// compare polynomials
+inline
+int comp (const CanonicalForm& A, const CanonicalForm& B)
+{
+  if (A.inCoeffDomain() && !B.inCoeffDomain())
+    return -1;
+  else if (!A.inCoeffDomain() && B.inCoeffDomain())
+    return 1;
+  else if (A.inCoeffDomain() && B.inCoeffDomain())
+    return 0;
+  else if (degree (A, 1) > degree (B, 1))
+    return 1;
+  else if (degree (A, 1) < degree (B, 1))
+    return -1;
+  // here A and B are not in CoeffDomain
+  int n= tmax (A.level(), B.level());
+  for (int i= 2; i <= n; i++)
+  {
+    if (degree (A,i) > degree (B,i))
+      return 1;
+    else if (degree (A,i) < degree (B,i))
+      return -1;
+  }
+  return 0;
+}
+
+/// compare two polynomials up to level @a level
+inline
+int comp (const CanonicalForm& A, const CanonicalForm& B, int level)
+{
+  if (A.inCoeffDomain() && !B.inCoeffDomain() && B.level() <= level)
+    return -1;
+  else if (!A.inCoeffDomain() && A.level() <= level && B.inCoeffDomain())
+    return 1;
+  else if (A.inCoeffDomain() && B.inCoeffDomain())
+    return 0;
+  else if (degree (A, 1) > degree (B, 1))
+    return 1;
+  else if (degree (A, 1) < degree (B, 1))
+    return -1;
+  // here A and B are not in coeffdomain
+  for (int i= 2; i <= level; i++)
+  {
+    if (degree (A,i) > degree (B,i))
+      return 1;
+    else if (degree (A,i) < degree (B,i))
+      return -1;
+  }
+  return 0;
+}
+
+/// swap entry @a i and @a j in @a A
+inline
+void swap (CFArray& A, int i, int j)
+{
+  CanonicalForm tmp= A[i];
+  A[i]= A[j];
+  A[j]= tmp;
+}
+
+/// quick sort helper function
+inline
+void quickSort (int lo, int hi, CFArray& A)
+{
+  int i= lo, j= hi;
+  CanonicalForm tmp= A[(lo+hi)/2];
+  while (i <= j)
+  {
+    while (comp (A [i], tmp) < 0 && i < hi) i++;
+    while (comp (tmp, A[j]) < 0 && j > lo) j--;
+    if (i <= j)
+    {
+      swap (A, i, j);
+      i++;
+      j--;
+    }
+  }
+  if (lo < j) quickSort (lo, j, A);
+  if (i < hi) quickSort (i, hi, A);
+}
+
+/// quick sort @a A
+inline
+void sort (CFArray& A)
+{
+  quickSort (0, A.size() - 1, A);
+}
+
+/// find normalizing factors for @a biFactors and build monic univariate factors
+/// from @a biFactors
+inline CFList
+findNormalizingFactor1 (const CFList& biFactors, const CanonicalForm& evalPoint,
+                        CFList& uniFactors)
+{
+  CFList result;
+  CanonicalForm tmp;
+  for (CFListIterator i= biFactors; i.hasItem(); i++)
+  {
+    tmp= i.getItem() (evalPoint);
+    uniFactors.append (tmp /Lc (tmp));
+    result.append (Lc (tmp));
+  }
+  return result;
+}
+
+/// find normalizing factors for @a biFactors and sort @a biFactors s.t.
+/// the returned @a biFactors evaluated at evalPoint coincide with @a uniFactors
+inline CFList
+findNormalizingFactor2 (CFList& biFactors, const CanonicalForm& evalPoint,
+                        const CFList& uniFactors)
+{
+  CFList result;
+  CFList uniBiFactors= biFactors;
+  CFList newBiFactors;
+  CFList l;
+  int pos;
+  CFListIterator iter;
+  for (iter= uniBiFactors; iter.hasItem(); iter++)
+  {
+    iter.getItem()= iter.getItem() (evalPoint);
+    l.append (Lc (iter.getItem()));
+    iter.getItem() /= Lc (iter.getItem());
+  }
+  for (CFListIterator i= uniFactors; i.hasItem(); i++)
+  {
+    pos= findItem (uniBiFactors, i.getItem());
+    newBiFactors.append (getItem (biFactors, pos));
+    result.append (getItem (l, pos));
+  }
+  biFactors= newBiFactors;
+  return result;
+}
+
+/// get terms of @a F
+inline CFArray
+getTerms (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;
+  }
+  int numMon= size (F);
+  CFArray result= CFArray (numMon);
+  int j= 0;
+  CFArray recResult;
+  Variable x= F.mvar();
+  CanonicalForm powX;
+  for (CFIterator i= F; i.hasTerms(); i++)
+  {
+    powX= power (x, i.exp());
+    recResult= getTerms (i.coeff());
+    for (int k= 0; k < recResult.size(); k++)
+      result[j+k]= powX*recResult[k];
+    j += recResult.size();
+  }
+  return result;
+}
+
+/// build a poly from entries in @a A
+inline CanonicalForm
+buildPolyFromArray (const CFArray& A)
+{
+  CanonicalForm result= 0;
+  for (int i= A.size() - 1; i > -1; i--)
+    result += A[i];
+  return result;
+}
+
+/// group together elements in @a A, where entries in @a A are put put together
+/// if they coincide up to level @a level
+inline void
+groupTogether (CFArray& A, int level)
+{
+  int n= A.size() - 1;
+  int k= A.size();
+  for (int i= 0; i < n; i++)
+  {
+    if (comp (A[i],A[i+1], level) == 0)
+    {
+      A[i+1] += A[i];
+      A[i]= 0;
+      k--;
+    }
+  }
+  CFArray B= CFArray (k);
+  n++;
+  k= 0;
+  for (int i= 0; i < n; i++)
+  {
+    if (!A[i].isZero())
+    {
+      B[k]= A[i];
+      k++;
+    }
+  }
+  A= B;
+}
+
+/// strip off those parts of entries in @a F whose level is less than or equal
+/// than @a level and store the stripped off parts in @a G
+inline void
+strip (CFArray& F, CFArray& G, int level)
+{
+  int n, m, i, j;
+  CanonicalForm g;
+  m= F.size();
+  G= CFArray (m);
+  for (j= 0; j < m; j++)
+  {
+    g= 1;
+    for (i= 1; i <= level; i++)
+    {
+      if ((n= degree (F[j],i)) > 0)
+        g *= power (Variable (i), n);
+    }
+    F[j] /= g;
+    G[j]= g;
+  }
+}
+
+/// s.a. stripped off parts are not returned
+inline void
+strip (CFArray& F, int level)
+{
+  int n, m, i;
+  CanonicalForm g;
+  m= F.size();
+  for (int j= 0; j < m; j++)
+  {
+    g= 1;
+    for (i= 1; i <= level; i++)
+    {
+      if ((n= degree (F[j],i)) > 0)
+        g *= power (Variable (i), n);
+    }
+    F[j] /= g;
+  }
+}
+
+/// get equations for LucksWangSparseHeuristic
+inline
+CFArray getEquations (const CFArray& A, const CFArray& B)
+{
+  ASSERT (A.size() == B.size(), "size of A and B has to coincide");
+  CFArray result= CFArray (A.size());
+  int n= A.size();
+  for (int i= 0; i < n; i++)
+    result[i]= A[i]-B[i];
+  return result;
+}
+
+/// evaluate every entry of @a A at @a B and level @a level
+inline void
+evaluate (CFArray& A, const CanonicalForm& B, int level)
+{
+  int n= A.size();
+  for (int i= 0; i < n; i++)
+  {
+    if (A[i].level() < level)
+      continue;
+    else
+      A[i]= A[i] (B, level);
+  }
+}
+
+/// evaluate every entry of @a A at every entry of @a B starting at level @a
+/// level
+inline void
+evaluate (CFArray& A, const CFArray& B, int level)
+{
+  int n= B.size();
+  for (int i= 0; i < n; i++)
+  {
+    if (!B[i].isZero())
+      evaluate (A, B[i], level + i);
+  }
+}
+
+/// simplify @a A if possible, i.e. @a A consists of 2 terms and contains only
+/// one variable of level greater or equal than @a level
+inline CanonicalForm
+simplify (const CanonicalForm& A, int level)
+{
+  CanonicalForm F= 0;
+  if (size (A, A.level()) == 2)
+  {
+    CanonicalForm C= getVars (A);
+    if ((C/C.mvar()).level() < level)
+    {
+      CanonicalForm B= LC (A);
+      if (B.level() < level)
+        F= -tailcoeff (A/B);
+    }
+  }
+  return F;
+}
+
+///  if possible simplify @a A as described above and store result in @a B
+inline bool
+simplify (CFArray& A, CFArray& B, int level)
+{
+  int n= A.size();
+  CanonicalForm f;
+  int index;
+  for (int i= 0; i < n; i++)
+  {
+    if (!A[i].isZero())
+    {
+      f= simplify (A[i], level);
+      if (!f.isZero())
+      {
+        index= A[i].level() - level;
+        if (index < 0 || index >= B.size())
+          return false;
+        if (!B[index].isZero() && B[index] != f)
+          return false;
+        else if (B[index].isZero())
+        {
+          B[index]= f;
+          A[i]= 0;
+        }
+      }
+    }
+  }
+  return true;
+}
+
+/// merge @a B into @a A if possible, i.e. every non-zero entry in @a A should
+/// be zero in @a B
+inline bool
+merge (CFArray& A, CFArray& B)
+{
+  if (A.size() != B.size())
+    return false;
+  int n= A.size();
+  for (int i= 0; i < n; i++)
+  {
+    if (!B[i].isZero())
+    {
+      if (A[i].isZero())
+      {
+        A[i]= B[i];
+        B[i]= 0;
+      }
+      else if (A[i] == B[i])
+        B[i]= 0;
+      else
+        return false;
+    }
+  }
+  return true;
+}
+
+/// checks if entries of @a A are zero
+inline bool
+isZero (const CFArray& A)
+{
+  int n= A.size();
+  for (int i= 0; i < n; i++)
+    if (!A[i].isZero())
+      return false;
+  return true;
+}
+
+/// checks if @a A equals @a B
+inline bool
+isEqual (const CFArray& A, const CFArray& B)
+{
+  if (A.size() != B.size())
+    return false;
+  int i, n= B.size();
+  for (i= 0; i < n; i++)
+    if (A[i] != B[i])
+      return false;
+  return true;
+}
+
+/// get terms of @a F wrt. Variable (1)
+inline CFArray
+getTerms2 (const CanonicalForm& F)
+{
+  CFArray result= CFArray (size (F));
+  int j= 0;
+  Variable x= F.mvar();
+  Variable y= Variable (1);
+  CFIterator k;
+  for (CFIterator i= F; i.hasTerms(); i++)
+  {
+    for (k= i.coeff(); k.hasTerms(); k++, j++)
+      result[j]= k.coeff()*power (x,i.exp())*power (y,k.exp());
+  }
+  sort (result);
+  return result;
+}
+
+/// get terms of entries in @a F and put them in @a result
+inline
+void getTerms2 (const CFList& F, CFArray* result)
+{
+  int j= 0;
+  for (CFListIterator i= F; i.hasItem(); i++, j++)
+    result[j]= getTerms2 (i.getItem());
+}
+
+/// evaluate entries in @a A at @a eval and @a y
+inline CFArray
+evaluate (const CFArray& A, const CanonicalForm& eval, const Variable& y)
+{
+  int j= A.size();
+  CFArray result= CFArray (j);
+  for (int i= 0; i < j; i++)
+    result [i]= A[i] (eval, y);
+  return result;
+}
+
+/// s.a.
+inline CFArray*
+evaluate (CFArray* const& A, int sizeA, const CanonicalForm& eval,
+          const Variable& y)
+{
+  CFArray* result= new CFArray [sizeA];
+  for (int i= 0; i < sizeA; i++)
+    result[i]= evaluate (A[i], eval, y);
+  return result;
+}
+
+/// normalize entries in @a L with @a normalizingFactor
+inline
+CFList normalize (const CFList& L, const CFList& normalizingFactor)
+{
+  CFList result;
+  CFListIterator j= normalizingFactor;
+  for (CFListIterator i= L; i.hasItem(); i++, j++)
+    result.append (i.getItem() / j.getItem());
+  return result;
+}
+
+/// search for @a F in @a A between index @a i and @a j
+inline
+int search (const CFArray& A, const CanonicalForm& F, int i, int j)
+{
+  for (; i < j; i++)
+    if (A[i] == F)
+      return i;
+  return -1;
+}
+
+/// patch together @a F1 and @a F2 and normalize by a power of @a eval
+/// @a F1 and @a F2 are assumed to be bivariate with one variable having level 1
+inline
+CanonicalForm patch (const CanonicalForm& F1, const CanonicalForm& F2,
+                     const CanonicalForm& eval)
+{
+  CanonicalForm result= F1;
+  if (F2.level() != 1)
+  {
+    int d= degree (F2);
+    result *= power (F2.mvar(), d);
+    result /= power (eval, d);
+  }
+  return result;
+}
+
+/// sparse heuristic lifting by Wang and Lucks
+///
+/// @return @a LucksWangSparseHeuristic returns true if it was successful
+bool
+LucksWangSparseHeuristic (const CanonicalForm& F,     ///<[in] polynomial to be
+                                                      ///< factored
+                          const CFList& factors,      ///<[in] factors of F
+                                                      ///< lifted to level
+                          int level,                  ///<[in] level of lifted
+                                                      ///< factors
+                          const CFList& leadingCoeffs,///<[in] leading
+                                                      ///< coefficients of
+                                                      ///< factors
+                          CFList& result              ///<[in,out] result
+                         );
+
+/// sparse heuristic which patches together bivariate factors of @a A wrt.
+/// different second variables by their univariate images
+///
+/// @return @a sparseHeuristic returns a list of found factors of A
+CFList
+sparseHeuristic (const CanonicalForm& A,  ///<[in] polynomial to be factored
+                 const CFList& biFactors, ///<[in] bivariate factors of A where
+                                          ///< the second variable has level 2
+                 CFList*& moreBiFactors,  ///<[in] more bivariate factorizations
+                                          ///< wrt. different second variables
+                 const CFList& evaluation,///<[in] evaluation point
+                 int minFactorsLength     ///<[in] minimal length of bivariate
+                                          ///< factorizations
+                );
+
+#endif
