Changeset 806c18 in git for factory/facFqFactorize.h
- Timestamp:
- Nov 15, 2010, 4:34:57 PM (13 years ago)
- Branches:
- (u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')
- Children:
- 7c3bca08c96331a56864c1d35b8c2e8ff2e0be89
- Parents:
- c840d97af622b4e4da8761738b540e21144f716b
- File:
-
- 1 edited
-
factory/facFqFactorize.h (modified) (24 diffs)
Legend:
- Unmodified
- Added
- Removed
-
factory/facFqFactorize.h
rc840d9 r806c18 1 1 /*****************************************************************************\ 2 * Computer Algebra System SINGULAR 2 * Computer Algebra System SINGULAR 3 3 \*****************************************************************************/ 4 4 /** @file facFqFactorize.h 5 * 5 * 6 6 * This file provides functions for factorizing a multivariate polynomial over 7 * \f$ F_{p} \f$ , \f$ F_{p}(\alpha ) \f$ or GF. 7 * \f$ F_{p} \f$ , \f$ F_{p}(\alpha ) \f$ or GF. 8 8 * 9 * ABSTRACT: So far factor recombination is done naive! 9 * ABSTRACT: So far factor recombination is done naive! 10 10 * 11 11 * @author Martin Lee … … 29 29 30 30 /// Factorization over a finite field 31 /// 31 /// 32 32 /// @return @a multiFactorize returns a factorization of F 33 33 /// @sa biFactorize(), extFactorize() 34 CFList 34 CFList 35 35 multiFactorize (const CanonicalForm& F, ///< [in] poly to be factored 36 36 const ExtensionInfo& info ///< [in] info about extension … … 39 39 /// factorize a squarefree multivariate polynomial over \f$ F_{p} \f$ 40 40 /// 41 /// @return @a FpSqrfFactorize returns a list of monic factors, the first 42 /// element is the leading coefficient. 41 /// @return @a FpSqrfFactorize returns a list of monic factors, the first 42 /// element is the leading coefficient. 43 43 /// @sa FqSqrfFactorize(), GFSqrfFactorize() 44 44 inline 45 45 CFList FpSqrfFactorize (const CanonicalForm & F ///< [in] a multivariate poly 46 ) 46 ) 47 47 { 48 48 ExtensionInfo info= ExtensionInfo (false); … … 54 54 /// factorize a squarefree multivariate polynomial over \f$ F_{p} (\alpha ) \f$ 55 55 /// 56 /// @return @a FqSqrfFactorize returns a list of monic factors, the first 57 /// element is the leading coefficient. 58 /// @sa FpSqrfFactorize(), GFSqrfFactorize() 56 /// @return @a FqSqrfFactorize returns a list of monic factors, the first 57 /// element is the leading coefficient. 58 /// @sa FpSqrfFactorize(), GFSqrfFactorize() 59 59 inline 60 60 CFList FqSqrfFactorize (const CanonicalForm & F, ///< [in] a multivariate poly 61 61 const Variable& alpha ///< [in] algebraic variable 62 ) 62 ) 63 63 { 64 64 ExtensionInfo info= ExtensionInfo (alpha, false); … … 68 68 } 69 69 70 /// factorize a squarefree multivariate polynomial over GF 71 /// 72 /// @return @a GFSqrfFactorize returns a list of monic factors, the first 73 /// element is the leading coefficient. 70 /// factorize a squarefree multivariate polynomial over GF 71 /// 72 /// @return @a GFSqrfFactorize returns a list of monic factors, the first 73 /// element is the leading coefficient. 74 74 /// @sa FpSqrfFactorize(), FqSqrfFactorize() 75 75 inline 76 76 CFList GFSqrfFactorize (const CanonicalForm & F ///< [in] a multivariate poly 77 ) 77 ) 78 78 { 79 ASSERT (CFFactory::gettype() == GaloisFieldDomain, 79 ASSERT (CFFactory::gettype() == GaloisFieldDomain, 80 80 "GF as base field expected"); 81 81 ExtensionInfo info= ExtensionInfo (getGFDegree(), gf_name, false); … … 85 85 } 86 86 87 /// factorize a multivariate polynomial over \f$ F_{p} \f$ 88 /// 89 /// @return @a FpFactorize returns a list of monic factors with 90 /// multiplicity, the first element is the leading coefficient. 87 /// factorize a multivariate polynomial over \f$ F_{p} \f$ 88 /// 89 /// @return @a FpFactorize returns a list of monic factors with 90 /// multiplicity, the first element is the leading coefficient. 91 91 /// @sa FqFactorize(), GFFactorize() 92 92 inline 93 93 CFFList FpFactorize (const CanonicalForm& F ///< [in] a multivariate poly 94 ) 94 ) 95 95 { 96 96 ExtensionInfo info= ExtensionInfo (false); 97 97 Variable a= Variable (1); 98 CanonicalForm LcF= Lc (F); 98 CanonicalForm LcF= Lc (F); 99 99 CanonicalForm pthRoot, A; 100 100 CanonicalForm sqrfP= sqrfPart (F/Lc(F), pthRoot, a); … … 114 114 } 115 115 else 116 { 116 { 117 117 buf= multiFactorize (sqrfP, info); 118 118 A= F/LcF; … … 131 131 /// factorize a multivariate polynomial over \f$ F_{p} (\alpha ) \f$ 132 132 /// 133 /// @return @a FqFactorize returns a list of monic factors with 134 /// multiplicity, the first element is the leading coefficient. 133 /// @return @a FqFactorize returns a list of monic factors with 134 /// multiplicity, the first element is the leading coefficient. 135 135 /// @sa FpFactorize(), GFFactorize() 136 136 inline 137 137 CFFList FqFactorize (const CanonicalForm& F, ///< [in] a multivariate poly 138 138 const Variable& alpha ///< [in] algebraic variable 139 ) 139 ) 140 140 { 141 ExtensionInfo info= ExtensionInfo (alpha, false); 142 CanonicalForm LcF= Lc (F); 141 ExtensionInfo info= ExtensionInfo (alpha, false); 142 CanonicalForm LcF= Lc (F); 143 143 CanonicalForm pthRoot, A; 144 144 CanonicalForm sqrfP= sqrfPart (F/Lc(F), pthRoot, alpha); … … 159 159 } 160 160 else 161 { 161 { 162 162 buf= multiFactorize (sqrfP, info); 163 163 A= F/LcF; … … 176 176 /// factorize a multivariate polynomial over GF 177 177 /// 178 /// @return @a GFFactorize returns a list of monic factors with 179 /// multiplicity, the first element is the leading coefficient. 178 /// @return @a GFFactorize returns a list of monic factors with 179 /// multiplicity, the first element is the leading coefficient. 180 180 /// @sa FpFactorize(), FqFactorize() 181 181 inline 182 182 CFFList GFFactorize (const CanonicalForm& F ///< [in] a multivariate poly 183 ) 183 ) 184 184 { 185 ASSERT (CFFactory::gettype() == GaloisFieldDomain, 185 ASSERT (CFFactory::gettype() == GaloisFieldDomain, 186 186 "GF as base field expected"); 187 187 Variable a= Variable (1); 188 ExtensionInfo info= ExtensionInfo (getGFDegree(), gf_name, false); 188 ExtensionInfo info= ExtensionInfo (getGFDegree(), gf_name, false); 189 189 CanonicalForm LcF= Lc (F); 190 190 CanonicalForm pthRoot, A; … … 221 221 } 222 222 223 /// compute the content of @a F wrt Variable (1) using routines from 223 /// compute the content of @a F wrt Variable (1) using routines from 224 224 /// @a cf_gcd_smallp.h 225 225 /// 226 226 /// @return @a myContent returns the content of F wrt Variable (1) 227 227 static inline 228 CanonicalForm 228 CanonicalForm 229 229 myContent (const CanonicalForm& F ///< [in] a poly 230 230 ); 231 231 232 /// compute the content of @a F wrt @a x using routines from 232 /// compute the content of @a F wrt @a x using routines from 233 233 /// @a cf_gcd_smallp.h 234 234 /// … … 236 236 static inline 237 237 CanonicalForm 238 myContent (const CanonicalForm& F, ///< [in] a poly 238 myContent (const CanonicalForm& F, ///< [in] a poly 239 239 const Variable& x ///< [in] a variable 240 240 ); 241 241 242 /// compute the GCD of all element in @a L using routines from 242 /// compute the GCD of all element in @a L using routines from 243 243 /// @a cf_gcd_smallp.h 244 244 /// 245 245 /// @return @a listGCD returns the GCD of all elements in @a L 246 246 static inline 247 CanonicalForm 247 CanonicalForm 248 248 listGCD (const CFList& L ///< [in] a list of polys 249 249 ); 250 250 251 /// compute the LCM of @a F and @a G using routines from 251 /// compute the LCM of @a F and @a G using routines from 252 252 /// @a cf_gcd_smallp.h 253 253 /// … … 262 262 /// A. 263 263 /// 264 /// @return @a lcmContent returns the LCM of the contents of @a A wrt to each 264 /// @return @a lcmContent returns the LCM of the contents of @a A wrt to each 265 265 /// variable occuring in @a A. 266 static inline 267 CanonicalForm 268 lcmContent (const CanonicalForm& A, ///< [in] a compressed multivariate poly 266 static inline 267 CanonicalForm 268 lcmContent (const CanonicalForm& A, ///< [in] a compressed multivariate poly 269 269 CFList& contentAi ///< [in,out] an empty list, returns a list 270 ///< of the contents of @a A wrt to each 270 ///< of the contents of @a A wrt to each 271 271 ///< variable occuring in @a A starting from 272 272 ///< @a A.mvar(). 273 273 ); 274 274 275 /// compress a polynomial s.t. \f$ deg_{x_{i}} (F) >= deg_{x_{i+1}} (F) \f$ and 275 /// compress a polynomial s.t. \f$ deg_{x_{i}} (F) >= deg_{x_{i+1}} (F) \f$ and 276 276 /// no gaps between the variables occur 277 277 /// … … 279 279 static inline 280 280 CanonicalForm myCompress (const CanonicalForm& F, ///< [in] a poly 281 CFMap& N ///< [in,out] a map to 281 CFMap& N ///< [in,out] a map to 282 282 ///< decompress 283 283 ); … … 286 286 /// Uses precomputed data to exclude combinations that are not possible. 287 287 /// 288 /// @return @a monicFactorRecombi returns a list of factors of F, that are 288 /// @return @a monicFactorRecombi returns a list of factors of F, that are 289 289 /// monic wrt Variable (1). 290 290 /// @sa extFactorRecombination(), factorRecombination(), biFactorizer() 291 CFList 291 CFList 292 292 monicFactorRecombi ( 293 293 const CFList& factors, ///< [in] list of lifted factors 294 294 ///< that are monic wrt Variable (1) 295 const CanonicalForm& F, ///< [in] bivariate poly 295 const CanonicalForm& F, ///< [in] bivariate poly 296 296 const CanonicalForm& M, ///< [in] Variable (2)^liftBound 297 297 const DegreePattern& degs ///< [in] degree pattern … … 300 300 /// detects factors of @a F at stage @a deg of Hensel lifting. 301 301 /// No combinations of more than one factor are tested. Lift bound and possible 302 /// degree pattern are updated. 303 /// 304 /// @return @a earlyMonicFactorDetect returns a list of factors of F (possibly 302 /// degree pattern are updated. 303 /// 304 /// @return @a earlyMonicFactorDetect returns a list of factors of F (possibly 305 305 /// incomplete) that are monic wrt Variable (1) 306 306 /// @sa monicFactorRecombi(), earlyFactorDetection(), monicFactorDetect(), 307 307 /// biFactorizer() 308 CFList 308 CFList 309 309 earlyMonicFactorDetect ( 310 310 CanonicalForm& F, ///< [in,out] poly to be factored, returns 311 311 ///< poly divided by detected factors in case 312 312 ///< of success 313 CFList& factors, ///< [in,out] list of factors lifted up to 313 CFList& factors, ///< [in,out] list of factors lifted up to 314 314 ///< @a deg, returns a list of factors 315 315 ///< without detected factors … … 319 319 bool& success, ///< [in,out] indicating success 320 320 int deg, ///< [in] stage of Hensel lifting 321 const int bound ///< [in] degree (A, 2) + 1 + 321 const int bound ///< [in] degree (A, 2) + 1 + 322 322 ///< degree (LC (A, 1), 2), where A is the 323 323 ///< multivariate polynomial corresponding to 324 ///< F. 324 ///< F. 325 325 ); 326 326 327 /// Bivariate factorization. In contrast to biFactorize() the factors returned 327 /// Bivariate factorization. In contrast to biFactorize() the factors returned 328 328 /// are monic wrt Variable (1), if @a F is not irreducible. And no factorization 329 /// wrt Variable (2) are performed. However, 330 /// 331 /// @return @a biFactorizer returns a list of factors that are monic wrt 329 /// wrt Variable (2) are performed. However, 330 /// 331 /// @return @a biFactorizer returns a list of factors that are monic wrt 332 332 /// Variable (1), if @a F is irreducible @a F is returned 333 /// @sa multiFactorize(), biFactorize() 334 CFList biFactorizer (const CanonicalForm& F, ///< [in] a bivariate poly 333 /// @sa multiFactorize(), biFactorize() 334 CFList biFactorizer (const CanonicalForm& F, ///< [in] a bivariate poly 335 335 const Variable& alpha, ///< [in] algebraic variable 336 CanonicalForm& bivarEval, ///< [in,out] a valid evaluation 337 ///< point 336 CanonicalForm& bivarEval, ///< [in,out] a valid evaluation 337 ///< point 338 338 int& liftBound ///< [in,out] lift bound, may be 339 ///< adapted during Hensel 340 ///< lifting 339 ///< adapted during Hensel 340 ///< lifting 341 341 ); 342 342 343 /// Naive factor recombination for multivariate factorization over an extension 344 /// of the initial field. No precomputed is used to exclude combinations. 343 /// Naive factor recombination for multivariate factorization over an extension 344 /// of the initial field. No precomputed is used to exclude combinations. 345 345 /// 346 346 /// @return @a extFactorRecombination returns a list of factors of @a F, whose 347 347 /// shift to zero is reversed. 348 /// @sa factorRecombination() 349 CFList 348 /// @sa factorRecombination() 349 CFList 350 350 extFactorRecombination ( 351 351 const CFList& factors, ///< [in] list of lifted factors 352 ///< that are monic wrt Variable (1) 352 ///< that are monic wrt Variable (1) 353 353 const CanonicalForm& F, ///< [in] poly to be factored 354 354 const CFList& M, ///< [in] a list of powers of 355 ///< Variables 356 const ExtensionInfo& info, ///< [in] info about extension 355 ///< Variables 356 const ExtensionInfo& info, ///< [in] info about extension 357 357 const CFList& evaluation ///< [in] evaluation point 358 358 ); … … 361 361 /// No precomputed is used to exclude combinations. 362 362 /// 363 /// @return @a factorRecombination returns a list of factors of @a F 364 /// @sa extFactorRecombination() 365 CFList 363 /// @return @a factorRecombination returns a list of factors of @a F 364 /// @sa extFactorRecombination() 365 CFList 366 366 factorRecombination (const CanonicalForm& F,///< [in] poly to be factored 367 367 const CFList& factors, ///< [in] list of lifted factors … … 375 375 /// 376 376 /// @return @a liftBoundAdaption returns an adapted lift bound. 377 /// @sa earlyFactorDetect(), earlyFactorDetection() 377 /// @sa earlyFactorDetect(), earlyFactorDetection() 378 378 int 379 379 liftBoundAdaption (const CanonicalForm& F, ///< [in] a poly 380 const CFList& factors, ///< [in] list of list of lifted 381 ///< factors that are monic wrt 380 const CFList& factors, ///< [in] list of list of lifted 381 ///< factors that are monic wrt 382 382 ///< Variable (1) 383 383 bool& success, ///< [in,out] indicates that no … … 393 393 /// 394 394 /// @return @a liftBoundAdaption returns an adapted lift bound. 395 /// @sa earlyFactorDetect(), earlyFactorDetection() 396 int 395 /// @sa earlyFactorDetect(), earlyFactorDetection() 396 int 397 397 extLiftBoundAdaption ( 398 399 const CFList& factors, ///< [in] list of list of lifted 400 ///< factors that are monic wrt 401 bool& success, ///< [in,out] indicates that no further 398 const CanonicalForm& F, ///< [in] a poly 399 const CFList& factors, ///< [in] list of list of lifted 400 ///< factors that are monic wrt 401 bool& success, ///< [in,out] indicates that no further 402 402 ///< lifting is necessary 403 404 405 406 407 ///< Variables 408 403 const ExtensionInfo& info, ///< [in] info about extension 404 const CFList& eval, ///< [in] evaluation point 405 const int deg, ///< [in] stage of Hensel lifting 406 const CFList& MOD, ///< [in] a list of powers of 407 ///< Variables 408 const int bound ///< [in] initial lift bound 409 409 ); 410 410 411 411 /// detects factors of @a F at stage @a deg of Hensel lifting. 412 /// No combinations of more than one factor are tested. Lift bound is adapted. 413 /// 414 /// @return @a earlyFactorDetect returns a list of factors of F (possibly 412 /// No combinations of more than one factor are tested. Lift bound is adapted. 413 /// 414 /// @return @a earlyFactorDetect returns a list of factors of F (possibly 415 415 /// incomplete), in case of success. Otherwise an empty list. 416 416 /// @sa factorRecombination(), extEarlyFactorDetect() 417 CFList 417 CFList 418 418 earlyFactorDetect ( 419 CanonicalForm& F, ///< [in,out] poly to be factored, 419 CanonicalForm& F, ///< [in,out] poly to be factored, 420 420 ///< returns poly divided by detected 421 421 ///< factors in case of success 422 422 CFList& factors, ///< [in,out] list of factors lifted up 423 423 ///< to @a deg, returns a list of factors 424 424 ///< without detected factors 425 426 427 428 425 int& adaptedLiftBound, ///< [in,out] adapted lift bound 426 bool& success, ///< [in,out] indicating success 427 const int deg, ///< [in] stage of Hensel lifting 428 const CFList& MOD, ///< [in] a list of powers of 429 429 ///< Variables 430 430 const int bound ///< [in] initial lift bound 431 431 ); 432 432 433 433 /// detects factors of @a F at stage @a deg of Hensel lifting. 434 /// No combinations of more than one factor are tested. Lift bound is adapted. 435 /// 436 /// @return @a extEarlyFactorDetect returns a list of factors of F (possibly 434 /// No combinations of more than one factor are tested. Lift bound is adapted. 435 /// 436 /// @return @a extEarlyFactorDetect returns a list of factors of F (possibly 437 437 /// incomplete), whose shift to zero is reversed, in case of success. 438 /// Otherwise an empty list. 438 /// Otherwise an empty list. 439 439 /// @sa factorRecombination(), earlyFactorDetection() 440 CFList 440 CFList 441 441 extEarlyFactorDetect ( 442 CanonicalForm& F, ///< [in,out] poly to be factored, 442 CanonicalForm& F, ///< [in,out] poly to be factored, 443 443 ///< returns poly divided by detected 444 444 ///< factors in case of success 445 445 CFList& factors, ///< [in,out] list of factors lifted up 446 446 ///< to @a deg, returns a list of factors 447 447 ///< without detected factors 448 449 450 451 452 453 454 448 int& adaptedLiftBound, ///< [in,out] adapted lift bound 449 bool& success, ///< [in,out] indicating succes 450 const ExtensionInfo& info, ///< [in] info about extension 451 const CFList& eval, ///< [in] evaluation point 452 const int deg, ///< [in] stage of Hensel lifting 453 const CFList& MOD, ///< [in] a list of powers of Variables 454 const int bound ///< [in] initial lift bound 455 455 ); 456 456 457 /// evaluation point search for multivariate factorization, 457 /// evaluation point search for multivariate factorization, 458 458 /// looks for a (F.level() - 1)-tuple such that the resulting univariate 459 459 /// polynomial has main variable F.mvar(), is squarefree and its degree 460 /// coincides with degree(F) and the bivariate one is primitive wrt. 461 /// Variable(1), fails if there are no valid evaluation points, eval contains 462 /// the intermediate evaluated polynomials. 460 /// coincides with degree(F) and the bivariate one is primitive wrt. 461 /// Variable(1), fails if there are no valid evaluation points, eval contains 462 /// the intermediate evaluated polynomials. 463 463 /// 464 464 /// @return @a evalPoints returns an evaluation point, which is valid if and 465 /// only if fail == false. 466 CFList 467 evalPoints (const CanonicalForm& F, ///< [in] a compressed poly 465 /// only if fail == false. 466 CFList 467 evalPoints (const CanonicalForm& F, ///< [in] a compressed poly 468 468 CFList & eval, ///< [in,out] an empty list, returns @a F 469 469 ///< successive evaluated … … 472 472 ///< considered, a point is encoded as a 473 473 ///< poly of degree F.level()-1 in 474 ///< Variable(1) 474 ///< Variable(1) 475 475 const bool& GF, ///< [in] GF? 476 476 bool& fail ///< [in,out] indicates failure … … 482 482 /// 483 483 /// @return @a newMainVariableSearch returns the level of the new main variable, 484 /// if there no variable which omitts a valid evaluation 0 is returned 484 /// if there no variable which omitts a valid evaluation 0 is returned 485 485 static inline 486 486 int newMainVariableSearch ( 487 487 CanonicalForm& A, ///< [in,out] a compressed poly, returns 488 ///< the swapped initial poly or the 489 ///< initial poly if 0 is returned 490 488 ///< the swapped initial poly or the 489 ///< initial poly if 0 is returned 490 CFList& Aeval, ///< [in,out] @a A successively evaluated, 491 491 ///< empty list if 0 is returned 492 493 ///< if 0 is returned 494 495 492 CFList& evaluation, ///< [in,out] evaluation point, empty list 493 ///< if 0 is returned 494 const Variable& alpha,///< [in] algebraic variable 495 const int lev ///< [in] some int <= A.level() 496 496 ); 497 /// hensel Lifting and early factor detection 498 /// 499 /// @return @a henselLiftAndEarly returns monic (wrt Variable (1)) lifted 497 /// hensel Lifting and early factor detection 498 /// 499 /// @return @a henselLiftAndEarly returns monic (wrt Variable (1)) lifted 500 500 /// factors without factors which have been detected at an early stage 501 501 /// of Hensel lifting … … 503 503 CFList 504 504 henselLiftAndEarly ( 505 CanonicalForm& A, ///< [in,out] poly to be factored, 505 CanonicalForm& A, ///< [in,out] poly to be factored, 506 506 ///< returns poly divided by detected 507 ///< factors, in case of success 508 507 ///< factors, in case of success 508 CFList& MOD, ///< [in,out] a list of powers of 509 509 ///< Variables 510 510 int*& liftBounds, ///< [in,out] initial lift bounds, returns 511 511 ///< adapted lift bounds 512 513 514 512 bool& earlySuccess, ///< [in,out] indicating success 513 CFList& earlyFactors, ///< [in,out] early factors 514 const CFList& Aeval, ///< [in] @a A successively evaluated at 515 515 ///< elements of @a evaluation 516 517 518 516 const CFList& biFactors, ///< [in] bivariate factors 517 const CFList& evaluation, ///< [in] evaluation point 518 const ExtensionInfo& info ///< [in] info about extension 519 519 ); 520 520 … … 523 523 /// @return @a extFactorize returns factorization of F over initial field 524 524 /// @sa extBiFactorize(), multiFactorize() 525 CFList 526 extFactorize (const CanonicalForm& F, ///< [in] poly to be factored 527 const ExtensionInfo& info ///< [in] info about extension 528 ); 525 CFList 526 extFactorize (const CanonicalForm& F, ///< [in] poly to be factored 527 const ExtensionInfo& info ///< [in] info about extension 528 ); 529 529 530 530 #endif
Note: See TracChangeset
for help on using the changeset viewer.
