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