Annotation of OpenXM/src/kan96xx/Kan/ecart.c, Revision 1.4
1.4 ! takayama 1: /* $OpenXM: OpenXM/src/kan96xx/Kan/ecart.c,v 1.3 2003/07/17 23:37:01 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;
19: };
20:
21: static struct ecartReducer ecartFindReducer(POLY r,struct gradedPolySet *gset,struct ecartPolyArray *epa);
22: static int ecartCheckPoly(POLY f); /* check if it does not contain s-variables */
23: static int ecartCheckEnv(); /* check if the environment is OK for ecart div*/
24: static struct ecartPolyArray *ecartPutPolyInG(POLY g,struct ecartPolyArray *eparray);
25: static int ecartGetEll(POLY r,POLY g);
26: static POLY ecartDivideSv(POLY r);
27:
28: extern int DebugReductionRed;
29:
30: /* This is used for goHomogenization */
31: extern int DegreeShifto_size;
32: extern int *DegreeShifto_vec;
33:
1.3 takayama 34: /* It is used reduction_ecart() and ecartFindReducer()
35: to determine if we homogenize in this function */
36: extern int EcartAutomaticHomogenization;
37:
1.1 takayama 38: #define LARGE 0x7fffffff
39:
40:
41: static POLY ecartDivideSv(POLY r) {
42: POLY f;
43: int k;
44: if (r == POLYNULL) return r;
45: f = r; k = LARGE;
46: while (r != POLYNULL) {
47: if (r->m->e[0].x < k) {
48: k = r->m->e[0].x;
49: }
50: r = r->next;
51: }
52: if (k > 0) {
53: f = r;
54: while (r != POLYNULL) {
55: r->m->e[0].x -= k;
56: r = r->next;
57: }
58: }
59: return f;
60: }
61:
62: static int ecartGetEll(POLY f,POLY g) {
63: int n,i,p;
64: MONOMIAL tf;
65: MONOMIAL tg;
66:
67: if (f ISZERO) return(-1);
68: if (g ISZERO) return(-1);
69:
70: checkRingIsR(f,g);
71:
72: if (!isSameComponent_x(f,g)) return(-1);
73: tf = f->m; tg = g->m; n = tf->ringp->n;
74: for (i=1; i<n; i++) {
75: if (tf->e[i].x < tg->e[i].x) return(-1);
76: if (tf->e[i].D < tg->e[i].D) return(-1);
77: }
78: if (tf->e[0].D < tg->e[0].D) return(-1); /* h */
1.2 takayama 79: p = tf->e[0].x - tg->e[0].x; /* H, s */
1.1 takayama 80: if (p >=0 ) return 0;
81: else return(-p);
82: }
83:
84:
85: #define EP_SIZE 10
86: static struct ecartPolyArray *ecartPutPolyInG(POLY g,struct ecartPolyArray *eparray)
87: {
88: struct ecartPolyArray *a;
89: POLY *ep;
90: int i;
91: if (eparray == (struct ecartPolyArray *)NULL) {
92: a = (struct ecartPolyArray *) sGC_malloc(sizeof(struct ecartPolyArray));
93: outofmemory(a);
94: ep = (POLY *) sGC_malloc(sizeof(POLY)*EP_SIZE);
95: outofmemory(ep);
96: a->limit = EP_SIZE;
97: a->size = 0;
98: a->pa = ep;
99: eparray = a;
100: }
101: if (eparray->size >= eparray->limit) {
102: a = (struct ecartPolyArray *) sGC_malloc(sizeof(struct ecartPolyArray));
103: outofmemory(a);
104: ep = (POLY *) sGC_malloc(sizeof(POLY)*((eparray->limit)*2));
105: outofmemory(ep);
106: a->limit = (eparray->limit)*2;
107: a->size = eparray->size;
108: a->pa = ep;
109: for (i=0; i<eparray->size; i++) {
110: (a->pa)[i] = (eparray->pa)[i];
111: }
112: eparray = a;
113: }
114: i = eparray->size;
115: (eparray->pa)[i] = g;
116: (eparray->size)++;
117: return eparray;
118: }
119:
120: static struct ecartReducer ecartFindReducer(POLY r,struct gradedPolySet *gset,
121: struct ecartPolyArray *epa)
122: {
123: int grd;
124: struct polySet *set;
125: int minGrade = 0;
126: int minGseti = 0;
127: int minGgi = 0;
128: int ell1 = LARGE;
129: int ell2 = LARGE;
130: int ell;
131: int i;
132: struct ecartReducer er;
133: /* Try to find a reducer in gset; */
134: grd = 0;
135: while (grd < gset->maxGrade) {
136: set = gset->polys[grd];
137: for (i=0; i<set->size; i++) {
1.2 takayama 138: if (set->gh[i] == POLYNULL) {
139: /* goHomogenize set->gh[i] */
1.4 ! takayama 140: if (EcartAutomaticHomogenization) {
! 141: set->gh[i] = goHomogenize11(set->g[i],DegreeShifto_vec,DegreeShifto_size,-1,1);
! 142: }else{
! 143: set->gh[i] = set->g[i];
! 144: }
1.2 takayama 145: }
146: ell = ecartGetEll(r,set->gh[i]);
1.1 takayama 147: if ((ell>=0) && (ell < ell1)) {
148: ell1 = ell;
149: minGrade = grd; minGseti=i;
150: }
151: }
152: grd++;
153: }
154: if (epa != NULL) {
155: /* Try to find in the second group. */
156: for (i=0; i< epa->size; i++) {
157: ell = ecartGetEll(r,(epa->pa)[i]);
158: if ((ell>=0) && (ell < ell2)) {
159: ell2 = ell;
160: minGgi = i;
161: }
162: }
163: }
164:
165: if (DebugReductionRed) {
166: printf("ecartFindReducer(): ell1=%d, ell2=%d, minGrade=%d, minGseti=%d, minGgi=%d\n",ell1,ell2,minGrade,minGseti,minGgi);
167: }
168: if (ell1 <= ell2) {
169: if (ell1 == LARGE) {
170: er.ell = -1;
171: return er;
172: }else{
173: er.ell = ell1;
174: er.first = 1;
175: er.grade = minGrade;
176: er.gseti = minGseti;
177: return er;
178: }
179: }else{
180: er.ell = ell2;
181: er.first = 0;
182: er.ggi = minGgi;
183: return er;
184: }
185: }
186:
187: /*
188: r and gset are assumed to be (0,1)-homogenized (h-homogenized)
1.3 takayama 189: If EcartAutomaticHomogenization == 0, then r and gset are assumed
190: to be double homogenized (h-homogenized and s(H)-homogenized)
1.1 takayama 191: */
192: POLY reduction_ecart(r,gset,needSyz,syzp)
193: POLY r;
194: struct gradedPolySet *gset;
195: int needSyz;
196: struct syz0 *syzp; /* set */
197: {
198: int reduced,reduced1,reduced2;
199: int grd;
200: struct polySet *set;
201: POLY cf,syz;
202: int i;
203: POLY cc,cg;
204: struct ecartReducer ells;
205: struct ecartPolyArray *gg;
206: POLY pp;
207: int ell;
208:
209: extern struct ring *CurrentRingp;
210: struct ring *rp;
211:
212: gg = NULL;
213: if (needSyz) {
214: if (r ISZERO) { rp = CurrentRingp; } else { rp = r->m->ringp; }
215: cf = cxx(1,0,0,rp);
216: syz = ZERO;
217: }
218:
219: if (r != POLYNULL) {
1.4 ! takayama 220: rp = r->m->ringp;
! 221: if (! rp->weightedHomogenization) {
! 222: errorKan1("%s\n","ecart.c: the given ring must be declared with [(weightedHomogenization) 1]");
! 223: }
1.1 takayama 224: }
225:
1.3 takayama 226: if (EcartAutomaticHomogenization) {
1.4 ! takayama 227: r = goHomogenize11(r,DegreeShifto_vec,DegreeShifto_size,-1,1);
1.3 takayama 228: }
1.1 takayama 229: /* 1 means homogenize only s */
230:
231: do {
232: if (DebugReductionRed) printf("r=%s\n",POLYToString(r,'*',1));
233: ells = ecartFindReducer(r,gset,gg);
234: ell = ells.ell;
235: if (ell > 0) {
236: gg = ecartPutPolyInG(r,gg);
237: }
238: if (ell >= 0) {
239: if (ells.first) {
240: pp = ((gset->polys[ells.grade])->gh)[ells.gseti];
241: }else{
242: pp = (gg->pa)[ells.ggi];
243: }
244: if (ell > 0) r = mpMult(cxx(1,0,ell,rp),r); /* r = s^ell r */
245: r = (*reduction1)(r,pp,needSyz,&cc,&cg);
246: if (needSyz) {
247: if (ells.first) {
248: cf = ppMult(cc,cf);
249: syz = cpMult(toSyzCoeff(cc),syz);
250: syz = ppAddv(syz,toSyzPoly(cg,ells.grade,ells.gseti));
251: }else{
252: /* BUG: not yet */
253: }
254: }
255: if (r ISZERO) goto ss;
256: r = ecartDivideSv(r); /* r = r/s^? */
257: }
258: }while (ell >= 0);
259:
260: ss: ;
261: if (needSyz) {
262: syzp->cf = cf; /* cf is in the CurrentRingp */
263: syzp->syz = syz; /* syz is in the SyzRingp */
264: /* BUG: dehomogenize the syzygy */
265: }
1.2 takayama 266: /*
1.1 takayama 267: r = goDeHomogenizeS(r);
1.2 takayama 268: */
1.1 takayama 269: return(r);
270: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>