Changeset c6d3744 in git
 Timestamp:
 Jan 22, 2008, 10:29:56 AM (15 years ago)
 Branches:
 (u'spielwiese', '0d6b7fcd9813a1ca1ed4220cfa2b104b97a0a003')
 Children:
 ef9d6b431bfae763ec3be1cc7fa8a7ff3a44d0d3
 Parents:
 a8107357ac68111e1051981bf688474782ef2671
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

factory/fac_multivar.cc
ra81073 rc6d3744 1 1 /* emacs edit mode for this file is * C++ * */ 2 /* $Id: fac_multivar.cc,v 1.1 2 20050822 17:24:02Singular Exp $ */2 /* $Id: fac_multivar.cc,v 1.13 20080122 09:29:56 Singular Exp $ */ 3 3 4 4 #include <config.h> … … 21 21 22 22 void out_cf(char *s1,const CanonicalForm &f,char *s2); 23 void out_cff(CFFList &L); 23 24 24 25 TIMING_DEFINE_PRINT(fac_content); … … 118 119 if ( r > 0 ) 119 120 A.nextpoint(); 120 while ( ! found ) { 121 while ( ! found ) 122 { 121 123 Vn = A( V ); 122 if ( Vn != 0 ) { 124 if ( Vn != 0 ) 125 { 123 126 U0 = A( U ); 124 127 DEBOUTLN( cerr, "U0 = " << U0 ); 125 if ( isSqrFree( U0 ) ) { 128 if ( isSqrFree( U0 ) ) 129 { 126 130 delta = content( U0 ); 127 131 DEBOUTLN( cerr, "content( U0 ) = " << delta ); … … 130 134 found = nonDivisors( omega, delta, FF, D ); 131 135 } 132 else { 136 else 137 { 133 138 DEBOUTLN( cerr, "not sqrfree : " << sqrFree( U0 ) ); 134 139 } … … 191 196 #endif 192 197 193 static CFArray 194 ZFactorizeMulti ( const CanonicalForm & arg ) 198 static CFArray ZFactorizeMulti ( const CanonicalForm & arg ) 195 199 { 196 200 DEBINCLEVEL( cerr, "ZFactorizeMulti" ); … … 217 221 218 222 maxdeg = 0; 219 for ( i = 2; i <= t; i++ ) { 223 for ( i = 2; i <= t; i++ ) 224 { 220 225 j = U.degree( Variable( i ) ); 221 226 if ( j > maxdeg ) maxdeg = j; 222 227 } 223 228 224 if ( F.getFirst().factor().inCoeffDomain() ) { 229 if ( F.getFirst().factor().inCoeffDomain() ) 230 { 225 231 omega = F.getFirst().factor(); 226 232 F.removeFirst(); 227 if ( omega < 0 ) { 233 if ( omega < 0 ) 234 { 228 235 negate = true; 229 236 omega = omega; … … 240 247 // A.nextpoint(); 241 248 242 while ( ! goodeval ) { 249 while ( ! goodeval ) 250 { 243 251 TIMING_START(fac_findeval); 244 252 findEvaluation( U, V, omega, F, A, U0, delta, D, r ); … … 254 262 { 255 263 int i=prime_number; 256 257 258 259 260 261 262 { 264 find_good_prime(arg,i); 265 find_good_prime(U0,i); 266 find_good_prime(U,i); 267 int p=cf_getSmallPrime(i); 268 //printf("found:p=%d (%d)\n",p,i); 269 if ((i==0)(i!=prime_number)) 270 { 263 271 b = coeffBound( U, p ); 264 265 } 266 267 268 269 272 prime_number=i; 273 } 274 modpk bb=coeffBound(U0,p); 275 if (bb.getk() > b.getk() ) b=bb; 276 bb=coeffBound(arg,p); 277 if (bb.getk() > b.getk() ) b=bb; 270 278 } 271 279 #else … … 274 282 b = getZFacModulus(); 275 283 #endif 276 284 //printf("p=%d, k=%d\n",b.getp(),b.getk()); 277 285 DEBOUTLN( cerr, "the coefficient bound of the factors of U is " << b.getpk() ); 278 286 … … 285 293 TIMING_END(fac_distrib); 286 294 #ifdef DEBUGOUTPUT 287 if ( goodeval ) { 295 if ( goodeval ) 296 { 288 297 DEBOUTLN( cerr, "the univariate factors after distribution are " << G ); 289 298 DEBOUTLN( cerr, "the distributed leading coeffs are " << lcG ); … … 291 300 DEBOUTLN( cerr, "which has leading coefficient " << LC( UU, Variable(1) ) ); 292 301 293 if ( LC( UU, Variable(1) ) != prod( lcG )  A(UU) != prod( G ) ) { 302 if ( LC( UU, Variable(1) ) != prod( lcG )  A(UU) != prod( G ) ) 303 { 294 304 DEBOUTLN( cerr, "!!! distribution was not correct !!!" ); 295 305 DEBOUTLN( cerr, "product of leading coeffs is " << prod( lcG ) ); … … 300 310 DEBOUTLN( cerr, "leading coeffs correct" ); 301 311 } 302 else { 312 else 313 { 303 314 DEBOUTLN( cerr, "we have found a bad evaluation point" ); 304 315 } 305 316 #endif 306 if ( goodeval ) { 317 if ( goodeval ) 318 { 307 319 TIMING_START(fac_hensel); 308 320 goodeval = Hensel( UU, G, lcG, A, b, Variable(1) ); … … 310 322 } 311 323 } 312 for ( i = 1; i <= r; i++ ) { 324 for ( i = 1; i <= r; i++ ) 325 { 313 326 G[i] /= icontent( G[i] ); 314 327 G[i] = M(G[i]); … … 321 334 } 322 335 323 CFFList 324 ZFactorizeMultivariate ( const CanonicalForm & f, bool issqrfree ) 336 CFFList ZFactorizeMultivariate ( const CanonicalForm & f, bool issqrfree ) 325 337 { 326 338 CFFList G, F, R; … … 336 348 F = CFFactor( f, 1 ); 337 349 else 338 F = sqrFree( f ); 339 340 for ( i = F; i.hasItem(); i++ ) { 341 if ( i.getItem().factor().inCoeffDomain() ) { 350 F = sqrFree( f, 0, false ); 351 352 for ( i = F; i.hasItem(); i++ ) 353 { 354 if ( i.getItem().factor().inCoeffDomain() ) 355 { 342 356 if ( ! i.getItem().factor().isOne() ) 343 357 R.append( CFFactor( i.getItem().factor(), i.getItem().exp() ) ); 344 358 } 345 else { 359 else 360 { 346 361 TIMING_START(fac_content); 347 362 g = compress( i.getItem().factor(), M ); … … 355 370 TIMING_END(fac_content); 356 371 DEBOUTLN( cerr, "now after content ..." ); 357 if ( g.isUnivariate() ) { 372 if ( g.isUnivariate() ) 373 { 358 374 G = factorize( g, true ); 359 375 for ( j = G; j.hasItem(); j++ ) … … 361 377 R.append( CFFactor( M( j.getItem().factor() ), n ) ); 362 378 } 363 else { 379 else 380 { 364 381 GG = ZFactorizeMulti( g ); 365 382 m = GG.max(); … … 376 393 return R; 377 394 } 395 396 static CFArray FpFactorizeMulti ( const CanonicalForm & arg ) 397 { 398 out_cf("FpFactorizeMulti:",arg,"\n"); 399 DEBINCLEVEL( cerr, "FpFactorizeMulti" ); 400 CFMap M; 401 CanonicalForm UU, U = compress( arg, M ); 402 CanonicalForm delta, omega, V = LC( U, 1 ); 403 int t = U.level(); 404 CFFList F = factorize( V ); 405 CFFListIterator I, J; 406 CFArray G, lcG, D; 407 int i, j, k, m, r, maxdeg, h; 408 REvaluation A( 2, t, FFRandom() ); 409 CanonicalForm U0; 410 CanonicalForm ft, ut, gt, d; 411 modpk b; 412 bool negate = false; 413 414 DEBOUTLN( cerr, "" ); 415 DEBOUTLN( cerr, "trying to factorize U = " << U ); 416 DEBOUTLN( cerr, "U is a polynomial of level = " << arg.level() ); 417 DEBOUTLN( cerr, "U will be factorized with respect to variable " << Variable(1) ); 418 DEBOUTLN( cerr, "the leading coefficient of U with respect to that variable is " << V ); 419 DEBOUTLN( cerr, "which is factorized as " << F ); 420 421 maxdeg = 0; 422 out_cf("try:",U,"\n"); 423 for ( i = 2; i <= t; i++ ) 424 { 425 j = U.degree( Variable( i ) ); 426 if ( j > maxdeg ) maxdeg = j; 427 } 428 429 if ( F.getFirst().factor().inCoeffDomain() ) 430 { 431 omega = F.getFirst().factor(); 432 F.removeFirst(); 433 if ( omega < 0 ) 434 { 435 negate = true; 436 omega = omega; 437 U = U; 438 } 439 } 440 else 441 omega = 1; 442 443 bool goodeval = false; 444 r = 0; 445 446 // for ( i = 0; i < 10*t; i++ ) 447 // A.nextpoint(); 448 449 while ( ! goodeval ) 450 { 451 TIMING_START(fac_findeval); 452 findEvaluation( U, V, omega, F, A, U0, delta, D, r ); 453 out_cf("univ.U0:",U0,"\n"); 454 TIMING_END(fac_findeval); 455 DEBOUTLN( cerr, "the evaluation point to reduce to an univariate problem is " << A ); 456 DEBOUTLN( cerr, "corresponding delta = " << delta ); 457 DEBOUTLN( cerr, " omega = " << omega ); 458 DEBOUTLN( cerr, " D = " << D ); 459 DEBOUTLN( cerr, "now factorize the univariate polynomial " << U0 ); 460 G = conv_to_factor_array( factorize( U0, false ) ); 461 printf("conv_to_factor_array\n"); 462 DEBOUTLN( cerr, "which factorizes into " << G ); 463 464 r = G.size(); 465 lcG = CFArray( 1, r ); 466 UU = U; 467 //if ( goodeval ) 468 { 469 printf("start hensel\n"); 470 TIMING_START(fac_hensel); 471 goodeval = Hensel( UU, G, lcG, A, b, Variable(1) ); 472 TIMING_END(fac_hensel); 473 } 474 } 475 for ( i = 1; i <= r; i++ ) 476 { 477 G[i] /= icontent( G[i] ); 478 G[i] = M(G[i]); 479 } 480 // negate noch beachten ! 481 if ( negate ) 482 G[1] = G[1]; 483 DEBDECLEVEL( cerr, "ZFactorMulti" ); 484 return G; 485 } 486 CFFList FpFactorizeMultivariate ( const CanonicalForm & f, bool issqrfree ) 487 { 488 CFFList G, F, R; 489 CFArray GG; 490 CFFListIterator i, j; 491 CFMap M; 492 CanonicalForm g, cont; 493 Variable v1, vm; 494 int k, m, n; 495 496 v1 = Variable(1); 497 if ( issqrfree ) 498 F = CFFactor( f, 1 ); 499 else 500 F = sqrFree( f, 0, false ); 501 502 printf("nach sqrFree:\n"); 503 out_cff(F); 504 for ( i = F; i.hasItem(); i++ ) 505 { 506 out_cf("consider:",i.getItem().factor(),"\n"); 507 if ( i.getItem().factor().inCoeffDomain() ) 508 { 509 if ( ! i.getItem().factor().isOne() ) 510 R.append( CFFactor( i.getItem().factor(), i.getItem().exp() ) ); 511 } 512 else 513 { 514 TIMING_START(fac_content); 515 g = compress( i.getItem().factor(), M ); 516 // now after compress g contains Variable(1) 517 vm = g.mvar(); 518 g = swapvar( g, v1, vm ); 519 cont = content( g ); 520 g = swapvar( g / cont, v1, vm ); 521 cont = swapvar( cont, v1, vm ); 522 n = i.getItem().exp(); 523 TIMING_END(fac_content); 524 DEBOUTLN( cerr, "now after content ..." ); 525 if ( g.isUnivariate() ) 526 { 527 G = factorize( g, true ); 528 for ( j = G; j.hasItem(); j++ ) 529 if ( ! j.getItem().factor().isOne() ) 530 R.append( CFFactor( M( j.getItem().factor() ), n ) ); 531 } 532 else 533 { 534 GG = FpFactorizeMulti( g ); 535 m = GG.max(); 536 for ( k = GG.min(); k <= m; k++ ) 537 if ( ! GG[k].isOne() ) 538 R.append( CFFactor( M( GG[k] ), n ) ); 539 } 540 out_cf("try cont:",cont,"\n"); 541 G = factorize( cont, true ); 542 out_cff(G); 543 for ( j = G; j.hasItem(); j++ ) 544 if ( ! j.getItem().factor().isOne() ) 545 R.append( CFFactor( M( j.getItem().factor() ), n ) ); 546 } 547 } 548 return R; 549 }
Note: See TracChangeset
for help on using the changeset viewer.