My Project  debian-1:4.1.1-p2+ds-4build2
Functions
facHensel.h File Reference
#include "cf_assert.h"
#include "debug.h"
#include "timing.h"
#include "canonicalform.h"
#include "fac_util.h"

Go to the source code of this file.

Functions

void sortList (CFList &list, const Variable &x)
 sort a list of polynomials by their degree in x. More...
 
void henselLift12 (const CanonicalForm &F, CFList &factors, int l, CFArray &Pi, CFList &diophant, CFMatrix &M, modpk &b, bool sort=true)
 Hensel lift from univariate to bivariate. More...
 
void henselLift12 (const CanonicalForm &F, CFList &factors, int l, CFArray &Pi, CFList &diophant, CFMatrix &M, bool sort=true)
 Hensel lift from univariate to bivariate. More...
 
void henselLiftResume12 (const CanonicalForm &F, CFList &factors, int start, int end, CFArray &Pi, const CFList &diophant, CFMatrix &M, const modpk &b=modpk())
 resume Hensel lift from univariate to bivariate. Assumes factors are lifted to precision Variable (2)^start and lifts them to precision Variable (2)^end More...
 
CFList henselLift23 (const CFList &eval, const CFList &factors, int *l, CFList &diophant, CFArray &Pi, CFMatrix &M)
 Hensel lifting from bivariate to trivariate. More...
 
void henselLiftResume (const CanonicalForm &F, CFList &factors, int start, int end, CFArray &Pi, const CFList &diophant, CFMatrix &M, const CFList &MOD)
 resume Hensel lifting. More...
 
CFList henselLift (const CFList &F, const CFList &factors, const CFList &MOD, CFList &diophant, CFArray &Pi, CFMatrix &M, int lOld, int lNew)
 Hensel lifting. More...
 
CFList henselLift (const CFList &eval, const CFList &factors, int *l, int lLength, bool sort=true)
 Hensel lifting from bivariate to multivariate. More...
 
void nonMonicHenselLift12 (const CanonicalForm &F, CFList &factors, int l, CFArray &Pi, CFList &diophant, CFMatrix &M, const CFArray &LCs, bool sort)
 Hensel lifting from univariate to bivariate, factors need not to be monic. More...
 
CFList nonMonicHenselLift2 (const CFList &eval, const CFList &factors, int *l, int lLength, bool sort, const CFList &LCs1, const CFList &LCs2, const CFArray &Pi, const CFList &diophant, bool &noOneToOne)
 two factor Hensel lifting from bivariate to multivariate, factors need not to be monic More...
 
CFList nonMonicHenselLift (const CFList &eval, const CFList &factors, CFList *const &LCs, CFList &diophant, CFArray &Pi, int *liftBound, int length, bool &noOneToOne)
 Hensel lifting of non monic factors, needs correct leading coefficients of factors and a one to one corresponds between bivariate and multivariate factors to succeed. More...
 

Detailed Description

This file defines functions for Hensel lifting.

ABSTRACT: function are used for bi- and multivariate factorization over finite fields. Described in "Efficient Multivariate Factorization over Finite Fields" by L. Bernardin & M. Monagon and "Algorithms for Computer Algebra" by Geddes, Czapor, Labahn

Author
Martin Lee

Definition in file facHensel.h.

Function Documentation

◆ henselLift() [1/2]

CFList henselLift ( const CFList eval,
const CFList factors,
int *  l,
int  lLength,
bool  sort = true 
)

Hensel lifting from bivariate to multivariate.

Returns
henselLift returns a list of lifted factors
See also
henselLift12(), henselLiftResume12(), henselLift23(), henselLiftResume()
Parameters
[in]eval[in] a list of polynomials the last element is a compressed multivariate poly, last but one element equals the last elements modulo its main variable and so on. The first element is a compressed bivariate poly.
[in]factors[in] bivariate factors, including leading coefficient
[in]l[in] lifting bounds
[in]lLength[in] length of l
[in]sort[in] sort factors by degree in Variable(1)

Definition at line 1760 of file facHensel.cc.

1762 {
1763  CFList diophant;
1764  CFList buf= factors;
1765  buf.insert (LC (eval.getFirst(), 1));
1766  if (sort)
1767  sortList (buf, Variable (1));
1768  CFArray Pi;
1769  CFMatrix M= CFMatrix (l[1], factors.length());
1770  CFList result= henselLift23 (eval, buf, l, diophant, Pi, M);
1771  if (eval.length() == 2)
1772  return result;
1773  CFList MOD;
1774  for (int i= 0; i < 2; i++)
1775  MOD.append (power (Variable (i + 2), l[i]));
1777  j++;
1778  CFList bufEval;
1779  bufEval.append (j.getItem());
1780  j++;
1781 
1782  for (int i= 2; i < lLength && j.hasItem(); i++, j++)
1783  {
1784  result.insert (LC (bufEval.getFirst(), 1));
1785  bufEval.append (j.getItem());
1786  M= CFMatrix (l[i], factors.length());
1787  result= henselLift (bufEval, result, MOD, diophant, Pi, M, l[i - 1], l[i]);
1788  MOD.append (power (Variable (i + 2), l[i]));
1789  bufEval.removeFirst();
1790  }
1791  return result;
1792 }

◆ henselLift() [2/2]

CFList henselLift ( const CFList F,
const CFList factors,
const CFList MOD,
CFList diophant,
CFArray Pi,
CFMatrix M,
int  lOld,
int  lNew 
)

Hensel lifting.

Returns
henselLift returns a list of polynomials lifted to precision F.getLast().mvar()^l_new
See also
henselLift12(), henselLiftResume12(), henselLift23(), henselLiftResume()
Parameters
[in]F[in] two compressed, multivariate polys F and G
[in]factors[in] monic multivariate factors including leading coefficient as first element.
[in]MOD[in] a list of powers of Variables of level higher than 1
[in,out]diophant[in,out] result of multiRecDiophantine()
[in,out]Pi[in,out] stores intermediate results
[in,out]M[in,out] stores intermediate results
[in]lOld[in] lifting precision of F.mvar()
[in]lNew[in] lifting precision of G.mvar()

Definition at line 1719 of file facHensel.cc.

1721 {
1722  diophant= multiRecDiophantine (F.getFirst(), factors, diophant, MOD, lOld);
1723  int k= 0;
1724  CFArray bufFactors= CFArray (factors.length());
1725  for (CFListIterator i= factors; i.hasItem(); i++, k++)
1726  {
1727  if (k == 0)
1728  bufFactors[k]= LC (F.getLast(), 1);
1729  else
1730  bufFactors[k]= i.getItem();
1731  }
1732  CFList buf= factors;
1733  buf.removeFirst();
1734  buf.insert (LC (F.getLast(), 1));
1735  CFListIterator i= buf;
1736  i++;
1737  Variable y= F.getLast().mvar();
1738  Variable x= F.getFirst().mvar();
1739  CanonicalForm xToLOld= power (x, lOld);
1740  Pi [0]= mod (Pi[0], xToLOld);
1741  M (1, 1)= Pi [0];
1742  k= 1;
1743  if (i.hasItem())
1744  i++;
1745  for (; i.hasItem(); i++, k++)
1746  {
1747  Pi [k]= mod (Pi [k], xToLOld);
1748  M (1, k + 1)= Pi [k];
1749  }
1750 
1751  for (int d= 1; d < lNew; d++)
1752  henselStep (F.getLast(), buf, bufFactors, diophant, M, Pi, d, MOD);
1753  CFList result;
1754  for (k= 1; k < factors.length(); k++)
1755  result.append (bufFactors[k]);
1756  return result;
1757 }

◆ henselLift12() [1/2]

void henselLift12 ( const CanonicalForm F,
CFList factors,
int  l,
CFArray Pi,
CFList diophant,
CFMatrix M,
bool  sort = true 
)

Hensel lift from univariate to bivariate.

See also
henselLiftResume12(), henselLift23(), henselLiftResume(), henselLift()
Parameters
[in]F[in] compressed, bivariate poly
[in,out]factors[in, out] monic univariate factors of F, including leading coefficient as first element. Returns monic lifted factors without the leading coefficient
[in]l[in] lifting precision
[in,out]Pi[in,out] stores intermediate results
[in,out]diophant[in,out] result of diophantine()
[in,out]M[in,out] stores intermediate results
[in]sort[in] sort factors by degree in Variable(1)

Definition at line 1206 of file facHensel.cc.

1208 {
1209  modpk dummy= modpk();
1210  henselLift12 (F, factors, l, Pi, diophant, M, dummy, sort);
1211 }

◆ henselLift12() [2/2]

void henselLift12 ( const CanonicalForm F,
CFList factors,
int  l,
CFArray Pi,
CFList diophant,
CFMatrix M,
modpk b,
bool  sort = true 
)

Hensel lift from univariate to bivariate.

See also
henselLiftResume12(), henselLift23(), henselLiftResume(), henselLift()
Parameters
[in]F[in] compressed, bivariate poly
[in,out]factors[in, out] monic univariate factors of F, including leading coefficient as first element. Returns monic lifted factors without the leading coefficient
[in]l[in] lifting precision
[in,out]Pi[in,out] stores intermediate results
[in,out]diophant[in,out] result of diophantine()
[in,out]M[in,out] stores intermediate results
[in]b[in] coeff bound
[in]sort[in] sort factors by degree in Variable(1)

Definition at line 1148 of file facHensel.cc.

1150 {
1151  if (sort)
1152  sortList (factors, Variable (1));
1153  Pi= CFArray (factors.length() - 1);
1154  CFListIterator j= factors;
1155  diophant= diophantine (F[0], F, factors, b);
1156  CanonicalForm bufF= F;
1157  if (getCharacteristic() == 0 && b.getp() != 0)
1158  {
1159  Variable v;
1160  bool hasAlgVar= hasFirstAlgVar (F, v);
1161  for (CFListIterator i= factors; i.hasItem() && !hasAlgVar; i++)
1162  hasAlgVar= hasFirstAlgVar (i.getItem(), v);
1163  Variable w;
1164  bool hasAlgVar2= false;
1165  for (CFListIterator i= diophant; i.hasItem() && !hasAlgVar2; i++)
1166  hasAlgVar2= hasFirstAlgVar (i.getItem(), w);
1167  if (hasAlgVar && hasAlgVar2 && v!=w)
1168  {
1169  bufF= replacevar (bufF, v, w);
1170  for (CFListIterator i= factors; i.hasItem(); i++)
1171  i.getItem()= replacevar (i.getItem(), v, w);
1172  }
1173  }
1174 
1175  DEBOUTLN (cerr, "diophant= " << diophant);
1176  j++;
1177  Pi [0]= mulNTL (j.getItem(), mod (factors.getFirst(), F.mvar()), b);
1178  M (1, 1)= Pi [0];
1179  int i= 1;
1180  if (j.hasItem())
1181  j++;
1182  for (; j.hasItem(); j++, i++)
1183  {
1184  Pi [i]= mulNTL (Pi [i - 1], j.getItem(), b);
1185  M (1, i + 1)= Pi [i];
1186  }
1187  CFArray bufFactors= CFArray (factors.length());
1188  i= 0;
1189  for (CFListIterator k= factors; k.hasItem(); i++, k++)
1190  {
1191  if (i == 0)
1192  bufFactors[i]= mod (k.getItem(), F.mvar());
1193  else
1194  bufFactors[i]= k.getItem();
1195  }
1196  for (i= 1; i < l; i++)
1197  henselStep12 (bufF, factors, bufFactors, diophant, M, Pi, i, b);
1198 
1199  CFListIterator k= factors;
1200  for (i= 0; i < factors.length (); i++, k++)
1201  k.getItem()= bufFactors[i];
1202  factors.removeFirst();
1203 }

◆ henselLift23()

CFList henselLift23 ( const CFList eval,
const CFList factors,
int *  l,
CFList diophant,
CFArray Pi,
CFMatrix M 
)

Hensel lifting from bivariate to trivariate.

Returns
henselLift23 returns a list of polynomials lifted to precision Variable (3)^l[1]
See also
henselLift12(), henselLiftResume12(), henselLiftResume(), henselLift()
Parameters
[in]eval[in] contains compressed, bivariate as first element and trivariate one as second element
[in]factors[in] monic bivariate factors, including leading coefficient as first element.
[in]l[in] l[0]: precision of bivariate lifting, l[1] as above
[in,out]diophant[in,out] returns the result of biDiophantine()
[in,out]Pi[in,out] stores intermediate results
[in,out]M[in,out] stores intermediate results

Definition at line 1653 of file facHensel.cc.

1655 {
1656  CFList buf= factors;
1657  int k= 0;
1658  int liftBoundBivar= l[k];
1659  diophant= biDiophantine (eval.getFirst(), buf, liftBoundBivar);
1660  CFList MOD;
1661  MOD.append (power (Variable (2), liftBoundBivar));
1662  CFArray bufFactors= CFArray (factors.length());
1663  k= 0;
1665  j++;
1666  buf.removeFirst();
1667  buf.insert (LC (j.getItem(), 1));
1668  for (CFListIterator i= buf; i.hasItem(); i++, k++)
1669  bufFactors[k]= i.getItem();
1670  Pi= CFArray (factors.length() - 1);
1671  CFListIterator i= buf;
1672  i++;
1673  Variable y= j.getItem().mvar();
1674  Pi [0]= mulMod (i.getItem(), mod (buf.getFirst(), y), MOD);
1675  M (1, 1)= Pi [0];
1676  k= 1;
1677  if (i.hasItem())
1678  i++;
1679  for (; i.hasItem(); i++, k++)
1680  {
1681  Pi [k]= mulMod (Pi [k - 1], i.getItem(), MOD);
1682  M (1, k + 1)= Pi [k];
1683  }
1684 
1685  for (int d= 1; d < l[1]; d++)
1686  henselStep (j.getItem(), buf, bufFactors, diophant, M, Pi, d, MOD);
1687  CFList result;
1688  for (k= 1; k < factors.length(); k++)
1689  result.append (bufFactors[k]);
1690  return result;
1691 }

◆ henselLiftResume()

void henselLiftResume ( const CanonicalForm F,
CFList factors,
int  start,
int  end,
CFArray Pi,
const CFList diophant,
CFMatrix M,
const CFList MOD 
)

resume Hensel lifting.

See also
henselLift12(), henselLiftResume12(), henselLift23(), henselLift()
Parameters
[in]F[in] compressed, multivariate poly
[in,out]factors[in,out] monic multivariate factors lifted to precision F.mvar()^start, including leading coefficient as first element. Returns factors lifted to precision F.mvar()^end
[in]start[in] starting precision
[in]end[in] end precision
[in,out]Pi[in,out] stores intermediate results
[in]diophant[in] result of multiRecDiophantine()
[in,out]M[in, out] stores intermediate results
[in]MOD[in] a list of powers of Variables of level higher than 1

Definition at line 1694 of file facHensel.cc.

1697 {
1698  CFArray bufFactors= CFArray (factors.length());
1699  int i= 0;
1700  CanonicalForm xToStart= power (F.mvar(), start);
1701  for (CFListIterator k= factors; k.hasItem(); k++, i++)
1702  {
1703  if (i == 0)
1704  bufFactors[i]= mod (k.getItem(), xToStart);
1705  else
1706  bufFactors[i]= k.getItem();
1707  }
1708  for (i= start; i < end; i++)
1709  henselStep (F, factors, bufFactors, diophant, M, Pi, i, MOD);
1710 
1711  CFListIterator k= factors;
1712  for (i= 0; i < factors.length(); k++, i++)
1713  k.getItem()= bufFactors [i];
1714  factors.removeFirst();
1715  return;
1716 }

◆ henselLiftResume12()

void henselLiftResume12 ( const CanonicalForm F,
CFList factors,
int  start,
int  end,
CFArray Pi,
const CFList diophant,
CFMatrix M,
const modpk b = modpk() 
)

resume Hensel lift from univariate to bivariate. Assumes factors are lifted to precision Variable (2)^start and lifts them to precision Variable (2)^end

See also
henselLift12(), henselLift23(), henselLiftResume(), henselLift()
Parameters
[in]F[in] compressed, bivariate poly
[in,out]factors[in,out] monic factors of F, lifted to precision start, including leading coefficient as first element. Returns monic lifted factors without the leading coefficient
[in]start[in] starting precision
[in]end[in] end precision
[in,out]Pi[in,out] stores intermediate results
[in]diophant[in] result of diophantine
[in,out]M[in,out] stores intermediate results
[in]b[in] coeff bound

Definition at line 1214 of file facHensel.cc.

1217 {
1218  CFArray bufFactors= CFArray (factors.length());
1219  int i= 0;
1220  CanonicalForm xToStart= power (F.mvar(), start);
1221  for (CFListIterator k= factors; k.hasItem(); k++, i++)
1222  {
1223  if (i == 0)
1224  bufFactors[i]= mod (k.getItem(), xToStart);
1225  else
1226  bufFactors[i]= k.getItem();
1227  }
1228  for (i= start; i < end; i++)
1229  henselStep12 (F, factors, bufFactors, diophant, M, Pi, i, b);
1230 
1231  CFListIterator k= factors;
1232  for (i= 0; i < factors.length(); k++, i++)
1233  k.getItem()= bufFactors [i];
1234  factors.removeFirst();
1235  return;
1236 }

◆ nonMonicHenselLift()

CFList nonMonicHenselLift ( const CFList eval,
const CFList factors,
CFList *const LCs,
CFList diophant,
CFArray Pi,
int *  liftBound,
int  length,
bool &  noOneToOne 
)

Hensel lifting of non monic factors, needs correct leading coefficients of factors and a one to one corresponds between bivariate and multivariate factors to succeed.

Returns
nonMonicHenselLift returns a list of lifted factors such that prod (factors) == eval.getLast() if there is a one to one correspondence
Parameters
[in]eval[in] a list of polys the last element is a compressed multivariate poly, last but one element equals the last elements modulo its main variable and so on. The first element is a compressed poly in 3 variables
[in]factors[in] a list of bivariate factors
[in]LCs[in] leading coefficients, evaluated in the same way as eval
[in,out]diophant[in, out] solution of univariate diophantine equation
[in,out]Pi[in, out] buffer intermediate results
[in]liftBound[in] lifting bounds
[in]length[in] length of lifting bounds
[in,out]noOneToOne[in, out] check for one to one correspondence

Definition at line 2792 of file facHensel.cc.

2796 {
2797  CFList bufDiophant= diophant;
2798  CFList buf= factors;
2799  CFArray bufPi= Pi;
2800  CFMatrix M= CFMatrix (liftBound[1], factors.length() - 1);
2801  int k= 0;
2802 
2803  TIMING_START (hensel23);
2804  CFList result=
2805  nonMonicHenselLift23 (eval.getFirst(), factors, LCs [0], diophant, bufPi,
2806  liftBound[1], liftBound[0], noOneToOne);
2807  TIMING_END_AND_PRINT (hensel23, "time for 23: ");
2808 
2809  if (noOneToOne)
2810  return CFList();
2811 
2812  if (eval.length() == 1)
2813  return result;
2814 
2815  k++;
2816  CFList MOD;
2817  for (int i= 0; i < 2; i++)
2818  MOD.append (power (Variable (i + 2), liftBound[i]));
2819 
2821  CFList bufEval;
2822  bufEval.append (j.getItem());
2823  j++;
2824 
2825  for (int i= 2; i <= length && j.hasItem(); i++, j++, k++)
2826  {
2827  bufEval.append (j.getItem());
2828  M= CFMatrix (liftBound[i], factors.length() - 1);
2829  TIMING_START (hensel);
2830  result= nonMonicHenselLift (bufEval, result, LCs [i-1], diophant, bufPi, M,
2831  liftBound[i-1], liftBound[i], MOD, noOneToOne);
2832  TIMING_END_AND_PRINT (hensel, "time for further hensel: ");
2833  if (noOneToOne)
2834  return result;
2835  MOD.append (power (Variable (i + 2), liftBound[i]));
2836  bufEval.removeFirst();
2837  }
2838 
2839  return result;
2840 }

◆ nonMonicHenselLift12()

void nonMonicHenselLift12 ( const CanonicalForm F,
CFList factors,
int  l,
CFArray Pi,
CFList diophant,
CFMatrix M,
const CFArray LCs,
bool  sort 
)

Hensel lifting from univariate to bivariate, factors need not to be monic.

Parameters
[in]F[in] a bivariate poly
[in,out]factors[in, out] a list of univariate polys lifted factors
[in]l[in] lift bound
[in,out]Pi[in, out] stores intermediate results
[in,out]diophant[in, out] result of diophantine
[in,out]M[in, out] stores intermediate results
[in]LCs[in] leading coefficients
[in]sort[in] if true factors are sorted by their degree

Definition at line 2018 of file facHensel.cc.

2021 {
2022  if (sort)
2023  sortList (factors, Variable (1));
2024  Pi= CFArray (factors.length() - 2);
2025  CFList bufFactors2= factors;
2026  bufFactors2.removeFirst();
2027  diophant= diophantine (F[0], bufFactors2);
2028  DEBOUTLN (cerr, "diophant= " << diophant);
2029 
2030  CFArray bufFactors= CFArray (bufFactors2.length());
2031  int i= 0;
2032  for (CFListIterator k= bufFactors2; k.hasItem(); i++, k++)
2033  bufFactors[i]= replaceLc (k.getItem(), LCs [i]);
2034 
2035  Variable x= F.mvar();
2036  if (degree (bufFactors[0], x) > 0 && degree (bufFactors [1], x) > 0)
2037  {
2038  M (1, 1)= mulNTL (bufFactors [0] [0], bufFactors[1] [0]);
2039  Pi [0]= M (1, 1) + (mulNTL (bufFactors [0] [1], bufFactors[1] [0]) +
2040  mulNTL (bufFactors [0] [0], bufFactors [1] [1]))*x;
2041  }
2042  else if (degree (bufFactors[0], x) > 0)
2043  {
2044  M (1, 1)= mulNTL (bufFactors [0] [0], bufFactors[1]);
2045  Pi [0]= M (1, 1) +
2046  mulNTL (bufFactors [0] [1], bufFactors[1])*x;
2047  }
2048  else if (degree (bufFactors[1], x) > 0)
2049  {
2050  M (1, 1)= mulNTL (bufFactors [0], bufFactors[1] [0]);
2051  Pi [0]= M (1, 1) +
2052  mulNTL (bufFactors [0], bufFactors[1] [1])*x;
2053  }
2054  else
2055  {
2056  M (1, 1)= mulNTL (bufFactors [0], bufFactors[1]);
2057  Pi [0]= M (1, 1);
2058  }
2059 
2060  for (i= 1; i < Pi.size(); i++)
2061  {
2062  if (degree (Pi[i-1], x) > 0 && degree (bufFactors [i+1], x) > 0)
2063  {
2064  M (1,i+1)= mulNTL (Pi[i-1] [0], bufFactors[i+1] [0]);
2065  Pi [i]= M (1,i+1) + (mulNTL (Pi[i-1] [1], bufFactors[i+1] [0]) +
2066  mulNTL (Pi[i-1] [0], bufFactors [i+1] [1]))*x;
2067  }
2068  else if (degree (Pi[i-1], x) > 0)
2069  {
2070  M (1,i+1)= mulNTL (Pi[i-1] [0], bufFactors [i+1]);
2071  Pi [i]= M(1,i+1) + mulNTL (Pi[i-1] [1], bufFactors[i+1])*x;
2072  }
2073  else if (degree (bufFactors[i+1], x) > 0)
2074  {
2075  M (1,i+1)= mulNTL (Pi[i-1], bufFactors [i+1] [0]);
2076  Pi [i]= M (1,i+1) + mulNTL (Pi[i-1], bufFactors[i+1] [1])*x;
2077  }
2078  else
2079  {
2080  M (1,i+1)= mulNTL (Pi [i-1], bufFactors [i+1]);
2081  Pi [i]= M (1,i+1);
2082  }
2083  }
2084 
2085  for (i= 1; i < l; i++)
2086  nonMonicHenselStep12 (F, bufFactors2, bufFactors, diophant, M, Pi, i, LCs);
2087 
2088  factors= CFList();
2089  for (i= 0; i < bufFactors.size(); i++)
2090  factors.append (bufFactors[i]);
2091  return;
2092 }

◆ nonMonicHenselLift2()

CFList nonMonicHenselLift2 ( const CFList eval,
const CFList factors,
int *  l,
int  lLength,
bool  sort,
const CFList LCs1,
const CFList LCs2,
const CFArray Pi,
const CFList diophant,
bool &  noOneToOne 
)

two factor Hensel lifting from bivariate to multivariate, factors need not to be monic

Returns
henselLift122 returns a list of lifted factors
Parameters
[in]eval[in] a list of polynomials the last element is a compressed multivariate poly, last but one element equals the last elements modulo its main variable and so on. The first element is a compressed bivariate poly.
[in]factors[in] bivariate factors
[in]l[in] lift bounds
[in]lLength[in] length of l
[in]sort[in] if true factors are sorted by their degree in Variable(1)
[in]LCs1[in] a list of evaluated LC of first factor
[in]LCs2[in] a list of evaluated LC of second factor
[in]Pi[in] intermediate result
[in]diophant[in] result of diophantine
[in,out]noOneToOne[in,out] check for one to one correspondence

Definition at line 2555 of file facHensel.cc.

2558 {
2559  CFList bufDiophant= diophant;
2560  CFList buf= factors;
2561  if (sort)
2562  sortList (buf, Variable (1));
2563  CFArray bufPi= Pi;
2564  CFMatrix M= CFMatrix (l[1], factors.length());
2565  CFList result=
2566  nonMonicHenselLift232(eval, buf, l, bufDiophant, bufPi, M, LCs1, LCs2, bad);
2567  if (bad)
2568  return CFList();
2569 
2570  if (eval.length() == 2)
2571  return result;
2572  CFList MOD;
2573  for (int i= 0; i < 2; i++)
2574  MOD.append (power (Variable (i + 2), l[i]));
2576  j++;
2577  CFList bufEval;
2578  bufEval.append (j.getItem());
2579  j++;
2580  CFListIterator jj= LCs1;
2581  CFListIterator jjj= LCs2;
2582  CFList bufLCs1, bufLCs2;
2583  jj++, jjj++;
2584  bufLCs1.append (jj.getItem());
2585  bufLCs2.append (jjj.getItem());
2586  jj++, jjj++;
2587 
2588  for (int i= 2; i < lLength && j.hasItem(); i++, j++, jj++, jjj++)
2589  {
2590  bufEval.append (j.getItem());
2591  bufLCs1.append (jj.getItem());
2592  bufLCs2.append (jjj.getItem());
2593  M= CFMatrix (l[i], factors.length());
2594  result= nonMonicHenselLift2 (bufEval, result, MOD, bufDiophant, bufPi, M,
2595  l[i - 1], l[i], bufLCs1, bufLCs2, bad);
2596  if (bad)
2597  return CFList();
2598  MOD.append (power (Variable (i + 2), l[i]));
2599  bufEval.removeFirst();
2600  bufLCs1.removeFirst();
2601  bufLCs2.removeFirst();
2602  }
2603  return result;
2604 }

◆ sortList()

void sortList ( CFList list,
const Variable x 
)

sort a list of polynomials by their degree in x.

Parameters
[in,out]list[in, out] list of polys, sorted list
[in]x[in] some Variable

Definition at line 441 of file facHensel.cc.

442 {
443  int l= 1;
444  int k= 1;
447  for (CFListIterator i= list; l <= list.length(); i++, l++)
448  {
449  for (CFListIterator j= list; k <= list.length() - l; k++)
450  {
451  m= j;
452  m++;
453  if (degree (j.getItem(), x) > degree (m.getItem(), x))
454  {
455  buf= m.getItem();
456  m.getItem()= j.getItem();
457  j.getItem()= buf;
458  j++;
459  j.getItem()= m.getItem();
460  }
461  else
462  j++;
463  }
464  k= 1;
465  }
466 }
Matrix
Definition: ftmpl_matrix.h:20
mod
static int mod(const CFList &L, const CanonicalForm &p)
Definition: facHensel.cc:244
nonMonicHenselLift
CFList nonMonicHenselLift(const CFList &F, const CFList &factors, const CFList &LCs, CFList &diophant, CFArray &Pi, CFMatrix &M, int lOld, int &lNew, const CFList &MOD, bool &noOneToOne)
Definition: facHensel.cc:2709
j
int j
Definition: facHensel.cc:105
M
const CanonicalForm & M
Definition: facHensel.cc:92
henselStep12
void henselStep12(const CanonicalForm &F, const CFList &factors, CFArray &bufFactors, const CFList &diophant, CFMatrix &M, CFArray &Pi, int j, const modpk &b)
Definition: facHensel.cc:945
biDiophantine
CFList biDiophantine(const CanonicalForm &F, const CFList &factors, int d)
Definition: facHensel.cc:1239
k
int k
Definition: cfEzgcd.cc:92
DEBOUTLN
#define DEBOUTLN(stream, objects)
Definition: debug.h:49
y
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
CFArray
Array< CanonicalForm > CFArray
Definition: canonicalform.h:390
nonMonicHenselLift23
CFList nonMonicHenselLift23(const CanonicalForm &F, const CFList &factors, const CFList &LCs, CFList &diophant, CFArray &Pi, int liftBound, int bivarLiftBound, bool &bad)
Definition: facHensel.cc:2607
henselStep
static void henselStep(const CanonicalForm &F, const CFList &factors, CFArray &bufFactors, const CFList &diophant, CFMatrix &M, CFArray &Pi, int j, const CFList &MOD)
Definition: facHensel.cc:1428
sortList
void sortList(CFList &list, const Variable &x)
sort a list of polynomials by their degree in x.
Definition: facHensel.cc:441
multiRecDiophantine
CFList multiRecDiophantine(const CanonicalForm &F, const CFList &factors, const CFList &recResult, const CFList &M, int d)
Definition: facHensel.cc:1339
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition: canonicalform.cc:1837
length
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:267
bad
bool bad
Definition: facFactorize.cc:65
CFMatrix
Matrix< CanonicalForm > CFMatrix
Definition: canonicalform.h:391
w
const CanonicalForm & w
Definition: facAbsFact.cc:55
getCharacteristic
int getCharacteristic()
Definition: cf_char.cc:51
b
CanonicalForm b
Definition: cfModGcd.cc:4044
buf
fq_nmod_t buf
Definition: facHensel.cc:96
CanonicalForm
factory's main class
Definition: canonicalform.h:77
replacevar
static CFList replacevar(const CFList &L, const Variable &a, const Variable &b)
Definition: facHensel.cc:281
replaceLc
CanonicalForm replaceLc(const CanonicalForm &f, const CanonicalForm &c)
Definition: fac_util.cc:89
nonMonicHenselLift232
CFList nonMonicHenselLift232(const CFList &eval, const CFList &factors, int *l, CFList &diophant, CFArray &Pi, CFMatrix &M, const CFList &LCs1, const CFList &LCs2, bool &bad)
Definition: facHensel.cc:2429
i
int i
Definition: cfEzgcd.cc:125
Array
Definition: ftmpl_array.h:17
result
CFList result
Definition: facHensel.cc:121
mulNTL
CanonicalForm mulNTL(const CanonicalForm &F, const CanonicalForm &G, const modpk &b)
multiplication of univariate polys using FLINT/NTL over F_p, F_q, Z/p^k, Z/p^k[t]/(f),...
Definition: facMul.cc:407
hasFirstAlgVar
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:665
Array::size
int size() const
Definition: ftmpl_array.cc:92
TIMING_START
TIMING_START(fac_alg_resultant)
henselLift12
void henselLift12(const CanonicalForm &F, CFList &factors, int l, CFArray &Pi, CFList &diophant, CFMatrix &M, modpk &b, bool sort)
Hensel lift from univariate to bivariate.
Definition: facHensel.cc:1148
x
Variable x
Definition: facHensel.cc:122
henselLift
CFList henselLift(const CFList &F, const CFList &factors, const CFList &MOD, CFList &diophant, CFArray &Pi, CFMatrix &M, int lOld, int lNew)
Hensel lifting.
Definition: facHensel.cc:1719
eval
CFList & eval
Definition: facFactorize.cc:48
sort
void sort(CFArray &A, int l=0)
quick sort A
Definition: facSparseHensel.h:114
List::removeFirst
void removeFirst()
Definition: ftmpl_list.cc:287
modpk
class to do operations mod p^k for int's p and k
Definition: fac_util.h:22
List::getFirst
T getFirst() const
Definition: ftmpl_list.cc:279
mulMod
CanonicalForm mulMod(const CanonicalForm &A, const CanonicalForm &B, const CFList &MOD)
Karatsuba style modular multiplication for multivariate polynomials.
Definition: facMul.cc:2947
diophantine
CFList diophantine(const CanonicalForm &F, const CFList &factors)
Definition: facHensel.cc:938
List::length
int length() const
Definition: ftmpl_list.cc:273
TIMING_END_AND_PRINT
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
Variable
factory's class for variables
Definition: factory.h:117
ListIterator::getItem
T & getItem() const
Definition: ftmpl_list.cc:431
CanonicalForm::mvar
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
Definition: canonicalform.cc:560
LC
CanonicalForm LC(const CanonicalForm &f)
Definition: canonicalform.h:303
m
int m
Definition: cfEzgcd.cc:121
l
int l
Definition: cfEzgcd.cc:93
hasAlgVar
int hasAlgVar(const CanonicalForm &f, const Variable &v)
Definition: facAlgFuncUtil.cc:322
nonMonicHenselLift2
CFList nonMonicHenselLift2(const CFList &F, const CFList &factors, const CFList &MOD, CFList &diophant, CFArray &Pi, CFMatrix &M, int lOld, int &lNew, const CFList &LCs1, const CFList &LCs2, bool &bad)
Definition: facHensel.cc:2492
nonMonicHenselStep12
void nonMonicHenselStep12(const CanonicalForm &F, const CFList &factors, CFArray &bufFactors, const CFList &diophant, CFMatrix &M, CFArray &Pi, int j, const CFArray &)
Definition: facHensel.cc:1797
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
List< CanonicalForm >
CFList
List< CanonicalForm > CFList
Definition: canonicalform.h:388
List::append
void append(const T &)
Definition: ftmpl_list.cc:256
modpk
return modpk(p, k)
degree
int degree(const CanonicalForm &f)
Definition: canonicalform.h:309
List::insert
void insert(const T &)
Definition: ftmpl_list.cc:193
List::getLast
T getLast() const
Definition: ftmpl_list.cc:309
henselLift23
CFList henselLift23(const CFList &eval, const CFList &factors, int *l, CFList &diophant, CFArray &Pi, CFMatrix &M)
Hensel lifting from bivariate to trivariate.
Definition: facHensel.cc:1653
ListIterator
Definition: ftmpl_list.h:17