Annotation of OpenXM/src/kan96xx/Kan/syz0.c, Revision 1.4
1.4 ! takayama 1: /* $OpenXM: OpenXM/src/kan96xx/Kan/syz0.c,v 1.3 2001/05/04 01:06:26 takayama Exp $ */
1.1 maekawa 2: #include <stdio.h>
3: #include "datatype.h"
4: #include "extern2.h"
5: #include "matrix.h"
6: #include "gradedset.h"
7:
8: extern int KanGBmessage;
9: static int Debugsyz0 = 0;
10:
11: static POLY getFactor0(struct gradedPolySet *grG,int grd,int index);
12: static void clearMark(struct gradedPolySet *grG);
13: static void printMatrixOfPOLY(struct matrixOfPOLY *mat);
14: static void printArrayOfPOLY(struct arrayOfPOLY *mat);
15: static int isZeroRow(struct matrixOfPOLY *mat,int i);
16:
17: static int getSize00OfGradedSet(struct gradedPolySet *g);
18: static int positionInPairs(struct pair *top,struct pair *pairs);
19: /* if the top is not in the list pairs, it returns -1. */
20: static struct pair *oldPairsToNewPairs(struct pair *opairs,
1.3 takayama 21: int *table,int size);
1.1 maekawa 22: /* In the function getSyzygy(), reduced Grobner basis *grBases is
23: constructed from grG by deleting unnecessary elements.
24: The array <<table>> gives the correspondence between the index
25: ig (i-grade), ii (i-index) of *grBases and grG.
26: When <<opairs>> keeps syzygies for grG, it returns syzygies for
27: *grBases.
28: Note that the result syzygies are not necessarily COMPLETE.
29: Note that the <<prev>> fields are not set properly.
30: */
31: struct matrixOfPOLY *getSyzygy01(struct gradedPolySet *reducedBasis,
1.3 takayama 32: struct pair *excludedPairs);
1.1 maekawa 33: /*
34: When <<excludedPairs>> is NULL,
35: this function computes all syzygies for the <<reducedBasis>>.
36: If not, this function computes all syzygies except those in excludedPairs.
37: The <<serial>> field of the <<reducedBasis>> is used to change
38: syzygy polynomials into arrays. March 15, 1997
39: */
40:
41:
42:
43: /* if (mark[j]), then the simplification is done. */
44: void getBackwardTransformation(grG)
1.3 takayama 45: struct gradedPolySet *grG;
46: /* grG->polys[i]->mark[j],syz[j] are modified. */
1.1 maekawa 47: {
48: int i,j;
49: struct polySet *ps;
50:
51:
52: for (i=0; i<grG->maxGrade; i++) {
53: ps = grG->polys[i];
54: for (j=0; j<ps->size; j++) {
55: if (ps->mark[j] == 0 && ps->del[j] == 0) {
1.3 takayama 56: simplifyBT(i,j,grG);
1.1 maekawa 57: }
58: }
59: }
60: }
61:
62: void simplifyBT(grd,index,grG)
1.3 takayama 63: int grd;
64: int index;
65: struct gradedPolySet *grG;
1.1 maekawa 66: {
67: POLY s,r;
68: int g0,i0;
69:
70: s = grG->polys[grd]->syz[index]->syz;
71: r = ZERO;
72:
73: if (KanGBmessage) {printf("."); fflush(stdout); }
74:
75: while (s != ZERO) {
76: g0 = srGrade(s);
77: i0 = srIndex(s);
78: if (grG->polys[g0]->mark[i0]) {
79: r = ppAdd(r,cpMult(s->coeffp,grG->polys[g0]->syz[i0]->syz));
80: }else{
81: simplifyBT(g0,i0,grG);
82: r = ppAdd(r,cpMult(s->coeffp,grG->polys[g0]->syz[i0]->syz));
83: }
84: s = s->next;
85: }
86: grG->polys[grd]->syz[index]->syz = r;
87: grG->polys[grd]->mark[index] = 1;
88: }
89:
90:
91: static POLY getFactor0(grG,grd,index)
1.3 takayama 92: struct gradedPolySet *grG;
93: int grd;
94: int index;
1.1 maekawa 95: {
96: POLY ans;
97: int i,j;
98: struct polySet *ps;
99:
100: ans = cxx(1,0,0,grG->polys[grd]->g[index]->m->ringp);
101: for (i=0; i<grG->maxGrade; i++) {
102: ps = grG->polys[i];
103: for (j=0; j<ps->size; j++) {
104: if (ps->mark[j] && !(i == grd && j == index)) {
1.3 takayama 105: ans = ppMult(ps->syz[j]->cf,ans);
1.1 maekawa 106: }
107: }
108: }
109: return(ans);
110: }
111:
112: struct arrayOfPOLY *getSyzygy0(grG,zeroPairs)
1.3 takayama 113: struct gradedPolySet *grG;
114: struct pair *zeroPairs;
1.1 maekawa 115: {
116: struct pair *tmp;
117: int size,k,i;
118: POLY s;
119: struct arrayOfPOLY *r;
120: struct arrayOfPOLY *ans;
121:
122: /* outputGradedPolySet(grG); */
123: /* outputNode(zeroPairs); */
124: /* outputNode() workds as outputPairs() */
125: tmp = zeroPairs; size = 0;
126: while (tmp != (struct pair *)NULL) {
127: size++;
128: tmp = tmp->next;
129: }
130: ans = newArrayOfPOLY(size+1);
131:
132: k = 0;
133:
134: while (zeroPairs != (struct pair *)NULL) {
135: s = getSyzPolyFromSp(zeroPairs,grG);
136: if (s ISZERO) {
137:
138: }else {
139: getArrayOfPOLY(ans,k) = s;
140: k++;
141: }
142: zeroPairs = zeroPairs->next;
143: }
144:
145: r = newArrayOfPOLY(k);
146: for (i=0; i<k; i++) {
147: getArrayOfPOLY(r,i) = getArrayOfPOLY(ans,i);
148: }
149: return(r);
150: }
151:
152: struct matrixOfPOLY *getSyzygy(grG,zeroPairs,grBasesp,backwardMatp)
1.3 takayama 153: struct gradedPolySet *grG;
154: struct pair *zeroPairs;
155: struct gradedPolySet **grBasesp;
156: struct matrixOfPOLY **backwardMatp;
1.1 maekawa 157: {
158: int serial;
159: int i,j,kk;
160: struct polySet *ps;
161: POLY fi;
162: int grd,indx;
163: struct gradedPolySet *newG;
164: POLY r;
165: struct syz0 syz;
166: struct arrayOfPOLY *ap,*vec;
167: struct matrixOfPOLY *mp;
168: struct matrixOfPOLY *b,*nc,*m2,*m1,*ans,*ans2;
169: struct arrayOfPOLY *dc;
170: int size;
171: int *table;
172: struct pair *excludePairs;
173: struct matrixOfPOLY *mp0;
174: struct matrixOfPOLY *m0;
175: extern int Sugar;
176:
177: size = getSize00OfGradedSet(grG);
178: table = (int *)sGC_malloc(sizeof(int)*4*(size+1));
179: if (table == (int *)NULL) errorSyz0("Out of memory.");
180:
181: if (Debugsyz0) { printf("grG=");outputGradedPolySet(grG,1);}
182:
183: /* set grBases */
184: *grBasesp = newGradedPolySet(0);
185: serial = 0;
186: for (i=0; i<grG->maxGrade; i++) {
187: ps = grG->polys[i];
188: for (j=0; j<ps->size; j++) {
189: if (ps->del[j] == 0) {
1.3 takayama 190: fi = ps->g[j];
191: grd = -1;whereInG(*grBasesp,fi,&grd,&indx,Sugar);
192: *grBasesp =
193: putPolyInG(*grBasesp,fi,grd,indx,newSyz0(),0,serial);
194: table[4*serial] = i; table[4*serial+1] = j;
195: table[4*serial+2] = grd; table[4*serial+3] = indx;
196: serial++;
1.1 maekawa 197: }
198: }
199: }
200: if (Debugsyz0) {printf("*grBasesp=");outputGradedPolySet(*grBasesp,1);}
201:
202: if (size != serial) {
203: fprintf(stderr," size(%d) != serial(%d) ",size,serial);
204: errorSyz0("Internal error size != serial");
205: }
206:
207: /* set newG. Compute the forward transformations.*/
208: newG = gradedPolySetCopy(grG);
209: for (i=0; i<grG->maxGrade;i++) {
210: ps = newG->polys[i];
211: for (j=0; j<ps->size; j++) {
212: fi = ps->g[j];
213: r = (*reduction)(fi,*grBasesp,1,&syz);
214: if (KanGBmessage) {printf("."); fflush(stdout);}
215: if (! (r ISZERO)) errorSyz0("Internal error; getSyzygy(): groebner basis must be given.");
216: ps->syz[j] = newSyz0();
217: /* printf("%s : ",POLYToString(syz.cf,'*',1));
218: printf("%s\n",POLYToString(syz.syz,'*',1)); */
219: ps->syz[j]->cf = syz.cf;
220: ps->syz[j]->syz = syz.syz;
221: }
222: }
223:
224: ap = getSyzygy0(newG,zeroPairs);
225:
226: /* */
227: excludePairs = oldPairsToNewPairs(zeroPairs,table,size);
228: if (Debugsyz0) {
229: printf("zeroPairs = "); outputNode(zeroPairs);
230: for (i=0; i<size; i++) {
231: printf("old gi=%d, old ii=%d, new gi=%d, new ii=%d\n",
1.3 takayama 232: table[4*i],table[4*i+1],table[4*i+2],table[4*i+3]);
1.1 maekawa 233: }
234: printf("excludePairs = "); outputNode(excludePairs);
235: printf("\n");
236: }
237:
238: if (KanGBmessage) {printf("#"); fflush(stdout); }
239: mp0 = getSyzygy01(*grBasesp,excludePairs);
1.4 ! takayama 240: if (mp0 == NULL) return NULL;
1.1 maekawa 241: if (KanGBmessage) {printf("#"); fflush(stdout); }
242:
243: /* We compute E-CB. The number of G (G-basis) is serial. */
244: /* F = - C G, G = B F , then F + CB F = 0*/
245: b = getBackwardMatrixOfPOLY(grG);
246: nc = getNC(newG,serial,*grBasesp);
247: dc = getDC(newG);
248: /*{
249: printf("\nb=\n"); printMatrixOfPOLY(b);
250: printf("\n\nnc=\n"); printMatrixOfPOLY(nc);
251: printf("\n\ndc=\n"); printArrayOfPOLY(dc);
1.3 takayama 252: }*/
1.1 maekawa 253:
254: if (KanGBmessage) {printf(":"); fflush(stdout);}
255: m2 = getSyzygy1(b,nc,dc);
256: *backwardMatp = b;
257:
258: /* mp is the syzygy of the G-basis. */
259: mp = newMatrixOfPOLY(ap->n,serial);
260: for (i=0; i < ap->n; i++) {
261: vec = syzPolyToArrayOfPOLY(serial,getArrayOfPOLY(ap,i),*grBasesp);
262: for (j=0; j < serial; j++) {
263: getMatrixOfPOLY(mp,i,j) = getArrayOfPOLY(vec,j);
264: }
265: }
266: /*printf(" ap->n = %d, serial=%d \n",ap->n, serial);
1.3 takayama 267: printf("\nmp = \n"); printMatrixOfPOLY(mp); */
1.1 maekawa 268:
269: if (KanGBmessage) {printf(";"); fflush(stdout);}
270: m1 = aaMult(mp,b);
271: m0 = aaMult(mp0,b);
272: /* printf("\nm0 = \n"); printMatrixOfPOLY(m0); */
273:
274: ans = newMatrixOfPOLY((m0->m)+(m1->m)+(m2->m),m2->n);
275: kk = 0;
276: for (i=0; i<m0->m; i++) {
277: if (!isZeroRow(m0,i)) {
278: for (j=0; j<m0->n; j++) {
1.3 takayama 279: getMatrixOfPOLY(ans,kk,j) = getMatrixOfPOLY(m0,i,j);
1.1 maekawa 280: }
281: kk++;
282: }
283: }
284: for (i=0; i<m1->m; i++) {
285: if (!isZeroRow(m1,i)) {
286: for (j=0; j<m1->n; j++) {
1.3 takayama 287: getMatrixOfPOLY(ans,kk,j) = getMatrixOfPOLY(m1,i,j);
1.1 maekawa 288: }
289: kk++;
290: }
291: }
292: for (i=0; i<m2->m; i++) {
293: if (!isZeroRow(m2,i)) {
294: for (j=0; j<m2->n; j++) {
1.3 takayama 295: getMatrixOfPOLY(ans,kk,j) = getMatrixOfPOLY(m2,i,j);
1.1 maekawa 296: }
297: kk++; if (KanGBmessage) printf("*");
298: }
299: }
300: if (kk != ans->m) {
301: ans2 = newMatrixOfPOLY(kk,ans->n);
302: for (i=0; i<kk; i++) {
303: for (j=0; j<ans->n; j++) {
1.3 takayama 304: getMatrixOfPOLY(ans2,i,j) = getMatrixOfPOLY(ans,i,j);
1.1 maekawa 305: }
306: }
307: return(ans2);
308: }else{
309: return(ans);
310: }
311:
312: }
313:
314: POLY getSyzPolyFromSp(spij,grG)
1.3 takayama 315: struct pair *spij;
316: struct gradedPolySet *grG;
1.1 maekawa 317: {
318: int ig,ii,jg,ji;
319: POLY dk;
320: POLY f;
321: POLY t,ans;
322: int grd,indx;
323:
324: ig = spij->ig; ii = spij->ii;
325: jg = spij->jg; ji = spij->ji;
326: if (grG->polys[ig]->del[ii] != 0 || grG->polys[jg]->del[ji] != 0)
327: return(ZERO);
328: dk = spij->syz; /* in SyzRing */
329: clearMark(grG);
330: f = dk;
331: while (f != POLYNULL) {
332: grd = srGrade(f);
333: indx = srIndex(f);
334: grG->polys[grd]->mark[indx] = 1;
335: f=f->next;
336: }
337:
338: f = dk; ans = ZERO;
339: while (f != POLYNULL) {
340: grd = srGrade(f);
341: indx = srIndex(f);
342: t = grG->polys[grd]->syz[indx]->syz;
343: t = cpMult(f->coeffp,t);
344: t = cpMult(toSyzCoeff(getFactor0(grG,grd,indx)),t);
345: ans = ppAdd(ans,t);
346: f = f->next;
347: }
348: return(ans);
349: }
350:
351: static void clearMark(grG)
1.3 takayama 352: struct gradedPolySet *grG;
1.1 maekawa 353: {
354: int i,j;
355: struct polySet *ps;
356: for (i=0; i<grG->maxGrade; i++) {
357: ps = grG->polys[i];
358: for (j=0; j<ps->size; j++) {
359: ps->mark[j] = 0;
360: }
361: }
362: }
363:
364:
365: struct arrayOfPOLY *syzPolyToArrayOfPOLY(size,f,grG)
1.3 takayama 366: int size;
367: POLY f; /* f is in the SyzRingp */
368: struct gradedPolySet *grG;
1.1 maekawa 369: {
370: struct arrayOfPOLY *ap;
371: int i,g0,i0,serial;
372:
373: ap = newArrayOfPOLY(size);
374: for (i=0; i<size; i++) {
375: getArrayOfPOLY(ap,i) = ZERO;
376: }
377:
378: while (f != POLYNULL) {
379: g0 = srGrade(f);
380: i0 = srIndex(f);
381: serial = grG->polys[g0]->serial[i0];
382: if (serial < 0) {
383: errorSyz0("syzPolyToArrayOfPOLY(): invalid serial[i] of grG.");
384: }
385: if (getArrayOfPOLY(ap,serial) != ZERO) {
386: errorSyz0("syzPolyToArrayOfPOLY(): syzygy polynomial is broken.");
387: }
388: getArrayOfPOLY(ap,serial) = srSyzCoeffToPOLY(f->coeffp);
389: f = f->next;
390: }
391: return(ap);
392: }
393:
394:
395:
396: struct matrixOfPOLY *getBackwardMatrixOfPOLY(struct gradedPolySet *grG)
397: {
398: /* use serial, del. cf. getBackwardArray() */
399: int inputSize,outputSize;
400: int i,j,k,p;
401: struct arrayOfPOLY *vec;
402: struct matrixOfPOLY *mat;
403: struct polySet *ps;
404:
405: inputSize = 0; outputSize = 0;
406: for (i=0; i<grG->maxGrade; i++) {
407: ps = grG->polys[i];
408: for (j=0; j<ps->size; j++) {
409: if (ps->serial[j] >= 0) ++inputSize;
410: if (ps->del[j] == 0) ++outputSize;
411: }
412: }
413:
414: mat = newMatrixOfPOLY(outputSize,inputSize);
415: k = 0;
416: for (i=0; i<grG->maxGrade; i++) {
417: ps = grG->polys[i];
418: for (j=0; j<ps->size; j++) {
419: if (ps->del[j] == 0) {
1.3 takayama 420: vec = syzPolyToArrayOfPOLY(inputSize,ps->syz[j]->syz,grG);
421: for (p=0; p<inputSize; p++) {
422: getMatrixOfPOLY(mat,k,p)=getArrayOfPOLY(vec,p);
423: }
424: k++;
1.1 maekawa 425: }
426: }
427: }
428: return(mat);
429: }
430:
431:
432: struct matrixOfPOLY *getNC(newG,n,grBases)
1.3 takayama 433: struct gradedPolySet *newG; /* F is stored and indexed by serial. */
434: int n; /* The number of G. */
435: struct gradedPolySet *grBases; /* G (G-basis) is stored. */
1.1 maekawa 436: {
437: int size,i,j,k,ii;
438: struct matrixOfPOLY *mat;
439: struct polySet *ps;
440: struct arrayOfPOLY *vec;
441:
442: if (newG == (struct gradedPolySet *)NULL) {
443: return(newMatrixOfPOLY(0,0));
444: }
445: size = 0;
446: for (i=0; i<newG->maxGrade; i++) {
447: ps = newG->polys[i];
448: for (j=0; j<ps->size; j++) {
449: if (ps->serial[j] >= 0) size++;
450: }
451: }
452: mat = newMatrixOfPOLY(size,n);
453: for (i=0; i<newG->maxGrade; i++) {
454: ps = newG->polys[i];
455: for (j=0; j<ps->size; j++) {
456: if (ps->serial[j] >= 0) {
1.3 takayama 457: ii = ps->serial[j];
458: vec = syzPolyToArrayOfPOLY(n,ps->syz[j]->syz,grBases);
459: for (k=0; k<n; k++) {
460: getMatrixOfPOLY(mat,ii,k) = getArrayOfPOLY(vec,k);
461: }
1.1 maekawa 462: }
463: }
464: }
465: return(mat);
466: }
467:
468: struct arrayOfPOLY *getDC(newG)
1.3 takayama 469: struct gradedPolySet *newG; /* F is stored and indexed by serial. */
1.1 maekawa 470: {
471: int size,i,j,k,ii;
472: struct arrayOfPOLY *mat;
473: struct polySet *ps;
474: extern struct ring *CurrentRingp;
475:
476: if (newG == (struct gradedPolySet *)NULL) {
477: return(newArrayOfPOLY(0));
478: }
479: size = 0;
480: for (i=0; i<newG->maxGrade; i++) {
481: ps = newG->polys[i];
482: for (j=0; j<ps->size; j++) {
483: if (ps->serial[j] >= 0) size++;
484: }
485: }
486: mat = newArrayOfPOLY(size);
487: for (i=0; i<newG->maxGrade; i++) {
488: ps = newG->polys[i];
489: for (j=0; j<ps->size; j++) {
490: if (ps->serial[j] >= 0) {
1.3 takayama 491: ii = ps->serial[j];
492: getArrayOfPOLY(mat,ii) = ps->syz[j]->cf;
1.1 maekawa 493: }
494: }
495: }
496: return(mat);
497: }
498:
499:
500:
501: /* Syzygy from E-CB */
502: struct matrixOfPOLY *getSyzygy1(b,nc,dc)
1.3 takayama 503: struct matrixOfPOLY *b;
504: struct matrixOfPOLY *nc;
505: struct arrayOfPOLY *dc;
1.1 maekawa 506: {
507: int m,n2,n;
508: struct matrixOfPOLY *mat;
509: int i,j,k;
510: POLY r;
511: POLY tmp;
512:
513: m = nc->m;
514: n2 = nc->n;
515: n = b->n;
516: mat = newMatrixOfPOLY(m,n);
517: for (i=0; i<m; i++) {
518: for (j=0; j<n; j++) {
519: r = ZERO;
520: if (i == j) {
1.3 takayama 521: r = getArrayOfPOLY(dc,i);
1.1 maekawa 522: }
523: for (k=0; k<n2; k++) {
1.3 takayama 524: tmp = ppMult(getMatrixOfPOLY(nc,i,k),getMatrixOfPOLY(b,k,j));
525: r = ppAdd(r,tmp);
1.1 maekawa 526: }
527: getMatrixOfPOLY(mat,i,j) = r;
528: }
529: }
530: return(mat);
531: }
532:
533: static int isZeroRow(mat,i)
1.3 takayama 534: struct matrixOfPOLY *mat;
535: int i;
1.1 maekawa 536: {
537: int n,j;
538: n = mat->n;
539: for (j=0; j<n; j++) {
540: if (getMatrixOfPOLY(mat,i,j) != ZERO) return(0);
541: }
542: return(1);
543: }
544:
545: void errorSyz0(s)
1.3 takayama 546: char *s;
1.1 maekawa 547: {
548: fprintf(stderr,"Error(syz0.c): %s \n",s);
549: exit(10);
550: }
551:
1.3 takayama 552:
1.1 maekawa 553: static void printMatrixOfPOLY(mat)
1.3 takayama 554: struct matrixOfPOLY *mat;
1.1 maekawa 555: {
556: int n,m,i,j;
557: POLY f;
558: m = mat->m; n = mat->n;
559: for (i=0; i<m; i++) {
560: for (j=0; j<n; j++) {
561: f = getMatrixOfPOLY(mat,i,j);
562: printf("%s, ",POLYToString(f,'*',1));
563: }
564: printf("\n");
565: }
566: printf("\n\n");
567: }
568:
569: static void printArrayOfPOLY(mat)
1.3 takayama 570: struct arrayOfPOLY *mat;
1.1 maekawa 571: {
572: int n,m,i,j;
573: POLY f;
574: m = mat->n;
575: for (i=0; i<m; i++) {
576: f = getArrayOfPOLY(mat,i);
577: printf("%s, ",POLYToString(f,'*',1));
578: }
579: printf("\n\n");
580: }
581:
582: struct matrixOfPOLY *getSyzygy01(struct gradedPolySet *reducedBasis,
1.3 takayama 583: struct pair *excludePairs)
1.1 maekawa 584: {
585: int r;
586: struct gradedPolySet *g;
587: struct gradedPairs *d;
588: int i,j;
589: int grade,indx;
590: POLY gt;
591: struct pair *top;
592: int ig,ii,jg,ji;
593: POLY gi,gj;
594: struct spValue h;
595: struct syz0 syz;
596: int pgrade = 0;
597: POLY rd;
598: POLY syzPoly;
599: POLY syzCf;
600: struct syz0 *syzp;
601: int serial;
602: struct pair *listP;
603: struct pair *listPfirst;
604: extern int Verbose;
605: extern struct ring *CurrentRingp;
606: struct polySet *ps;
607: int size;
608: int listPsize = 0;
609: struct arrayOfPOLY *vec;
610: struct matrixOfPOLY *mp;
611: extern int Sugar;
612:
613:
614: if (Debugsyz0) printf("--------------------- getSyzygy01 -----------\n");
615: if (reducedBasis == (struct gradedPolySet *)NULL)
616: return((struct matrixOfPOLY *)NULL);
617:
618: g = newGradedPolySet(reducedBasis->maxGrade+1);
619: for (i=0; i<g->lim; i++) { g->polys[i] = newPolySet(1); }
620: d = newGradedPairs((reducedBasis->maxGrade)*(reducedBasis->maxGrade)+1);
621: for (i=0; i< reducedBasis->maxGrade; i++) {
622: ps = reducedBasis->polys[i];
623: for (j=0; j< ps->size; j++) {
624: gt = ps->g[j];
625: grade=-1;whereInG(g,gt,&grade,&indx,Sugar);
626: d = updatePairs(d,gt,grade,indx,g);
627: g = putPolyInG(g,gt,grade,indx,newSyz0(),1,ps->serial[j]);
628: if (Debugsyz0) {
1.3 takayama 629: outputGradedPairs(d); outputGradedPolySet(g,1);
1.1 maekawa 630: }
631: }
632: }
633:
634: listP = newPair((struct pair *)NULL); /* A list of syzygies will be stored*/
635: listPfirst = listP;
636:
637: while ((top = getPair(d)) != (struct pair *)NULL) {
638: if (positionInPairs(top,excludePairs) < 0) {
639: ig = top->ig; ii = top->ii; /* [ig,ii] */
640: jg = top->jg; ji = top->ji; /* [jg,ji] */
641: gi = g->polys[ig]->g[ii];
642: gj = g->polys[jg]->g[ji];
643:
644: h = (*sp)(gi,gj);
645: rd = ppAddv(ppMult(h.a,gi),ppMult(h.b,gj));
646: rd = (*reduction)(rd,g,1,&syz);
647: syzPoly = syz.syz;
648: syzCf = syz.cf;
649:
650: if (KanGBmessage) {
1.3 takayama 651: if (pgrade != top->grade) {
652: pgrade = top->grade;
653: printf(" %d",pgrade);
654: fflush(stdout);
655: }else{
656: if (rd ISZERO) {
657: printf("o"); fflush(stdout);
658: }else{
659: printf("."); fflush(stdout);
660: }
661: }
1.1 maekawa 662: }
663:
664: if (!(rd ISZERO)) {
1.3 takayama 665: fprintf(stderr,"The given argument of getSyzygy01 is not a g-basis.\n");
666: return((struct matrixOfPOLY *)NULL);
1.1 maekawa 667: }else{
1.3 takayama 668: top->syz = ppAdd(toSyzPoly(h.a,ig,ii),toSyzPoly(h.b,jg,ji));
669: top->syz = cpMult(toSyzCoeff(syzCf),top->syz);
670: top->syz = ppAdd(top->syz,syzPoly);
671: listP->next = top; top->prev = listP; listP = listP->next;
672: listPsize++;
1.1 maekawa 673: }
674: }
675: }
676:
677: if (KanGBmessage) { printf("c"); fflush(stdout); }
678:
679: size = getSize00OfGradedSet(g);
680: listPfirst = listPfirst->next; /* It is the true top of sygyzies. */
681: mp = newMatrixOfPOLY(listPsize,size);
682: for (i=0; i<listPsize; i++) {
683: vec = syzPolyToArrayOfPOLY(size,listPfirst->syz,g);
684: for (j=0; j<size; j++) {
685: getMatrixOfPOLY(mp,i,j) = getArrayOfPOLY(vec,j);
686: }
687: listPfirst = listPfirst->next;
688: }
689: return(mp);
690:
691:
692: }
693:
694: static int getSize00OfGradedSet(struct gradedPolySet *g) {
695: int size;
696: int i,j;
697: struct polySet *ps;
698: size = 0;
699: if (g == (struct gradedPolySet *)NULL) return(0);
700: for (i=0; i<g->maxGrade; i++) {
701: ps = g->polys[i];
702: for (j=0; j<ps->size; j++) {
703: if (ps->del[j] == 0) {
1.3 takayama 704: size += 1;
1.1 maekawa 705: }
706: }
707: }
708: return(size);
709: }
710:
711: static int positionInPairs(struct pair *top, struct pair *pairs) {
712: struct pair *tmp;
713: int pos;
714: tmp = pairs;
715: pos = 0;
716: if (top == (struct pair *)NULL) return(-1);
717: while (tmp != (struct pair *)NULL) {
718: if (((top->ig == tmp->ig) && (top->ii == tmp->ii) &&
1.3 takayama 719: (top->jg == tmp->jg) && (top->ji == tmp->ji)) ||
720: ((top->ig == tmp->jg) && (top->ii == tmp->ji) &&
721: (top->jg == tmp->ig) && (top->ji == tmp->ii))) {
1.1 maekawa 722: return(pos);
723: }
724: pos++;
725: tmp = tmp->next;
726: }
727: return(-1);
728: }
729:
730: static struct pair *oldPairsToNewPairs(struct pair *opairs,
1.3 takayama 731: int *table,int size) {
1.1 maekawa 732: /* Never loop up prev field. */
733: int ig,ii,jg,ji;
734: int p,q;
735: struct pair *ans;
736:
737: if (opairs == (struct pair *)NULL) return((struct pair *)NULL);
738: ig = opairs->ig; ii = opairs->ii;
739: jg = opairs->jg; ji = opairs->ji;
740: for (p=0; p<size; p++) {
741: if (table[4*p] == ig && table[4*p+1] == ii ) {
742: for (q = 0; q<size; q++) {
1.3 takayama 743: if (table[4*q] == jg && table[4*q+1] == ji) {
744: ans = newPair(NULL);
745: *ans = *opairs;
746: ans->prev = NULL;
747: ans->ig = table[4*p+2]; ans->ii = table[4*p+3];
748: ans->jg = table[4*q+2]; ans->ji = table[4*q+3];
749: ans->next = oldPairsToNewPairs(opairs->next,table,size);
750: return(ans);
751: }
1.1 maekawa 752: }
753: }
754: }
755: return(oldPairsToNewPairs(opairs->next,table,size));
756: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>