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