source: git/factory/facFqBivarUtil.h @ d8a7da

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