# source:git/factory/facHensel.h@72bfc8

jengelh-datetimespielwiese
Last change on this file since 72bfc8 was 72bfc8, checked in by Martin Lee <martinlee84@…>, 11 years ago
chg: deleted @internal
• Property mode set to `100644`
File size: 12.5 KB
Line
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
10 *
11 * @author Martin Lee
12 *
13 **/
14/*****************************************************************************/
15
16#ifndef FAC_HENSEL_H
17#define FAC_HENSEL_H
18
19// #include "config.h"
20#include "cf_assert.h"
21#include "debug.h"
22#include "timing.h"
23
24#include "canonicalform.h"
25#include "fac_util.h"
26
27#ifdef HAVE_NTL
28/// sort a list of polynomials by their degree in @a x.
29///
30void sortList (CFList& list,     ///< [in, out] list of polys, sorted list
31               const Variable& x ///< [in] some Variable
32              );
33
34/// Hensel lift from univariate to bivariate.
35///
36/// @sa henselLiftResume12(), henselLift23(), henselLiftResume(), henselLift()
37void
38henselLift12 (const CanonicalForm& F, ///< [in] compressed, bivariate poly
39              CFList& factors,        ///< [in, out] monic univariate factors of
40                                      ///< F, including leading coefficient as
41                                      ///< first element. Returns monic lifted
42                                      ///< factors without the leading
43                                      ///< coefficient
44              int l,                  ///< [in] lifting precision
45              CFArray& Pi,            ///< [in,out] stores intermediate results
46              CFList& diophant,       ///< [in,out] result of diophantine()
47              CFMatrix& M,            ///< [in,out] stores intermediate results
48              modpk& b,               ///< [in] coeff bound
49              bool sort= true         ///< [in] sort factors by degree in
50                                      ///< Variable(1)
51             );
52
53/// Hensel lift from univariate to bivariate.
54///
55/// @sa henselLiftResume12(), henselLift23(), henselLiftResume(), henselLift()
56void
57henselLift12 (const CanonicalForm& F, ///< [in] compressed, bivariate poly
58              CFList& factors,        ///< [in, out] monic univariate factors of
59                                      ///< F, including leading coefficient as
60                                      ///< first element. Returns monic lifted
61                                      ///< factors without the leading
62                                      ///< coefficient
63              int l,                  ///< [in] lifting precision
64              CFArray& Pi,            ///< [in,out] stores intermediate results
65              CFList& diophant,       ///< [in,out] result of diophantine()
66              CFMatrix& M,            ///< [in,out] stores intermediate results
67              bool sort= true        ///< [in] sort factors by degree in
68                                      ///< Variable(1)
69             );
70
71/// resume Hensel lift from univariate to bivariate. Assumes factors are lifted
72/// to precision Variable (2)^start and lifts them to precision Variable (2)^end
73///
74/// @sa henselLift12(), henselLift23(), henselLiftResume(), henselLift()
75void
76henselLiftResume12 (const CanonicalForm& F, ///< [in] compressed, bivariate poly
77                    CFList& factors,        ///< [in,out] monic factors of F,
78                                            ///< lifted to precision start,
80                                            ///< as first element. Returns monic
81                                            ///< lifted factors without the
83                    int start,              ///< [in] starting precision
84                    int end,                ///< [in] end precision
85                    CFArray& Pi,            ///< [in,out] stores intermediate
86                                            ///< results
87                    const CFList& diophant, ///< [in] result of diophantine
88                    CFMatrix& M,            ///< [in,out] stores intermediate
89                                            ///< results
90                    const modpk& b= modpk() ///< [in] coeff bound
91                   );
92
93/// Hensel lifting from bivariate to trivariate.
94///
95/// @return @a henselLift23 returns a list of polynomials lifted to precision
96///          Variable (3)^l[1]
97/// @sa henselLift12(), henselLiftResume12(), henselLiftResume(), henselLift()
98CFList
99henselLift23 (const CFList& eval,    ///< [in] contains compressed, bivariate
100                                     ///< as first element and trivariate one as
101                                     ///< second element
102              const CFList& factors, ///< [in] monic bivariate factors,
104                                     ///< as first element.
105              int* l,          ///< [in] l[0]: precision of bivariate
106                                     ///< lifting, l[1] as above
107              CFList& diophant,      ///< [in,out] returns the result of
108                                     ///< biDiophantine()
109              CFArray& Pi,           ///< [in,out] stores intermediate results
110              CFMatrix& M            ///< [in,out] stores intermediate results
111             );
112
113/// resume Hensel lifting.
114///
115/// @sa henselLift12(), henselLiftResume12(), henselLift23(), henselLift()
116void
117henselLiftResume (
118              const CanonicalForm& F, ///< [in] compressed, multivariate poly
119              CFList& factors,        ///< [in,out] monic multivariate factors
120                                      ///< lifted to precision F.mvar()^start,
122                                      ///< as first element. Returns factors
123                                      ///< lifted to precision F.mvar()^end
124              int start,              ///< [in] starting precision
125              int end,                ///< [in] end precision
126              CFArray& Pi,            ///< [in,out] stores intermediate results
127              const CFList& diophant, ///< [in] result of multiRecDiophantine()
128              CFMatrix& M,            ///< [in, out] stores intermediate results
129              const CFList& MOD       ///< [in] a list of powers of Variables
130                                      ///< of level higher than 1
131                 );
132
133/// Hensel lifting
134///
135/// @return @a henselLift returns a list of polynomials lifted to
136///          precision F.getLast().mvar()^l_new
137/// @sa henselLift12(), henselLiftResume12(), henselLift23(), henselLiftResume()
138CFList
139henselLift (const CFList& F,       ///< [in] two compressed, multivariate
140                                   ///< polys F and G
141            const CFList& factors, ///< [in] monic multivariate factors
143                                   ///< as first element.
144            const CFList& MOD,     ///< [in] a list of powers of Variables
145                                   ///< of level higher than 1
146            CFList& diophant,      ///< [in,out] result of multiRecDiophantine()
147            CFArray& Pi,           ///< [in,out] stores intermediate results
148            CFMatrix& M,           ///< [in,out] stores intermediate results
149            int lOld,       ///< [in] lifting precision of F.mvar()
150            int lNew        ///< [in] lifting precision of G.mvar()
151           );
152
153/// Hensel lifting from bivariate to multivariate
154///
155/// @return @a henselLift returns a list of lifted factors
156/// @sa henselLift12(), henselLiftResume12(), henselLift23(), henselLiftResume()
157CFList
158henselLift (const CFList& eval,    ///< [in] a list of polynomials the last
159                                   ///< element is a compressed multivariate
160                                   ///< poly, last but one element equals the
161                                   ///< last elements modulo its main variable
162                                   ///< and so on. The first element is a
163                                   ///< compressed bivariate poly.
164            const CFList& factors, ///< [in] bivariate factors, including
166            int* l,          ///< [in] lifting bounds
167            int lLength,     ///< [in] length of l
168            bool sort= true        ///< [in] sort factors by degree in
169                                   ///< Variable(1)
170           );
171
172/// Hensel lifting from univariate to bivariate, factors need not to be monic
173void
174nonMonicHenselLift12 (const CanonicalForm& F,///< [in] a bivariate poly
175               CFList& factors,       ///< [in, out] a list of univariate polys
176                                      ///< lifted factors
177               int l,                 ///< [in] lift bound
178               CFArray& Pi,           ///< [in, out] stores intermediate results
179               CFList& diophant,      ///< [in, out] result of diophantine
180               CFMatrix& M,           ///< [in, out] stores intermediate results
181               const CFArray& LCs,    ///< [in] leading coefficients
182               bool sort              ///< [in] if true factors are sorted by
183                                      ///< their degree
184              );
185
186/// two factor Hensel lifting from bivariate to multivariate, factors need not
187/// to be monic
188///
189/// @return @a henselLift122 returns a list of lifted factors
190CFList
191nonMonicHenselLift2 (const CFList& eval,///< [in] a list of polynomials the last
192                                   ///< element is a compressed multivariate
193                                   ///< poly, last but one element equals the
194                                   ///< last elements modulo its main variable
195                                   ///< and so on. The first element is a
196                                   ///< compressed bivariate poly.
197             const CFList& factors,///< [in] bivariate factors
198             int* l,               ///< [in] lift bounds
199             int lLength,          ///< [in] length of l
200             bool sort,            ///< [in] if true factors are sorted by
201                                   ///< their degree in Variable(1)
202             const CFList& LCs1,   ///< [in] a list of evaluated LC of first
203                                   ///< factor
204             const CFList& LCs2,   ///< [in] a list of evaluated LC of second
205                                   ///< factor
206             const CFArray& Pi,    ///< [in] intermediate result
207             const CFList& diophant,///< [in] result of diophantine
208             bool& noOneToOne      ///< [in,out] check for one to one
209                                   ///< correspondence
210            );
211
212/// Hensel lifting of non monic factors, needs correct leading coefficients of
213/// factors and a one to one corresponds between bivariate and multivariate
214/// factors to succeed
215///
216/// @return @a nonMonicHenselLift returns a list of lifted factors
217/// such that prod (factors) == eval.getLast() if there is a one to one
218/// correspondence
219CFList
220nonMonicHenselLift (const CFList& eval,    ///< [in] a list of polys the last
221                                           ///< element is a compressed
222                                           ///< multivariate poly, last but one
223                                           ///< element equals the last elements
224                                           ///< modulo its main variable and so
225                                           ///< on. The first element is a
226                                           ///< compressed poly in 3 variables
227                    const CFList& factors, ///< [in] a list of bivariate factors
228                    CFList* const& LCs,    ///< [in] leading coefficients,
229                                           ///< evaluated in the same way as
230                                           ///< eval
231                    CFList& diophant,      ///< [in, out] solution of univariate
232                                           ///< diophantine equation
233                    CFArray& Pi,           ///< [in, out] buffer intermediate
234                                           ///< results
235                    int* liftBound,        ///< [in] lifting bounds
236                    int length,            ///< [in] length of lifting bounds
237                    bool& noOneToOne       ///< [in, out] check for one to one
238                                           ///< correspondence
239                   );
240#endif /* HAVE_NTL */
241#endif
242/* FAC_HENSEL_H */
243
Note: See TracBrowser for help on using the repository browser.