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     ! 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: }