Return to resol.c CVS log

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

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

1.5     ! takayama    1: /* $OpenXM: OpenXM/src/kan96xx/Kan/resol.c,v 1.4 2000/06/26 11:15:04 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: {
1.5     ! takayama   49:   int m,j,k,flag;
1.1       maekawa    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) {
1.5     ! takayama   78:        do {
        !            79:          flag = 0;
        !            80:       for (j=0; j<m-i-1;j++) {
        !            81:                if (s_ij[j]->deleted != 1) {
        !            82:                  for (k=0; k<m-i-1;k++) {
        !            83:                        if ((j != k) && (s_ij[k]->deleted != 1)) {
        !            84:                          if ((*isReducible)(s_ij[k]->a,s_ij[j]->a)) {
        !            85:                                s_ij[k]->deleted = 1;
        !            86:                                flag = 1;
        !            87:                          }
        !            88:                        }
        !            89:                  }
        !            90:                }
        !            91:          }
        !            92:        }while (flag);
1.1       maekawa    93:   }
                     94:   ans.size = m-i-1;
                     95:   ans.limit = s_ij_size;
                     96:   ans.p = s_ij;
                     97:   return(ans);
                     98: }
                     99:
                    100: static struct arrayOfMonomialSyz putMonomialSyz(struct arrayOfMonomialSyz a,
                    101:                                                struct monomialSyz *s)
                    102: {
                    103:   if (a.limit <= a.size) {
                    104:     a = enlargeArrayOfMonomialSyz(a);
                    105:   }
                    106:   (a.p)[a.size] = s;
                    107:   a.size = a.size+1;
                    108:   return(a);
                    109: }
                    110:
                    111:
                    112:
                    113: struct arrayOfMonomialSyz schreyerSkelton(struct arrayOfPOLY g)
                    114: {
                    115:   int i,k,m;
                    116:   struct arrayOfMonomialSyz ans;
                    117:   struct arrayOfMonomialSyz ipart;
                    118:   ans.size = 0;
                    119:   ans.limit = 0;
                    120:   ans.p = NULL;
                    121:
                    122:   m = g.n;
                    123:   for (i=0;  i<m; i++ ) {
                    124:     ipart = schreyerSkelton0(g,i);
                    125:     for (k=0; k< ipart.size; k++) {
                    126:       if ((ipart.p)[k]->deleted != 1) {
1.3       takayama  127:         ans = putMonomialSyz(ans,(ipart.p)[k]);
1.1       maekawa   128:       }
                    129:     }
                    130:   }
                    131:   shellForMonomialSyz(ans.p, ans.size);
                    132:   return(ans);
                    133: }
                    134:
                    135: static void shellForMonomialSyz(struct monomialSyz **p,int n)
                    136: {
                    137:   int gap, i, j, r;
                    138:   struct monomialSyz *temp;
                    139:   for (gap = n/2; gap > 0; gap /= 2) {
                    140:     for (i = gap; i < n; i++) {
                    141:       for (j = i - gap ; j >= 0; j -= gap) {
                    142:        r = (*mmLarger)(p[j+gap]->a, p[j]->a);
                    143:        if ( r >= 1) break;
                    144:        temp = p[j];
                    145:        p[j] = p[j+gap];
                    146:        p[j+gap] = temp;
                    147:       }
                    148:     }
                    149:   }
                    150: }