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