Changeset 806c18 in git for factory/facHensel.h
- Timestamp:
- Nov 15, 2010, 4:34:57 PM (13 years ago)
- Branches:
- (u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')
- Children:
- 7c3bca08c96331a56864c1d35b8c2e8ff2e0be89
- Parents:
- c840d97af622b4e4da8761738b540e21144f716b
- File:
-
- 1 edited
-
factory/facHensel.h (modified) (28 diffs)
Legend:
- Unmodified
- Added
- Removed
-
factory/facHensel.h
rc840d9 r806c18 1 1 /*****************************************************************************\ 2 * Computer Algebra System SINGULAR 2 * Computer Algebra System SINGULAR 3 3 \*****************************************************************************/ 4 4 /** @file facHensel.h 5 * 6 * This file defines functions for Hensel lifting and modular multiplication. 7 * 8 * ABSTRACT: function are used for bi- and multivariate factorization over 5 * 6 * This file defines functions for Hensel lifting and modular multiplication. 7 * 8 * ABSTRACT: function are used for bi- and multivariate factorization over 9 9 * finite fields 10 10 * … … 25 25 26 26 #include "canonicalform.h" 27 #include "cf_iter.h" 27 #include "cf_iter.h" 28 28 #include "ftmpl_functions.h" 29 29 #include "algext.h" … … 31 31 CanonicalForm mul (const CanonicalForm& F, const CanonicalForm& G); 32 32 CanonicalForm mulMod3 (const CanonicalForm& F, const CanonicalForm& G, const CFList& MOD); 33 /// multiplication of univariate polys over a finite field using NTL, if we are 33 /// multiplication of univariate polys over a finite field using NTL, if we are 34 34 /// in GF factory's default multiplication is used. 35 35 /// … … 37 37 static inline 38 38 CanonicalForm 39 mulNTL (const CanonicalForm& F, ///< [in] a univariate poly 39 mulNTL (const CanonicalForm& F, ///< [in] a univariate poly 40 40 const CanonicalForm& G ///< [in] a univariate poly 41 41 ); 42 42 43 /// mod of univariate polys over a finite field using NTL, if we are 43 /// mod of univariate polys over a finite field using NTL, if we are 44 44 /// in GF factory's default mod is used. 45 45 /// … … 47 47 static inline 48 48 CanonicalForm 49 modNTL (const CanonicalForm& F, ///< [in] a univariate poly 49 modNTL (const CanonicalForm& F, ///< [in] a univariate poly 50 50 const CanonicalForm& G ///< [in] a univariate poly 51 51 ); 52 52 53 /// division of univariate polys over a finite field using NTL, if we are 53 /// division of univariate polys over a finite field using NTL, if we are 54 54 /// in GF factory's default division is used. 55 55 /// … … 57 57 static inline 58 58 CanonicalForm 59 divNTL (const CanonicalForm& F, ///< [in] a univariate poly 59 divNTL (const CanonicalForm& F, ///< [in] a univariate poly 60 60 const CanonicalForm& G ///< [in] a univariate poly 61 61 ); 62 62 63 /*/// division with remainder of univariate polys over a finite field using NTL, 63 /*/// division with remainder of univariate polys over a finite field using NTL, 64 64 /// if we are in GF factory's default division with remainder is used. 65 65 static inline 66 66 void 67 divremNTL (const CanonicalForm& F, ///< [in] a univariate poly 67 divremNTL (const CanonicalForm& F, ///< [in] a univariate poly 68 68 const CanonicalForm& G, ///< [in] a univariate poly 69 69 CanonicalForm& Q, ///< [in,out] dividend … … 71 71 );*/ 72 72 73 /// splits @a F into degree (F, x)/m polynomials each of degree less than @a m 73 /// splits @a F into degree (F, x)/m polynomials each of degree less than @a m 74 74 /// in @a x. 75 75 /// 76 76 /// @return @a split returns a list of polynomials of degree less than @a m in 77 /// @a x. If degree (F, x) <= 0, F is returned. 77 /// @a x. If degree (F, x) <= 0, F is returned. 78 78 /// @sa divrem32(), divrem21() 79 79 static inline … … 81 81 const int m, ///< [in] some int 82 82 const Variable& x ///< [in] some Variable 83 ); 83 ); 84 84 85 85 /// division with remainder of @a F by 86 86 /// @a G wrt Variable (1) modulo @a M. 87 /// 87 /// 88 88 /// @sa divrem(), divrem21(), divrem2() 89 89 static inline 90 void divrem32 (const CanonicalForm& F, ///< [in] poly, s.t. 3*(degree (G, 1)/2)> 90 void divrem32 (const CanonicalForm& F, ///< [in] poly, s.t. 3*(degree (G, 1)/2)> 91 91 ///< degree (F, 1) 92 92 const CanonicalForm& G, ///< [in] some poly 93 93 CanonicalForm& Q, ///< [in,out] dividend 94 CanonicalForm& R, ///< [in,out] remainder, degree (R, 1) < 94 CanonicalForm& R, ///< [in,out] remainder, degree (R, 1) < 95 95 ///< degree (G, 1) 96 96 const CFList& M ///< [in] only contains powers of … … 100 100 /// division with remainder of @a F by 101 101 /// @a G wrt Variable (1) modulo @a M. 102 /// 102 /// 103 103 /// @sa divrem(), divrem32(), divrem2() 104 104 static inline … … 107 107 const CanonicalForm& G, ///< [in] some poly 108 108 CanonicalForm& Q, ///< [in,out] dividend 109 CanonicalForm& R, ///< [in,out] remainder, degree (R, 1) < 109 CanonicalForm& R, ///< [in,out] remainder, degree (R, 1) < 110 110 ///< degree (G, 1) 111 111 const CFList& M ///< [in] only contains powers of … … 114 114 115 115 /// division with remainder of @a F by 116 /// @a G wrt Variable (1) modulo @a M. 117 /// 116 /// @a G wrt Variable (1) modulo @a M. 117 /// 118 118 /// @return @a Q returns the dividend, @a R returns the remainder. 119 119 /// @sa divrem() 120 void divrem2 (const CanonicalForm& F, ///< [in] bivariate, compressed polynomial 120 void divrem2 (const CanonicalForm& F, ///< [in] bivariate, compressed polynomial 121 121 const CanonicalForm& G, ///< [in] bivariate, compressed polynomial 122 122 CanonicalForm& Q, ///< [in,out] dividend 123 CanonicalForm& R, ///< [in,out] remainder, degree (R, 1) < 123 CanonicalForm& R, ///< [in,out] remainder, degree (R, 1) < 124 124 ///< degree (G, 1) 125 125 const CanonicalForm& M ///< [in] power of Variable (2) … … 134 134 const CanonicalForm& G, ///< [in] multivariate, compressed polynomial 135 135 CanonicalForm& Q, ///< [in,out] dividend 136 CanonicalForm& R, ///< [in,out] remainder, degree (R, 1) < 136 CanonicalForm& R, ///< [in,out] remainder, degree (R, 1) < 137 137 ///< degree (G, 1) 138 138 const CFList& MOD ///< [in] only contains powers of … … 144 144 /// @return @a mod returns @a F modulo @a M 145 145 CanonicalForm mod (const CanonicalForm& F, ///< [in] compressed polynomial 146 const CFList& M ///< [in] list containing only 146 const CFList& M ///< [in] list containing only 147 147 ///< univariate polynomials 148 148 ); … … 151 151 /// 152 152 /// @return @a mulMod2 returns @a A * @a B mod @a M. 153 CanonicalForm 153 CanonicalForm 154 154 mulMod2 (const CanonicalForm& A, ///< [in] bivariate, compressed polynomial 155 155 const CanonicalForm& B, ///< [in] bivariate, compressed polynomial … … 160 160 /// 161 161 /// @return @a mulMod2 returns @a A * @a B mod @a MOD. 162 CanonicalForm 162 CanonicalForm 163 163 mulMod (const CanonicalForm& A, ///< [in] multivariate, compressed polynomial 164 164 const CanonicalForm& B, ///< [in] multivariate, compressed polynomial … … 170 170 /// 171 171 /// @return @a prodMod returns product of all elements in @a L modulo @a M. 172 CanonicalForm 173 prodMod (const CFList& L, ///< [in] contains only bivariate, compressed 172 CanonicalForm 173 prodMod (const CFList& L, ///< [in] contains only bivariate, compressed 174 174 ///< polynomials 175 175 const CanonicalForm& M ///< [in] power of Variable (2) … … 179 179 /// 180 180 /// @return @a prodMod returns product of all elements in @a L modulo @a M. 181 CanonicalForm 182 prodMod (const CFList& L, ///< [in] contains multivariate, compressed 181 CanonicalForm 182 prodMod (const CFList& L, ///< [in] contains multivariate, compressed 183 183 ///< polynomials 184 184 const CFList& M ///< [in] contains only powers of Variables 185 185 ); 186 186 187 187 /// sort a list of polynomials by their degree in @a x. 188 188 /// 189 void sortList (CFList& list, ///< [in, out] list of polys, sorted list 190 const Variable& x ///< [in] some Variable 189 void sortList (CFList& list, ///< [in, out] list of polys, sorted list 190 const Variable& x ///< [in] some Variable 191 191 ); 192 192 193 /// solve the univariate diophantine equation 193 /// solve the univariate diophantine equation 194 194 /// \f$ 1\equiv \sum_{i= 1}^{r} {\delta_{i} F/g_{i}} \f$. 195 /// Where \f$ F= \prod_{i= 1}^{r} {g_{i}} \f$ and \f$ F \f$ is squarefree 195 /// Where \f$ F= \prod_{i= 1}^{r} {g_{i}} \f$ and \f$ F \f$ is squarefree 196 196 /// the \f$ \delta_{i} \f$ have degree less than the degree of \f$ g_{i} \f$. 197 197 /// … … 200 200 /// @sa biDiophantine(), multiRecDiophantine() 201 201 static inline 202 CFList diophantine (const CanonicalForm& F, ///< [in] compressed, bivariate 202 CFList diophantine (const CanonicalForm& F, ///< [in] compressed, bivariate 203 203 ///< polynomial 204 const CFList& factors ///< [in] a list of factors, as 204 const CFList& factors ///< [in] a list of factors, as 205 205 ///< specified above, including 206 ///< LC (F, Variable (1)) as first 206 ///< LC (F, Variable (1)) as first 207 207 ///< element 208 208 ); 209 209 210 210 /// Hensel lift from univariate to bivariate. 211 /// 211 /// 212 212 /// @sa henselLiftResume12(), henselLift23(), henselLiftResume(), henselLift() 213 void 213 void 214 214 henselLift12 (const CanonicalForm& F, ///< [in] compressed, bivariate poly 215 CFList& factors, ///< [in, out] monic univariate factors of 215 CFList& factors, ///< [in, out] monic univariate factors of 216 216 ///< F, including leading coefficient as 217 ///< first element. Returns monic lifted 218 ///< factors without the leading 217 ///< first element. Returns monic lifted 218 ///< factors without the leading 219 219 ///< coefficient 220 220 int l, ///< [in] lifting precision … … 224 224 ); 225 225 226 /// resume Hensel lift from univariate to bivariate. Assumes factors are lifted 226 /// resume Hensel lift from univariate to bivariate. Assumes factors are lifted 227 227 /// to precision Variable (2)^start and lifts them to precision Variable (2)^end 228 /// 228 /// 229 229 /// @sa henselLift12(), henselLift23(), henselLiftResume(), henselLift() 230 void 230 void 231 231 henselLiftResume12 (const CanonicalForm& F, ///< [in] compressed, bivariate poly 232 CFList& factors, ///< [in,out] monic factors of F, 233 ///< lifted to precision start, 234 ///< including leading coefficient 235 ///< as first element. Returns monic 236 ///< lifted factors without the 232 CFList& factors, ///< [in,out] monic factors of F, 233 ///< lifted to precision start, 234 ///< including leading coefficient 235 ///< as first element. Returns monic 236 ///< lifted factors without the 237 237 ///< leading coefficient 238 238 int start, ///< [in] starting precision … … 247 247 /// solves the bivariate polynomial diophantine equation 248 248 /// \f$ 1\equiv \sum_{i= 1}^{r} {\delta_{i} F/g_{i}} \ mod\ y^{d} \f$, 249 /// where \f$ F= \prod_{i= 1}^{r} {g_{i}} \ mod\ y^{d}\f$ and 249 /// where \f$ F= \prod_{i= 1}^{r} {g_{i}} \ mod\ y^{d}\f$ and 250 250 /// \f$ F \in K[x][y]\f$ is squarefree, the \f$ \delta_{i} \f$ have degree less 251 251 /// than the degree of \f$ g_{i} \f$ in x. … … 258 258 biDiophantine (const CanonicalForm& F, ///< [in] compressed, bivariate poly 259 259 const CFList& factors, ///< [in] list of monic bivariate factors 260 ///< including LC (F, Variable (1)) as 260 ///< including LC (F, Variable (1)) as 261 261 ///< first element 262 262 const int d ///< [in] precision … … 265 265 /// solve the multivariate polynomial diophantine equation 266 266 /// \f$ 1\equiv \sum_{i= 1}^{r} {\delta_{i} F/g_{i}} \ mod\ <M,F.mvar()^{d}>\f$, 267 /// where \f$ F= \prod_{i= 1}^{r} {g_{i}} \ mod\ <M,F.mvar()^{d}>\f$ and 268 /// \f$ F \in K[x][x_1,\ldots , x_n]\f$ is squarefree, the \f$ \delta_{i} \f$ 269 /// have degree less than the degree of \f$ g_{i} \f$ in x. 270 /// 271 /// @return @a multiDiophantine returns a list of polynomials \f$ \delta_{i} \f$ 267 /// where \f$ F= \prod_{i= 1}^{r} {g_{i}} \ mod\ <M,F.mvar()^{d}>\f$ and 268 /// \f$ F \in K[x][x_1,\ldots , x_n]\f$ is squarefree, the \f$ \delta_{i} \f$ 269 /// have degree less than the degree of \f$ g_{i} \f$ in x. 270 /// 271 /// @return @a multiDiophantine returns a list of polynomials \f$ \delta_{i} \f$ 272 272 /// as specified above 273 273 /// @sa diophantine(), biDiophantine() … … 275 275 CFList 276 276 multiRecDiophantine ( 277 const CanonicalForm& F, ///< [in] compressed, 277 const CanonicalForm& F, ///< [in] compressed, 278 278 ///< multivariate polynomial 279 279 const CFList& factors, ///< [in] list of monic factors … … 292 292 /// Variable (3)^l[1] 293 293 /// @sa henselLift12(), henselLiftResume12(), henselLiftResume(), henselLift() 294 CFList 294 CFList 295 295 henselLift23 (const CFList& eval, ///< [in] contains compressed, bivariate 296 296 ///< as first element and trivariate one as 297 ///< second element 298 const CFList& factors, ///< [in] monic bivariate factors, 299 ///< including leading coefficient 297 ///< second element 298 const CFList& factors, ///< [in] monic bivariate factors, 299 ///< including leading coefficient 300 300 ///< as first element. 301 const int* l, ///< [in] l[0]: precision of bivariate 301 const int* l, ///< [in] l[0]: precision of bivariate 302 302 ///< lifting, l[1] as above 303 303 CFList& diophant, ///< [in,out] returns the result of … … 310 310 /// 311 311 /// @sa henselLift12(), henselLiftResume12(), henselLift23(), henselLift() 312 void 312 void 313 313 henselLiftResume ( 314 const CanonicalForm& F, ///< [in] compressed, multivariate poly 314 const CanonicalForm& F, ///< [in] compressed, multivariate poly 315 315 CFList& factors, ///< [in,out] monic multivariate factors 316 ///< lifted to precision F.mvar()^start, 317 ///< including leading coefficient 316 ///< lifted to precision F.mvar()^start, 317 ///< including leading coefficient 318 318 ///< as first element. Returns factors 319 319 ///< lifted to precision F.mvar()^end 320 int start, ///< [in] starting precision 320 int start, ///< [in] starting precision 321 321 int end, ///< [in] end precision 322 322 CFArray& Pi, ///< [in,out] stores intermediate results … … 329 329 /// Hensel lifting 330 330 /// 331 /// @return @a henselLift returns a list of polynomials lifted to 331 /// @return @a henselLift returns a list of polynomials lifted to 332 332 /// precision F.getLast().mvar()^l_new 333 333 /// @sa henselLift12(), henselLiftResume12(), henselLift23(), henselLiftResume() … … 335 335 henselLift (const CFList& F, ///< [in] two compressed, multivariate 336 336 ///< polys F and G 337 const CFList& factors, ///< [in] monic multivariate factors 338 ///< including leading coefficient 339 ///< as first element. 337 const CFList& factors, ///< [in] monic multivariate factors 338 ///< including leading coefficient 339 ///< as first element. 340 340 const CFList& MOD, ///< [in] a list of powers of Variables 341 341 ///< of level higher than 1 … … 343 343 CFArray& Pi, ///< [in,out] stores intermediate results 344 344 CFMatrix& M, ///< [in,out] stores intermediate results 345 const int lOld, ///< [in] lifting precision of F.mvar() 345 const int lOld, ///< [in] lifting precision of F.mvar() 346 346 const int lNew ///< [in] lifting precision of G.mvar() 347 347 ); 348 348 349 /// Hensel lifting from bivariate to multivariate 350 /// 351 /// @return @a henselLift returns a list of lifted factors 352 /// @sa henselLift12(), henselLiftResume12(), henselLift23(), henselLiftResume() 353 CFList 354 henselLift (const CFList& eval, ///< [in] a list of polynomials the last 355 ///< element is a compressed multivariate 356 ///< poly, last but one element equals the 349 /// Hensel lifting from bivariate to multivariate 350 /// 351 /// @return @a henselLift returns a list of lifted factors 352 /// @sa henselLift12(), henselLiftResume12(), henselLift23(), henselLiftResume() 353 CFList 354 henselLift (const CFList& eval, ///< [in] a list of polynomials the last 355 ///< element is a compressed multivariate 356 ///< poly, last but one element equals the 357 357 ///< last elements modulo its main variable 358 ///< and so on. The first element is a 358 ///< and so on. The first element is a 359 359 ///< compressed bivariate poly. 360 const CFList& factors, ///< [in] bivariate factors, including 360 const CFList& factors, ///< [in] bivariate factors, including 361 361 ///< leading coefficient 362 362 const int* l, ///< [in] lifting bounds
Note: See TracChangeset
for help on using the changeset viewer.
