Return to resol.c CVS log

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

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

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