source: git/factory/facHensel.h @ c1b9927

fieker-DuValspielwiese
Last change on this file since c1b9927 was c1b9927, checked in by Hans Schoenemann <hannes@…>, 13 years ago
- removed some unsed variables - never put static inline routine without a body in a .h file git-svn-id: file:///usr/local/Singular/svn/trunk@14265 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 17.0 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/// division with remainder of @a F by
68/// @a G wrt Variable (1) modulo @a M.
69///
70/// @return @a Q returns the dividend, @a R returns the remainder.
71/// @sa divrem()
72void divrem2 (const CanonicalForm& F, ///< [in] bivariate, compressed polynomial
73              const CanonicalForm& G, ///< [in] bivariate, compressed polynomial
74              CanonicalForm& Q,       ///< [in,out] dividend
75              CanonicalForm& R,       ///< [in,out] remainder, degree (R, 1) <
76                                      ///< degree (G, 1)
77              const CanonicalForm& M  ///< [in] power of Variable (2)
78             );
79
80/// division with remainder of @a F by
81/// @a G wrt Variable (1) modulo @a MOD.
82///
83/// @sa divrem2()
84void divrem (
85           const CanonicalForm& F, ///< [in] multivariate, compressed polynomial
86           const CanonicalForm& G, ///< [in] multivariate, compressed polynomial
87           CanonicalForm& Q,       ///< [in,out] dividend
88           CanonicalForm& R,       ///< [in,out] remainder, degree (R, 1) <
89                                   ///< degree (G, 1)
90           const CFList& MOD       ///< [in] only contains powers of
91                                   ///< Variables of level higher than 1
92            );
93
94
95/// division with remainder of @a F by
96/// @a G wrt Variable (1) modulo @a M using Newton inversion
97///
98/// @return @a Q returns the dividend, @a R returns the remainder.
99/// @sa divrem2(), newtonDiv()
100void
101newtonDivrem (const CanonicalForm& F, ///< [in] bivariate, compressed polynomial
102              const CanonicalForm& G, ///< [in] bivariate, compressed polynomial
103                                      ///< which is monic in Variable (1)
104              CanonicalForm& Q,       ///< [in,out] dividend
105              CanonicalForm& R,       ///< [in,out] remainder, degree (R, 1) <
106                                      ///< degree (G, 1)
107              const CanonicalForm& M  ///< [in] power of Variable (2)
108             );
109
110/// division of @a F by
111/// @a G wrt Variable (1) modulo @a M using Newton inversion
112///
113/// @return @a newtonDiv returns the dividend
114/// @sa divrem2(), newtonDivrem()
115CanonicalForm
116newtonDiv (const CanonicalForm& F, ///< [in] bivariate, compressed polynomial
117           const CanonicalForm& G, ///< [in] bivariate, compressed polynomial
118                                   ///< which is monic in Variable (1)
119           const CanonicalForm& M  ///< [in] power of Variable (2)
120          );
121
122/// reduce @a F modulo elements in @a M.
123///
124/// @return @a mod returns @a F modulo @a M
125CanonicalForm mod (const CanonicalForm& F, ///< [in] compressed polynomial
126                   const CFList& M         ///< [in] list containing only
127                                           ///< univariate polynomials
128                  );
129
130/// Karatsuba style modular multiplication for bivariate polynomials.
131///
132/// @return @a mulMod2 returns @a A * @a B mod @a M.
133CanonicalForm
134mulMod2 (const CanonicalForm& A, ///< [in] bivariate, compressed polynomial
135         const CanonicalForm& B, ///< [in] bivariate, compressed polynomial
136         const CanonicalForm& M  ///< [in] power of Variable (2)
137        );
138
139/// Karatsuba style modular multiplication for multivariate polynomials.
140///
141/// @return @a mulMod2 returns @a A * @a B mod @a MOD.
142CanonicalForm
143mulMod (const CanonicalForm& A, ///< [in] multivariate, compressed polynomial
144        const CanonicalForm& B, ///< [in] multivariate, compressed polynomial
145        const CFList& MOD       ///< [in] only contains powers of
146                                ///< Variables of level higher than 1
147       );
148
149/// product of all elements in @a L modulo @a M via divide-and-conquer.
150///
151/// @return @a prodMod returns product of all elements in @a L modulo @a M.
152CanonicalForm
153prodMod (const CFList& L,       ///< [in] contains only bivariate, compressed
154                                ///< polynomials
155         const CanonicalForm& M ///< [in] power of Variable (2)
156        );
157
158/// product of all elements in @a L modulo @a M via divide-and-conquer.
159///
160/// @return @a prodMod returns product of all elements in @a L modulo @a M.
161CanonicalForm
162prodMod (const CFList& L, ///< [in] contains multivariate, compressed
163                          ///< polynomials
164         const CFList& M  ///< [in] contains only powers of Variables
165        );
166
167/// sort a list of polynomials by their degree in @a x.
168///
169void sortList (CFList& list,     ///< [in, out] list of polys, sorted list
170               const Variable& x ///< [in] some Variable
171              );
172
173/// Hensel lift from univariate to bivariate.
174///
175/// @sa henselLiftResume12(), henselLift23(), henselLiftResume(), henselLift()
176void
177henselLift12 (const CanonicalForm& F, ///< [in] compressed, bivariate poly
178              CFList& factors,        ///< [in, out] monic univariate factors of
179                                      ///< F, including leading coefficient as
180                                      ///< first element. Returns monic lifted
181                                      ///< factors without the leading
182                                      ///< coefficient
183              int l,                  ///< [in] lifting precision
184              CFArray& Pi,            ///< [in,out] stores intermediate results
185              CFList& diophant,       ///< [in,out] result of diophantine()
186              CFMatrix& M,            ///< [in,out] stores intermediate results
187              bool sort= true         ///< [in] sort factors by degree in
188                                      ///< Variable(1)
189             );
190
191/// resume Hensel lift from univariate to bivariate. Assumes factors are lifted
192/// to precision Variable (2)^start and lifts them to precision Variable (2)^end
193///
194/// @sa henselLift12(), henselLift23(), henselLiftResume(), henselLift()
195void
196henselLiftResume12 (const CanonicalForm& F, ///< [in] compressed, bivariate poly
197                    CFList& factors,        ///< [in,out] monic factors of F,
198                                            ///< lifted to precision start,
199                                            ///< including leading coefficient
200                                            ///< as first element. Returns monic
201                                            ///< lifted factors without the
202                                            ///< leading coefficient
203                    int start,              ///< [in] starting precision
204                    int end,                ///< [in] end precision
205                    CFArray& Pi,            ///< [in,out] stores intermediate
206                                            ///< results
207                    const CFList& diophant, ///< [in] result of diophantine
208                    CFMatrix& M             ///< [in,out] stores intermediate
209                                            ///< results
210                   );
211
212/// Hensel lifting from bivariate to trivariate.
213///
214/// @return @a henselLift23 returns a list of polynomials lifted to precision
215///          Variable (3)^l[1]
216/// @sa henselLift12(), henselLiftResume12(), henselLiftResume(), henselLift()
217CFList
218henselLift23 (const CFList& eval,    ///< [in] contains compressed, bivariate
219                                     ///< as first element and trivariate one as
220                                     ///< second element
221              const CFList& factors, ///< [in] monic bivariate factors,
222                                     ///< including leading coefficient
223                                     ///< as first element.
224              const int* l,          ///< [in] l[0]: precision of bivariate
225                                     ///< lifting, l[1] as above
226              CFList& diophant,      ///< [in,out] returns the result of
227                                     ///< biDiophantine()
228              CFArray& Pi,           ///< [in,out] stores intermediate results
229              CFMatrix& M            ///< [in,out] stores intermediate results
230             );
231
232/// resume Hensel lifting.
233///
234/// @sa henselLift12(), henselLiftResume12(), henselLift23(), henselLift()
235void
236henselLiftResume (
237              const CanonicalForm& F, ///< [in] compressed, multivariate poly
238              CFList& factors,        ///< [in,out] monic multivariate factors
239                                      ///< lifted to precision F.mvar()^start,
240                                      ///< including leading coefficient
241                                      ///< as first element. Returns factors
242                                      ///< lifted to precision F.mvar()^end
243              int start,              ///< [in] starting precision
244              int end,                ///< [in] end precision
245              CFArray& Pi,            ///< [in,out] stores intermediate results
246              const CFList& diophant, ///< [in] result of multiRecDiophantine()
247              CFMatrix& M,            ///< [in, out] stores intermediate results
248              const CFList& MOD       ///< [in] a list of powers of Variables
249                                      ///< of level higher than 1
250                 );
251
252/// Hensel lifting
253///
254/// @return @a henselLift returns a list of polynomials lifted to
255///          precision F.getLast().mvar()^l_new
256/// @sa henselLift12(), henselLiftResume12(), henselLift23(), henselLiftResume()
257CFList
258henselLift (const CFList& F,       ///< [in] two compressed, multivariate
259                                   ///< polys F and G
260            const CFList& factors, ///< [in] monic multivariate factors
261                                   ///< including leading coefficient
262                                   ///< as first element.
263            const CFList& MOD,     ///< [in] a list of powers of Variables
264                                   ///< of level higher than 1
265            CFList& diophant,      ///< [in,out] result of multiRecDiophantine()
266            CFArray& Pi,           ///< [in,out] stores intermediate results
267            CFMatrix& M,           ///< [in,out] stores intermediate results
268            const int lOld,       ///< [in] lifting precision of F.mvar()
269            const int lNew        ///< [in] lifting precision of G.mvar()
270           );
271
272/// Hensel lifting from bivariate to multivariate
273///
274/// @return @a henselLift returns a list of lifted factors
275/// @sa henselLift12(), henselLiftResume12(), henselLift23(), henselLiftResume()
276CFList
277henselLift (const CFList& eval,    ///< [in] a list of polynomials the last
278                                   ///< element is a compressed multivariate
279                                   ///< poly, last but one element equals the
280                                   ///< last elements modulo its main variable
281                                   ///< and so on. The first element is a
282                                   ///< compressed bivariate poly.
283            const CFList& factors, ///< [in] bivariate factors, including
284                                   ///< leading coefficient
285            const int* l,          ///< [in] lifting bounds
286            const int lLength,     ///< [in] length of l
287            bool sort= true        ///< [in] sort factors by degree in
288                                   ///< Variable(1)
289           );
290
291/// two factor Hensel lifting from univariate to bivariate, factors need not to
292/// be monic
293void
294henselLift122 (const CanonicalForm& F,///< [in] a bivariate poly
295               CFList& factors,       ///< [in, out] a list of univariate polys
296                                      ///< lifted factors
297               int l,                 ///< [in] lift bound
298               CFArray& Pi,           ///< [in, out] stores intermediate results
299               CFList& diophant,      ///< [in, out] result of diophantine
300               CFMatrix& M,           ///< [in, out] stores intermediate results
301               const CFArray& LCs,    ///< [in] leading coefficients
302               bool sort              ///< [in] if true factors are sorted by
303                                      ///< their degree
304              );
305
306/// two factor Hensel lifting from bivariate to multivariate, factors need not
307/// to be monic
308///
309/// @return @a henselLift122 returns a list of lifted factors
310CFList
311henselLift2 (const CFList& eval,   ///< [in] a list of polynomials the last
312                                   ///< element is a compressed multivariate
313                                   ///< poly, last but one element equals the
314                                   ///< last elements modulo its main variable
315                                   ///< and so on. The first element is a
316                                   ///< compressed bivariate poly.
317             const CFList& factors,///< [in] bivariate factors
318             int* l,               ///< [in] lift bounds
319             const int lLength,    ///< [in] length of l
320             bool sort,            ///< [in] if true factors are sorted by
321                                   ///< their degree in Variable(1)
322             const CFList& LCs1,   ///< [in] a list of evaluated LC of first
323                                   ///< factor
324             const CFList& LCs2,   ///< [in] a list of evaluated LC of second
325                                   ///< factor
326             const CFArray& Pi,    ///< [in] intermediate result
327             const CFList& diophant,///< [in] result of diophantine
328             bool& noOneToOne      ///< [in,out] check for one to one
329                                   ///< correspondence
330            );
331
332/// Hensel lifting of non monic factors, needs correct leading coefficients of
333/// factors and a one to one corresponds between bivariate and multivariate
334/// factors to succeed
335///
336/// @return @a nonMonicHenselLift returns a list of lifted factors
337/// such that prod (factors) == eval.getLast() if there is a one to one
338/// correspondence
339CFList
340nonMonicHenselLift (const CFList& eval,    ///< [in] a list of polys the last
341                                           ///< element is a compressed
342                                           ///< multivariate poly, last but one
343                                           ///< element equals the last elements
344                                           ///< modulo its main variable and so
345                                           ///< on. The first element is a
346                                           ///< compressed poly in 3 variables
347                    const CFList& factors, ///< [in] a list of bivariate factors
348                    CFList* const& LCs,    ///< [in] leading coefficients,
349                                           ///< evaluated in the same way as
350                                           ///< eval
351                    CFList& diophant,      ///< [in, out] solution of univariate
352                                           ///< diophantine equation
353                    CFArray& Pi,           ///< [in, out] buffer intermediate
354                                           ///< results
355                    int* liftBound,        ///< [in] lifting bounds
356                    int length,            ///< [in] length of lifting bounds
357                    bool& noOneToOne       ///< [in, out] check for one to one
358                                           ///< correspondence
359                   );
360#endif
361/* FAC_HENSEL_H */
362
Note: See TracBrowser for help on using the repository browser.