[BACK]Return to ecart.c CVS log [TXT][DIR] Up to [local] / OpenXM / src / kan96xx / Kan

Annotation of OpenXM/src/kan96xx/Kan/ecart.c, Revision 1.19

1.19    ! takayama    1: /* $OpenXM: OpenXM/src/kan96xx/Kan/ecart.c,v 1.18 2003/09/12 02:52:50 takayama Exp $ */
1.1       takayama    2: #include <stdio.h>
                      3: #include "datatype.h"
                      4: #include "extern2.h"
                      5: #include "gradedset.h"
                      6:
                      7: #define outofmemory(a) if (a == NULL) {fprintf(stderr,"ecart.c: out of memory.\n"); exit(10);}
                      8: /* Local structures */
                      9: struct ecartReducer {
                     10:   int ell; /* s^\ell */
                     11:   int first; /* first =1 ==> gset else gg */
                     12:   int grade;  int gseti;  /* if first==1,  gradedPolySet */
                     13:   int ggi;                /* if first==0   ecartPoly [] */
                     14: };
                     15: struct ecartPolyArray {
                     16:   int size;
                     17:   int limit;
                     18:   POLY *pa;
1.5       takayama   19:   POLY *cf;
                     20:   POLY *syz;
1.1       takayama   21: };
                     22:
                     23: static struct ecartReducer ecartFindReducer(POLY r,struct gradedPolySet *gset,struct ecartPolyArray *epa);
1.8       takayama   24: static struct ecartReducer ecartFindReducer_mod(POLY r,struct gradedPolySet *gset,struct ecartPolyArray *epa);
1.1       takayama   25: static int ecartCheckPoly(POLY f);  /* check if it does not contain s-variables */
                     26: static int ecartCheckEnv();         /* check if the environment is OK for ecart div*/
1.5       takayama   27: static struct ecartPolyArray *ecartPutPolyInG(POLY g,struct ecartPolyArray *eparray,POLY cf, POLY syz);
1.1       takayama   28: static int ecartGetEll(POLY r,POLY g);
1.5       takayama   29: static POLY ecartDivideSv(POLY r,int *d);
                     30: /* No automatic homogenization and s is used as a standart var. */
                     31: static POLY reduction_ecart0(POLY r,struct gradedPolySet *gset,
                     32:                              int needSyz, struct syz0 *syzp);
                     33: /* Automatic homogenization and s->1 */
                     34: static POLY reduction_ecart1(POLY r,struct gradedPolySet *gset,
                     35:                              int needSyz, struct syz0 *syzp);
1.8       takayama   36: static POLY reduction_ecart1_mod(POLY r,struct gradedPolySet *gset);
1.5       takayama   37: static POLY  ecartCheckSyz0(POLY cf,POLY r_0,POLY syz,
                     38:                             struct gradedPolySet *gg,POLY r);
1.16      takayama   39: static void  ecartCheckSyz0_printinfo(POLY cf,POLY r_0,POLY syz,
                     40:                             struct gradedPolySet *gg,POLY r);
1.1       takayama   41:
1.8       takayama   42: extern int DebugReductionRed;
                     43: extern int TraceLift;
                     44: struct ring *TraceLift_ringmod;
1.9       takayama   45: extern DoCancel;
1.6       takayama   46: int DebugReductionEcart = 0;
1.11      takayama   47: extern DebugContentReduction;
1.19    ! takayama   48: extern int Sugar;
1.1       takayama   49:
                     50: /* This is used for goHomogenization */
                     51: extern int DegreeShifto_size;
                     52: extern int *DegreeShifto_vec;
1.19    ! takayama   53: int Ecart_sugarGrade;
1.1       takayama   54:
1.3       takayama   55: /* It is used reduction_ecart() and ecartFindReducer()
                     56:    to determine if we homogenize in this function */
                     57: extern int EcartAutomaticHomogenization;
                     58:
1.1       takayama   59: #define LARGE 0x7fffffff
                     60:
                     61:
1.5       takayama   62: static POLY ecartDivideSv(POLY r,int *d) {
1.1       takayama   63:   POLY f;
                     64:   int k;
1.5       takayama   65:   *d = 0;
1.1       takayama   66:   if (r == POLYNULL) return r;
                     67:   f = r; k = LARGE;
                     68:   while (r != POLYNULL) {
                     69:     if (r->m->e[0].x < k) {
                     70:       k = r->m->e[0].x;
                     71:     }
                     72:     r = r->next;
                     73:   }
1.16      takayama   74:
                     75:   if (k > 0) {
                     76:     *d = k;
                     77:        return ppMult(cxx(1,0,-k,f->m->ringp),f);
                     78:   }else{
                     79:        return f;
                     80:   }
                     81:
                     82:   /* Do not do the below. It caused a bug. cf. misc-2003/07/ecart/b4.sm1 test2.
                     83:      Note. 2003.8.26
                     84:    */
                     85:   /*
1.1       takayama   86:   if (k > 0) {
1.5       takayama   87:     *d = k;
1.1       takayama   88:     f = r;
                     89:     while (r != POLYNULL) {
                     90:       r->m->e[0].x -= k;
                     91:       r = r->next;
                     92:     }
                     93:   }
                     94:   return f;
1.16      takayama   95:   */
1.1       takayama   96: }
                     97:
                     98: static int ecartGetEll(POLY f,POLY g) {
                     99:   int n,i,p;
                    100:   MONOMIAL tf;
                    101:   MONOMIAL tg;
                    102:
                    103:   if (f ISZERO) return(-1);
                    104:   if (g ISZERO) return(-1);
                    105:
                    106:   checkRingIsR(f,g);
                    107:
                    108:   if (!isSameComponent_x(f,g)) return(-1);
                    109:   tf = f->m; tg = g->m; n = tf->ringp->n;
                    110:   for (i=1; i<n; i++) {
                    111:     if (tf->e[i].x < tg->e[i].x) return(-1);
                    112:     if (tf->e[i].D < tg->e[i].D) return(-1);
                    113:   }
                    114:   if (tf->e[0].D < tg->e[0].D) return(-1);  /*  h  */
1.2       takayama  115:   p = tf->e[0].x - tg->e[0].x;  /* H,  s */
1.1       takayama  116:   if (p >=0 ) return 0;
                    117:   else return(-p);
                    118: }
                    119:
                    120:
                    121: #define EP_SIZE 10
1.5       takayama  122: static struct ecartPolyArray *ecartPutPolyInG(POLY g,struct ecartPolyArray *eparray,POLY cf,POLY syz)
1.1       takayama  123: {
                    124:   struct ecartPolyArray *a;
                    125:   POLY *ep;
                    126:   int i;
                    127:   if (eparray == (struct ecartPolyArray *)NULL) {
                    128:     a = (struct ecartPolyArray *) sGC_malloc(sizeof(struct ecartPolyArray));
                    129:     outofmemory(a);
                    130:     ep = (POLY *) sGC_malloc(sizeof(POLY)*EP_SIZE);
                    131:     outofmemory(ep);
1.5       takayama  132:     a->cf = (POLY *) sGC_malloc(sizeof(POLY)*EP_SIZE);
                    133:     outofmemory(a->cf);
                    134:     a->syz = (POLY *) sGC_malloc(sizeof(POLY)*EP_SIZE);
                    135:     outofmemory(a->syz);
1.1       takayama  136:     a->limit = EP_SIZE;
                    137:     a->size = 0;
                    138:     a->pa = ep;
                    139:     eparray = a;
                    140:   }
                    141:   if (eparray->size >= eparray->limit) {
                    142:     a = (struct ecartPolyArray *) sGC_malloc(sizeof(struct ecartPolyArray));
                    143:     outofmemory(a);
                    144:     ep = (POLY *) sGC_malloc(sizeof(POLY)*((eparray->limit)*2));
                    145:     outofmemory(ep);
1.5       takayama  146:     a->cf = (POLY *) sGC_malloc(sizeof(POLY)*((eparray->limit)*2));
                    147:     outofmemory(a->cf);
                    148:     a->syz = (POLY *) sGC_malloc(sizeof(POLY)*((eparray->limit)*2));
                    149:     outofmemory(a->syz);
1.1       takayama  150:     a->limit = (eparray->limit)*2;
                    151:     a->size = eparray->size;
                    152:     a->pa = ep;
                    153:     for (i=0; i<eparray->size; i++) {
                    154:       (a->pa)[i] = (eparray->pa)[i];
1.5       takayama  155:       (a->cf)[i] = (eparray->cf)[i];
                    156:       (a->syz)[i] = (eparray->syz)[i];
1.1       takayama  157:     }
                    158:     eparray  = a;
                    159:   }
                    160:   i = eparray->size;
                    161:   (eparray->pa)[i] = g;
1.5       takayama  162:   (eparray->cf)[i] = cf;
                    163:   (eparray->syz)[i] = syz;
1.1       takayama  164:   (eparray->size)++;
                    165:   return eparray;
                    166: }
                    167:
                    168: static struct ecartReducer ecartFindReducer(POLY r,struct gradedPolySet *gset,
                    169:                                             struct ecartPolyArray *epa)
                    170: {
                    171:   int grd;
                    172:   struct polySet *set;
                    173:   int minGrade = 0;
                    174:   int minGseti = 0;
                    175:   int minGgi   = 0;
                    176:   int ell1 = LARGE;
                    177:   int ell2 = LARGE;
                    178:   int ell;
                    179:   int i;
                    180:   struct ecartReducer er;
                    181:   /* Try to find a reducer in gset; */
                    182:   grd = 0;
                    183:   while (grd < gset->maxGrade) {
                    184:     set = gset->polys[grd];
                    185:     for (i=0; i<set->size; i++) {
1.2       takayama  186:       if (set->gh[i] == POLYNULL) {
                    187:         /* goHomogenize set->gh[i] */
1.4       takayama  188:           if (EcartAutomaticHomogenization) {
                    189:               set->gh[i] = goHomogenize11(set->g[i],DegreeShifto_vec,DegreeShifto_size,-1,1);
                    190:           }else{
                    191:               set->gh[i] = set->g[i];
                    192:           }
1.2       takayama  193:       }
                    194:       ell = ecartGetEll(r,set->gh[i]);
1.1       takayama  195:       if ((ell>=0) && (ell < ell1)) {
                    196:         ell1 = ell;
                    197:         minGrade = grd; minGseti=i;
                    198:       }
                    199:     }
                    200:     grd++;
                    201:   }
                    202:   if (epa != NULL) {
                    203:     /* Try to find in the second group. */
                    204:     for (i=0; i< epa->size; i++) {
                    205:       ell = ecartGetEll(r,(epa->pa)[i]);
                    206:       if ((ell>=0) && (ell < ell2)) {
                    207:         ell2 = ell;
                    208:         minGgi = i;
                    209:       }
                    210:     }
                    211:   }
                    212:
1.18      takayama  213:   if ((DebugReductionRed&1) || (DebugReductionEcart&1)) {
1.1       takayama  214:     printf("ecartFindReducer(): ell1=%d, ell2=%d, minGrade=%d, minGseti=%d, minGgi=%d\n",ell1,ell2,minGrade,minGseti,minGgi);
                    215:   }
1.19    ! takayama  216:   if (Sugar) {  /* experimental */
        !           217:        if (ell1 <= ell2) {
        !           218:          if (ell1 == LARGE) {
        !           219:                er.ell = -1;
        !           220:                return er;
        !           221:          }else{
        !           222:                int new_s;
        !           223:                er.ell = ell1;
        !           224:                er.first = 1;
        !           225:                er.grade = minGrade;
        !           226:                er.gseti = minGseti;
        !           227:                /* reduce if and only if Ecart_sugarGrade does not increase. */
        !           228:                new_s = grade_gen(r)-grade_gen(gset->polys[minGrade]->gh[minGseti]);
        !           229:                if (new_s + minGrade <= Ecart_sugarGrade) {
        !           230:                  return er;
        !           231:                }else{
        !           232:                  printf("new_s=%d, minGrade=%d, sugarGrade=%d\n",new_s,minGrade,
        !           233:                                 Ecart_sugarGrade);
        !           234:                  er.ell = -1;
        !           235:                  return er;
        !           236:                }
        !           237:          }
        !           238:        }else{
        !           239:       er.ell = ell2;
        !           240:       er.first = 0;
        !           241:       er.ggi = minGgi;
        !           242:          return er;
        !           243:        }
        !           244:   }
        !           245:
1.1       takayama  246:   if (ell1 <= ell2) {
                    247:     if (ell1 == LARGE) {
                    248:       er.ell = -1;
                    249:       return er;
                    250:     }else{
                    251:       er.ell = ell1;
                    252:       er.first = 1;
                    253:       er.grade = minGrade;
                    254:       er.gseti = minGseti;
                    255:       return er;
                    256:     }
                    257:   }else{
                    258:       er.ell = ell2;
                    259:       er.first = 0;
                    260:       er.ggi = minGgi;
                    261:       return er;
                    262:   }
                    263: }
                    264:
1.5       takayama  265: static POLY  ecartCheckSyz0(POLY cf,POLY r_0,POLY syz,
                    266:                            struct gradedPolySet *gg,POLY r)
                    267: {
                    268:   POLY f;
                    269:   int grd,i;
                    270:   POLY q;
                    271:   struct coeff *c;
                    272:   f = ppMult(cf,r_0);
                    273:   while (syz != POLYNULL) {
                    274:     grd = syz->m->e[0].x;
                    275:     i = syz->m->e[0].D;
                    276:     c = syz->coeffp;
                    277:     if (c->tag == POLY_COEFF) {
                    278:       q = c->val.f;
                    279:     }else{
                    280:       q = POLYNULL;
                    281:     }
                    282:     f = ppAdd(f,ppMult(q,((gg->polys[grd])->g)[i]));
                    283:                                 /* not gh, works only for _ecart0 */
                    284:     syz = syz->next;
                    285:   }
                    286:   f = ppSub(f,r);
                    287:   return f;
                    288: }
                    289:
1.16      takayama  290: static void  ecartCheckSyz0_printinfo(POLY cf,POLY r_0,POLY syz,
                    291:                                       struct gradedPolySet *gg,POLY r)
                    292: {
                    293:   POLY f;
                    294:   int grd,i;
                    295:   POLY q;
                    296:   struct coeff *c;
                    297:   fprintf(stderr,"cf=%s\n",POLYToString(cf,'*',1));
                    298:   fprintf(stderr,"r_0=%s\n",POLYToString(r_0,'*',1));
                    299:   fprintf(stderr,"syz=%s\n",POLYToString(syz,'*',1));
                    300:   fprintf(stderr,"r=%s\n",POLYToString(r,'*',1));
                    301:   f = ppMult(cf,r_0);
                    302:   while (syz != POLYNULL) {
                    303:     grd = syz->m->e[0].x;
                    304:     i = syz->m->e[0].D;
                    305:     c = syz->coeffp;
                    306:     if (c->tag == POLY_COEFF) {
                    307:       q = c->val.f;
                    308:     }else{
                    309:       q = POLYNULL;
                    310:     }
                    311:        fprintf(stderr,"[grd,idx]=[%d,%d], %s\n",grd,i,
                    312:                        POLYToString(((gg->polys[grd])->g)[i],'*',1));
                    313:     /* f = ppAdd(f,ppMult(q,((gg->polys[grd])->g)[i])); */
                    314:     syz = syz->next;
                    315:   }
                    316:   /* f = ppSub(f,r); */
                    317: }
                    318:
1.5       takayama  319:
                    320: POLY reduction_ecart(r,gset,needSyz,syzp)
                    321:      POLY r;
                    322:      struct gradedPolySet *gset;
                    323:      int needSyz;
                    324:      struct syz0 *syzp; /* set */
                    325: {
1.8       takayama  326:   POLY rn;
1.12      takayama  327:   if (TraceLift && needSyz) {
                    328:     warningGradedSet("TraceLift cannot be used to get syzygy. TraceLift is turned off.\n");
                    329:     TraceLift = 0;
                    330:   }
1.8       takayama  331:   if (TraceLift) {
                    332:        if (EcartAutomaticHomogenization) {
                    333:          if (TraceLift_ringmod == NULL) {
                    334:                warningPoly("reduction_ecart: TraceLift_ringmod is not set.\n");
                    335:                return reduction_ecart1(r,gset,needSyz,syzp);
                    336:          }
1.12      takayama  337:          rn = reduction_ecart1_mod(r,gset);
1.8       takayama  338:          if (rn == POLYNULL) return rn;
                    339:          else return reduction_ecart1(r,gset,needSyz,syzp);
                    340:        }else{
                    341:          return reduction_ecart0(r,gset,needSyz,syzp);
                    342:        }
1.5       takayama  343:   }else{
1.8       takayama  344:        if (EcartAutomaticHomogenization) {
                    345:          return reduction_ecart1(r,gset,needSyz,syzp);
                    346:        }else{
                    347:          return reduction_ecart0(r,gset,needSyz,syzp);
                    348:        }
1.5       takayama  349:   }
                    350: }
                    351:
1.1       takayama  352: /*
                    353:   r and gset are assumed to be (0,1)-homogenized (h-homogenized)
1.5       takayama  354:   Polynomials r and gset are assumed
1.3       takayama  355:   to be double homogenized (h-homogenized and s(H)-homogenized)
1.1       takayama  356:  */
1.5       takayama  357: static POLY reduction_ecart0(r,gset,needSyz,syzp)
1.1       takayama  358:      POLY r;
                    359:      struct gradedPolySet *gset;
                    360:      int needSyz;
                    361:      struct syz0 *syzp; /* set */
                    362: {
                    363:   int reduced,reduced1,reduced2;
                    364:   int grd;
                    365:   struct polySet *set;
                    366:   POLY cf,syz;
                    367:   int i;
                    368:   POLY cc,cg;
                    369:   struct ecartReducer ells;
                    370:   struct ecartPolyArray *gg;
                    371:   POLY pp;
                    372:   int ell;
1.5       takayama  373:   POLY cf_o;
                    374:   POLY syz_o;
                    375:   POLY r_0;
1.15      takayama  376:   int se;
1.14      takayama  377:   struct coeff *cont;
1.1       takayama  378:
                    379:   extern struct ring *CurrentRingp;
                    380:   struct ring *rp;
                    381:
1.5       takayama  382:   r_0 = r;
1.1       takayama  383:   gg = NULL;
                    384:   if (needSyz) {
                    385:     if (r ISZERO) { rp = CurrentRingp; } else { rp = r->m->ringp; }
                    386:     cf = cxx(1,0,0,rp);
                    387:     syz = ZERO;
                    388:   }
                    389:
                    390:   if (r != POLYNULL) {
1.4       takayama  391:     rp = r->m->ringp;
                    392:     if (! rp->weightedHomogenization) {
                    393:       errorKan1("%s\n","ecart.c: the given ring must be declared with [(weightedHomogenization) 1]");
                    394:     }
1.1       takayama  395:   }
                    396:
1.14      takayama  397:   if (DoCancel && (r != POLYNULL)) shouldReduceContent(r,1);
                    398:
1.6       takayama  399:   if (DebugReductionEcart&1) printf("--------------------------------------\n");
1.5       takayama  400:   do {
1.18      takayama  401:     if (DebugReductionRed&1) printf("r=%s\n",POLYToString(r,'*',1));
1.6       takayama  402:     if (DebugReductionEcart & 1) printf("r=%s+...\n",POLYToString(head(r),'*',1));
1.5       takayama  403:     ells = ecartFindReducer(r,gset,gg);
                    404:     ell = ells.ell;
                    405:     if (ell > 0) {
1.6       takayama  406:       if (DebugReductionEcart & 2) printf("*");
1.5       takayama  407:       if (needSyz) {
                    408:         gg = ecartPutPolyInG(r,gg,cf,syz);
                    409:       }else{
                    410:         gg = ecartPutPolyInG(r,gg,POLYNULL,POLYNULL);
                    411:       }
                    412:     }
                    413:     if (ell >= 0) {
                    414:       if (ells.first) {
                    415:         pp = ((gset->polys[ells.grade])->gh)[ells.gseti];
                    416:       }else{
1.6       takayama  417:         if (DebugReductionEcart & 4) printf("#");
1.5       takayama  418:         pp = (gg->pa)[ells.ggi];
                    419:       }
1.16      takayama  420:       if (ell > 0) r = ppMult(cxx(1,0,ell,rp),r); /* r = s^ell r */
1.5       takayama  421:       r = (*reduction1)(r,pp,needSyz,&cc,&cg);
1.14      takayama  422:
                    423:       if (DoCancel && (r != POLYNULL)) {
                    424:         if (shouldReduceContent(r,0)) {
                    425:           r = reduceContentOfPoly(r,&cont);
                    426:           shouldReduceContent(r,1);
                    427:           if (DebugReductionEcart || DebugReductionRed || DebugContentReduction) printf("CONT=%s ",coeffToString(cont));
                    428:         }
                    429:       }
                    430:
                    431:
1.5       takayama  432:       if (needSyz) {
                    433:         if (ells.first) {
                    434:           if (ell >0) cc = ppMult(cc,cxx(1,0,ell,rp));
                    435:           cf = ppMult(cc,cf);
                    436:           syz = cpMult(toSyzCoeff(cc),syz);
                    437:           syz = ppAdd(syz,toSyzPoly(cg,ells.grade,ells.gseti));
                    438:         }else{
                    439:           if (ell >0) cc = ppMult(cc,cxx(1,0,ell,rp));
                    440:           cf_o = (gg->cf)[ells.ggi];
                    441:           syz_o = (gg->syz)[ells.ggi];
                    442:           cf = ppMult(cc,cf);
                    443:           cf = ppAdd(cf,ppMult(cg,cf_o));
                    444:           syz = cpMult(toSyzCoeff(cc),syz);
                    445:           syz = ppAdd(syz,cpMult(toSyzCoeff(cg),syz_o));
1.6       takayama  446:           /* Note. 2003.07.19 */
1.5       takayama  447:         }
1.18      takayama  448:         if (DebugReductionRed && needSyz) {
1.6       takayama  449:           POLY tp;
                    450:           tp = ecartCheckSyz0(cf,r_0,syz,gset,r);
                    451:           if (tp != POLYNULL) {
                    452:             fprintf(stderr,"reduction_ecart0(): sygyzy is broken. Return the Current values.\n");
1.16      takayama  453:             fprintf(stderr,"tp=%s\n",POLYToString(tp,'*',1));
                    454:                        ecartCheckSyz0_printinfo(cf,r_0,syz,gset,r);
1.6       takayama  455:             syzp->cf = cf;
                    456:             syzp->syz = syz;
                    457:             return r;
                    458:           }
1.5       takayama  459:         }
                    460:       }
                    461:       if (r ISZERO) goto ss;
1.15      takayama  462:
                    463:       /* r = r/s^? Don't do this?? */
                    464:       r = ecartDivideSv(r,&se);
                    465:          if (needSyz && (se > 0)) {
                    466:                POLY tt;
                    467:                tt = cxx(1,0,-se,rp);
1.16      takayama  468:                cf = ppMult(tt,cf);
1.15      takayama  469:                syz = cpMult(toSyzCoeff(tt),syz);
                    470:          }
                    471:
1.5       takayama  472:     }
                    473:   }while (ell >= 0);
                    474:
                    475:  ss: ;
                    476:   if (needSyz) {
1.16      takayama  477:     syzp->cf = cf;   /* cf is in the ring of r */
                    478:     syzp->syz = syz; /* syz is in the syzRing of r */
1.14      takayama  479:   }
                    480:
                    481:   if (DoCancel && (r != POLYNULL)) {
                    482:     if (r->m->ringp->p == 0) {
                    483:          r = reduceContentOfPoly(r,&cont);
                    484:          if (DebugReductionEcart || DebugReductionRed || DebugContentReduction) printf("cont=%s ",coeffToString(cont));
                    485:     }
1.5       takayama  486:   }
                    487:
                    488:   return(r);
                    489: }
                    490:
                    491: /*
                    492:   r and gset are assumed to be (0,1)-homogenized (h-homogenized)
                    493:   r and gset are not assumed
                    494:   to be double homogenized (h-homogenized and s(H)-homogenized)
                    495:   They are automatically s(H)-homogenized, and s is set to 1
                    496:   when this function returns.
                    497:  */
                    498: static POLY reduction_ecart1(r,gset,needSyz,syzp)
                    499:      POLY r;
                    500:      struct gradedPolySet *gset;
                    501:      int needSyz;
                    502:      struct syz0 *syzp; /* set */
                    503: {
                    504:   int reduced,reduced1,reduced2;
                    505:   int grd;
                    506:   struct polySet *set;
                    507:   POLY cf,syz;
                    508:   int i;
                    509:   POLY cc,cg;
                    510:   struct ecartReducer ells;
                    511:   struct ecartPolyArray *gg;
                    512:   POLY pp;
                    513:   int ell;
1.12      takayama  514:   POLY cf_o;
                    515:   POLY syz_o;
                    516:   POLY r_0;
1.18      takayama  517:   POLY r0;
1.5       takayama  518:   int se;
1.9       takayama  519:   struct coeff *cont;
1.5       takayama  520:
                    521:   extern struct ring *CurrentRingp;
                    522:   struct ring *rp;
1.9       takayama  523:   extern struct ring *SmallRingp;
1.5       takayama  524:
1.12      takayama  525:   r_0 = r;
1.5       takayama  526:   gg = NULL;
                    527:   if (needSyz) {
                    528:     if (r ISZERO) { rp = CurrentRingp; } else { rp = r->m->ringp; }
                    529:     cf = cxx(1,0,0,rp);
                    530:     syz = ZERO;
                    531:   }
                    532:
                    533:   if (r != POLYNULL) {
                    534:     rp = r->m->ringp;
                    535:     if (! rp->weightedHomogenization) {
                    536:       errorKan1("%s\n","ecart.c: the given ring must be declared with [(weightedHomogenization) 1]");
                    537:     }
1.3       takayama  538:   }
1.5       takayama  539:
                    540:   r = goHomogenize11(r,DegreeShifto_vec,DegreeShifto_size,-1,1);
1.1       takayama  541:   /* 1 means homogenize only s */
1.10      takayama  542:   if (DoCancel && (r != POLYNULL)) shouldReduceContent(r,1);
1.1       takayama  543:
1.7       takayama  544:   if (DebugReductionEcart&1) printf("=======================================\n");
1.1       takayama  545:   do {
1.18      takayama  546:     if (DebugReductionRed & 1) printf("(ecart1(d)) r=%s\n",POLYToString(r,'*',1));
1.7       takayama  547:     if (DebugReductionEcart & 1) printf("r=%s+,,,\n",POLYToString(head(r),'*',1));
                    548:
1.1       takayama  549:     ells = ecartFindReducer(r,gset,gg);
                    550:     ell = ells.ell;
                    551:     if (ell > 0) {
1.7       takayama  552:       if (DebugReductionEcart & 2) printf("%");
1.16      takayama  553:       if (needSyz) {
                    554:         gg = ecartPutPolyInG(r,gg,cf,syz);
                    555:       }else{
                    556:         gg = ecartPutPolyInG(r,gg,POLYNULL,POLYNULL);
                    557:       }
1.1       takayama  558:     }
                    559:     if (ell >= 0) {
                    560:       if (ells.first) {
                    561:         pp = ((gset->polys[ells.grade])->gh)[ells.gseti];
                    562:       }else{
1.9       takayama  563:         if (DebugReductionEcart & 4) {printf("+"); fflush(NULL);}
1.1       takayama  564:         pp = (gg->pa)[ells.ggi];
                    565:       }
1.16      takayama  566:       if (ell > 0) r = ppMult(cxx(1,0,ell,rp),r); /* r = s^ell r */
1.18      takayama  567:          r0 = r;
1.1       takayama  568:       r = (*reduction1)(r,pp,needSyz,&cc,&cg);
1.18      takayama  569:       if (DebugReductionEcart & 8) {
                    570:         if (ell > 0) {printf("ell+ "); fflush(NULL);
                    571:         }else {
                    572:                  printf("ell0 "); fflush(NULL);
                    573:           if ((*mmLarger)(r,r0) >= 1) {
                    574:             printf("error in reduction.");
                    575:             printf("   r0=%s\n",POLYToString(r0,'*',1));
                    576:             printf("==>r=%s\n",POLYToString(r,'*',1));
                    577:             getchar(); getchar();
                    578:           }
                    579:         }
                    580:       }
1.10      takayama  581:
1.12      takayama  582:       if (DoCancel && (r != POLYNULL)) {
1.10      takayama  583:         if (shouldReduceContent(r,0)) {
                    584:           r = reduceContentOfPoly(r,&cont);
                    585:           shouldReduceContent(r,1);
1.11      takayama  586:           if (DebugReductionEcart || DebugReductionRed || DebugContentReduction) printf("CONT=%s ",coeffToString(cont));
1.10      takayama  587:         }
                    588:       }
                    589:
1.1       takayama  590:       if (needSyz) {
                    591:         if (ells.first) {
1.16      takayama  592:           if (ell > 0) cc = ppMult(cc,cxx(1,0,ell,rp));
1.1       takayama  593:           cf = ppMult(cc,cf);
                    594:           syz = cpMult(toSyzCoeff(cc),syz);
1.16      takayama  595:           syz = ppAdd(syz,toSyzPoly(cg,ells.grade,ells.gseti));
1.1       takayama  596:         }else{
1.12      takayama  597:           if (ell >0) cc = ppMult(cc,cxx(1,0,ell,rp));
                    598:           cf_o = (gg->cf)[ells.ggi];
                    599:           syz_o = (gg->syz)[ells.ggi];
                    600:           cf = ppMult(cc,cf);
                    601:           cf = ppAdd(cf,ppMult(cg,cf_o));
                    602:           syz = cpMult(toSyzCoeff(cc),syz);
                    603:           syz = ppAdd(syz,cpMult(toSyzCoeff(cg),syz_o));
                    604:           /* Note. 2003.07.19 */
1.1       takayama  605:         }
                    606:       }
1.12      takayama  607:
1.18      takayama  608:       if (DebugReductionRed && needSyz) {
1.12      takayama  609:         POLY tp;
                    610:         tp = ecartCheckSyz0(cf,r_0,syz,gset,r);
1.16      takayama  611:         tp = goDeHomogenizeS(tp);
1.12      takayama  612:         if (tp != POLYNULL) {
1.16      takayama  613:           fprintf(stderr,"Error: reduction_ecart1(): sygyzy is broken. Return the Current values.\n");
1.12      takayama  614:           fprintf(stderr,"%s\n",POLYToString(tp,'*',1));
                    615:           syzp->cf = cf;
                    616:           syzp->syz = syz;
                    617:           return r;
                    618:         }
                    619:       }
                    620:
1.5       takayama  621:       if (r ISZERO) goto ss1;
                    622:       r = ecartDivideSv(r,&se); /* r = r/s^? */
1.15      takayama  623:
1.16      takayama  624:       if (needSyz && (se > 0)) { /* It may not necessary because of dehomo*/
                    625:         POLY tt;
                    626:         /*printf("!1/H!"); fflush(NULL);*/ /* misc-2003/ecart/t1.sm1 foo4 */
                    627:         tt = cxx(1,0,-se,rp);
                    628:         cf = ppMult(tt,cf);
                    629:         syz = cpMult(toSyzCoeff(tt),syz);
                    630:       }
                    631:
                    632:       /* For debug */
                    633:       if (DebugReductionRed && needSyz) {
                    634:         POLY tp;
                    635:         tp = ecartCheckSyz0(cf,r_0,syz,gset,r);
                    636:         tp = goDeHomogenizeS(tp);
                    637:         if (tp != POLYNULL) {
                    638:           fprintf(stderr,"Error: reduction_ecart1() after divide: sygyzy is broken. Return the Current values.\n");
                    639:           fprintf(stderr,"%s\n",POLYToString(tp,'*',1));
                    640:           syzp->cf = cf;
                    641:           syzp->syz = syz;
                    642:           return r;
                    643:         }
                    644:       }
1.15      takayama  645:
1.1       takayama  646:     }
                    647:   }while (ell >= 0);
                    648:
1.5       takayama  649:  ss1: ;
1.1       takayama  650:   if (needSyz) {
1.12      takayama  651:     /* dehomogenize the syzygy. BUG, this may be inefficient.  */
1.16      takayama  652:     cf = goDeHomogenizeS(cf);
                    653:     syz = goDeHomogenizeS(syz);
                    654:     /*printf("cf=%s\n",POLYToString(cf,'*',1));
                    655:       printf("syz=%s\n",POLYToString(syz,'*',1));*/
1.1       takayama  656:     syzp->cf = cf;   /* cf is in the CurrentRingp */
                    657:     syzp->syz = syz; /* syz is in the SyzRingp */
                    658:   }
1.8       takayama  659:
                    660:   r = goDeHomogenizeS(r);
1.12      takayama  661:   if (DoCancel && (r != POLYNULL)) {
1.10      takayama  662:     if (r->m->ringp->p == 0) {
1.16      takayama  663:       r = reduceContentOfPoly(r,&cont);
                    664:       if (DebugReductionEcart || DebugReductionRed || DebugContentReduction) printf("cont=%s ",coeffToString(cont));
                    665:     }
                    666:   }
                    667:
                    668:   /* For debug */
                    669:   if (DebugReductionRed && needSyz) {
                    670:     POLY tp;
                    671:     tp = ecartCheckSyz0(cf,r_0,syz,gset,r);
                    672:     tp = goDeHomogenizeS(tp);
                    673:     if (tp != POLYNULL) {
                    674:       fprintf(stderr,"Error: reduction_ecart1() last step: sygyzy is broken. Return the Current values.\n");
                    675:       fprintf(stderr,"%s\n",POLYToString(tp,'*',1));
                    676:       syzp->cf = cf;
                    677:       syzp->syz = syz;
                    678:       return r;
1.10      takayama  679:     }
1.9       takayama  680:   }
1.8       takayama  681:
                    682:   return(r);
                    683: }
                    684:
                    685: /* Functions for trace lift  */
                    686: static struct ecartReducer ecartFindReducer_mod(POLY r,
                    687:                                                 struct gradedPolySet *gset,
                    688:                                                 struct ecartPolyArray *epa)
                    689: {
                    690:   int grd;
                    691:   struct polySet *set;
                    692:   int minGrade = 0;
                    693:   int minGseti = 0;
                    694:   int minGgi   = 0;
                    695:   int ell1 = LARGE;
                    696:   int ell2 = LARGE;
                    697:   int ell;
                    698:   int i;
                    699:   struct ecartReducer er;
                    700:   /* Try to find a reducer in gset; */
                    701:   grd = 0;
                    702:   while (grd < gset->maxGrade) {
                    703:     set = gset->polys[grd];
                    704:     for (i=0; i<set->size; i++) {
                    705:       if (set->gh[i] == POLYNULL) {
                    706:         /* goHomogenize set->gh[i] */
                    707:           if (EcartAutomaticHomogenization) {
                    708:               set->gh[i] = goHomogenize11(set->g[i],DegreeShifto_vec,DegreeShifto_size,-1,1);
                    709:           }else{
                    710:               set->gh[i] = set->g[i];
                    711:           }
                    712:       }
                    713:          if (TraceLift && (set->gmod[i] == POLYNULL)) {
                    714:                set->gmod[i] = modulop(set->gh[i],TraceLift_ringmod);
                    715:          }
                    716:          if (TraceLift) {
                    717:                ell = ecartGetEll(r,set->gmod[i]);
                    718:          }else{
                    719:                ell = ecartGetEll(r,set->gh[i]);
                    720:          }
                    721:       if ((ell>=0) && (ell < ell1)) {
                    722:         ell1 = ell;
                    723:         minGrade = grd; minGseti=i;
                    724:       }
                    725:     }
                    726:     grd++;
                    727:   }
                    728:   if (epa != NULL) {
                    729:     /* Try to find in the second group. */
                    730:     for (i=0; i< epa->size; i++) {
                    731:       ell = ecartGetEll(r,(epa->pa)[i]);
                    732:       if ((ell>=0) && (ell < ell2)) {
                    733:         ell2 = ell;
                    734:         minGgi = i;
                    735:       }
                    736:     }
                    737:   }
                    738:
1.18      takayama  739:   if ((DebugReductionRed & 1)|| (DebugReductionEcart&1)) {
1.8       takayama  740:     printf("ecartFindReducer_mod(): ell1=%d, ell2=%d, minGrade=%d, minGseti=%d, minGgi=%d, p=%d\n",ell1,ell2,minGrade,minGseti,minGgi,TraceLift_ringmod->p);
                    741:   }
                    742:   if (ell1 <= ell2) {
                    743:     if (ell1 == LARGE) {
                    744:       er.ell = -1;
                    745:       return er;
                    746:     }else{
                    747:       er.ell = ell1;
                    748:       er.first = 1;
                    749:       er.grade = minGrade;
                    750:       er.gseti = minGseti;
                    751:       return er;
                    752:     }
                    753:   }else{
                    754:       er.ell = ell2;
                    755:       er.first = 0;
                    756:       er.ggi = minGgi;
                    757:       return er;
                    758:   }
                    759: }
                    760:
                    761: static POLY reduction_ecart1_mod(r,gset)
                    762:      POLY r;
                    763:      struct gradedPolySet *gset;
                    764: {
                    765:   int reduced,reduced1,reduced2;
                    766:   int grd;
                    767:   struct polySet *set;
                    768:   int i;
                    769:   POLY cc,cg;
                    770:   struct ecartReducer ells;
                    771:   struct ecartPolyArray *gg;
                    772:   POLY pp;
1.18      takayama  773:   POLY r0;
1.8       takayama  774:   int ell;
                    775:   int se;
                    776:
                    777:   extern struct ring *CurrentRingp;
                    778:   struct ring *rp;
                    779:
                    780:   gg = NULL;
                    781:
                    782:   if (r != POLYNULL) {
                    783:     rp = r->m->ringp;
                    784:     if (! rp->weightedHomogenization) {
                    785:       errorKan1("%s\n","ecart.c: the given ring must be declared with [(weightedHomogenization) 1]");
                    786:     }
                    787:   }
                    788:
                    789:   r = goHomogenize11(r,DegreeShifto_vec,DegreeShifto_size,-1,1);
                    790:   /* 1 means homogenize only s */
                    791:   /*printf("r=%s (mod 0)\n",POLYToString(head(r),'*',1));
                    792:        KshowRing(TraceLift_ringmod); **/
                    793:
                    794:   r = modulop(r,TraceLift_ringmod);
1.17      takayama  795:   if (r != POLYNULL) rp = r->m->ringp; /* reset rp */
1.8       takayama  796:
                    797:   /* printf("r=%s (mod p)\n",POLYToString(head(r),'*',1)); **/
                    798:
                    799:   if (DebugReductionEcart&1) printf("=====================================mod\n");
                    800:   do {
1.18      takayama  801:     if (DebugReductionRed & 1) printf("(ecart1_mod(d)) r=%s\n",POLYToString(r,'*',1));
1.8       takayama  802:     if (DebugReductionEcart & 1) printf("r=%s+,,,\n",POLYToString(head(r),'*',1));
                    803:
                    804:     ells = ecartFindReducer_mod(r,gset,gg);
                    805:     ell = ells.ell;
                    806:     if (ell > 0) {
                    807:       if (DebugReductionEcart & 2) printf("%");
                    808:       gg = ecartPutPolyInG(r,gg,POLYNULL,POLYNULL);
                    809:     }
                    810:     if (ell >= 0) {
                    811:       if (ells.first) {
                    812:         pp = ((gset->polys[ells.grade])->gmod)[ells.gseti];
                    813:       }else{
1.9       takayama  814:         if (DebugReductionEcart & 4) {printf("+"); fflush(NULL);}
1.8       takayama  815:         pp = (gg->pa)[ells.ggi];
                    816:       }
1.16      takayama  817:       if (ell > 0) r = ppMult(cxx(1,0,ell,rp),r); /* r = s^ell r */
1.18      takayama  818:
                    819:          r0 = r;
1.8       takayama  820:       r = (*reduction1)(r,pp,0,&cc,&cg);
1.18      takayama  821:
                    822:       if (DebugReductionEcart & 8) {
                    823:         if (ell > 0) {printf("ell+ "); fflush(NULL);
                    824:         }else {
                    825:                  printf("ell0 "); fflush(NULL);
                    826:           if ((*mmLarger)(r,r0) >= 1) {
                    827:             printf("error in reduction.");
                    828:             printf("   r0=%s\n",POLYToString(r0,'*',1));
                    829:             printf("==>r=%s\n",POLYToString(r,'*',1));
                    830:             getchar(); getchar();
                    831:           }
                    832:         }
                    833:       }
                    834:
1.8       takayama  835:       if (r ISZERO) goto ss1;
                    836:       r = ecartDivideSv(r,&se); /* r = r/s^? */
                    837:     }
                    838:   }while (ell >= 0);
                    839:
                    840:  ss1: ;
1.5       takayama  841:
1.1       takayama  842:   r = goDeHomogenizeS(r);
1.5       takayama  843:
1.1       takayama  844:   return(r);
1.10      takayama  845: }
                    846:

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>