Return to resol.c CVS log

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

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

1.4     ! takayama    1: /* $OpenXM: OpenXM/src/kan96xx/Kan/resol.c,v 1.3 2000/05/24 15:31:29 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;
1.4     ! takayama   72:          /* If isConstant(sv.a) is added, (x^3 - y^2 z^2) deRham stops
        !            73:          with an error. I've not yet understood the reason.
        !            74:          At Posthouse at Heathrow. June 24, 2000 */
        !            75:          if (isConstant(sv.b)) {
        !            76:                s->deleted = 1;
        !            77:          }
1.1       maekawa    78:     }else{
                     79:       s->deleted = 1;
                     80:     }
                     81:   }
                     82:   shellForMonomialSyz(s_ij,m-i-1);
1.3       takayama   83:   if (RemoveRedundantInSchreyerSkelton) {
                     84:    for (j=0; j<m-i-1;j++) {
1.1       maekawa    85:     s = s_ij[j];
                     86:     if (s->deleted != 1) {
                     87:       for (k=j+1; k<m-i-1; k++) {
1.3       takayama   88:         if (s_ij[k]->deleted != 1) {
                     89:           if ((*isReducible)(s_ij[k]->a,s->a)) s_ij[k]->deleted = 1;
                     90:         }
1.1       maekawa    91:       }
                     92:     }
1.3       takayama   93:    }
1.1       maekawa    94:   }
                     95:   ans.size = m-i-1;
                     96:   ans.limit = s_ij_size;
                     97:   ans.p = s_ij;
                     98:   return(ans);
                     99: }
                    100:
                    101: static struct arrayOfMonomialSyz putMonomialSyz(struct arrayOfMonomialSyz a,
                    102:                                                struct monomialSyz *s)
                    103: {
                    104:   if (a.limit <= a.size) {
                    105:     a = enlargeArrayOfMonomialSyz(a);
                    106:   }
                    107:   (a.p)[a.size] = s;
                    108:   a.size = a.size+1;
                    109:   return(a);
                    110: }
                    111:
                    112:
                    113:
                    114: struct arrayOfMonomialSyz schreyerSkelton(struct arrayOfPOLY g)
                    115: {
                    116:   int i,k,m;
                    117:   struct arrayOfMonomialSyz ans;
                    118:   struct arrayOfMonomialSyz ipart;
                    119:   ans.size = 0;
                    120:   ans.limit = 0;
                    121:   ans.p = NULL;
                    122:
                    123:   m = g.n;
                    124:   for (i=0;  i<m; i++ ) {
                    125:     ipart = schreyerSkelton0(g,i);
                    126:     for (k=0; k< ipart.size; k++) {
                    127:       if ((ipart.p)[k]->deleted != 1) {
1.3       takayama  128:         ans = putMonomialSyz(ans,(ipart.p)[k]);
1.1       maekawa   129:       }
                    130:     }
                    131:   }
                    132:   shellForMonomialSyz(ans.p, ans.size);
                    133:   return(ans);
                    134: }
                    135:
                    136: static void shellForMonomialSyz(struct monomialSyz **p,int n)
                    137: {
                    138:   int gap, i, j, r;
                    139:   struct monomialSyz *temp;
                    140:   for (gap = n/2; gap > 0; gap /= 2) {
                    141:     for (i = gap; i < n; i++) {
                    142:       for (j = i - gap ; j >= 0; j -= gap) {
                    143:        r = (*mmLarger)(p[j+gap]->a, p[j]->a);
                    144:        if ( r >= 1) break;
                    145:        temp = p[j];
                    146:        p[j] = p[j+gap];
                    147:        p[j+gap] = temp;
                    148:       }
                    149:     }
                    150:   }
                    151: }