facHensel.h
Go to the documentation of this file.
1 /*****************************************************************************\
2  * Computer Algebra System SINGULAR
3 \*****************************************************************************/
4 /** @file facHensel.h
5  *
6  * This file defines functions for Hensel lifting.
7  *
8  * ABSTRACT: function are used for bi- and multivariate factorization over
9  * finite fields. Described in "Efficient Multivariate Factorization over Finite
10  * Fields" by L. Bernardin & M. Monagon and "Algorithms for Computer Algebra" by
11  * Geddes, Czapor, Labahn
12  *
13  * @author Martin Lee
14  *
15  **/
16 /*****************************************************************************/
17 
18 #ifndef FAC_HENSEL_H
19 #define FAC_HENSEL_H
20 
21 // #include "config.h"
22 #include "cf_assert.h"
23 #include "debug.h"
24 #include "timing.h"
25 
26 #include "canonicalform.h"
27 #include "fac_util.h"
28 
29 #ifdef HAVE_NTL
30 /// sort a list of polynomials by their degree in @a x.
31 ///
32 void sortList (CFList& list, ///< [in, out] list of polys, sorted list
33  const Variable& x ///< [in] some Variable
34  );
35 
36 /// Hensel lift from univariate to bivariate.
37 ///
38 /// @sa henselLiftResume12(), henselLift23(), henselLiftResume(), henselLift()
39 void
40 henselLift12 (const CanonicalForm& F, ///< [in] compressed, bivariate poly
41  CFList& factors, ///< [in, out] monic univariate factors of
42  ///< F, including leading coefficient as
43  ///< first element. Returns monic lifted
44  ///< factors without the leading
45  ///< coefficient
46  int l, ///< [in] lifting precision
47  CFArray& Pi, ///< [in,out] stores intermediate results
48  CFList& diophant, ///< [in,out] result of diophantine()
49  CFMatrix& M, ///< [in,out] stores intermediate results
50  modpk& b, ///< [in] coeff bound
51  bool sort= true ///< [in] sort factors by degree in
52  ///< Variable(1)
53  );
54 
55 /// Hensel lift from univariate to bivariate.
56 ///
57 /// @sa henselLiftResume12(), henselLift23(), henselLiftResume(), henselLift()
58 void
59 henselLift12 (const CanonicalForm& F, ///< [in] compressed, bivariate poly
60  CFList& factors, ///< [in, out] monic univariate factors of
61  ///< F, including leading coefficient as
62  ///< first element. Returns monic lifted
63  ///< factors without the leading
64  ///< coefficient
65  int l, ///< [in] lifting precision
66  CFArray& Pi, ///< [in,out] stores intermediate results
67  CFList& diophant, ///< [in,out] result of diophantine()
68  CFMatrix& M, ///< [in,out] stores intermediate results
69  bool sort= true ///< [in] sort factors by degree in
70  ///< Variable(1)
71  );
72 
73 /// resume Hensel lift from univariate to bivariate. Assumes factors are lifted
74 /// to precision Variable (2)^start and lifts them to precision Variable (2)^end
75 ///
76 /// @sa henselLift12(), henselLift23(), henselLiftResume(), henselLift()
77 void
78 henselLiftResume12 (const CanonicalForm& F, ///< [in] compressed, bivariate poly
79  CFList& factors, ///< [in,out] monic factors of F,
80  ///< lifted to precision start,
81  ///< including leading coefficient
82  ///< as first element. Returns monic
83  ///< lifted factors without the
84  ///< leading coefficient
85  int start, ///< [in] starting precision
86  int end, ///< [in] end precision
87  CFArray& Pi, ///< [in,out] stores intermediate
88  ///< results
89  const CFList& diophant, ///< [in] result of diophantine
90  CFMatrix& M, ///< [in,out] stores intermediate
91  ///< results
92  const modpk& b= modpk() ///< [in] coeff bound
93  );
94 
95 /// Hensel lifting from bivariate to trivariate.
96 ///
97 /// @return @a henselLift23 returns a list of polynomials lifted to precision
98 /// Variable (3)^l[1]
99 /// @sa henselLift12(), henselLiftResume12(), henselLiftResume(), henselLift()
100 CFList
101 henselLift23 (const CFList& eval, ///< [in] contains compressed, bivariate
102  ///< as first element and trivariate one as
103  ///< second element
104  const CFList& factors, ///< [in] monic bivariate factors,
105  ///< including leading coefficient
106  ///< as first element.
107  int* l, ///< [in] l[0]: precision of bivariate
108  ///< lifting, l[1] as above
109  CFList& diophant, ///< [in,out] returns the result of
110  ///< biDiophantine()
111  CFArray& Pi, ///< [in,out] stores intermediate results
112  CFMatrix& M ///< [in,out] stores intermediate results
113  );
114 
115 /// resume Hensel lifting.
116 ///
117 /// @sa henselLift12(), henselLiftResume12(), henselLift23(), henselLift()
118 void
120  const CanonicalForm& F, ///< [in] compressed, multivariate poly
121  CFList& factors, ///< [in,out] monic multivariate factors
122  ///< lifted to precision F.mvar()^start,
123  ///< including leading coefficient
124  ///< as first element. Returns factors
125  ///< lifted to precision F.mvar()^end
126  int start, ///< [in] starting precision
127  int end, ///< [in] end precision
128  CFArray& Pi, ///< [in,out] stores intermediate results
129  const CFList& diophant, ///< [in] result of multiRecDiophantine()
130  CFMatrix& M, ///< [in, out] stores intermediate results
131  const CFList& MOD ///< [in] a list of powers of Variables
132  ///< of level higher than 1
133  );
134 
135 /// Hensel lifting
136 ///
137 /// @return @a henselLift returns a list of polynomials lifted to
138 /// precision F.getLast().mvar()^l_new
139 /// @sa henselLift12(), henselLiftResume12(), henselLift23(), henselLiftResume()
140 CFList
141 henselLift (const CFList& F, ///< [in] two compressed, multivariate
142  ///< polys F and G
143  const CFList& factors, ///< [in] monic multivariate factors
144  ///< including leading coefficient
145  ///< as first element.
146  const CFList& MOD, ///< [in] a list of powers of Variables
147  ///< of level higher than 1
148  CFList& diophant, ///< [in,out] result of multiRecDiophantine()
149  CFArray& Pi, ///< [in,out] stores intermediate results
150  CFMatrix& M, ///< [in,out] stores intermediate results
151  int lOld, ///< [in] lifting precision of F.mvar()
152  int lNew ///< [in] lifting precision of G.mvar()
153  );
154 
155 /// Hensel lifting from bivariate to multivariate
156 ///
157 /// @return @a henselLift returns a list of lifted factors
158 /// @sa henselLift12(), henselLiftResume12(), henselLift23(), henselLiftResume()
159 CFList
160 henselLift (const CFList& eval, ///< [in] a list of polynomials the last
161  ///< element is a compressed multivariate
162  ///< poly, last but one element equals the
163  ///< last elements modulo its main variable
164  ///< and so on. The first element is a
165  ///< compressed bivariate poly.
166  const CFList& factors, ///< [in] bivariate factors, including
167  ///< leading coefficient
168  int* l, ///< [in] lifting bounds
169  int lLength, ///< [in] length of l
170  bool sort= true ///< [in] sort factors by degree in
171  ///< Variable(1)
172  );
173 
174 /// Hensel lifting from univariate to bivariate, factors need not to be monic
175 void
176 nonMonicHenselLift12 (const CanonicalForm& F,///< [in] a bivariate poly
177  CFList& factors, ///< [in, out] a list of univariate polys
178  ///< lifted factors
179  int l, ///< [in] lift bound
180  CFArray& Pi, ///< [in, out] stores intermediate results
181  CFList& diophant, ///< [in, out] result of diophantine
182  CFMatrix& M, ///< [in, out] stores intermediate results
183  const CFArray& LCs, ///< [in] leading coefficients
184  bool sort ///< [in] if true factors are sorted by
185  ///< their degree
186  );
187 
188 /// two factor Hensel lifting from bivariate to multivariate, factors need not
189 /// to be monic
190 ///
191 /// @return @a henselLift122 returns a list of lifted factors
192 CFList
193 nonMonicHenselLift2 (const CFList& eval,///< [in] a list of polynomials the last
194  ///< element is a compressed multivariate
195  ///< poly, last but one element equals the
196  ///< last elements modulo its main variable
197  ///< and so on. The first element is a
198  ///< compressed bivariate poly.
199  const CFList& factors,///< [in] bivariate factors
200  int* l, ///< [in] lift bounds
201  int lLength, ///< [in] length of l
202  bool sort, ///< [in] if true factors are sorted by
203  ///< their degree in Variable(1)
204  const CFList& LCs1, ///< [in] a list of evaluated LC of first
205  ///< factor
206  const CFList& LCs2, ///< [in] a list of evaluated LC of second
207  ///< factor
208  const CFArray& Pi, ///< [in] intermediate result
209  const CFList& diophant,///< [in] result of diophantine
210  bool& noOneToOne ///< [in,out] check for one to one
211  ///< correspondence
212  );
213 
214 /// Hensel lifting of non monic factors, needs correct leading coefficients of
215 /// factors and a one to one corresponds between bivariate and multivariate
216 /// factors to succeed
217 ///
218 /// @return @a nonMonicHenselLift returns a list of lifted factors
219 /// such that prod (factors) == eval.getLast() if there is a one to one
220 /// correspondence
221 CFList
222 nonMonicHenselLift (const CFList& eval, ///< [in] a list of polys the last
223  ///< element is a compressed
224  ///< multivariate poly, last but one
225  ///< element equals the last elements
226  ///< modulo its main variable and so
227  ///< on. The first element is a
228  ///< compressed poly in 3 variables
229  const CFList& factors, ///< [in] a list of bivariate factors
230  CFList* const& LCs, ///< [in] leading coefficients,
231  ///< evaluated in the same way as
232  ///< eval
233  CFList& diophant, ///< [in, out] solution of univariate
234  ///< diophantine equation
235  CFArray& Pi, ///< [in, out] buffer intermediate
236  ///< results
237  int* liftBound, ///< [in] lifting bounds
238  int length, ///< [in] length of lifting bounds
239  bool& noOneToOne ///< [in, out] check for one to one
240  ///< correspondence
241  );
242 #endif /* HAVE_NTL */
243 #endif
244 /* FAC_HENSEL_H */
245 
void henselLiftResume(const CanonicalForm &F, CFList &factors, int start, int end, CFArray &Pi, const CFList &diophant, CFMatrix &M, const CFList &MOD)
resume Hensel lifting.
Definition: facHensel.cc:1694
functions to print debug output
factory&#39;s class for variables
Definition: factory.h:115
factory&#39;s main class
Definition: canonicalform.h:75
assertions for Factory
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
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 c...
Definition: facHensel.cc:2792
return modpk(p, k)
#define M
Definition: sirandom.c:24
CFList & eval
Definition: facFactorize.cc:48
void sortList(CFList &list, const Variable &x)
sort a list of polynomials by their degree in x.
Definition: facHensel.cc:441
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.
Definition: facHensel.cc:1148
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 ...
Definition: facHensel.cc:2555
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)...
Definition: facHensel.cc:1214
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.
Definition: facHensel.cc:2018
Variable x
Definition: cfModGcd.cc:4023
void sort(CFArray &A, int l=0)
quick sort A
operations mod p^k and some other useful functions for factorization
const poly b
Definition: syzextra.cc:213
class to do operations mod p^k for int&#39;s p and k
Definition: fac_util.h:22
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
int l
Definition: cfEzgcd.cc:94
Header for factory&#39;s main class CanonicalForm.