[9f7665] | 1 | |
---|
| 2 | |
---|
| 3 | |
---|
[a356910] | 4 | |
---|
[b1dfaf] | 5 | #include <kernel/mod2.h> |
---|
| 6 | #include <omalloc/omalloc.h> |
---|
[5ff1d3] | 7 | |
---|
[0fb34ba] | 8 | #include <coeffs/numbers.h> |
---|
[a356910] | 9 | // #include <coeffs/longrat.h> |
---|
[5ff1d3] | 10 | |
---|
[0fb34ba] | 11 | #include <polys/monomials/ring.h> |
---|
[fe66ba8] | 12 | #include <polys/monomials/p_polys.h> |
---|
[5ff1d3] | 13 | #include <polys/kbuckets.h> |
---|
| 14 | |
---|
| 15 | #include <kernel/ideals.h> |
---|
[a356910] | 16 | #include <kernel/polys.h> |
---|
[57fa2c4] | 17 | #include <kernel/GBEngine/kutil.h> |
---|
[5ff1d3] | 18 | |
---|
[a356910] | 19 | // #include "subexpr.h" |
---|
[5ff1d3] | 20 | |
---|
[57fa2c4] | 21 | #include <kernel/GBEngine/janet.h> |
---|
[5a66d0] | 22 | |
---|
[a356910] | 23 | |
---|
| 24 | #include <stdio.h> |
---|
| 25 | #include <stdlib.h> |
---|
| 26 | #include <string.h> |
---|
| 27 | #include <stdarg.h> |
---|
| 28 | #include <time.h> |
---|
| 29 | |
---|
[5a66d0] | 30 | #if (defined(__CYGWIN__)) |
---|
| 31 | #include <ctype.h> |
---|
| 32 | #endif |
---|
[5ff1d3] | 33 | |
---|
[5a66d0] | 34 | |
---|
| 35 | //------GLOBALS------- |
---|
[6909cfb] | 36 | static int /*m_s,v_s,vectorized,VarN1,*/offset; |
---|
[5a66d0] | 37 | static jList *T,*Q; |
---|
| 38 | static TreeM *G; |
---|
[6909cfb] | 39 | // static Poly *phD; |
---|
[5a66d0] | 40 | static NodeM *FreeNodes; |
---|
| 41 | static int degree_compatible; |
---|
| 42 | static int (*ListGreatMove)(jList *,jList *,poly); |
---|
| 43 | static int Mask[8]={0x80,0x40,0x20,0x10,0x8,0x4,0x2,0x1}; |
---|
| 44 | |
---|
| 45 | //#define DebugPrint |
---|
| 46 | |
---|
| 47 | //#define pow_(x) pTotaldegree((x)) |
---|
[31f1850] | 48 | //#define pow_(x) p_Deg((x,currRing)) |
---|
[5a66d0] | 49 | pFDegProc jDeg; |
---|
[08db0a] | 50 | #define pow_(x) jDeg((x),currRing) |
---|
[5a66d0] | 51 | |
---|
[312083] | 52 | #if 0 |
---|
[5a66d0] | 53 | void Debug() |
---|
| 54 | { |
---|
| 55 | LCI it=T->root; |
---|
| 56 | |
---|
[ca4d0e6] | 57 | PrintS("T==================================\n"); |
---|
[5a66d0] | 58 | while (it) |
---|
| 59 | { |
---|
| 60 | pWrite(it->info->root); |
---|
| 61 | it=it->next; |
---|
| 62 | } |
---|
| 63 | |
---|
| 64 | it=Q->root; |
---|
| 65 | |
---|
[ca4d0e6] | 66 | PrintS("Q==================================\n"); |
---|
[5a66d0] | 67 | while (it) |
---|
| 68 | { |
---|
| 69 | if (it->info->root) pWrite(it->info->root); |
---|
| 70 | else |
---|
| 71 | { |
---|
| 72 | Print("%d.........",it->info->prolonged); |
---|
| 73 | pWrite(it->info->history); |
---|
| 74 | } |
---|
| 75 | it=it->next; |
---|
| 76 | } |
---|
[ca4d0e6] | 77 | PrintS("===================================\n"); |
---|
[5a66d0] | 78 | } |
---|
[312083] | 79 | #endif |
---|
[5a66d0] | 80 | |
---|
| 81 | int ReducePolyLead(Poly *x,Poly *y) |
---|
| 82 | { |
---|
| 83 | if (!x->root || !y->root) |
---|
| 84 | return 0; |
---|
| 85 | |
---|
| 86 | /* poly b1=pDivide(x->root,y->root); |
---|
| 87 | |
---|
[2b7e8f] | 88 | number gcd=n_Gcd(pGetCoeff(x->root),pGetCoeff(y->root),currRing->cf); |
---|
[5a66d0] | 89 | |
---|
| 90 | number a1=nDiv(pGetCoeff(y->root),gcd); |
---|
| 91 | pGetCoeff(b1)=nDiv(pGetCoeff(x->root),gcd); |
---|
| 92 | |
---|
| 93 | x->root=pMult_nn(x->root,a1); |
---|
| 94 | nDelete(&a1); |
---|
| 95 | |
---|
| 96 | x->root=pMinus_mm_Mult_qq(x->root,b1,y->root); |
---|
| 97 | |
---|
| 98 | pDelete(&b1); |
---|
| 99 | */ |
---|
| 100 | #if 1 |
---|
| 101 | if (x->root_b==NULL) |
---|
| 102 | { |
---|
| 103 | if (x->root_l<=0) x->root_l=pLength(x->root); |
---|
| 104 | x->root_b=kBucketCreate(currRing); |
---|
| 105 | kBucketInit(x->root_b,x->root,x->root_l); |
---|
| 106 | } |
---|
| 107 | number coef; |
---|
| 108 | if (y->root_l<=0) y->root_l=pLength(y->root); |
---|
| 109 | coef=kBucketPolyRed(x->root_b,y->root,y->root_l,NULL); |
---|
| 110 | nDelete(&coef); |
---|
| 111 | x->root=kBucketGetLm(x->root_b); |
---|
| 112 | if (x->root==NULL) |
---|
| 113 | { |
---|
| 114 | kBucketDestroy(&x->root_b); |
---|
| 115 | x->root_b=NULL; |
---|
| 116 | x->root_l=0; |
---|
| 117 | } |
---|
| 118 | #else |
---|
| 119 | x->root=ksOldSpolyRed(y->root,x->root,NULL); |
---|
| 120 | #endif |
---|
[6e0750] | 121 | // if (x->root) p_Content(x->root,currRing); |
---|
[5a66d0] | 122 | // if (x->root) pSimpleContent(x->root,5); |
---|
| 123 | |
---|
| 124 | return 1; |
---|
| 125 | } |
---|
| 126 | |
---|
| 127 | int ReducePoly(Poly *x,poly from,Poly *y) |
---|
| 128 | { |
---|
| 129 | if (!x->root || !y->root) |
---|
| 130 | return 0; |
---|
| 131 | |
---|
| 132 | /* poly b1=pDivide(from,y->root); |
---|
| 133 | |
---|
[2b7e8f] | 134 | number gcd=n_Gcd(pGetCoeff(from),pGetCoeff(y->root),currRing->cf); |
---|
[5a66d0] | 135 | |
---|
| 136 | number a1=nDiv(pGetCoeff(y->root),gcd); |
---|
| 137 | pGetCoeff(b1)=nDiv(pGetCoeff(from),gcd); |
---|
| 138 | |
---|
| 139 | x->root=pMult_nn(x->root,a1); |
---|
| 140 | nDelete(&a1);*/ |
---|
| 141 | |
---|
| 142 | // x->root=pMinus_mm_Mult_qq(x->root,b1,y->root); |
---|
| 143 | // pDelete(&b1); |
---|
| 144 | |
---|
| 145 | ksOldSpolyTail(y->root,x->root,from,NULL,currRing); |
---|
| 146 | y->root_l=0; |
---|
| 147 | |
---|
| 148 | return 1; |
---|
| 149 | } |
---|
| 150 | |
---|
| 151 | void PNF(Poly *p, TreeM *F) |
---|
| 152 | { |
---|
| 153 | if (p->root==NULL) return; |
---|
| 154 | |
---|
| 155 | Poly *f; |
---|
| 156 | BOOLEAN done=FALSE; |
---|
| 157 | poly temp=p->root; |
---|
| 158 | |
---|
| 159 | // if (TEST_OPT_PROT) { PrintS("r"); mflush(); } |
---|
| 160 | int count=0; |
---|
| 161 | poly pp=p->root; |
---|
| 162 | int old_size=nSize(pGetCoeff(pp)); |
---|
| 163 | p->root_l=0; |
---|
| 164 | while(temp->next) |
---|
| 165 | { |
---|
| 166 | f=is_div_(F,temp->next); |
---|
| 167 | if (f) |
---|
| 168 | { |
---|
| 169 | if (ReducePoly(p,temp,f)) //temp->next |
---|
| 170 | { |
---|
| 171 | count++; |
---|
| 172 | //if (TEST_OPT_PROT) { PrintS("-"); mflush(); } |
---|
| 173 | if ((f!=NULL) |
---|
| 174 | && (count>20) |
---|
| 175 | && (nSize(pGetCoeff(pp))>old_size) |
---|
| 176 | ) |
---|
| 177 | { |
---|
| 178 | //pSimpleContent(pp,2); |
---|
[6e0750] | 179 | p_Content(pp,currRing); |
---|
[5a66d0] | 180 | count=0; |
---|
| 181 | // old_size=nSize(pGetCoeff(pp)); |
---|
| 182 | } |
---|
| 183 | } |
---|
| 184 | done=TRUE; |
---|
| 185 | } |
---|
| 186 | else |
---|
| 187 | temp=temp->next; |
---|
| 188 | } |
---|
| 189 | |
---|
[6e0750] | 190 | if (done) p_Content(p->root,currRing); |
---|
[5a66d0] | 191 | //if (done) pSimpleContent(p->root,-1); |
---|
| 192 | pTest(p->root); |
---|
| 193 | } |
---|
| 194 | |
---|
| 195 | void NFL(Poly *p, TreeM *F) |
---|
| 196 | { |
---|
| 197 | Poly *f; |
---|
[6909cfb] | 198 | // int g1,f1,gg; |
---|
[5a66d0] | 199 | |
---|
| 200 | if ((f=is_div_(F,p->lead))==NULL) return; |
---|
| 201 | |
---|
| 202 | int pX=pow_(p->lead); |
---|
| 203 | int phX=pow_(p->history); |
---|
| 204 | |
---|
| 205 | if (pX!=phX) |
---|
| 206 | { |
---|
| 207 | int phF=pow_(f->history); |
---|
| 208 | if (pX >= (phX+phF)) |
---|
| 209 | { |
---|
| 210 | pDelete(&p->root); |
---|
| 211 | //p->root=NULL; |
---|
| 212 | return; |
---|
| 213 | } |
---|
| 214 | |
---|
| 215 | /* poly p2=pInit(); |
---|
| 216 | pLcm(p->history,f->history,p2); |
---|
| 217 | pSetm(p2); |
---|
| 218 | |
---|
| 219 | if (pLmCmp(p->root,p2) > 0) |
---|
| 220 | { |
---|
| 221 | pLmDelete(&p2); |
---|
| 222 | pDelete(&p->root); |
---|
| 223 | //p->root=NULL; |
---|
| 224 | return; |
---|
| 225 | } |
---|
| 226 | |
---|
| 227 | pLmDelete(&p2); |
---|
| 228 | */ |
---|
| 229 | /* for(int i=0, gg=0 ; i<currRing->N;i++) |
---|
| 230 | if ((g1=pGetExp(p->history,i+1)) > (f1=pGetExp(f->history,i+1))) |
---|
| 231 | gg+=g1; |
---|
| 232 | else gg+=f1; |
---|
| 233 | |
---|
| 234 | if (pX > gg) |
---|
| 235 | { |
---|
| 236 | pDelete(&p->root); |
---|
| 237 | //x->root=NULL; |
---|
| 238 | return; |
---|
| 239 | } |
---|
| 240 | */ |
---|
| 241 | int pF=pow_(f->lead); |
---|
| 242 | |
---|
| 243 | if ((pX == pF) && (pF == phF)) |
---|
| 244 | { |
---|
[256305] | 245 | pLmFree(&f->history); |
---|
| 246 | f->history=p_Copy_noCheck(p->history,currRing); /* cf of p->history is NULL */ |
---|
[5a66d0] | 247 | } |
---|
| 248 | } |
---|
| 249 | |
---|
| 250 | //if (TEST_OPT_PROT) { PrintS("R"); mflush(); } |
---|
[6909cfb] | 251 | int /*old_size, */count; |
---|
[5a66d0] | 252 | count=0; |
---|
| 253 | while(f && p->root) |
---|
| 254 | { |
---|
[ca4d0e6] | 255 | // PrintS("R"); |
---|
[5a66d0] | 256 | // if (TEST_OPT_PROT) { PrintS("R"); mflush(); } |
---|
| 257 | #if 0 |
---|
| 258 | old_size=nSize(pGetCoeff(p->root)); |
---|
| 259 | #endif |
---|
| 260 | if (ReducePolyLead(p,f) == 0) break; |
---|
| 261 | if (p->root!=NULL) |
---|
| 262 | { |
---|
| 263 | count++; |
---|
| 264 | #if 0 |
---|
| 265 | if ((count>4) && (3<nSize(pGetCoeff(p->root))) |
---|
| 266 | && (nSize(pGetCoeff(p->root))>old_size)) |
---|
| 267 | { |
---|
| 268 | pSimpleContent(p->root,old_size); |
---|
| 269 | count=0; |
---|
| 270 | } |
---|
| 271 | #else |
---|
[312083] | 272 | if (count>50) |
---|
[5a66d0] | 273 | { |
---|
| 274 | kBucketClear(p->root_b,&p->root,&p->root_l); |
---|
[fe66ba8] | 275 | p_SimpleContent(p->root,2,currRing); |
---|
[5a66d0] | 276 | kBucketInit(p->root_b,p->root,p->root_l); |
---|
| 277 | count=0; |
---|
[ca4d0e6] | 278 | //PrintS("."); |
---|
[5a66d0] | 279 | } |
---|
| 280 | #endif |
---|
| 281 | f=is_div_(F,p->root); |
---|
| 282 | } |
---|
| 283 | } |
---|
| 284 | #if 1 |
---|
| 285 | if (p->root_b!=NULL) |
---|
| 286 | { |
---|
| 287 | kBucketClear(p->root_b,&p->root,&p->root_l); |
---|
| 288 | kBucketDestroy(&p->root_b); |
---|
| 289 | p->root_b=NULL; |
---|
| 290 | } |
---|
| 291 | #endif |
---|
| 292 | |
---|
| 293 | if (!p->root) |
---|
| 294 | return; |
---|
| 295 | |
---|
| 296 | InitHistory(p); |
---|
| 297 | InitProl(p); |
---|
| 298 | InitLead(p); |
---|
| 299 | p->changed=1; |
---|
| 300 | |
---|
[6e0750] | 301 | p_Content(p->root,currRing); |
---|
[5a66d0] | 302 | //pSimpleContent(p->root,-1); |
---|
| 303 | pTest(p->root); |
---|
| 304 | } |
---|
| 305 | |
---|
[2e4ec14] | 306 | int ValidatePoly(Poly *x, TreeM */*F*/) |
---|
[5a66d0] | 307 | { |
---|
[6909cfb] | 308 | Poly /*f,*/*g; |
---|
| 309 | // int g1,f1; |
---|
[5a66d0] | 310 | |
---|
| 311 | if (x->root) return 1; |
---|
| 312 | |
---|
| 313 | g=is_present(T,x->history); //it's a prolongation - do we have a parent ? |
---|
| 314 | |
---|
| 315 | if (!g) return 0; //if not - kill him ! |
---|
| 316 | |
---|
| 317 | poly lmX=pDivide(x->lead,g->root); |
---|
| 318 | pGetCoeff(lmX)=nInit(1); |
---|
| 319 | |
---|
| 320 | /* if ((f=is_div_(F,lmX)) != NULL) |
---|
| 321 | { |
---|
| 322 | int pX=pow_(lmX); |
---|
| 323 | int phX=pow_(x->history); |
---|
| 324 | |
---|
| 325 | if (pX!=phX) |
---|
| 326 | { |
---|
| 327 | int phF=pow_(f->history); |
---|
| 328 | if (pX >= (phX+phF)) |
---|
| 329 | { |
---|
| 330 | pLmDelete(&lmX); |
---|
| 331 | //x->root=NULL; |
---|
| 332 | return 0; |
---|
| 333 | } |
---|
| 334 | |
---|
| 335 | for(int i=0, gg=0 ; i<currRing->N;i++) |
---|
| 336 | if ((g1=pGetExp(x->history,i+1)) > (f1=pGetExp(f->history,i+1))) |
---|
| 337 | gg+=g1; |
---|
| 338 | else |
---|
| 339 | gg+=f1; |
---|
| 340 | |
---|
| 341 | if (pX > gg) |
---|
| 342 | { |
---|
| 343 | pLmDelete(&lmX); |
---|
| 344 | return 0; |
---|
| 345 | } |
---|
| 346 | int pF=pow_(f->root); |
---|
| 347 | |
---|
| 348 | if ((pX == pF) && (pF == phF)) |
---|
| 349 | f->history=x->history; |
---|
| 350 | } |
---|
| 351 | } |
---|
| 352 | |
---|
| 353 | pLmDelete(&lmX); |
---|
| 354 | |
---|
| 355 | */ |
---|
| 356 | x->root=pCopy(g->root); |
---|
| 357 | x->root_l=g->root_l; |
---|
| 358 | |
---|
| 359 | x->root=pMult(x->root,lmX); |
---|
| 360 | |
---|
| 361 | pTest(x->root); |
---|
| 362 | |
---|
| 363 | x->prolonged=-1; |
---|
| 364 | |
---|
| 365 | return 1; |
---|
| 366 | } |
---|
| 367 | |
---|
| 368 | Poly *NewPoly(poly p) |
---|
| 369 | { |
---|
| 370 | Poly *beg=(Poly *)GCM(sizeof(Poly)); |
---|
| 371 | |
---|
| 372 | beg->root=p;//(p == NULL ? pInit() : p); |
---|
| 373 | beg->root_b=NULL; |
---|
| 374 | beg->root_l=0; |
---|
| 375 | beg->history=NULL;//pInit(); |
---|
| 376 | beg->lead=NULL; |
---|
| 377 | beg->mult=(char *)GCMA(sizeof(char)*2*offset); |
---|
| 378 | |
---|
| 379 | for (int i=0; i < currRing->N; i++) |
---|
| 380 | { |
---|
| 381 | ClearMult(beg,i); |
---|
| 382 | ClearProl(beg,i); |
---|
| 383 | }; |
---|
| 384 | |
---|
| 385 | beg->prolonged=-1; |
---|
| 386 | |
---|
| 387 | return beg; |
---|
| 388 | } |
---|
| 389 | |
---|
| 390 | void DestroyPoly(Poly *x) |
---|
| 391 | { |
---|
| 392 | pDelete(&x->root); |
---|
[256305] | 393 | pLmFree(&x->history); |
---|
[5a66d0] | 394 | if (x->lead) pDelete(&x->lead); |
---|
| 395 | GCF(x->mult); |
---|
| 396 | GCF(x); |
---|
| 397 | } |
---|
| 398 | |
---|
| 399 | void ControlProlong(Poly *x) |
---|
| 400 | { |
---|
| 401 | for (int i = 0; i< offset; i++) |
---|
| 402 | { |
---|
| 403 | (x->mult+offset)[i]&=~((x->mult)[i]); |
---|
| 404 | // if (!GetMult(x,i) && !GetProl(x,i)) |
---|
| 405 | // ProlVar(x,i); |
---|
| 406 | } |
---|
| 407 | } |
---|
| 408 | |
---|
| 409 | void InitHistory(Poly *p) |
---|
| 410 | { |
---|
[256305] | 411 | if (p->history) pLmFree(&p->history); |
---|
[5a66d0] | 412 | p->history=pLmInit(p->root); |
---|
| 413 | p->changed=0; |
---|
| 414 | } |
---|
| 415 | |
---|
| 416 | void InitLead(Poly *p) |
---|
| 417 | { |
---|
| 418 | if (p->lead) pLmDelete(&p->lead); |
---|
| 419 | p->lead=pLmInit(p->root); |
---|
| 420 | p->prolonged=-1; |
---|
| 421 | } |
---|
| 422 | |
---|
| 423 | void InitProl(Poly *p) |
---|
| 424 | { |
---|
| 425 | memset(p->mult+offset,0,sizeof(char)*offset); |
---|
| 426 | } |
---|
| 427 | |
---|
| 428 | int GetMult(Poly *x,int i) |
---|
| 429 | { |
---|
| 430 | return x->mult[i/8] & Mask[i%8]; |
---|
| 431 | } |
---|
| 432 | |
---|
| 433 | void SetMult(Poly *x,int i) |
---|
| 434 | { |
---|
| 435 | x->mult[i/8] |= Mask[i%8]; |
---|
| 436 | } |
---|
| 437 | |
---|
| 438 | void ClearMult(Poly *x,int i) |
---|
| 439 | { |
---|
| 440 | x->mult[i/8] &= ~Mask[i%8]; |
---|
| 441 | } |
---|
| 442 | |
---|
| 443 | int GetProl(Poly *x, int i) |
---|
| 444 | { |
---|
| 445 | return (x->mult+offset)[i/8] & Mask[i%8]; |
---|
| 446 | } |
---|
| 447 | |
---|
| 448 | void SetProl(Poly *x, int i) |
---|
| 449 | { |
---|
| 450 | (x->mult+offset)[i/8] |= Mask[i%8]; |
---|
| 451 | } |
---|
| 452 | |
---|
| 453 | void ClearProl(Poly *x, int i) |
---|
| 454 | { |
---|
| 455 | (x->mult+offset)[i/8] &= ~Mask[i%8]; |
---|
| 456 | } |
---|
| 457 | |
---|
| 458 | int LengthCompare(poly p1,poly p2) |
---|
| 459 | { |
---|
| 460 | do |
---|
| 461 | { |
---|
| 462 | if (p1 == NULL) return 1; |
---|
| 463 | if (p2 == NULL) return 0; |
---|
| 464 | pIter(p1); |
---|
| 465 | pIter(p2); |
---|
| 466 | }while(p1 && p2); |
---|
| 467 | return 1; |
---|
| 468 | } |
---|
| 469 | |
---|
| 470 | int ProlCompare(Poly *item1, Poly *item2) |
---|
| 471 | { |
---|
| 472 | switch(pLmCmp(item1->lead,item2->lead)) |
---|
| 473 | { |
---|
| 474 | case -1: |
---|
| 475 | return 1; |
---|
| 476 | |
---|
| 477 | case 1: |
---|
| 478 | return 0; |
---|
| 479 | |
---|
| 480 | default: |
---|
| 481 | if ((item1->root_l<=0)||(item2->root_l<=0)) |
---|
| 482 | return LengthCompare(item1->root,item2->root); |
---|
| 483 | return item1->root_l<=item2->root_l; |
---|
| 484 | } |
---|
| 485 | } |
---|
| 486 | |
---|
| 487 | void ProlVar(Poly *temp,int i) |
---|
| 488 | { |
---|
| 489 | Poly *Pr; |
---|
| 490 | |
---|
| 491 | if (!GetProl(temp,i) && !GetMult(temp,i)) |
---|
| 492 | { |
---|
| 493 | Pr=NewPoly(); |
---|
| 494 | SetProl(temp,i); |
---|
| 495 | |
---|
| 496 | Pr->prolonged=i; |
---|
| 497 | Pr->history=pLmInit(temp->history); |
---|
| 498 | Pr->lead=pLmInit(temp->lead); |
---|
| 499 | pIncrExp(Pr->lead,i+1); |
---|
| 500 | pSetm(Pr->lead); |
---|
| 501 | InitProl(temp); |
---|
| 502 | |
---|
| 503 | Pr->changed=0; |
---|
| 504 | // pTest(Pr->root); |
---|
| 505 | InsertInCount(Q,Pr); |
---|
| 506 | } |
---|
| 507 | } |
---|
| 508 | |
---|
| 509 | void DestroyListNode(ListNode *x) |
---|
| 510 | { |
---|
| 511 | DestroyPoly(x->info); |
---|
| 512 | GCF(x); |
---|
| 513 | } |
---|
| 514 | |
---|
| 515 | ListNode* CreateListNode(Poly *x) |
---|
| 516 | { |
---|
| 517 | ListNode* ret=(ListNode *)GCM(sizeof(ListNode)); |
---|
| 518 | ret->info=x; |
---|
| 519 | ret->next=NULL; |
---|
| 520 | return ret; |
---|
| 521 | } |
---|
| 522 | |
---|
| 523 | |
---|
| 524 | Poly *FindMinList(jList *L) |
---|
| 525 | { |
---|
| 526 | LI min=&(L->root); |
---|
| 527 | LI l; |
---|
| 528 | LCI xl; |
---|
| 529 | Poly *x; |
---|
| 530 | |
---|
| 531 | if (degree_compatible) |
---|
| 532 | { |
---|
| 533 | while ((*min) && ((*min)->info->root == NULL)) |
---|
| 534 | min=&((*min)->next); |
---|
| 535 | } |
---|
| 536 | |
---|
| 537 | if (!(*min)) return NULL; |
---|
| 538 | |
---|
| 539 | l=&((*min)->next); |
---|
| 540 | |
---|
| 541 | while (*l) |
---|
| 542 | { |
---|
| 543 | if ((*l)->info->root != NULL) |
---|
| 544 | { |
---|
| 545 | if (ProlCompare((*l)->info,(*min)->info)) |
---|
| 546 | min=l; |
---|
| 547 | } |
---|
| 548 | |
---|
| 549 | l=&((*l)->next); |
---|
| 550 | } |
---|
| 551 | x=(*min)->info; |
---|
| 552 | xl=*min; |
---|
| 553 | *min=(*min)->next; |
---|
| 554 | GCF(xl); |
---|
| 555 | |
---|
| 556 | return x; |
---|
| 557 | } |
---|
| 558 | |
---|
| 559 | void InsertInList(jList *x,Poly *y) |
---|
| 560 | { |
---|
| 561 | ListNode *ins; |
---|
| 562 | LI ix=&(x->root); |
---|
| 563 | |
---|
| 564 | while (*ix) |
---|
| 565 | { |
---|
| 566 | if (pLmCmp(y->lead,(*ix)->info->lead) == -1) |
---|
| 567 | ix=(ListNode **)&((*ix)->next); |
---|
| 568 | else |
---|
| 569 | break; |
---|
| 570 | } |
---|
| 571 | |
---|
| 572 | ins=CreateListNode(y); |
---|
| 573 | ins->next=(ListNode *)(*ix); |
---|
| 574 | *ix=ins; |
---|
| 575 | return; |
---|
| 576 | } |
---|
| 577 | |
---|
| 578 | void InsertInCount(jList *x,Poly *y) |
---|
| 579 | { |
---|
| 580 | ListNode *ins; |
---|
| 581 | LI ix=&(x->root); |
---|
| 582 | |
---|
| 583 | ins=CreateListNode(y); |
---|
| 584 | ins->next=(ListNode *)(*ix); |
---|
| 585 | *ix=ins; |
---|
| 586 | return; |
---|
| 587 | } |
---|
| 588 | |
---|
| 589 | int ListGreatMoveOrder(jList *A,jList *B,poly x) |
---|
| 590 | { |
---|
| 591 | LCI y=A->root; |
---|
| 592 | |
---|
| 593 | if (!y || pLmCmp(y->info->lead,x) < 0) return 0; |
---|
| 594 | |
---|
| 595 | while(y && pLmCmp(y->info->lead,x) >= 0) |
---|
| 596 | { |
---|
| 597 | InsertInCount(B,y->info); |
---|
| 598 | A->root=y->next; |
---|
| 599 | GCF(y); |
---|
| 600 | y=A->root; |
---|
| 601 | } |
---|
| 602 | |
---|
| 603 | return 1; |
---|
| 604 | } |
---|
| 605 | |
---|
| 606 | int ListGreatMoveDegree(jList *A,jList *B,poly x) |
---|
| 607 | { |
---|
| 608 | LCI y=A->root; |
---|
| 609 | int pow_x=pow_(x); |
---|
| 610 | |
---|
| 611 | if (!y || pow_(y->info->lead) <= pow_x) return 0; |
---|
| 612 | |
---|
| 613 | while(y && pow_(y->info->lead) > pow_x) |
---|
| 614 | { |
---|
| 615 | InsertInCount(B,y->info); |
---|
| 616 | A->root=y->next; |
---|
| 617 | GCF(y); |
---|
| 618 | y=A->root; |
---|
| 619 | } |
---|
| 620 | |
---|
| 621 | return 1; |
---|
| 622 | } |
---|
| 623 | |
---|
| 624 | int CountList(jList *Q) |
---|
| 625 | { |
---|
| 626 | int i=0; |
---|
| 627 | LCI y=Q->root; |
---|
| 628 | |
---|
| 629 | while(y) |
---|
| 630 | { |
---|
| 631 | i++; |
---|
| 632 | y=y->next; |
---|
| 633 | } |
---|
| 634 | |
---|
| 635 | return i; |
---|
| 636 | } |
---|
| 637 | |
---|
| 638 | void NFListQ() |
---|
| 639 | { |
---|
| 640 | LCI ll; |
---|
| 641 | int p,p1; |
---|
| 642 | LI l; |
---|
| 643 | |
---|
| 644 | do |
---|
| 645 | { |
---|
| 646 | if (!Q->root) break; |
---|
| 647 | |
---|
| 648 | ll=Q->root; |
---|
| 649 | |
---|
| 650 | p=pow_(Q->root->info->lead); |
---|
| 651 | |
---|
| 652 | while (ll) |
---|
| 653 | { |
---|
| 654 | int ploc=pow_(ll->info->lead); |
---|
| 655 | if (ploc < p) p=ploc; |
---|
| 656 | ll=ll->next; |
---|
| 657 | } |
---|
| 658 | |
---|
| 659 | p1=1; |
---|
| 660 | |
---|
| 661 | l=&(Q->root); |
---|
| 662 | |
---|
| 663 | while (*l) |
---|
| 664 | { |
---|
[ca4d0e6] | 665 | // PrintS("*"); |
---|
[5a66d0] | 666 | int ploc=pow_((*l)->info->lead); |
---|
| 667 | |
---|
| 668 | if (ploc == p) |
---|
| 669 | { |
---|
| 670 | if (!ValidatePoly((*l)->info,G)) |
---|
| 671 | { |
---|
| 672 | ll=(*l); |
---|
| 673 | *l=(*l)->next; |
---|
| 674 | DestroyListNode(ll); |
---|
| 675 | continue; |
---|
| 676 | }; |
---|
| 677 | |
---|
| 678 | (*l)->info->changed=0; |
---|
[ca4d0e6] | 679 | // PrintS("!"); |
---|
[5a66d0] | 680 | NFL((*l)->info,G); |
---|
[ca4d0e6] | 681 | // PrintS("$"); |
---|
[5a66d0] | 682 | if (!(*l)->info->root) |
---|
| 683 | { |
---|
| 684 | ll=(*l); |
---|
| 685 | *l=(*l)->next; |
---|
| 686 | DestroyListNode(ll); |
---|
| 687 | continue; |
---|
| 688 | }; |
---|
| 689 | p1=0; |
---|
| 690 | } |
---|
| 691 | |
---|
| 692 | l=&((*l)->next); |
---|
| 693 | } |
---|
| 694 | }while(p1); |
---|
[ca4d0e6] | 695 | // PrintLn(); |
---|
[5a66d0] | 696 | } |
---|
| 697 | |
---|
| 698 | |
---|
| 699 | void ForEachPNF(jList *x,int i) |
---|
| 700 | { |
---|
| 701 | LCI y=x->root; |
---|
| 702 | |
---|
| 703 | while(y) |
---|
| 704 | { |
---|
| 705 | if (pow_(y->info->root) == i) PNF(y->info,G); |
---|
| 706 | y=y->next; |
---|
| 707 | } |
---|
| 708 | } |
---|
| 709 | |
---|
| 710 | void ForEachControlProlong(jList *x) |
---|
| 711 | { |
---|
| 712 | LCI y=x->root; |
---|
| 713 | |
---|
| 714 | while(y) |
---|
| 715 | { |
---|
| 716 | ControlProlong(y->info); |
---|
| 717 | y=y->next; |
---|
| 718 | } |
---|
| 719 | } |
---|
| 720 | |
---|
| 721 | void DestroyList(jList *x) |
---|
| 722 | { |
---|
| 723 | LCI y=x->root,z; |
---|
| 724 | |
---|
| 725 | while(y) |
---|
| 726 | { |
---|
| 727 | z=y->next; |
---|
| 728 | DestroyPoly(y->info); |
---|
| 729 | GCF(y); |
---|
| 730 | y=z; |
---|
| 731 | } |
---|
| 732 | |
---|
| 733 | GCF(x); |
---|
| 734 | } |
---|
| 735 | |
---|
| 736 | Poly* is_present(jList *F,poly x) |
---|
| 737 | { |
---|
| 738 | LCI iF=F->root; |
---|
| 739 | while(iF) |
---|
| 740 | if (pLmCmp(iF->info->root,x) == 0) |
---|
| 741 | return iF->info; |
---|
| 742 | else iF=iF->next; |
---|
| 743 | |
---|
| 744 | return NULL; |
---|
| 745 | } |
---|
| 746 | |
---|
| 747 | int GB_length() |
---|
| 748 | { |
---|
| 749 | LCI iT=T->root; |
---|
| 750 | int l=0; |
---|
| 751 | |
---|
| 752 | while(iT) |
---|
| 753 | { |
---|
| 754 | if (pow_(iT->info->lead) == pow_(iT->info->history)) |
---|
| 755 | ++l; |
---|
| 756 | iT=iT->next; |
---|
| 757 | } |
---|
| 758 | |
---|
| 759 | return l; |
---|
| 760 | } |
---|
| 761 | |
---|
| 762 | static Poly *temp_l; |
---|
| 763 | |
---|
| 764 | NodeM* create() |
---|
| 765 | { |
---|
| 766 | NodeM *y; |
---|
| 767 | |
---|
| 768 | if (FreeNodes == NULL) |
---|
| 769 | { |
---|
| 770 | y=(NodeM *)GCM(sizeof(NodeM)); |
---|
| 771 | } |
---|
| 772 | else |
---|
| 773 | { |
---|
| 774 | y=FreeNodes; |
---|
| 775 | FreeNodes=FreeNodes->left; |
---|
| 776 | } |
---|
| 777 | |
---|
| 778 | y->left=y->right=NULL; |
---|
| 779 | y->ended=NULL; |
---|
| 780 | return y; |
---|
| 781 | } |
---|
| 782 | |
---|
| 783 | void DestroyFreeNodes() |
---|
| 784 | { |
---|
| 785 | NodeM *y; |
---|
| 786 | |
---|
| 787 | while((y=FreeNodes)!=NULL) |
---|
| 788 | { |
---|
| 789 | FreeNodes=FreeNodes->left; |
---|
| 790 | GCF(y); |
---|
| 791 | } |
---|
| 792 | } |
---|
| 793 | |
---|
[654726] | 794 | #if 0 |
---|
[5a66d0] | 795 | static void go_right(NodeM *current,poly_function disp) |
---|
| 796 | { |
---|
| 797 | if (current) |
---|
| 798 | { |
---|
| 799 | go_right(current->left,disp); |
---|
| 800 | if (current->ended) disp(current->ended); |
---|
| 801 | go_right(current->right,disp); |
---|
| 802 | } |
---|
| 803 | } |
---|
| 804 | |
---|
| 805 | void ForEach(TreeM *t,poly_function disp) |
---|
| 806 | { |
---|
| 807 | go_right(t->root,disp); |
---|
| 808 | } |
---|
[312083] | 809 | #endif |
---|
[5a66d0] | 810 | |
---|
| 811 | void DestroyTree(NodeM *G) |
---|
| 812 | { |
---|
| 813 | if (G) |
---|
| 814 | { |
---|
| 815 | DestroyTree(G->left); |
---|
| 816 | DestroyTree(G->right); |
---|
| 817 | G->left=FreeNodes; |
---|
| 818 | FreeNodes=G; |
---|
| 819 | } |
---|
| 820 | } |
---|
| 821 | |
---|
| 822 | void Define(TreeM **G) |
---|
| 823 | { |
---|
| 824 | *G=(TreeM *)GCM(sizeof(TreeM)); |
---|
| 825 | (*G)->root=create(); |
---|
| 826 | } |
---|
| 827 | |
---|
| 828 | int sp_div(poly m1,poly m2,int from) |
---|
| 829 | { |
---|
| 830 | |
---|
| 831 | if (pow_(m2) == 0 && pow_(m1)) return 0; |
---|
| 832 | |
---|
| 833 | for(int k=from; k < currRing->N; k++) |
---|
| 834 | if (pGetExp(m1,k+1) < pGetExp(m2,k+1)) return 0; |
---|
| 835 | |
---|
| 836 | return 1; |
---|
| 837 | } |
---|
| 838 | |
---|
| 839 | void div_l(poly item, NodeM *x,int from) |
---|
| 840 | { |
---|
| 841 | if (x && !temp_l) |
---|
| 842 | { |
---|
| 843 | div_l(item,x->left,from); |
---|
| 844 | if ((x->ended) && sp_div(item,x->ended->root,from)) |
---|
| 845 | { |
---|
| 846 | temp_l=x->ended; |
---|
| 847 | return; |
---|
| 848 | }; |
---|
| 849 | div_l(item,x->right,from); |
---|
| 850 | } |
---|
| 851 | } |
---|
| 852 | |
---|
| 853 | Poly* is_div_upper(poly item, NodeM *x,int from) |
---|
| 854 | { |
---|
| 855 | temp_l=NULL; |
---|
| 856 | div_l(item,x,from); |
---|
| 857 | return temp_l; |
---|
| 858 | } |
---|
| 859 | |
---|
| 860 | Poly* is_div_(TreeM *tree, poly item) |
---|
| 861 | { |
---|
| 862 | int power_tmp,i,i_con=currRing->N-1; |
---|
| 863 | NodeM *curr=tree->root; |
---|
| 864 | |
---|
| 865 | if (!curr) return NULL; |
---|
| 866 | if (pow_(item) == 0) return NULL; |
---|
| 867 | |
---|
| 868 | for ( ; i_con>=0 && !pGetExp(item,i_con+1) ; i_con--) |
---|
| 869 | ; |
---|
| 870 | |
---|
| 871 | for (i=0; i <= i_con ; i++) |
---|
| 872 | { |
---|
| 873 | power_tmp=pGetExp(item,i+1); |
---|
| 874 | |
---|
| 875 | while (power_tmp) |
---|
| 876 | { |
---|
| 877 | if (curr->ended) return curr->ended; |
---|
| 878 | |
---|
| 879 | if (!curr->left) |
---|
| 880 | { |
---|
| 881 | if (curr->right) |
---|
| 882 | return is_div_upper(item,curr->right,i); //?????? |
---|
| 883 | return NULL; |
---|
| 884 | } |
---|
| 885 | |
---|
| 886 | curr=curr->left; |
---|
| 887 | power_tmp--; |
---|
| 888 | } |
---|
| 889 | |
---|
| 890 | if (curr->ended) return curr->ended; |
---|
| 891 | |
---|
| 892 | if (!curr->right) return NULL; |
---|
| 893 | |
---|
| 894 | curr=curr->right; |
---|
| 895 | } |
---|
| 896 | |
---|
| 897 | if (curr->ended) return curr->ended; |
---|
| 898 | else return NULL; |
---|
| 899 | } |
---|
| 900 | |
---|
| 901 | static void ClearMultiplicative(NodeM *xx,int i) |
---|
| 902 | { |
---|
| 903 | if (!xx) return; |
---|
| 904 | |
---|
| 905 | while (xx->left) |
---|
| 906 | { |
---|
| 907 | ClearMultiplicative(xx->right, i); |
---|
| 908 | xx = xx->left; |
---|
| 909 | } |
---|
| 910 | if ((xx->ended) && (GetMult(xx->ended,i))) |
---|
| 911 | { |
---|
| 912 | ClearMult(xx->ended,i); |
---|
| 913 | ProlVar(xx->ended,i); |
---|
| 914 | } |
---|
| 915 | else |
---|
| 916 | ClearMultiplicative(xx->right,i); |
---|
| 917 | } |
---|
| 918 | //====================================================== |
---|
| 919 | void insert_(TreeM **tree, Poly *item) |
---|
| 920 | { |
---|
| 921 | int power_tmp,i,i_con=currRing->N-1; |
---|
| 922 | NodeM *curr=(*tree)->root; |
---|
| 923 | |
---|
| 924 | for ( ; (i_con>=0) && !pGetExp(item->root,i_con+1) ; i_con--) |
---|
| 925 | SetMult(item,i_con); |
---|
| 926 | |
---|
| 927 | for (i = 0; i<= i_con; i++) |
---|
| 928 | //<= |
---|
| 929 | { |
---|
| 930 | power_tmp=pGetExp(item->root,i+1); |
---|
| 931 | |
---|
| 932 | ClearMult(item,i); |
---|
| 933 | |
---|
| 934 | while (power_tmp) |
---|
| 935 | { |
---|
| 936 | if (!curr->left) |
---|
| 937 | { |
---|
| 938 | SetMult(item,i); |
---|
| 939 | ClearMultiplicative(curr->right,i); |
---|
| 940 | curr->left=create(); |
---|
| 941 | }; |
---|
| 942 | curr=curr->left; |
---|
| 943 | power_tmp--; |
---|
| 944 | }; |
---|
| 945 | |
---|
| 946 | if (i<i_con) |
---|
| 947 | { |
---|
| 948 | if (!curr->left) SetMult(item,i); |
---|
| 949 | if (!curr->right) curr->right=create(); |
---|
| 950 | curr=curr->right; |
---|
| 951 | |
---|
| 952 | ProlVar(item,i); |
---|
| 953 | } |
---|
| 954 | } |
---|
| 955 | |
---|
| 956 | curr->ended=item; |
---|
| 957 | } |
---|
| 958 | |
---|
| 959 | void Initialization(char *Ord) |
---|
| 960 | { |
---|
| 961 | offset=(currRing->N % 8 == 0) ? (currRing->N/8)*8 : (currRing->N/8+1)*8; |
---|
| 962 | if (strstr(Ord,"dp\0") || strstr(Ord,"Dp\0")) |
---|
| 963 | { |
---|
| 964 | degree_compatible=1; |
---|
[31f1850] | 965 | jDeg=p_Deg; |
---|
[5a66d0] | 966 | ListGreatMove=ListGreatMoveDegree; |
---|
| 967 | } |
---|
| 968 | else |
---|
| 969 | { |
---|
| 970 | degree_compatible=0; |
---|
[99bdcf] | 971 | jDeg=p_Totaldegree; |
---|
[5a66d0] | 972 | ListGreatMove=ListGreatMoveOrder; |
---|
| 973 | } |
---|
| 974 | |
---|
| 975 | Define(&G); |
---|
[e8a9f3] | 976 | } |
---|
[5a66d0] | 977 | |
---|
[6909cfb] | 978 | static Poly *h/*,*f*/; |
---|
[5a66d0] | 979 | |
---|
[312083] | 980 | #if 0 |
---|
[5a66d0] | 981 | void insert_in_G(Poly *x) |
---|
| 982 | { |
---|
| 983 | insert_(&G,x); |
---|
| 984 | } |
---|
[312083] | 985 | #endif |
---|
[5a66d0] | 986 | |
---|
| 987 | void T2G(); |
---|
| 988 | |
---|
[312083] | 989 | #if 0 |
---|
[5a66d0] | 990 | void Q2TG() |
---|
| 991 | { |
---|
| 992 | LCI t; |
---|
| 993 | Poly *x; |
---|
| 994 | |
---|
| 995 | while (Q->root) |
---|
| 996 | { |
---|
| 997 | t=Q->root; |
---|
| 998 | x=t->info; |
---|
| 999 | insert_(&G,x); |
---|
| 1000 | InsertInList(T,x); |
---|
| 1001 | Q->root=t->next; |
---|
| 1002 | GCF(t); |
---|
| 1003 | } |
---|
| 1004 | } |
---|
[312083] | 1005 | #endif |
---|
[5a66d0] | 1006 | |
---|
[eb72ba1] | 1007 | int ComputeBasis(jList *_lT,jList *_lQ) |
---|
[5a66d0] | 1008 | { |
---|
[6909cfb] | 1009 | // int gb_l,i,ret_value=1; |
---|
[5a66d0] | 1010 | |
---|
[eb72ba1] | 1011 | T=_lT; Q=_lQ; |
---|
[5a66d0] | 1012 | |
---|
| 1013 | // Debug(); |
---|
| 1014 | |
---|
| 1015 | while((h=FindMinList(Q))!=NULL) |
---|
| 1016 | { |
---|
[ca4d0e6] | 1017 | // PrintS("New element\n"); |
---|
[5a66d0] | 1018 | // Debug(); |
---|
| 1019 | |
---|
| 1020 | if (!degree_compatible) |
---|
| 1021 | { |
---|
| 1022 | if (!ValidatePoly(h,G)) |
---|
| 1023 | { |
---|
| 1024 | DestroyPoly(h); |
---|
| 1025 | continue; |
---|
| 1026 | } |
---|
| 1027 | |
---|
| 1028 | h->changed=0; |
---|
| 1029 | |
---|
| 1030 | NFL(h,G); |
---|
| 1031 | |
---|
| 1032 | if (!h->root) |
---|
| 1033 | { |
---|
| 1034 | DestroyPoly(h); |
---|
| 1035 | continue; |
---|
| 1036 | } |
---|
| 1037 | } |
---|
| 1038 | |
---|
| 1039 | if (h->root) |
---|
| 1040 | { |
---|
| 1041 | if (pIsConstant(h->root)) |
---|
| 1042 | { |
---|
| 1043 | WarnS("Constant in basis\n"); |
---|
| 1044 | return 0; |
---|
| 1045 | } |
---|
| 1046 | |
---|
| 1047 | if (h->changed && ListGreatMove(T,Q,h->root)) |
---|
| 1048 | { |
---|
[ca4d0e6] | 1049 | // PrintS("<-\n"); |
---|
[5a66d0] | 1050 | DestroyTree(G->root); |
---|
| 1051 | G->root=create(); |
---|
| 1052 | T2G(); |
---|
| 1053 | } |
---|
| 1054 | } |
---|
| 1055 | |
---|
[ca4d0e6] | 1056 | // PrintS("PNF\n"); |
---|
[5a66d0] | 1057 | PNF(h,G); |
---|
| 1058 | // Print("{%d}\n",pow_(h->root)); |
---|
| 1059 | insert_(&G,h); |
---|
| 1060 | InsertInList(T,h); |
---|
| 1061 | |
---|
[ca4d0e6] | 1062 | // PrintS("For each PNF\n"); |
---|
[5a66d0] | 1063 | if (degree_compatible) |
---|
| 1064 | ForEachPNF(T,pow_(h->root)); |
---|
| 1065 | |
---|
[ca4d0e6] | 1066 | // PrintS("Control of prolongations\n"); |
---|
[5a66d0] | 1067 | if (h->changed) |
---|
| 1068 | ForEachControlProlong(T); |
---|
| 1069 | else |
---|
| 1070 | ControlProlong(h); |
---|
| 1071 | |
---|
| 1072 | // Debug(); |
---|
| 1073 | |
---|
[ca4d0e6] | 1074 | // PrintS("NFListQ\n"); |
---|
[5a66d0] | 1075 | if (degree_compatible) |
---|
| 1076 | NFListQ(); |
---|
| 1077 | //Debug(); |
---|
| 1078 | } |
---|
| 1079 | |
---|
| 1080 | // gb_l=GB_length(); |
---|
| 1081 | |
---|
| 1082 | Print("Length of Janet basis: %d\n",CountList(T)); |
---|
| 1083 | // Print("Length of Groebner basis: %d\n",gb_l); |
---|
| 1084 | |
---|
| 1085 | DestroyTree(G->root); |
---|
| 1086 | GCF(G); |
---|
| 1087 | DestroyFreeNodes(); |
---|
| 1088 | |
---|
| 1089 | return 1; |
---|
| 1090 | } |
---|
| 1091 | |
---|
| 1092 | void T2G() |
---|
| 1093 | { |
---|
| 1094 | LCI i=T->root; |
---|
| 1095 | while (i) |
---|
| 1096 | { |
---|
| 1097 | insert_(&G,i->info); |
---|
| 1098 | i=i->next; |
---|
| 1099 | } |
---|
| 1100 | } |
---|