Return to resol.c CVS log

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

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

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