source: git/factory/facFqBivarUtil.h @ 542864

jengelh-datetimespielwiese
Last change on this file since 542864 was 542864, checked in by Martin Lee <martinlee84@…>, 11 years ago
chg: use irreducibility criterion
  • Property mode set to 100644
File size: 13.3 KB
Line 
1/*****************************************************************************\
2 * Computer Algebra System SINGULAR
3\*****************************************************************************/
4/** @file facFqBivarUtil.h
5 *
6 * This file provides utility functions for bivariate factorization
7 *
8 * @author Martin Lee
9 *
10 * @internal @version \$Id$
11 *
12 **/
13/*****************************************************************************/
14
15#ifndef FAC_FQ_BIVAR_UTIL_H
16#define FAC_FQ_BIVAR_UTIL_H
17
18// #include "config.h"
19
20#include "cf_map.h"
21#include "ExtensionInfo.h"
22
23#ifdef HAVE_NTL
24#include "NTLconvert.h"
25#endif
26
27/// append @a factors2 on @a factors1
28void append (CFList& factors1,       ///< [in,out] a list of polys
29             const CFList& factors2  ///< [in] a list of polys
30            );
31
32/// decompress a list of polys @a factors using the map @a N
33void decompress (CFList& factors, ///< [in,out] a list of polys
34                 const CFMap& N   ///< [in] a map
35                );
36
37/// as above
38void decompress (CFFList& factors, ///< [in,out] a list of factors
39                 const CFMap& N    ///< [in] a map
40                );
41
42/// first swap Variables in @a factors1 if necessary, then append @a factors2
43/// and @a factors3 on @a factors1 and finally decompress @a factors1
44void appendSwapDecompress (CFList& factors1,       ///< [in,out] a list of polys
45                           const CFList& factors2, ///< [in] a list of polys
46                           const CFList& factors3, ///< [in] a list of polys
47                           const bool swap1,       ///< [in] indicates the need
48                                                   ///< to swap
49                           const bool swap2,       ///< [in] indicates the need
50                                                   ///< to swap
51                           const CFMap& N          ///< [in] a map
52                          );
53
54/// swap Variables in @a factors, then decompress @a factors
55void swapDecompress (CFList& factors, ///< [in,out] a list of polys
56                     const bool swap, ///< [in] indicates the need to swap
57                     const CFMap& N   ///< [in] a map
58                    );
59
60/// tests if F is not contained in a subfield defined by @a gamma (Fq case) or
61/// @a k (GF case)
62///
63/// @return @a isInExtension returns true if @a F is not contained in a subfield
64///         defined by @a gamma (Fq case) or @a k (GF case), false else
65/// @sa appendTestMapDown()
66bool isInExtension (const CanonicalForm& F,      ///< [in] a poly over
67                                                 ///< F_p (alpha)=Fq or GF(p^l)
68                    const CanonicalForm& gamma,  ///< [in] a primitive element
69                                                 ///< defining a subfield of
70                                                 ///< Fq if we are not over some
71                                                 ///< GF
72                    const int k,                 ///< some int k such that k
73                                                 ///< divides l if we are not
74                                                 ///< over some Fq
75                    const CanonicalForm& delta,  ///< [in] image of gamma
76                    CFList& source,              ///< [in,out] list of preimages
77                    CFList& dest                 ///< [in,out] list of images
78                   );
79
80/// map a poly into a subfield of the current field, no testing is performed!
81///
82/// @return @a mapDown returns @a F mapped into a subfield of the current field
83/// @sa appendTestMapDown(), appendMapDown()
84CanonicalForm
85mapDown (const CanonicalForm& F,    ///< [in] a poly
86         const ExtensionInfo& info, ///< [in] information about the sub- and
87                                    ///< current field
88         CFList& source,            ///< [in,out] in case we are over some
89                                    ///< F_p (alpha) and want to map down into
90                                    ///< F_p (beta) source contains powers of
91                                    ///< the primitive element of F_p (alpha)
92         CFList& dest               ///< [in,out] as source but contains
93                                    ///< the corresponding powers of the
94                                    ///< primitive element of F_p (beta)
95        );
96
97/// test if @a g is in a subfield of the current field, if so map it down and
98/// append it to @a factors
99///
100/// @sa mapDown(), isInExtension()
101void appendTestMapDown (CFList& factors,          ///< [in,out] a list of polys
102                        const CanonicalForm& f,   ///< [in] a poly
103                        const ExtensionInfo& info,///< [in] information about
104                                                  ///< extension
105                        CFList& source,           ///< [in,out] @sa mapDown()
106                        CFList& dest              ///< [in,out] @sa mapDown()
107                       );
108
109/// map @a g down into a subfield of the current field and append it to @a
110/// factors
111///
112/// @sa mapDown(), appendTestMapDown()
113void
114appendMapDown (CFList& factors,          ///< [in,out] a list of polys
115               const CanonicalForm& g,   ///< [in] a poly
116               const ExtensionInfo& info,///< [in] information about extension
117               CFList& source,           ///< [in,out] @sa mapDown()
118               CFList& dest              ///< [in,out] @sa mapDown()
119              );
120
121/// normalize factors, i.e. make factors monic
122void normalize (CFList& factors ///< [in,out] a list of polys
123               );
124
125/// as above
126void normalize (CFFList& factors ///< [in,out] a list of factors
127               );
128
129/// extract a subset given by @a index of size @a s from @a elements, if there
130/// is no subset we have not yet considered noSubset is set to true. @a index
131/// encodes the next subset, e.g. if s= 3, elements= {a,b,c,d},
132/// index= {1, 2, 4, 0}, then subset= {a,c,d}. @a index is of size
133/// @a elements.size().
134///
135/// @return @a subset returns a list of polys of length @a s if there is a
136///         subset we have not yet considered.
137CFList subset (int index [],            ///< [in,out] an array encoding the next
138                                        ///< subset
139               const int& s,            ///< [in] size of the subset
140               const CFArray& elements, ///< [in] an array of polys
141               bool& noSubset           ///< [in,out] if there is no subset we
142                                        ///< have not yet considered @a noSubset
143                                        ///< is true
144              );
145
146/// write elements of @a list into an array
147///
148/// @return an array of polys
149CFArray copy (const CFList& list ///< [in] a list of polys
150             );
151
152/// update @a index
153void indexUpdate (int index [],          ///< [in,out] an array encoding a
154                                         ///< subset of size subsetSize
155                  const int& subsetSize, ///< [in] size of the subset
156                  const int& setSize,    ///< [in] size of the given set
157                  bool& noSubset         ///< [in,out] if there is no subset we
158                                         ///< have not yet considered @a
159                                         ///< noSubset is true
160                 );
161
162/// compute the sum of degrees in Variable(1) of elements in S
163///
164/// @return @a subsetDegree returns the sum of degrees in Variable(1) of
165///         elements in S
166int subsetDegree (const CFList& S ///< [in] a list of polys
167                 );
168
169/// determine multiplicity of the factors
170///
171/// @return a list of factors of F with their multiplicity
172CFFList multiplicity (CanonicalForm& F,     ///< [in] a poly
173                      const CFList& factors ///< [in] a list of factors of F
174                     );
175
176/// compute the coefficients of the logarithmic derivative of G mod
177/// Variable (2)^l over Fq
178///
179/// @return an array of coefficients of the logarithmic derivative of G mod
180///         Variable (2)^l
181CFArray logarithmicDerivative (const CanonicalForm& F,///<[in] a bivariate poly
182                              const CanonicalForm& G, ///<[in] a factor of F
183                              int l,                  ///<[in] lifting precision
184                              CanonicalForm& Q        ///<[in,out] F/G
185                              );
186
187/// compute the coefficients of the logarithmic derivative of G mod
188/// Variable (2)^l over Fq with oldQ= F/G mod Variable (2)^oldL
189///
190/// @return an array of coefficients of the logarithmic derivative of G mod
191///         Variable (2)^l
192CFArray
193logarithmicDerivative (const CanonicalForm& F,   ///< [in] bivariate poly
194                                                 ///< truncated at Variable(2)^l
195                       const CanonicalForm& G,   ///< [in] a factor of F
196                       int l,                    ///< [in] lifting precision
197                       int oldL,                 ///< [in] old precision
198                       const CanonicalForm& oldQ,///< [in] F/G mod
199                                                 ///< Variable(2)^oldL
200                       CanonicalForm& Q          ///< [in, out] F/G
201                      );
202
203/// compute bounds for logarithmic derivative as described in K. Belabas,
204/// M. van Hoeij, J. KlÃŒners, and A. Steel, Factoring polynomials over global
205/// fields
206///
207/// @return @a computeBounds returns bounds as described above
208int *
209computeBounds (const CanonicalForm& F,///< [in] compressed bivariate polynomial
210               int& n,                ///< [in,out] length of output
211               bool& isIrreducible    ///< [in,out] check if poly is irreducible
212              );
213
214/// extract coefficients of \f$ x^i \f$ for \f$i\geq k\f$ where \f$ x \f$ is
215/// a variable of level 1
216///
217/// @return coefficients of \f$ x^i \f$ for \f$i\geq k\f$
218/// @sa {getCoeffs (const CanonicalForm&, const int, const Variable&),
219/// getCoeffs (const CanonicalForm&, const int, const int, const int,
220/// const Variable&, const CanonicalForm&, const mat_zz_p&)}
221CFArray
222getCoeffs (const CanonicalForm& F,///< [in] compressed bivariate poly over F_p
223           const int k            ///< [in] some int
224          );
225
226/// extract coefficients of \f$ x^i \f$ for \f$i\geq k\f$ where \f$ x \f$ is
227/// a variable of level 1
228///
229/// @return coefficients of \f$ x^i \f$ for \f$i\geq k\f$
230/// @sa {getCoeffs (const CanonicalForm&, const int),
231/// getCoeffs (const CanonicalForm&, const int, const int, const int,
232/// const Variable&, const CanonicalForm&, const mat_zz_p&)}
233CFArray
234getCoeffs (const CanonicalForm& F,///< [in] compressed bivariate poly over
235                                  ///< F_p(alpha)
236           const int k,           ///< [in] some int
237           const Variable& alpha  ///< [in] algebraic variable
238          );
239
240#ifdef HAVE_NTL
241/// extract coefficients of \f$ x^i \f$ for \f$i\geq k\f$ where \f$ x \f$ is
242/// a variable of level 1
243///
244/// @return coefficients of \f$ x^i \f$ for \f$i\geq k\f$
245/// @sa {getCoeffs (const CanonicalForm&, const int, const Variable& alpha),
246/// getCoeffs (const CanonicalForm&, const int)}
247CFArray
248getCoeffs (const CanonicalForm& F,         ///< [in] compressed bivariate poly
249           const int k,                    ///< [in] some int
250           const int l,                    ///< [in] precision
251           const int degMipo,              ///< [in] degree of minimal poly
252           const Variable& alpha,          ///< [in] algebraic variable
253           const CanonicalForm& evaluation,///< [in] evaluation point
254           const mat_zz_p& M               ///< [in] bases change matrix
255          );
256#endif
257
258/// write A into M starting at row startIndex
259void
260writeInMatrix (CFMatrix& M,        ///< [in,out] some matrix
261               const CFArray& A,   ///< [in] array of polys
262               const int column,   ///< [in] column in which A is written
263               const int startIndex///< [in] row in which to start
264              );
265
266/// checks if a substitution x^n->x is possible
267///
268/// @return an integer n > 1, if a substitution described as above is possible
269///         else n <= 1
270int substituteCheck (const CFList& L ///< [in] a list of univariate polys
271                    );
272
273/// substitute x^d by x in F
274void
275subst (const CanonicalForm& F, ///< [in] a polynomial
276       CanonicalForm& A,       ///< [in,out] returns F with x^d replaced by x
277       const int d,            ///< d > 1 such that a substitution x^d -> x
278                               ///< [in] is possible
279       const Variable& x       ///< [in] a Variable
280      );
281
282/// reverse a substitution x^d->x
283///
284/// @return a poly with x replaced by x^d
285CanonicalForm
286reverseSubst (const CanonicalForm& F, ///< [in] a poly
287              const int d,            ///< [in] an integer > 0
288              const Variable& x       ///< [in] a Variable
289             );
290
291/// reverse a substitution x^d->x
292void
293reverseSubst (CFList& L,        ///< [in,out] a list of polys, returns the
294                                ///< given list with x replaced by x^d
295              const int d,      ///< [in] an integer > 0
296              const Variable& x ///< [in] a Variable
297             );
298
299/// check if a substitution x^n->x is possible
300///
301/// @return an integer n > 1, if a substitution described as above is possible
302///         else n <= 1
303int
304substituteCheck (const CanonicalForm& F, ///<[in] a polynomial
305                 const Variable& x       ///<[in] some variable
306                );
307
308#endif
309/* FAC_FQ_BIVAR_UTIL_H */
310
Note: See TracBrowser for help on using the repository browser.