source: git/factory/facHensel.h @ 6e2ef0e

spielwiese
Last change on this file since 6e2ef0e was e368746, checked in by Martin Lee <martinlee84@…>, 13 years ago
added new functions for multivariate Hensel lifting minor changes of existing Hensel lift functions git-svn-id: file:///usr/local/Singular/svn/trunk@14259 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 21.8 KB
Line 
1/*****************************************************************************\
2 * Computer Algebra System SINGULAR
3\*****************************************************************************/
4/** @file facHensel.h
5 *
6 * This file defines functions for Hensel lifting and modular multiplication.
7 *
8 * ABSTRACT: function are used for bi- and multivariate factorization over
9 * finite fields
10 *
11 * @author Martin Lee
12 *
13 * @internal @version \$Id$
14 *
15 **/
16/*****************************************************************************/
17
18#ifndef FAC_HENSEL_H
19#define FAC_HENSEL_H
20
21#include <config.h>
22#include "assert.h"
23#include "debug.h"
24#include "timing.h"
25
26#include "canonicalform.h"
27#include "cf_iter.h"
28#include "templates/ftmpl_functions.h"
29#include "algext.h"
30
31/// multiplication of univariate polys over a finite field using NTL, if we are
32/// in GF factory's default multiplication is used.
33///
34/// @return @a mulNTL returns F*G
35CanonicalForm
36mulNTL (const CanonicalForm& F, ///< [in] a univariate poly
37        const CanonicalForm& G  ///< [in] a univariate poly
38       );
39
40/// mod of univariate polys over a finite field using NTL, if we are
41/// in GF factory's default mod is used.
42///
43/// @return @a modNTL returns F mod G
44CanonicalForm
45modNTL (const CanonicalForm& F, ///< [in] a univariate poly
46        const CanonicalForm& G  ///< [in] a univariate poly
47       );
48
49/// division of univariate polys over a finite field using NTL, if we are
50/// in GF factory's default division is used.
51///
52/// @return @a divNTL returns F/G
53CanonicalForm
54divNTL (const CanonicalForm& F, ///< [in] a univariate poly
55        const CanonicalForm& G  ///< [in] a univariate poly
56       );
57
58/*/// division with remainder of univariate polys over a finite field using NTL,
59/// if we are in GF factory's default division with remainder is used.
60void
61divremNTL (const CanonicalForm& F, ///< [in] a univariate poly
62           const CanonicalForm& G, ///< [in] a univariate poly
63           CanonicalForm& Q,       ///< [in,out] dividend
64           CanonicalForm& R        ///< [in,out] remainder
65          );*/
66
67/// splits @a F into degree (F, x)/m polynomials each of degree less than @a m
68/// in @a x.
69///
70/// @return @a split returns a list of polynomials of degree less than @a m in
71///         @a x. If degree (F, x) <= 0, F is returned.
72/// @sa divrem32(), divrem21()
73static inline
74CFList split (const CanonicalForm& F, ///< [in] some poly
75              const int m,            ///< [in] some int
76              const Variable& x       ///< [in] some Variable
77             );
78
79/// division with remainder of @a F by
80/// @a G wrt Variable (1) modulo @a M.
81///
82/// @sa divrem(), divrem21(), divrem2()
83static inline
84void divrem32 (const CanonicalForm& F, ///< [in] poly, s.t. 3*(degree (G, 1)/2)>
85                                       ///< degree (F, 1)
86               const CanonicalForm& G, ///< [in] some poly
87               CanonicalForm& Q,       ///< [in,out] dividend
88               CanonicalForm& R,       ///< [in,out] remainder, degree (R, 1) <
89                                       ///< degree (G, 1)
90               const CFList& M         ///< [in] only contains powers of
91                                       ///< Variables of level higher than 1
92              );
93
94/// division with remainder of @a F by
95/// @a G wrt Variable (1) modulo @a M.
96///
97/// @sa divrem(), divrem32(), divrem2()
98static inline
99void divrem21 (const CanonicalForm& F, ///< [in] poly, s.t. 2*degree (G, 1) >
100                                       ///< degree (F, 1)
101               const CanonicalForm& G, ///< [in] some poly
102               CanonicalForm& Q,       ///< [in,out] dividend
103               CanonicalForm& R,       ///< [in,out] remainder, degree (R, 1) <
104                                       ///< degree (G, 1)
105               const CFList& M         ///< [in] only contains powers of
106                                       ///< Variables of level higher than 1
107              );
108
109/// division with remainder of @a F by
110/// @a G wrt Variable (1) modulo @a M.
111///
112/// @return @a Q returns the dividend, @a R returns the remainder.
113/// @sa divrem()
114void divrem2 (const CanonicalForm& F, ///< [in] bivariate, compressed polynomial
115              const CanonicalForm& G, ///< [in] bivariate, compressed polynomial
116              CanonicalForm& Q,       ///< [in,out] dividend
117              CanonicalForm& R,       ///< [in,out] remainder, degree (R, 1) <
118                                      ///< degree (G, 1)
119              const CanonicalForm& M  ///< [in] power of Variable (2)
120             );
121
122/// division with remainder of @a F by
123/// @a G wrt Variable (1) modulo @a MOD.
124///
125/// @sa divrem2()
126void divrem (
127           const CanonicalForm& F, ///< [in] multivariate, compressed polynomial
128           const CanonicalForm& G, ///< [in] multivariate, compressed polynomial
129           CanonicalForm& Q,       ///< [in,out] dividend
130           CanonicalForm& R,       ///< [in,out] remainder, degree (R, 1) <
131                                   ///< degree (G, 1)
132           const CFList& MOD       ///< [in] only contains powers of
133                                   ///< Variables of level higher than 1
134            );
135
136
137/// division with remainder of @a F by
138/// @a G wrt Variable (1) modulo @a M using Newton inversion
139///
140/// @return @a Q returns the dividend, @a R returns the remainder.
141/// @sa divrem2(), newtonDiv()
142void
143newtonDivrem (const CanonicalForm& F, ///< [in] bivariate, compressed polynomial
144              const CanonicalForm& G, ///< [in] bivariate, compressed polynomial
145                                      ///< which is monic in Variable (1)
146              CanonicalForm& Q,       ///< [in,out] dividend
147              CanonicalForm& R,       ///< [in,out] remainder, degree (R, 1) <
148                                      ///< degree (G, 1)
149              const CanonicalForm& M  ///< [in] power of Variable (2)
150             );
151
152/// division of @a F by
153/// @a G wrt Variable (1) modulo @a M using Newton inversion
154///
155/// @return @a newtonDiv returns the dividend
156/// @sa divrem2(), newtonDivrem()
157CanonicalForm
158newtonDiv (const CanonicalForm& F, ///< [in] bivariate, compressed polynomial
159           const CanonicalForm& G, ///< [in] bivariate, compressed polynomial
160                                   ///< which is monic in Variable (1)
161           const CanonicalForm& M  ///< [in] power of Variable (2)
162          );
163
164/// reduce @a F modulo elements in @a M.
165///
166/// @return @a mod returns @a F modulo @a M
167CanonicalForm mod (const CanonicalForm& F, ///< [in] compressed polynomial
168                   const CFList& M         ///< [in] list containing only
169                                           ///< univariate polynomials
170                  );
171
172/// Karatsuba style modular multiplication for bivariate polynomials.
173///
174/// @return @a mulMod2 returns @a A * @a B mod @a M.
175CanonicalForm
176mulMod2 (const CanonicalForm& A, ///< [in] bivariate, compressed polynomial
177         const CanonicalForm& B, ///< [in] bivariate, compressed polynomial
178         const CanonicalForm& M  ///< [in] power of Variable (2)
179        );
180
181/// Karatsuba style modular multiplication for multivariate polynomials.
182///
183/// @return @a mulMod2 returns @a A * @a B mod @a MOD.
184CanonicalForm
185mulMod (const CanonicalForm& A, ///< [in] multivariate, compressed polynomial
186        const CanonicalForm& B, ///< [in] multivariate, compressed polynomial
187        const CFList& MOD       ///< [in] only contains powers of
188                                ///< Variables of level higher than 1
189       );
190
191/// product of all elements in @a L modulo @a M via divide-and-conquer.
192///
193/// @return @a prodMod returns product of all elements in @a L modulo @a M.
194CanonicalForm
195prodMod (const CFList& L,       ///< [in] contains only bivariate, compressed
196                                ///< polynomials
197         const CanonicalForm& M ///< [in] power of Variable (2)
198        );
199
200/// product of all elements in @a L modulo @a M via divide-and-conquer.
201///
202/// @return @a prodMod returns product of all elements in @a L modulo @a M.
203CanonicalForm
204prodMod (const CFList& L, ///< [in] contains multivariate, compressed
205                          ///< polynomials
206         const CFList& M  ///< [in] contains only powers of Variables
207        );
208
209/// sort a list of polynomials by their degree in @a x.
210///
211void sortList (CFList& list,     ///< [in, out] list of polys, sorted list
212               const Variable& x ///< [in] some Variable
213              );
214
215/// solve the univariate diophantine equation
216/// \f$ 1\equiv \sum_{i= 1}^{r} {\delta_{i} F/g_{i}} \f$.
217/// Where \f$ F= \prod_{i= 1}^{r} {g_{i}} \f$ and \f$ F \f$ is squarefree
218/// the \f$ \delta_{i} \f$ have degree less than the degree of \f$ g_{i} \f$.
219///
220/// @return @a diophantine returns a list of polynomials \f$ \delta_{i} \f$ as
221/// specified above
222/// @sa biDiophantine(), multiRecDiophantine()
223static inline
224CFList diophantine (const CanonicalForm& F, ///< [in] compressed, bivariate
225                                            ///< polynomial
226                    const CFList& factors   ///< [in] a list of factors, as
227                                            ///< specified above, including
228                                            ///< LC (F, Variable (1)) as first
229                                            ///< element
230                   );
231
232/// Hensel lift from univariate to bivariate.
233///
234/// @sa henselLiftResume12(), henselLift23(), henselLiftResume(), henselLift()
235void
236henselLift12 (const CanonicalForm& F, ///< [in] compressed, bivariate poly
237              CFList& factors,        ///< [in, out] monic univariate factors of
238                                      ///< F, including leading coefficient as
239                                      ///< first element. Returns monic lifted
240                                      ///< factors without the leading
241                                      ///< coefficient
242              int l,                  ///< [in] lifting precision
243              CFArray& Pi,            ///< [in,out] stores intermediate results
244              CFList& diophant,       ///< [in,out] result of diophantine()
245              CFMatrix& M,            ///< [in,out] stores intermediate results
246              bool sort= true         ///< [in] sort factors by degree in
247                                      ///< Variable(1)
248             );
249
250/// resume Hensel lift from univariate to bivariate. Assumes factors are lifted
251/// to precision Variable (2)^start and lifts them to precision Variable (2)^end
252///
253/// @sa henselLift12(), henselLift23(), henselLiftResume(), henselLift()
254void
255henselLiftResume12 (const CanonicalForm& F, ///< [in] compressed, bivariate poly
256                    CFList& factors,        ///< [in,out] monic factors of F,
257                                            ///< lifted to precision start,
258                                            ///< including leading coefficient
259                                            ///< as first element. Returns monic
260                                            ///< lifted factors without the
261                                            ///< leading coefficient
262                    int start,              ///< [in] starting precision
263                    int end,                ///< [in] end precision
264                    CFArray& Pi,            ///< [in,out] stores intermediate
265                                            ///< results
266                    const CFList& diophant, ///< [in] result of diophantine
267                    CFMatrix& M             ///< [in,out] stores intermediate
268                                            ///< results
269                   );
270
271/// solves the bivariate polynomial diophantine equation
272/// \f$ 1\equiv \sum_{i= 1}^{r} {\delta_{i} F/g_{i}} \ mod\ y^{d} \f$,
273/// where \f$ F= \prod_{i= 1}^{r} {g_{i}} \ mod\ y^{d}\f$ and
274/// \f$ F \in K[x][y]\f$ is squarefree, the \f$ \delta_{i} \f$ have degree less
275/// than the degree of \f$ g_{i} \f$ in x.
276///
277/// @return @a biDiophantine returns a list of polynomials \f$ \delta_{i} \f$ as
278///         specified above
279/// @sa diophantine(), multiRecDiophantine()
280static inline
281CFList
282biDiophantine (const CanonicalForm& F, ///< [in] compressed, bivariate poly
283               const CFList& factors,  ///< [in] list of monic bivariate factors
284                                       ///< including LC (F, Variable (1)) as
285                                       ///< first element
286               const int d             ///< [in] precision
287              );
288
289/// solve the multivariate polynomial diophantine equation
290/// \f$ 1\equiv \sum_{i= 1}^{r} {\delta_{i} F/g_{i}} \ mod\ <M,F.mvar()^{d}>\f$,
291/// where \f$ F= \prod_{i= 1}^{r} {g_{i}} \ mod\ <M,F.mvar()^{d}>\f$ and
292/// \f$ F \in K[x][x_1,\ldots , x_n]\f$ is squarefree, the \f$ \delta_{i} \f$
293/// have degree less than the degree of \f$ g_{i} \f$ in x.
294///
295/// @return @a multiDiophantine returns a list of polynomials \f$ \delta_{i} \f$
296///         as specified above
297/// @sa diophantine(), biDiophantine()
298static inline
299CFList
300multiRecDiophantine (
301               const CanonicalForm& F,   ///< [in] compressed,
302                                         ///< multivariate polynomial
303               const CFList& factors,    ///< [in] list of monic factors
304                                         ///< including LC (F, Variable (1)) as
305                                         ///< first element
306               const CFList& recResult, ///< [in] result of above equation
307                                         ///< modulo M
308               const CFList& M,          ///< [in] a list of powers of Variables
309                                         ///< of level higher than 1
310               const int d               ///< [in] precision
311                    );
312
313/// Hensel lifting from bivariate to trivariate.
314///
315/// @return @a henselLift23 returns a list of polynomials lifted to precision
316///          Variable (3)^l[1]
317/// @sa henselLift12(), henselLiftResume12(), henselLiftResume(), henselLift()
318CFList
319henselLift23 (const CFList& eval,    ///< [in] contains compressed, bivariate
320                                     ///< as first element and trivariate one as
321                                     ///< second element
322              const CFList& factors, ///< [in] monic bivariate factors,
323                                     ///< including leading coefficient
324                                     ///< as first element.
325              const int* l,          ///< [in] l[0]: precision of bivariate
326                                     ///< lifting, l[1] as above
327              CFList& diophant,      ///< [in,out] returns the result of
328                                     ///< biDiophantine()
329              CFArray& Pi,           ///< [in,out] stores intermediate results
330              CFMatrix& M            ///< [in,out] stores intermediate results
331             );
332
333/// resume Hensel lifting.
334///
335/// @sa henselLift12(), henselLiftResume12(), henselLift23(), henselLift()
336void
337henselLiftResume (
338              const CanonicalForm& F, ///< [in] compressed, multivariate poly
339              CFList& factors,        ///< [in,out] monic multivariate factors
340                                      ///< lifted to precision F.mvar()^start,
341                                      ///< including leading coefficient
342                                      ///< as first element. Returns factors
343                                      ///< lifted to precision F.mvar()^end
344              int start,              ///< [in] starting precision
345              int end,                ///< [in] end precision
346              CFArray& Pi,            ///< [in,out] stores intermediate results
347              const CFList& diophant, ///< [in] result of multiRecDiophantine()
348              CFMatrix& M,            ///< [in, out] stores intermediate results
349              const CFList& MOD       ///< [in] a list of powers of Variables
350                                      ///< of level higher than 1
351                 );
352
353/// Hensel lifting
354///
355/// @return @a henselLift returns a list of polynomials lifted to
356///          precision F.getLast().mvar()^l_new
357/// @sa henselLift12(), henselLiftResume12(), henselLift23(), henselLiftResume()
358CFList
359henselLift (const CFList& F,       ///< [in] two compressed, multivariate
360                                   ///< polys F and G
361            const CFList& factors, ///< [in] monic multivariate factors
362                                   ///< including leading coefficient
363                                   ///< as first element.
364            const CFList& MOD,     ///< [in] a list of powers of Variables
365                                   ///< of level higher than 1
366            CFList& diophant,      ///< [in,out] result of multiRecDiophantine()
367            CFArray& Pi,           ///< [in,out] stores intermediate results
368            CFMatrix& M,           ///< [in,out] stores intermediate results
369            const int lOld,       ///< [in] lifting precision of F.mvar()
370            const int lNew        ///< [in] lifting precision of G.mvar()
371           );
372
373/// Hensel lifting from bivariate to multivariate
374///
375/// @return @a henselLift returns a list of lifted factors
376/// @sa henselLift12(), henselLiftResume12(), henselLift23(), henselLiftResume()
377CFList
378henselLift (const CFList& eval,    ///< [in] a list of polynomials the last
379                                   ///< element is a compressed multivariate
380                                   ///< poly, last but one element equals the
381                                   ///< last elements modulo its main variable
382                                   ///< and so on. The first element is a
383                                   ///< compressed bivariate poly.
384            const CFList& factors, ///< [in] bivariate factors, including
385                                   ///< leading coefficient
386            const int* l,          ///< [in] lifting bounds
387            const int lLength,     ///< [in] length of l
388            bool sort= true        ///< [in] sort factors by degree in
389                                   ///< Variable(1)
390           );
391
392/// two factor Hensel lifting from univariate to bivariate, factors need not to
393/// be monic
394void
395henselLift122 (const CanonicalForm& F,///< [in] a bivariate poly
396               CFList& factors,       ///< [in, out] a list of univariate polys
397                                      ///< lifted factors
398               int l,                 ///< [in] lift bound
399               CFArray& Pi,           ///< [in, out] stores intermediate results
400               CFList& diophant,      ///< [in, out] result of diophantine
401               CFMatrix& M,           ///< [in, out] stores intermediate results
402               const CFArray& LCs,    ///< [in] leading coefficients
403               bool sort              ///< [in] if true factors are sorted by
404                                      ///< their degree
405              );
406
407/// two factor Hensel lifting from bivariate to multivariate, factors need not
408/// to be monic
409///
410/// @return @a henselLift122 returns a list of lifted factors
411CFList
412henselLift2 (const CFList& eval,   ///< [in] a list of polynomials the last
413                                   ///< element is a compressed multivariate
414                                   ///< poly, last but one element equals the
415                                   ///< last elements modulo its main variable
416                                   ///< and so on. The first element is a
417                                   ///< compressed bivariate poly.
418             const CFList& factors,///< [in] bivariate factors
419             int* l,               ///< [in] lift bounds
420             const int lLength,    ///< [in] length of l
421             bool sort,            ///< [in] if true factors are sorted by
422                                   ///< their degree in Variable(1)
423             const CFList& LCs1,   ///< [in] a list of evaluated LC of first
424                                   ///< factor
425             const CFList& LCs2,   ///< [in] a list of evaluated LC of second
426                                   ///< factor
427             const CFArray& Pi,    ///< [in] intermediate result
428             const CFList& diophant,///< [in] result of diophantine
429             bool& noOneToOne      ///< [in,out] check for one to one
430                                   ///< correspondence
431            );
432
433/// Hensel lifting of non monic factors, needs correct leading coefficients of
434/// factors and a one to one corresponds between bivariate and multivariate
435/// factors to succeed
436///
437/// @return @a nonMonicHenselLift returns a list of lifted factors
438/// such that prod (factors) == eval.getLast() if there is a one to one
439/// correspondence
440CFList
441nonMonicHenselLift (const CFList& eval,    ///< [in] a list of polys the last
442                                           ///< element is a compressed
443                                           ///< multivariate poly, last but one
444                                           ///< element equals the last elements
445                                           ///< modulo its main variable and so
446                                           ///< on. The first element is a
447                                           ///< compressed poly in 3 variables
448                    const CFList& factors, ///< [in] a list of bivariate factors
449                    CFList* const& LCs,    ///< [in] leading coefficients,
450                                           ///< evaluated in the same way as
451                                           ///< eval
452                    CFList& diophant,      ///< [in, out] solution of univariate
453                                           ///< diophantine equation
454                    CFArray& Pi,           ///< [in, out] buffer intermediate
455                                           ///< results
456                    int* liftBound,        ///< [in] lifting bounds
457                    int length,            ///< [in] length of lifting bounds
458                    bool& noOneToOne       ///< [in, out] check for one to one
459                                           ///< correspondence
460                   );
461#endif
462/* FAC_HENSEL_H */
463
Note: See TracBrowser for help on using the repository browser.