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>