[7bf145] | 1 | /*****************************************************************************\ |
---|
[806c18] | 2 | * Computer Algebra System SINGULAR |
---|
[7bf145] | 3 | \*****************************************************************************/ |
---|
| 4 | /** @file facFqBivarUtil.h |
---|
[806c18] | 5 | * |
---|
| 6 | * This file provides utility functions for bivariate factorization |
---|
[7bf145] | 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 | |
---|
[e4fe2b] | 18 | // #include "config.h" |
---|
[7bf145] | 19 | |
---|
| 20 | #include "cf_map.h" |
---|
| 21 | #include "ExtensionInfo.h" |
---|
| 22 | |
---|
[f876a66] | 23 | #ifdef HAVE_NTL |
---|
| 24 | #include "NTLconvert.h" |
---|
| 25 | #endif |
---|
| 26 | |
---|
[7bf145] | 27 | /// append @a factors2 on @a factors1 |
---|
| 28 | void 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 |
---|
| 33 | void decompress (CFList& factors, ///< [in,out] a list of polys |
---|
| 34 | const CFMap& N ///< [in] a map |
---|
| 35 | ); |
---|
| 36 | |
---|
[f876a66] | 37 | /// as above |
---|
| 38 | void decompress (CFFList& factors, ///< [in,out] a list of factors |
---|
| 39 | const CFMap& N ///< [in] a map |
---|
| 40 | ); |
---|
| 41 | |
---|
[806c18] | 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 |
---|
| 44 | void appendSwapDecompress (CFList& factors1, ///< [in,out] a list of polys |
---|
[7bf145] | 45 | const CFList& factors2, ///< [in] a list of polys |
---|
[806c18] | 46 | const CFList& factors3, ///< [in] a list of polys |
---|
[7bf145] | 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 |
---|
| 55 | void 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 | |
---|
[806c18] | 60 | /// tests if F is not contained in a subfield defined by @a gamma (Fq case) or |
---|
[7bf145] | 61 | /// @a k (GF case) |
---|
| 62 | /// |
---|
[806c18] | 63 | /// @return @a isInExtension returns true if @a F is not contained in a subfield |
---|
[7bf145] | 64 | /// defined by @a gamma (Fq case) or @a k (GF case), false else |
---|
| 65 | /// @sa appendTestMapDown() |
---|
[806c18] | 66 | bool isInExtension (const CanonicalForm& F, ///< [in] a poly over |
---|
| 67 | ///< F_p (alpha)=Fq or GF(p^l) |
---|
[7bf145] | 68 | const CanonicalForm& gamma, ///< [in] a primitive element |
---|
| 69 | ///< defining a subfield of |
---|
| 70 | ///< Fq if we are not over some |
---|
| 71 | ///< GF |
---|
[f876a66] | 72 | const int k, ///< some int k such that k |
---|
[7bf145] | 73 | ///< divides l if we are not |
---|
| 74 | ///< over some Fq |
---|
[f876a66] | 75 | const CanonicalForm& delta, ///< [in] image of gamma |
---|
| 76 | CFList& source, ///< [in,out] list of preimages |
---|
| 77 | CFList& dest ///< [in,out] list of images |
---|
[7bf145] | 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() |
---|
[806c18] | 84 | CanonicalForm |
---|
[7bf145] | 85 | mapDown (const CanonicalForm& F, ///< [in] a poly |
---|
| 86 | const ExtensionInfo& info, ///< [in] information about the sub- and |
---|
| 87 | ///< current field |
---|
[806c18] | 88 | CFList& source, ///< [in,out] in case we are over some |
---|
[7bf145] | 89 | ///< F_p (alpha) and want to map down into |
---|
| 90 | ///< F_p (beta) source contains powers of |
---|
[806c18] | 91 | ///< the primitive element of F_p (alpha) |
---|
[7bf145] | 92 | CFList& dest ///< [in,out] as source but contains |
---|
[806c18] | 93 | ///< the corresponding powers of the |
---|
[7bf145] | 94 | ///< primitive element of F_p (beta) |
---|
| 95 | ); |
---|
| 96 | |
---|
[806c18] | 97 | /// test if @a g is in a subfield of the current field, if so map it down and |
---|
[7bf145] | 98 | /// append it to @a factors |
---|
| 99 | /// |
---|
| 100 | /// @sa mapDown(), isInExtension() |
---|
| 101 | void appendTestMapDown (CFList& factors, ///< [in,out] a list of polys |
---|
| 102 | const CanonicalForm& f, ///< [in] a poly |
---|
[806c18] | 103 | const ExtensionInfo& info,///< [in] information about |
---|
[7bf145] | 104 | ///< extension |
---|
| 105 | CFList& source, ///< [in,out] @sa mapDown() |
---|
| 106 | CFList& dest ///< [in,out] @sa mapDown() |
---|
| 107 | ); |
---|
| 108 | |
---|
[806c18] | 109 | /// map @a g down into a subfield of the current field and append it to @a |
---|
[7bf145] | 110 | /// factors |
---|
| 111 | /// |
---|
[806c18] | 112 | /// @sa mapDown(), appendTestMapDown() |
---|
| 113 | void |
---|
[7bf145] | 114 | appendMapDown (CFList& factors, ///< [in,out] a list of polys |
---|
| 115 | const CanonicalForm& g, ///< [in] a poly |
---|
[806c18] | 116 | const ExtensionInfo& info,///< [in] information about extension |
---|
[7bf145] | 117 | CFList& source, ///< [in,out] @sa mapDown() |
---|
| 118 | CFList& dest ///< [in,out] @sa mapDown() |
---|
| 119 | ); |
---|
| 120 | |
---|
| 121 | /// normalize factors, i.e. make factors monic |
---|
[806c18] | 122 | void normalize (CFList& factors ///< [in,out] a list of polys |
---|
[7bf145] | 123 | ); |
---|
| 124 | |
---|
[f876a66] | 125 | /// as above |
---|
| 126 | void normalize (CFFList& factors ///< [in,out] a list of factors |
---|
| 127 | ); |
---|
| 128 | |
---|
[806c18] | 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 |
---|
[7bf145] | 131 | /// encodes the next subset, e.g. if s= 3, elements= {a,b,c,d}, |
---|
[806c18] | 132 | /// index= {1, 2, 4, 0}, then subset= {a,c,d}. @a index is of size |
---|
| 133 | /// @a elements.size(). |
---|
[7bf145] | 134 | /// |
---|
[806c18] | 135 | /// @return @a subset returns a list of polys of length @a s if there is a |
---|
| 136 | /// subset we have not yet considered. |
---|
[7bf145] | 137 | CFList 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 |
---|
[806c18] | 141 | bool& noSubset ///< [in,out] if there is no subset we |
---|
[7bf145] | 142 | ///< have not yet considered @a noSubset |
---|
| 143 | ///< is true |
---|
| 144 | ); |
---|
| 145 | |
---|
[806c18] | 146 | /// write elements of @a list into an array |
---|
[7bf145] | 147 | /// |
---|
[806c18] | 148 | /// @return an array of polys |
---|
[7bf145] | 149 | CFArray copy (const CFList& list ///< [in] a list of polys |
---|
| 150 | ); |
---|
| 151 | |
---|
[806c18] | 152 | /// update @a index |
---|
| 153 | void indexUpdate (int index [], ///< [in,out] an array encoding a |
---|
| 154 | ///< subset of size subsetSize |
---|
[7bf145] | 155 | const int& subsetSize, ///< [in] size of the subset |
---|
| 156 | const int& setSize, ///< [in] size of the given set |
---|
[806c18] | 157 | bool& noSubset ///< [in,out] if there is no subset we |
---|
| 158 | ///< have not yet considered @a |
---|
| 159 | ///< noSubset is true |
---|
[7bf145] | 160 | ); |
---|
| 161 | |
---|
| 162 | /// compute the sum of degrees in Variable(1) of elements in S |
---|
| 163 | /// |
---|
[806c18] | 164 | /// @return @a subsetDegree returns the sum of degrees in Variable(1) of |
---|
| 165 | /// elements in S |
---|
[7bf145] | 166 | int subsetDegree (const CFList& S ///< [in] a list of polys |
---|
| 167 | ); |
---|
| 168 | |
---|
| 169 | /// determine multiplicity of the factors |
---|
| 170 | /// |
---|
[806c18] | 171 | /// @return a list of factors of F with their multiplicity |
---|
[7bf145] | 172 | CFFList multiplicity (CanonicalForm& F, ///< [in] a poly |
---|
| 173 | const CFList& factors ///< [in] a list of factors of F |
---|
| 174 | ); |
---|
| 175 | |
---|
[f876a66] | 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 |
---|
| 181 | CFArray 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 |
---|
| 192 | CFArray |
---|
[5335ba] | 193 | logarithmicDerivative (const CanonicalForm& F, ///< [in] bivariate poly |
---|
| 194 | ///< truncated at Variable(2)^l |
---|
[f876a66] | 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 |
---|
| 208 | int * |
---|
| 209 | computeBounds (const CanonicalForm& F,///< [in] compressed bivariate polynomial |
---|
| 210 | int& n ///< [in,out] length of output |
---|
| 211 | ); |
---|
| 212 | |
---|
| 213 | /// extract coefficients of \f$ x^i \f$ for \f$i\geq k\f$ where \f$ x \f$ is |
---|
| 214 | /// a variable of level 1 |
---|
| 215 | /// |
---|
| 216 | /// @return coefficients of \f$ x^i \f$ for \f$i\geq k\f$ |
---|
| 217 | /// @sa {getCoeffs (const CanonicalForm&, const int, const Variable&), |
---|
| 218 | /// getCoeffs (const CanonicalForm&, const int, const int, const int, |
---|
| 219 | /// const Variable&, const CanonicalForm&, const mat_zz_p&)} |
---|
| 220 | CFArray |
---|
| 221 | getCoeffs (const CanonicalForm& F,///< [in] compressed bivariate poly over F_p |
---|
| 222 | const int k ///< [in] some int |
---|
| 223 | ); |
---|
| 224 | |
---|
| 225 | /// extract coefficients of \f$ x^i \f$ for \f$i\geq k\f$ where \f$ x \f$ is |
---|
| 226 | /// a variable of level 1 |
---|
| 227 | /// |
---|
| 228 | /// @return coefficients of \f$ x^i \f$ for \f$i\geq k\f$ |
---|
| 229 | /// @sa {getCoeffs (const CanonicalForm&, const int), |
---|
| 230 | /// getCoeffs (const CanonicalForm&, const int, const int, const int, |
---|
| 231 | /// const Variable&, const CanonicalForm&, const mat_zz_p&)} |
---|
| 232 | CFArray |
---|
| 233 | getCoeffs (const CanonicalForm& F,///< [in] compressed bivariate poly over |
---|
| 234 | ///< F_p(alpha) |
---|
| 235 | const int k, ///< [in] some int |
---|
| 236 | const Variable& alpha ///< [in] algebraic variable |
---|
| 237 | ); |
---|
| 238 | |
---|
| 239 | #ifdef HAVE_NTL |
---|
| 240 | /// extract coefficients of \f$ x^i \f$ for \f$i\geq k\f$ where \f$ x \f$ is |
---|
| 241 | /// a variable of level 1 |
---|
| 242 | /// |
---|
| 243 | /// @return coefficients of \f$ x^i \f$ for \f$i\geq k\f$ |
---|
| 244 | /// @sa {getCoeffs (const CanonicalForm&, const int, const Variable& alpha), |
---|
| 245 | /// getCoeffs (const CanonicalForm&, const int)} |
---|
| 246 | CFArray |
---|
| 247 | getCoeffs (const CanonicalForm& F, ///< [in] compressed bivariate poly |
---|
| 248 | const int k, ///< [in] some int |
---|
| 249 | const int l, ///< [in] precision |
---|
| 250 | const int degMipo, ///< [in] degree of minimal poly |
---|
| 251 | const Variable& alpha, ///< [in] algebraic variable |
---|
| 252 | const CanonicalForm& evaluation,///< [in] evaluation point |
---|
| 253 | const mat_zz_p& M ///< [in] bases change matrix |
---|
| 254 | ); |
---|
| 255 | #endif |
---|
| 256 | |
---|
| 257 | /// write A into M starting at row startIndex |
---|
| 258 | void |
---|
| 259 | writeInMatrix (CFMatrix& M, ///< [in,out] some matrix |
---|
| 260 | const CFArray& A, ///< [in] array of polys |
---|
| 261 | const int column, ///< [in] column in which A is written |
---|
| 262 | const int startIndex///< [in] row in which to start |
---|
| 263 | ); |
---|
| 264 | |
---|
[686ce3] | 265 | /// checks if a substitution x^n->x is possible |
---|
| 266 | /// |
---|
| 267 | /// @return an integer n > 1, if a substitution described as above is possible |
---|
| 268 | /// else n <= 1 |
---|
| 269 | int substituteCheck (const CFList& L ///< [in] a list of univariate polys |
---|
| 270 | ); |
---|
| 271 | |
---|
| 272 | /// substitute x^d by x in F |
---|
| 273 | void |
---|
| 274 | subst (const CanonicalForm& F, ///< [in] a polynomial |
---|
| 275 | CanonicalForm& A, ///< [in,out] returns F with x^d replaced by x |
---|
| 276 | const int d, ///< d > 1 such that a substitution x^d -> x |
---|
| 277 | ///< [in] is possible |
---|
| 278 | const Variable& x ///< [in] a Variable |
---|
| 279 | ); |
---|
| 280 | |
---|
| 281 | /// reverse a substitution x^d->x |
---|
| 282 | /// |
---|
| 283 | /// @return a poly with x replaced by x^d |
---|
| 284 | CanonicalForm |
---|
| 285 | reverseSubst (const CanonicalForm& F, ///< [in] a poly |
---|
| 286 | const int d, ///< [in] an integer > 0 |
---|
| 287 | const Variable& x ///< [in] a Variable |
---|
| 288 | ); |
---|
| 289 | |
---|
| 290 | /// reverse a substitution x^d->x |
---|
| 291 | void |
---|
| 292 | reverseSubst (CFList& L, ///< [in,out] a list of polys, returns the |
---|
| 293 | ///< given list with x replaced by x^d |
---|
| 294 | const int d, ///< [in] an integer > 0 |
---|
| 295 | const Variable& x ///< [in] a Variable |
---|
| 296 | ); |
---|
| 297 | |
---|
[dd8047] | 298 | /// check if a substitution x^n->x is possible |
---|
| 299 | /// |
---|
| 300 | /// @return an integer n > 1, if a substitution described as above is possible |
---|
| 301 | /// else n <= 1 |
---|
| 302 | int |
---|
| 303 | substituteCheck (const CanonicalForm& F, ///<[in] a polynomial |
---|
| 304 | const Variable& x ///<[in] some variable |
---|
| 305 | ); |
---|
| 306 | |
---|
[7bf145] | 307 | #endif |
---|
| 308 | /* FAC_FQ_BIVAR_UTIL_H */ |
---|
| 309 | |
---|