Return to resol.c CVS log

Up to [local] / OpenXM / src / kan96xx / Kan

Annotation of OpenXM/src/kan96xx/Kan/resol.c, Revision 1.1.1.1

1.1       maekawa     1: /* resol.c */
                      2: #include <stdio.h>
                      3: #include "datatype.h"
                      4: #include "extern2.h"
                      5: #include "gradedset.h"
                      6:
                      7: #define lcomp_tower(f) ((f)==NULL? -1 : (f)->m->x[(f)->m->ringp->nn])
                      8: /* returns leading component number of POLY f, which is equal to i of ee^i */
                      9: static void shellForMonomialSyz(struct monomialSyz **p,int size);
                     10: static struct arrayOfMonomialSyz schreyerSkelton0(struct arrayOfPOLY g,int i);
                     11: static struct arrayOfMonomialSyz putMonomialSyz(struct arrayOfMonomialSyz a,
                     12:                                                struct monomialSyz *s);
                     13:
                     14: struct monomialSyz *newMonomialSyz(void)
                     15: {
                     16:   struct monomialSyz *s;
                     17:   s = (struct monomialSyz *)sGC_malloc(sizeof(struct monomialSyz));
                     18:   if (s == NULL) errorGradedSet("newMonomialSyz(): no memory.");
                     19:   s->i = s->j = -1;
                     20:   s->deleted = 0;
                     21:   s->a = POLYNULL;  s->b = POLYNULL;
                     22:   return(s);
                     23: }
                     24:
                     25: struct arrayOfMonomialSyz enlargeArrayOfMonomialSyz(struct arrayOfMonomialSyz pp)
                     26: {
                     27:   struct monomialSyz **newp;
                     28:   int i;
                     29:   int newlimit;
                     30:   if (pp.limit <= 0) newlimit = 10; else newlimit = (pp.limit)*2;
                     31:   newp = (struct monomialSyz **) sGC_malloc(sizeof(struct monomialSyz *)*newlimit);
                     32:   if (newp == NULL) errorGradedSet("enlargeArrayOfMonomialSyz(): no memory.");
                     33:   for (i=0; i< pp.size; i++) {
                     34:     newp[i] = (pp.p)[i];
                     35:   }
                     36:   for (i=pp.size ; i<newlimit; i++) newp[i] = NULL;
                     37:   pp.limit = newlimit;
                     38:   pp.p = newp;
                     39:   return(pp);
                     40: }
                     41:
                     42:
                     43: static struct arrayOfMonomialSyz schreyerSkelton0(struct arrayOfPOLY g,int i)
                     44: /* return value will be changed by the next call of this function. */
                     45: {
                     46:   int m,j,k;
                     47:   static int s_ij_size = 0;
                     48:   static struct monomialSyz **s_ij = NULL;
                     49:   struct monomialSyz *s;
                     50:   struct spValue sv;
                     51:   struct arrayOfMonomialSyz ans;
                     52:
                     53:   m = g.n;
                     54:   if (m > s_ij_size) {
                     55:     s_ij_size = m+1;
                     56:     s_ij = (struct monomialSyz **)sGC_malloc(sizeof(struct monomialSyz *)*
                     57:                                            s_ij_size);
                     58:     if (s_ij == NULL) errorGradedSet("schreyerSkelton(): no memory");
                     59:   }
                     60:   for (j=i+1; j<m; j++) {
                     61:     s_ij[j-i-1] = s = newMonomialSyz();
                     62:     s->i = i; s->j = j;
                     63:     if ((*isSameComponent)((g.array)[i],(g.array)[j])) {
                     64:       s->deleted = 0;
                     65:       sv = (*sp)((g.array)[i],(g.array)[j]);
                     66:       s->a = sv.a; s->b = sv.b;
                     67:     }else{
                     68:       s->deleted = 1;
                     69:     }
                     70:   }
                     71:   shellForMonomialSyz(s_ij,m-i-1);
                     72:   for (j=0; j<m-i-1;j++) {
                     73:     s = s_ij[j];
                     74:     if (s->deleted != 1) {
                     75:       for (k=j+1; k<m-i-1; k++) {
                     76:        if (s_ij[k]->deleted != 1) {
                     77:          if ((*isReducible)(s_ij[k]->a,s->a)) s_ij[k]->deleted = 1;
                     78:        }
                     79:       }
                     80:     }
                     81:   }
                     82:   ans.size = m-i-1;
                     83:   ans.limit = s_ij_size;
                     84:   ans.p = s_ij;
                     85:   return(ans);
                     86: }
                     87:
                     88: static struct arrayOfMonomialSyz putMonomialSyz(struct arrayOfMonomialSyz a,
                     89:                                                struct monomialSyz *s)
                     90: {
                     91:   if (a.limit <= a.size) {
                     92:     a = enlargeArrayOfMonomialSyz(a);
                     93:   }
                     94:   (a.p)[a.size] = s;
                     95:   a.size = a.size+1;
                     96:   return(a);
                     97: }
                     98:
                     99:
                    100:
                    101: struct arrayOfMonomialSyz schreyerSkelton(struct arrayOfPOLY g)
                    102: {
                    103:   int i,k,m;
                    104:   struct arrayOfMonomialSyz ans;
                    105:   struct arrayOfMonomialSyz ipart;
                    106:   ans.size = 0;
                    107:   ans.limit = 0;
                    108:   ans.p = NULL;
                    109:
                    110:   m = g.n;
                    111:   for (i=0;  i<m; i++ ) {
                    112:     ipart = schreyerSkelton0(g,i);
                    113:     for (k=0; k< ipart.size; k++) {
                    114:       if ((ipart.p)[k]->deleted != 1) {
                    115:        ans = putMonomialSyz(ans,(ipart.p)[k]);
                    116:       }
                    117:     }
                    118:   }
                    119:   shellForMonomialSyz(ans.p, ans.size);
                    120:   return(ans);
                    121: }
                    122:
                    123: static void shellForMonomialSyz(struct monomialSyz **p,int n)
                    124: {
                    125:   int gap, i, j, r;
                    126:   struct monomialSyz *temp;
                    127:   for (gap = n/2; gap > 0; gap /= 2) {
                    128:     for (i = gap; i < n; i++) {
                    129:       for (j = i - gap ; j >= 0; j -= gap) {
                    130:        r = (*mmLarger)(p[j+gap]->a, p[j]->a);
                    131:        if ( r >= 1) break;
                    132:        temp = p[j];
                    133:        p[j] = p[j+gap];
                    134:        p[j+gap] = temp;
                    135:       }
                    136:     }
                    137:   }
                    138: }