source: git/factory/facHensel.h @ ee668e

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