Annotation of OpenXM/src/kan96xx/Kan/syz0.c, Revision 1.3
1.3 ! takayama 1: /* $OpenXM: OpenXM/src/kan96xx/Kan/syz0.c,v 1.2 2000/01/16 07:55:41 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);
240: if (KanGBmessage) {printf("#"); fflush(stdout); }
241:
242: /* We compute E-CB. The number of G (G-basis) is serial. */
243: /* F = - C G, G = B F , then F + CB F = 0*/
244: b = getBackwardMatrixOfPOLY(grG);
245: nc = getNC(newG,serial,*grBasesp);
246: dc = getDC(newG);
247: /*{
248: printf("\nb=\n"); printMatrixOfPOLY(b);
249: printf("\n\nnc=\n"); printMatrixOfPOLY(nc);
250: printf("\n\ndc=\n"); printArrayOfPOLY(dc);
1.3 ! takayama 251: }*/
1.1 maekawa 252:
253: if (KanGBmessage) {printf(":"); fflush(stdout);}
254: m2 = getSyzygy1(b,nc,dc);
255: *backwardMatp = b;
256:
257: /* mp is the syzygy of the G-basis. */
258: mp = newMatrixOfPOLY(ap->n,serial);
259: for (i=0; i < ap->n; i++) {
260: vec = syzPolyToArrayOfPOLY(serial,getArrayOfPOLY(ap,i),*grBasesp);
261: for (j=0; j < serial; j++) {
262: getMatrixOfPOLY(mp,i,j) = getArrayOfPOLY(vec,j);
263: }
264: }
265: /*printf(" ap->n = %d, serial=%d \n",ap->n, serial);
1.3 ! takayama 266: printf("\nmp = \n"); printMatrixOfPOLY(mp); */
1.1 maekawa 267:
268: if (KanGBmessage) {printf(";"); fflush(stdout);}
269: m1 = aaMult(mp,b);
270: m0 = aaMult(mp0,b);
271: /* printf("\nm0 = \n"); printMatrixOfPOLY(m0); */
272:
273: ans = newMatrixOfPOLY((m0->m)+(m1->m)+(m2->m),m2->n);
274: kk = 0;
275: for (i=0; i<m0->m; i++) {
276: if (!isZeroRow(m0,i)) {
277: for (j=0; j<m0->n; j++) {
1.3 ! takayama 278: getMatrixOfPOLY(ans,kk,j) = getMatrixOfPOLY(m0,i,j);
1.1 maekawa 279: }
280: kk++;
281: }
282: }
283: for (i=0; i<m1->m; i++) {
284: if (!isZeroRow(m1,i)) {
285: for (j=0; j<m1->n; j++) {
1.3 ! takayama 286: getMatrixOfPOLY(ans,kk,j) = getMatrixOfPOLY(m1,i,j);
1.1 maekawa 287: }
288: kk++;
289: }
290: }
291: for (i=0; i<m2->m; i++) {
292: if (!isZeroRow(m2,i)) {
293: for (j=0; j<m2->n; j++) {
1.3 ! takayama 294: getMatrixOfPOLY(ans,kk,j) = getMatrixOfPOLY(m2,i,j);
1.1 maekawa 295: }
296: kk++; if (KanGBmessage) printf("*");
297: }
298: }
299: if (kk != ans->m) {
300: ans2 = newMatrixOfPOLY(kk,ans->n);
301: for (i=0; i<kk; i++) {
302: for (j=0; j<ans->n; j++) {
1.3 ! takayama 303: getMatrixOfPOLY(ans2,i,j) = getMatrixOfPOLY(ans,i,j);
1.1 maekawa 304: }
305: }
306: return(ans2);
307: }else{
308: return(ans);
309: }
310:
311: }
312:
313: POLY getSyzPolyFromSp(spij,grG)
1.3 ! takayama 314: struct pair *spij;
! 315: struct gradedPolySet *grG;
1.1 maekawa 316: {
317: int ig,ii,jg,ji;
318: POLY dk;
319: POLY f;
320: POLY t,ans;
321: int grd,indx;
322:
323: ig = spij->ig; ii = spij->ii;
324: jg = spij->jg; ji = spij->ji;
325: if (grG->polys[ig]->del[ii] != 0 || grG->polys[jg]->del[ji] != 0)
326: return(ZERO);
327: dk = spij->syz; /* in SyzRing */
328: clearMark(grG);
329: f = dk;
330: while (f != POLYNULL) {
331: grd = srGrade(f);
332: indx = srIndex(f);
333: grG->polys[grd]->mark[indx] = 1;
334: f=f->next;
335: }
336:
337: f = dk; ans = ZERO;
338: while (f != POLYNULL) {
339: grd = srGrade(f);
340: indx = srIndex(f);
341: t = grG->polys[grd]->syz[indx]->syz;
342: t = cpMult(f->coeffp,t);
343: t = cpMult(toSyzCoeff(getFactor0(grG,grd,indx)),t);
344: ans = ppAdd(ans,t);
345: f = f->next;
346: }
347: return(ans);
348: }
349:
350: static void clearMark(grG)
1.3 ! takayama 351: struct gradedPolySet *grG;
1.1 maekawa 352: {
353: int i,j;
354: struct polySet *ps;
355: for (i=0; i<grG->maxGrade; i++) {
356: ps = grG->polys[i];
357: for (j=0; j<ps->size; j++) {
358: ps->mark[j] = 0;
359: }
360: }
361: }
362:
363:
364: struct arrayOfPOLY *syzPolyToArrayOfPOLY(size,f,grG)
1.3 ! takayama 365: int size;
! 366: POLY f; /* f is in the SyzRingp */
! 367: struct gradedPolySet *grG;
1.1 maekawa 368: {
369: struct arrayOfPOLY *ap;
370: int i,g0,i0,serial;
371:
372: ap = newArrayOfPOLY(size);
373: for (i=0; i<size; i++) {
374: getArrayOfPOLY(ap,i) = ZERO;
375: }
376:
377: while (f != POLYNULL) {
378: g0 = srGrade(f);
379: i0 = srIndex(f);
380: serial = grG->polys[g0]->serial[i0];
381: if (serial < 0) {
382: errorSyz0("syzPolyToArrayOfPOLY(): invalid serial[i] of grG.");
383: }
384: if (getArrayOfPOLY(ap,serial) != ZERO) {
385: errorSyz0("syzPolyToArrayOfPOLY(): syzygy polynomial is broken.");
386: }
387: getArrayOfPOLY(ap,serial) = srSyzCoeffToPOLY(f->coeffp);
388: f = f->next;
389: }
390: return(ap);
391: }
392:
393:
394:
395: struct matrixOfPOLY *getBackwardMatrixOfPOLY(struct gradedPolySet *grG)
396: {
397: /* use serial, del. cf. getBackwardArray() */
398: int inputSize,outputSize;
399: int i,j,k,p;
400: struct arrayOfPOLY *vec;
401: struct matrixOfPOLY *mat;
402: struct polySet *ps;
403:
404: inputSize = 0; outputSize = 0;
405: for (i=0; i<grG->maxGrade; i++) {
406: ps = grG->polys[i];
407: for (j=0; j<ps->size; j++) {
408: if (ps->serial[j] >= 0) ++inputSize;
409: if (ps->del[j] == 0) ++outputSize;
410: }
411: }
412:
413: mat = newMatrixOfPOLY(outputSize,inputSize);
414: k = 0;
415: for (i=0; i<grG->maxGrade; i++) {
416: ps = grG->polys[i];
417: for (j=0; j<ps->size; j++) {
418: if (ps->del[j] == 0) {
1.3 ! takayama 419: vec = syzPolyToArrayOfPOLY(inputSize,ps->syz[j]->syz,grG);
! 420: for (p=0; p<inputSize; p++) {
! 421: getMatrixOfPOLY(mat,k,p)=getArrayOfPOLY(vec,p);
! 422: }
! 423: k++;
1.1 maekawa 424: }
425: }
426: }
427: return(mat);
428: }
429:
430:
431: struct matrixOfPOLY *getNC(newG,n,grBases)
1.3 ! takayama 432: struct gradedPolySet *newG; /* F is stored and indexed by serial. */
! 433: int n; /* The number of G. */
! 434: struct gradedPolySet *grBases; /* G (G-basis) is stored. */
1.1 maekawa 435: {
436: int size,i,j,k,ii;
437: struct matrixOfPOLY *mat;
438: struct polySet *ps;
439: struct arrayOfPOLY *vec;
440:
441: if (newG == (struct gradedPolySet *)NULL) {
442: return(newMatrixOfPOLY(0,0));
443: }
444: size = 0;
445: for (i=0; i<newG->maxGrade; i++) {
446: ps = newG->polys[i];
447: for (j=0; j<ps->size; j++) {
448: if (ps->serial[j] >= 0) size++;
449: }
450: }
451: mat = newMatrixOfPOLY(size,n);
452: for (i=0; i<newG->maxGrade; i++) {
453: ps = newG->polys[i];
454: for (j=0; j<ps->size; j++) {
455: if (ps->serial[j] >= 0) {
1.3 ! takayama 456: ii = ps->serial[j];
! 457: vec = syzPolyToArrayOfPOLY(n,ps->syz[j]->syz,grBases);
! 458: for (k=0; k<n; k++) {
! 459: getMatrixOfPOLY(mat,ii,k) = getArrayOfPOLY(vec,k);
! 460: }
1.1 maekawa 461: }
462: }
463: }
464: return(mat);
465: }
466:
467: struct arrayOfPOLY *getDC(newG)
1.3 ! takayama 468: struct gradedPolySet *newG; /* F is stored and indexed by serial. */
1.1 maekawa 469: {
470: int size,i,j,k,ii;
471: struct arrayOfPOLY *mat;
472: struct polySet *ps;
473: extern struct ring *CurrentRingp;
474:
475: if (newG == (struct gradedPolySet *)NULL) {
476: return(newArrayOfPOLY(0));
477: }
478: size = 0;
479: for (i=0; i<newG->maxGrade; i++) {
480: ps = newG->polys[i];
481: for (j=0; j<ps->size; j++) {
482: if (ps->serial[j] >= 0) size++;
483: }
484: }
485: mat = newArrayOfPOLY(size);
486: for (i=0; i<newG->maxGrade; i++) {
487: ps = newG->polys[i];
488: for (j=0; j<ps->size; j++) {
489: if (ps->serial[j] >= 0) {
1.3 ! takayama 490: ii = ps->serial[j];
! 491: getArrayOfPOLY(mat,ii) = ps->syz[j]->cf;
1.1 maekawa 492: }
493: }
494: }
495: return(mat);
496: }
497:
498:
499:
500: /* Syzygy from E-CB */
501: struct matrixOfPOLY *getSyzygy1(b,nc,dc)
1.3 ! takayama 502: struct matrixOfPOLY *b;
! 503: struct matrixOfPOLY *nc;
! 504: struct arrayOfPOLY *dc;
1.1 maekawa 505: {
506: int m,n2,n;
507: struct matrixOfPOLY *mat;
508: int i,j,k;
509: POLY r;
510: POLY tmp;
511:
512: m = nc->m;
513: n2 = nc->n;
514: n = b->n;
515: mat = newMatrixOfPOLY(m,n);
516: for (i=0; i<m; i++) {
517: for (j=0; j<n; j++) {
518: r = ZERO;
519: if (i == j) {
1.3 ! takayama 520: r = getArrayOfPOLY(dc,i);
1.1 maekawa 521: }
522: for (k=0; k<n2; k++) {
1.3 ! takayama 523: tmp = ppMult(getMatrixOfPOLY(nc,i,k),getMatrixOfPOLY(b,k,j));
! 524: r = ppAdd(r,tmp);
1.1 maekawa 525: }
526: getMatrixOfPOLY(mat,i,j) = r;
527: }
528: }
529: return(mat);
530: }
531:
532: static int isZeroRow(mat,i)
1.3 ! takayama 533: struct matrixOfPOLY *mat;
! 534: int i;
1.1 maekawa 535: {
536: int n,j;
537: n = mat->n;
538: for (j=0; j<n; j++) {
539: if (getMatrixOfPOLY(mat,i,j) != ZERO) return(0);
540: }
541: return(1);
542: }
543:
544: void errorSyz0(s)
1.3 ! takayama 545: char *s;
1.1 maekawa 546: {
547: fprintf(stderr,"Error(syz0.c): %s \n",s);
548: exit(10);
549: }
550:
1.3 ! takayama 551:
1.1 maekawa 552: static void printMatrixOfPOLY(mat)
1.3 ! takayama 553: struct matrixOfPOLY *mat;
1.1 maekawa 554: {
555: int n,m,i,j;
556: POLY f;
557: m = mat->m; n = mat->n;
558: for (i=0; i<m; i++) {
559: for (j=0; j<n; j++) {
560: f = getMatrixOfPOLY(mat,i,j);
561: printf("%s, ",POLYToString(f,'*',1));
562: }
563: printf("\n");
564: }
565: printf("\n\n");
566: }
567:
568: static void printArrayOfPOLY(mat)
1.3 ! takayama 569: struct arrayOfPOLY *mat;
1.1 maekawa 570: {
571: int n,m,i,j;
572: POLY f;
573: m = mat->n;
574: for (i=0; i<m; i++) {
575: f = getArrayOfPOLY(mat,i);
576: printf("%s, ",POLYToString(f,'*',1));
577: }
578: printf("\n\n");
579: }
580:
581: struct matrixOfPOLY *getSyzygy01(struct gradedPolySet *reducedBasis,
1.3 ! takayama 582: struct pair *excludePairs)
1.1 maekawa 583: {
584: int r;
585: struct gradedPolySet *g;
586: struct gradedPairs *d;
587: int i,j;
588: int grade,indx;
589: POLY gt;
590: struct pair *top;
591: int ig,ii,jg,ji;
592: POLY gi,gj;
593: struct spValue h;
594: struct syz0 syz;
595: int pgrade = 0;
596: POLY rd;
597: POLY syzPoly;
598: POLY syzCf;
599: struct syz0 *syzp;
600: int serial;
601: struct pair *listP;
602: struct pair *listPfirst;
603: extern int Verbose;
604: extern struct ring *CurrentRingp;
605: struct polySet *ps;
606: int size;
607: int listPsize = 0;
608: struct arrayOfPOLY *vec;
609: struct matrixOfPOLY *mp;
610: extern int Sugar;
611:
612:
613: if (Debugsyz0) printf("--------------------- getSyzygy01 -----------\n");
614: if (reducedBasis == (struct gradedPolySet *)NULL)
615: return((struct matrixOfPOLY *)NULL);
616:
617: g = newGradedPolySet(reducedBasis->maxGrade+1);
618: for (i=0; i<g->lim; i++) { g->polys[i] = newPolySet(1); }
619: d = newGradedPairs((reducedBasis->maxGrade)*(reducedBasis->maxGrade)+1);
620: for (i=0; i< reducedBasis->maxGrade; i++) {
621: ps = reducedBasis->polys[i];
622: for (j=0; j< ps->size; j++) {
623: gt = ps->g[j];
624: grade=-1;whereInG(g,gt,&grade,&indx,Sugar);
625: d = updatePairs(d,gt,grade,indx,g);
626: g = putPolyInG(g,gt,grade,indx,newSyz0(),1,ps->serial[j]);
627: if (Debugsyz0) {
1.3 ! takayama 628: outputGradedPairs(d); outputGradedPolySet(g,1);
1.1 maekawa 629: }
630: }
631: }
632:
633: listP = newPair((struct pair *)NULL); /* A list of syzygies will be stored*/
634: listPfirst = listP;
635:
636: while ((top = getPair(d)) != (struct pair *)NULL) {
637: if (positionInPairs(top,excludePairs) < 0) {
638: ig = top->ig; ii = top->ii; /* [ig,ii] */
639: jg = top->jg; ji = top->ji; /* [jg,ji] */
640: gi = g->polys[ig]->g[ii];
641: gj = g->polys[jg]->g[ji];
642:
643: h = (*sp)(gi,gj);
644: rd = ppAddv(ppMult(h.a,gi),ppMult(h.b,gj));
645: rd = (*reduction)(rd,g,1,&syz);
646: syzPoly = syz.syz;
647: syzCf = syz.cf;
648:
649: if (KanGBmessage) {
1.3 ! takayama 650: if (pgrade != top->grade) {
! 651: pgrade = top->grade;
! 652: printf(" %d",pgrade);
! 653: fflush(stdout);
! 654: }else{
! 655: if (rd ISZERO) {
! 656: printf("o"); fflush(stdout);
! 657: }else{
! 658: printf("."); fflush(stdout);
! 659: }
! 660: }
1.1 maekawa 661: }
662:
663: if (!(rd ISZERO)) {
1.3 ! takayama 664: fprintf(stderr,"The given argument of getSyzygy01 is not a g-basis.\n");
! 665: return((struct matrixOfPOLY *)NULL);
1.1 maekawa 666: }else{
1.3 ! takayama 667: top->syz = ppAdd(toSyzPoly(h.a,ig,ii),toSyzPoly(h.b,jg,ji));
! 668: top->syz = cpMult(toSyzCoeff(syzCf),top->syz);
! 669: top->syz = ppAdd(top->syz,syzPoly);
! 670: listP->next = top; top->prev = listP; listP = listP->next;
! 671: listPsize++;
1.1 maekawa 672: }
673: }
674: }
675:
676: if (KanGBmessage) { printf("c"); fflush(stdout); }
677:
678: size = getSize00OfGradedSet(g);
679: listPfirst = listPfirst->next; /* It is the true top of sygyzies. */
680: mp = newMatrixOfPOLY(listPsize,size);
681: for (i=0; i<listPsize; i++) {
682: vec = syzPolyToArrayOfPOLY(size,listPfirst->syz,g);
683: for (j=0; j<size; j++) {
684: getMatrixOfPOLY(mp,i,j) = getArrayOfPOLY(vec,j);
685: }
686: listPfirst = listPfirst->next;
687: }
688: return(mp);
689:
690:
691: }
692:
693: static int getSize00OfGradedSet(struct gradedPolySet *g) {
694: int size;
695: int i,j;
696: struct polySet *ps;
697: size = 0;
698: if (g == (struct gradedPolySet *)NULL) return(0);
699: for (i=0; i<g->maxGrade; i++) {
700: ps = g->polys[i];
701: for (j=0; j<ps->size; j++) {
702: if (ps->del[j] == 0) {
1.3 ! takayama 703: size += 1;
1.1 maekawa 704: }
705: }
706: }
707: return(size);
708: }
709:
710: static int positionInPairs(struct pair *top, struct pair *pairs) {
711: struct pair *tmp;
712: int pos;
713: tmp = pairs;
714: pos = 0;
715: if (top == (struct pair *)NULL) return(-1);
716: while (tmp != (struct pair *)NULL) {
717: if (((top->ig == tmp->ig) && (top->ii == tmp->ii) &&
1.3 ! takayama 718: (top->jg == tmp->jg) && (top->ji == tmp->ji)) ||
! 719: ((top->ig == tmp->jg) && (top->ii == tmp->ji) &&
! 720: (top->jg == tmp->ig) && (top->ji == tmp->ii))) {
1.1 maekawa 721: return(pos);
722: }
723: pos++;
724: tmp = tmp->next;
725: }
726: return(-1);
727: }
728:
729: static struct pair *oldPairsToNewPairs(struct pair *opairs,
1.3 ! takayama 730: int *table,int size) {
1.1 maekawa 731: /* Never loop up prev field. */
732: int ig,ii,jg,ji;
733: int p,q;
734: struct pair *ans;
735:
736: if (opairs == (struct pair *)NULL) return((struct pair *)NULL);
737: ig = opairs->ig; ii = opairs->ii;
738: jg = opairs->jg; ji = opairs->ji;
739: for (p=0; p<size; p++) {
740: if (table[4*p] == ig && table[4*p+1] == ii ) {
741: for (q = 0; q<size; q++) {
1.3 ! takayama 742: if (table[4*q] == jg && table[4*q+1] == ji) {
! 743: ans = newPair(NULL);
! 744: *ans = *opairs;
! 745: ans->prev = NULL;
! 746: ans->ig = table[4*p+2]; ans->ii = table[4*p+3];
! 747: ans->jg = table[4*q+2]; ans->ji = table[4*q+3];
! 748: ans->next = oldPairsToNewPairs(opairs->next,table,size);
! 749: return(ans);
! 750: }
1.1 maekawa 751: }
752: }
753: }
754: return(oldPairsToNewPairs(opairs->next,table,size));
755: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>