facSparseHensel.h File Reference

This file provides functions for sparse heuristic Hensel lifting. More...

#include "canonicalform.h"
#include "cf_map_ext.h"
#include "cf_iter.h"
#include "templates/ftmpl_functions.h"
#include "cf_algorithm.h"
#include "cf_map.h"

Go to the source code of this file.

Functions
int	comp (const CanonicalForm &A, const CanonicalForm &B)
	compare polynomials More...
int	comp (const CanonicalForm &A, const CanonicalForm &B, int level)
	compare two polynomials up to level level More...
void	swap (CFArray &A, int i, int j)
	swap entry i and j in A More...
void	quickSort (int lo, int hi, CFArray &A, int l)
	quick sort helper function More...
void	sort (CFArray &A, int l=0)
	quick sort A More...
CFList	findNormalizingFactor1 (const CFList &biFactors, const CanonicalForm &evalPoint, CFList &uniFactors)
	find normalizing factors for biFactors and build monic univariate factors from biFactors More...
CFList	findNormalizingFactor2 (CFList &biFactors, const CanonicalForm &evalPoint, const CFList &uniFactors)
	find normalizing factors for biFactors and sort biFactors s.t. the returned biFactors evaluated at evalPoint coincide with uniFactors More...
CFArray	getTerms (const CanonicalForm &F)
	get terms of F More...
CFArray	getBiTerms_helper (const CanonicalForm &F, const CFMap &M, int threshold)
	helper function for getBiTerms More...
CFArray	getBiTerms (const CanonicalForm &F, int threshold)
	get terms of F where F is considered a bivariate poly in Variable(1), Variable (2) More...
CanonicalForm	buildPolyFromArray (const CFArray &A)
	build a poly from entries in A More...
void	groupTogether (CFArray &A, int level)
	group together elements in A, where entries in A are put together if they coincide up to level level More...
void	strip (CFArray &F, CFArray &G, int level)
	strip off those parts of entries in F whose level is less than or equal than level and store the stripped off parts in G More...
void	strip (CFArray &F, int level)
	s.a. stripped off parts are not returned More...
CFArray	getEquations (const CFArray &A, const CFArray &B)
	get equations for LucksWangSparseHeuristic More...
void	evaluate (CFArray &A, const CanonicalForm &B, int level)
	evaluate every entry of A at B and level level More...
void	evaluate (CFArray &A, const CFArray &B, int level)
	evaluate every entry of A at every entry of B starting at level level More...
CanonicalForm	simplify (const CanonicalForm &A, int level)
	simplify A if possible, i.e. A consists of 2 terms and contains only one variable of level greater or equal than level More...
bool	simplify (CFArray &A, CFArray &B, int level)
	if possible simplify A as described above and store result in B More...
bool	merge (CFArray &A, CFArray &B)
	merge B into A if possible, i.e. every non-zero entry in A should be zero in B More...
bool	isZero (const CFArray &A)
	checks if entries of A are zero More...
bool	isEqual (const CFArray &A, const CFArray &B)
	checks if A equals B More...
CFArray	getTerms2 (const CanonicalForm &F)
	get terms of F wrt. Variable (1) More...
void	getTerms2 (const CFList &F, CFArray *result)
	get terms of entries in F and put them in result More...
CFArray	evaluate (const CFArray &A, const CanonicalForm &eval, const Variable &y)
	evaluate entries in A at eval and y More...
CFArray *	evaluate (CFArray *const &A, int sizeA, const CanonicalForm &eval, const Variable &y)
	s.a. More...
CFList	normalize (const CFList &L, const CFList &normalizingFactor)
	normalize entries in L with normalizingFactor More...
int	search (const CFArray &A, const CanonicalForm &F, int i, int j)
	search for F in A between index i and j More...
CanonicalForm	patch (const CanonicalForm &F1, const CanonicalForm &F2, const CanonicalForm &eval)
	patch together F1 and F2 and normalize by a power of eval F1 and F2 are assumed to be bivariate with one variable having level 1 More...
int	LucksWangSparseHeuristic (const CanonicalForm &F, const CFList &factors, int level, const CFList &leadingCoeffs, CFList &result)
	sparse heuristic lifting by Wang and Lucks More...
CFList	sparseHeuristic (const CanonicalForm &A, const CFList &biFactors, CFList *&moreBiFactors, const CFList &evaluation, int minFactorsLength)
	sparse heuristic which patches together bivariate factors of A wrt. different second variables by their univariate images More...

Detailed Description

This file provides functions for sparse heuristic Hensel lifting.

Author

Martin Lee

Definition in file facSparseHensel.h.

Function Documentation

buildPolyFromArray()

CanonicalForm buildPolyFromArray ( const CFArray &  A )

inline

build a poly from entries in A

Definition at line 267 of file facSparseHensel.h.

{
  CanonicalForm result= 0;
  for (int i= A.size() - 1; i > -1; i--)
    result += A[i];
  return result;
}

comp() [1/2]

int comp ( const CanonicalForm &  A, const CanonicalForm &  B  )

inline

compare polynomials

Definition at line 25 of file facSparseHensel.h.

{
  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;
}

comp() [2/2]

int comp ( const CanonicalForm &  A, const CanonicalForm &  B, int  level  )

inline

compare two polynomials up to level level

Definition at line 51 of file facSparseHensel.h.

{
  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;
}

evaluate() [1/4]

void evaluate ( CFArray &  A, const CanonicalForm &  B, int  level  )

inline

evaluate every entry of A at B and level level

Definition at line 362 of file facSparseHensel.h.

{
  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() [2/4]

void evaluate ( CFArray &  A, const CFArray &  B, int  level  )

inline

evaluate every entry of A at every entry of B starting at level level

Definition at line 377 of file facSparseHensel.h.

{
  int n= B.size();
  for (int i= 0; i < n; i++)
  {
    if (!B[i].isZero())
      evaluate (A, B[i], level + i);
  }
}

evaluate() [3/4]

CFArray * evaluate ( CFArray *const &  A, int  sizeA, const CanonicalForm &  eval, const Variable &  y  )

inline

s.a.

Definition at line 544 of file facSparseHensel.h.

{
  CFArray* result= new CFArray [sizeA];
  for (int i= 0; i < sizeA; i++)
    result[i]= evaluate (A[i], eval, y);
  return result;
}

evaluate() [4/4]

CFArray evaluate ( const CFArray &  A, const CanonicalForm &  eval, const Variable &  y  )

inline

evaluate entries in A at eval and y

Definition at line 533 of file facSparseHensel.h.

{
  int j= A.size();
  CFArray result= CFArray (j);
  for (int i= 0; i < j; i++)
    result [i]= A[i] (eval, y);
  return result;
}

findNormalizingFactor1()

CFList findNormalizingFactor1 ( const CFList &  biFactors, const CanonicalForm &  evalPoint, CFList &  uniFactors  )

inline

find normalizing factors for biFactors and build monic univariate factors from biFactors

Definition at line 123 of file facSparseHensel.h.

{
  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;
}

findNormalizingFactor2()

CFList findNormalizingFactor2 ( CFList &  biFactors, const CanonicalForm &  evalPoint, const CFList &  uniFactors  )

inline

find normalizing factors for biFactors and sort biFactors s.t. the returned biFactors evaluated at evalPoint coincide with uniFactors

Definition at line 140 of file facSparseHensel.h.

{
  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;
}

getBiTerms()

CFArray getBiTerms ( const CanonicalForm &  F, int  threshold  )

inline

get terms of F where F is considered a bivariate poly in Variable(1), Variable (2)

Definition at line 236 of file facSparseHensel.h.

{
  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, threshold);
  return result;
}

getBiTerms_helper()

CFArray getBiTerms_helper ( const CanonicalForm &  F, const CFMap &  M, int  threshold  )

inline

helper function for getBiTerms

Definition at line 202 of file facSparseHensel.h.

{
  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++;
      if (k > threshold)
        break;
      continue;
    }
    j= i.coeff();
    for (;j.hasTerms() && k <= threshold; j++, k++)
      buf[k]= power (one,i.exp())*power (two,j.exp())*M (j.coeff());
    if (k > threshold)
      break;
  }
  CFArray result= CFArray (k);
  for (int i= 0; i < k && k <= threshold; i++)
    result[i]= buf[i];
  return result;
}

getEquations()

CFArray getEquations ( const CFArray &  A, const CFArray &  B  )

inline

get equations for LucksWangSparseHeuristic

Definition at line 350 of file facSparseHensel.h.

{
  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;
}

getTerms()

CFArray getTerms ( const CanonicalForm &  F )

inline

get terms of F

Definition at line 167 of file facSparseHensel.h.

{
  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;
}

getTerms2() [1/2]

CFArray getTerms2 ( const CanonicalForm &  F )

inline

get terms of F wrt. Variable (1)

Definition at line 492 of file facSparseHensel.h.

{
  if (F.inCoeffDomain())
  {
    CFArray result= CFArray (1);
    result[0]= F;
    return result;
  }
  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++)
  {
    if (i.coeff().inCoeffDomain())
    {
      result[j]= i.coeff()*power (x,i.exp());
      j++;
    }
    else
    {
      for (k= i.coeff(); k.hasTerms(); k++, j++)
        result[j]= k.coeff()*power (x,i.exp())*power (y,k.exp());
    }
  }
  sort (result);
  return result;
}

getTerms2() [2/2]

void getTerms2 ( const CFList &  F, CFArray *  result  )

inline

get terms of entries in F and put them in result

Definition at line 524 of file facSparseHensel.h.

{
  int j= 0;
  for (CFListIterator i= F; i.hasItem(); i++, j++)
    result[j]= getTerms2 (i.getItem());
}

groupTogether()

void groupTogether ( CFArray &  A, int  level  )

inline

group together elements in A, where entries in A are put together if they coincide up to level level

Definition at line 278 of file facSparseHensel.h.

{
  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--;
    }
  }
  if (A[n].isZero())
    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;
}

isEqual()

bool isEqual ( const CFArray &  A, const CFArray &  B  )

inline

checks if A equals B

Definition at line 479 of file facSparseHensel.h.

{
  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;
}

isZero()

bool isZero ( const CFArray &  A )

inline

checks if entries of A are zero

Definition at line 468 of file facSparseHensel.h.

{
  int n= A.size();
  for (int i= 0; i < n; i++)
    if (!A[i].isZero())
      return false;
  return true;
}

LucksWangSparseHeuristic()

int LucksWangSparseHeuristic	(	const CanonicalForm &	F,
		const CFList &	factors,
		int	level,
		const CFList &	leadingCoeffs,
		CFList &	result
	)

sparse heuristic lifting by Wang and Lucks

Returns

LucksWangSparseHeuristic returns true if it was successful

Parameters

[in]	F	polynomial to be factored
[in]	factors	factors of F lifted to level
[in]	level	level of lifted factors
[in]	leadingCoeffs	leading coefficients of factors
[in,out]	result	result

Definition at line 26 of file facSparseHensel.cc.

{
  int threshold= 450;
  CFArray termsF= getBiTerms (F, threshold);
  int si=termsF.size();
  int fl=factors.length();
  //printf("size:%d, length=%d, char=%d\n",si,fl,getCharacteristic());
  if ((si > threshold)
  || (si <= fl)
  )
    return 0;
  sort (termsF, level);
 
  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;
 
  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,F.level());
 
  groupTogether (monomsH, F.level());
 
  if (monomsH.size() != termsF.size())
  {
    delete [] stripped2;
    return 0;
  }
 
  CFArray strippedH;
  strip (monomsH, strippedH, level);
  CFArray strippedF;
  strip (termsF, strippedF, level);
 
  if (!isEqual (strippedH, strippedF))
  {
    delete [] stripped2;
    return 0;
  }
 
  CFArray A= getEquations (monomsH, termsF);
  CFArray startingSolution= solution;
  CFArray newSolution= CFArray (solution.size());
  result= CFList();
  do
  {
    evaluate (A, solution, F.level() + 1);
    if (isZero (A))
      break;
    if (!simplify (A, newSolution, F.level() + 1))
    {
      delete [] stripped2;
      return 0;
    }
    if (isZero (newSolution))
      break;
    if (!merge (solution, newSolution))
      break;
  } while (1);
 
  if (isEqual (startingSolution, solution))
  {
    delete [] stripped2;
    return 0;
  }
  CanonicalForm factor;
  num= 0;
  for (i= 0; i < factors.length(); i++)
  {
    k= stripped2[i].size();
    factor= 0;
    for (j= 0; j < k; j++, num++)
    {
      if (solution [num].isZero())
        continue;
      factor += solution [num]*stripped2[i][j];
    }
    result.append (factor);
  }
 
  delete [] stripped2;
  if (result.length() > 0)
    return 1;
  return 0;
}

merge()

bool merge ( CFArray &  A, CFArray &  B  )

inline

merge B into A if possible, i.e. every non-zero entry in A should be zero in B

Definition at line 443 of file facSparseHensel.h.

{
  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;
}

normalize()

CFList normalize ( const CFList &  L, const CFList &  normalizingFactor  )

inline

normalize entries in L with normalizingFactor

Definition at line 555 of file facSparseHensel.h.

{
  CFList result;
  CFListIterator j= normalizingFactor;
  for (CFListIterator i= L; i.hasItem(); i++, j++)
    result.append (i.getItem() / j.getItem());
  return result;
}

patch()

CanonicalForm patch ( const CanonicalForm &  F1, const CanonicalForm &  F2, const CanonicalForm &  eval  )

inline

patch together F1 and F2 and normalize by a power of eval F1 and F2 are assumed to be bivariate with one variable having level 1

Definition at line 577 of file facSparseHensel.h.

{
  CanonicalForm result= F1;
  if (F2.level() != 1 && !F2.inCoeffDomain())
  {
    int d= degree (F2);
    result *= power (F2.mvar(), d);
    result /= power (eval, d);
  }
  return result;
}

quickSort()

void quickSort ( int  lo, int  hi, CFArray &  A, int  l  )

inline

quick sort helper function

Definition at line 85 of file facSparseHensel.h.

{
  int i= lo, j= hi;
  CanonicalForm tmp= A[(lo+hi)/2];
  while (i <= 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)
    {
      swap (A, i, j);
      i++;
      j--;
    }
  }
  if (lo < j) quickSort (lo, j, A, l);
  if (i < hi) quickSort (i, hi, A, l);
}

search()

int search ( const CFArray &  A, const CanonicalForm &  F, int  i, int  j  )

inline

search for F in A between index i and j

Definition at line 566 of file facSparseHensel.h.

{
  for (; i < j; i++)
    if (A[i] == F)
      return i;
  return -1;
}

simplify() [1/2]

bool simplify ( CFArray &  A, CFArray &  B, int  level  )

inline

if possible simplify A as described above and store result in B

Definition at line 412 of file facSparseHensel.h.

{
  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;
}

simplify() [2/2]

CanonicalForm simplify ( const CanonicalForm &  A, int  level  )

inline

simplify A if possible, i.e. A consists of 2 terms and contains only one variable of level greater or equal than level

Definition at line 390 of file facSparseHensel.h.

{
  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)
      {
        CanonicalForm quot;
        if (fdivides (B, A, quot))
          F= -tailcoeff (quot);
      }
    }
  }
  return F;
}

sort()

void sort ( CFArray &  A, int  l = 0  )

inline

quick sort A

Definition at line 114 of file facSparseHensel.h.

{
  quickSort (0, A.size() - 1, A, l);
}

sparseHeuristic()

CFList sparseHeuristic	(	const CanonicalForm &	A,
		const CFList &	biFactors,
		CFList *&	moreBiFactors,
		const CFList &	evaluation,
		int	minFactorsLength
	)

sparse heuristic which patches together bivariate factors of A wrt. different second variables by their univariate images

Returns

sparseHeuristic returns a list of found factors of A

Parameters

[in]	A	polynomial to be factored
[in]	biFactors	bivariate factors of A where the second variable has level 2
[in]	moreBiFactors	more bivariate factorizations wrt. different second variables
[in]	evaluation	evaluation point
[in]	minFactorsLength	minimal length of bivariate factorizations

Definition at line 160 of file facSparseHensel.cc.

{
  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;
        delete [] seperator;
        delete [] normalizingFactors;
        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;
  delete [] normalizingFactors;
  //
 
  return result;
}

strip() [1/2]

void strip ( CFArray &  F, CFArray &  G, int  level  )

inline

strip off those parts of entries in F whose level is less than or equal than level and store the stripped off parts in G

Definition at line 310 of file facSparseHensel.h.

{
  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;
  }
}

strip() [2/2]

void strip ( CFArray &  F, int  level  )

inline

s.a. stripped off parts are not returned

Definition at line 331 of file facSparseHensel.h.

{
  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;
  }
}

swap()

void swap ( CFArray &  A, int  i, int  j  )

inline

swap entry i and j in A

Definition at line 76 of file facSparseHensel.h.

{
  CanonicalForm tmp= A[i];
  A[i]= A[j];
  A[j]= tmp;
}