[BACK]Return to redm.c CVS log [TXT][DIR] Up to [local] / OpenXM / src / kan96xx / Kan

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

1.5     ! takayama    1: /* $OpenXM: OpenXM/src/kan96xx/Kan/redm.c,v 1.4 2003/07/10 08:20:05 takayama Exp $ */
1.1       maekawa     2: #include <stdio.h>
                      3: #include "datatype.h"
                      4: #include "extern2.h"
                      5: #include "gradedset.h"
                      6:
                      7: #define mymax(p,q) (p>q?p:q)
                      8:
                      9: static int DebugReduction = 0;
                     10:
                     11:
                     12: int isReducible_module(f,g)
1.3       takayama   13:      POLY f;
                     14:      POLY g;
1.1       maekawa    15: {
                     16:   int n,i;
                     17:   MONOMIAL tf;
                     18:   MONOMIAL tg;
                     19:
                     20:   if (f ISZERO) return(0);
                     21:   if (g ISZERO) return(0);
                     22:
                     23:   checkRingIsR(f,g);
                     24:
                     25:   if (!(*isSameComponent)(f,g)) return(0);
                     26:   tf = f->m; tg = g->m; n = tf->ringp->n;
                     27:   for (i=0; i<n; i++) {
                     28:     if (tf->e[i].x < tg->e[i].x) return(0);
                     29:     if (tf->e[i].D < tg->e[i].D) return(0);
                     30:   }
                     31:   return(1);
                     32: }
                     33:
                     34:
                     35: int isSameComponent_x(f,g)
1.3       takayama   36:      POLY f;
                     37:      POLY g;
1.1       maekawa    38: {
                     39:   static int nn,mm,ll,cc,n,m,l,c;
                     40:   static struct ring *cr = (struct ring *)NULL;
                     41:   MONOMIAL tf;
                     42:   MONOMIAL tg;
                     43:   int i;
                     44:
                     45:   if (f ISZERO) return(1);
                     46:   if (g ISZERO) return(1);
                     47:
                     48:   tf = f->m; tg = g->m;
                     49:   if (tf->ringp != cr) {
                     50:     n = tf->ringp->n;
                     51:     m = tf->ringp->m;
                     52:     l = tf->ringp->l;
                     53:     c = tf->ringp->c;
                     54:     nn = tf->ringp->nn;
                     55:     mm = tf->ringp->mm;
                     56:     ll = tf->ringp->ll;
                     57:     cc = tf->ringp->cc;
                     58:     cr = tf->ringp;
                     59:   }
                     60:   for (i=cc; i<c; i++) {
                     61:     if (tf->e[i].x != tg->e[i].x) return(0);
                     62:     if (tf->e[i].D != tg->e[i].D) return(0);
                     63:   }
                     64:   for (i=ll; i<l; i++) {
                     65:     if (tf->e[i].x != tg->e[i].x) return(0);
                     66:     /*if (tf->e[i].D != tg->e[i].D) return(0);*/
                     67:   }
                     68:   for (i=mm; i<m; i++) {
                     69:     if (tf->e[i].x != tg->e[i].x) return(0);
                     70:     /*if (tf->e[i].D != tg->e[i].D) return(0);*/
                     71:   }
                     72:   for (i=nn; i<n; i++) {
                     73:     if (tf->e[i].x != tg->e[i].x) return(0);
                     74:     /*if (tf->e[i].D != tg->e[i].D) return(0);*/
                     75:   }
                     76:   return(1);
                     77: }
                     78:
                     79: int isSameComponent_xd(f,g)
1.3       takayama   80:      POLY f;
                     81:      POLY g;
1.1       maekawa    82: {
                     83:   static int nn,mm,ll,cc,n,m,l,c;
                     84:   static struct ring *cr = (struct ring *)NULL;
                     85:   MONOMIAL tf;
                     86:   MONOMIAL tg;
                     87:   int i;
                     88:
                     89:   if (f ISZERO) return(1);
                     90:   if (g ISZERO) return(1);
                     91:
                     92:   tf = f->m; tg = g->m;
                     93:   if (tf->ringp != cr) {
                     94:     n = tf->ringp->n;
                     95:     m = tf->ringp->m;
                     96:     l = tf->ringp->l;
                     97:     c = tf->ringp->c;
                     98:     nn = tf->ringp->nn;
                     99:     mm = tf->ringp->mm;
                    100:     ll = tf->ringp->ll;
                    101:     cc = tf->ringp->cc;
                    102:     cr = tf->ringp;
                    103:   }
                    104:   for (i=cc; i<c; i++) {
                    105:     if (tf->e[i].x != tg->e[i].x) return(0);
                    106:     if (tf->e[i].D != tg->e[i].D) return(0);
                    107:   }
                    108:   for (i=ll; i<l; i++) {
                    109:     if (tf->e[i].x != tg->e[i].x) return(0);
                    110:     if (tf->e[i].D != tg->e[i].D) return(0);
                    111:   }
                    112:   for (i=mm; i<m; i++) {
                    113:     if (tf->e[i].x != tg->e[i].x) return(0);
                    114:     if (tf->e[i].D != tg->e[i].D) return(0);
                    115:   }
                    116:   for (i=nn; i<n; i++) {
                    117:     if (tf->e[i].x != tg->e[i].x) return(0);
                    118:     if (tf->e[i].D != tg->e[i].D) return(0);
                    119:   }
                    120:   return(1);
                    121: }
                    122:
                    123:
                    124: POLY lcm_module(f,g)
1.3       takayama  125:      POLY f;
                    126:      POLY g;
1.1       maekawa   127: {
                    128:   MONOMIAL tf,tg;
                    129:   MONOMIAL lcm;
                    130:   int n;
                    131:   int i;
                    132:
                    133:   tf = f->m; tg = g->m;
                    134:   if (!(*isSameComponent)(f,g)) return(ZERO);
                    135:   n = tf->ringp->n;
                    136:   lcm = newMonomial(tf->ringp);
                    137:   for (i=0; i<n; i++) {
                    138:     lcm->e[i].x = mymax(tf->e[i].x,tg->e[i].x);
                    139:     lcm->e[i].D = mymax(tf->e[i].D,tg->e[i].D);
                    140:   }
                    141:   return(newCell(intToCoeff(1,tf->ringp),lcm));
                    142: }
                    143:
                    144:
                    145: int grade_module1v(f)
1.3       takayama  146:      POLY f;
1.1       maekawa   147: {
                    148:   int r;
                    149:   int i;
                    150:   MONOMIAL tf;
                    151:   static int nn,mm,ll,cc,n,m,l,c;
                    152:   static struct ring *cr = (struct ring *)NULL;
                    153:
                    154:   if (f ISZERO) return(-1);
                    155:   tf = f->m;
                    156:   if (tf->ringp != cr) {
                    157:     n = tf->ringp->n;
                    158:     m = tf->ringp->m;
                    159:     l = tf->ringp->l;
                    160:     c = tf->ringp->c;
                    161:     nn = tf->ringp->nn;
                    162:     mm = tf->ringp->mm;
                    163:     ll = tf->ringp->ll;
                    164:     cc = tf->ringp->cc;
                    165:     cr = tf->ringp;
                    166:   }
                    167:
                    168:   r = 0;
                    169:   for (i=0; i<cc; i++) {
                    170:     r += tf->e[i].x;
                    171:     r += tf->e[i].D;
                    172:   }
                    173:   for (i=c; i<ll; i++) {
                    174:     r += tf->e[i].x;
                    175:     r += tf->e[i].D;
                    176:   }
                    177:   for (i=l; i<mm; i++) {
                    178:     r += tf->e[i].x;
                    179:     r += tf->e[i].D;
                    180:   }
                    181:   for (i=m; i<nn; i++) {
                    182:     r += tf->e[i].x;
                    183:     r += tf->e[i].D;
                    184:   }
                    185:   /*printf("%s --> %d\n",POLYToString(f,'*',1),r);*/
                    186:   return(r);
                    187: }
                    188:
                    189:
                    190: int grade_module1(f)
1.3       takayama  191:      POLY f;
1.1       maekawa   192: {
                    193:   int r;
                    194:   int i;
                    195:   MONOMIAL tf;
                    196:   static int nn,mm,ll,cc,n,m,l,c;
                    197:   static struct ring *cr = (struct ring *)NULL;
                    198:
                    199:   if (f ISZERO) return(-1);
                    200:   tf = f->m;
                    201:   if (tf->ringp != cr) {
                    202:     n = tf->ringp->n;
                    203:     m = tf->ringp->m;
                    204:     l = tf->ringp->l;
                    205:     c = tf->ringp->c;
                    206:     nn = tf->ringp->nn;
                    207:     mm = tf->ringp->mm;
                    208:     ll = tf->ringp->ll;
                    209:     cc = tf->ringp->cc;
                    210:     cr = tf->ringp;
                    211:   }
                    212:
                    213:   r = 0;
                    214:   for (i=0; i<n; i++) {
                    215:     r += tf->e[i].x;
                    216:     r += tf->e[i].D;
                    217:   }
                    218:   /*printf("%s --> %d\n",POLYToString(f,'*',1),r);*/
                    219:   return(r);
                    220: }
                    221:
                    222:
                    223:
                    224: int grade_firstvec(f)   /* grading by the first vector and h */
1.3       takayama  225:      POLY f;
1.1       maekawa   226: {
                    227:   int r;
                    228:   int i,k;
                    229:   int exp[2*N0];
                    230:   MONOMIAL tf;
                    231:   static int n;
                    232:   static int *order,*from,*to;
                    233:   static struct ring *cr = (struct ring *)NULL;
                    234:
                    235:   if (f ISZERO) return(-1);
                    236:   tf = f->m;
                    237:   if (tf->ringp != cr) {
                    238:     n = tf->ringp->n;
                    239:     order = tf->ringp->order;
                    240:     from = tf->ringp->from;
                    241:     to = tf->ringp->to;
                    242:   }
                    243:
                    244:   for (i=n-1,k=0; i>=0; i--,k++) {
                    245:     exp[k] = tf->e[i].x;
                    246:     exp[k+n] = tf->e[i].D;
                    247:   }
                    248:   r = exp[2*n-1]; /* degree of h */
                    249:   for (i=from[0]; i<to[0]; i++) {
                    250:     r += exp[i]*order[i];
                    251:   }
                    252:   /*printf("%s --> %d\n",POLYToString(f,'*',1),r);*/
                    253:   return(r);
                    254: }
                    255:
                    256: int eliminated(ff)
1.3       takayama  257:      POLY ff;
1.1       maekawa   258: {
                    259: #define RULEMAX 10
                    260:   int r;
                    261:   int i; int k;
                    262:   MONOMIAL tf;
                    263:   static int nn,mm,ll,cc,n,m,l,c;
                    264:   static struct ring *cr = (struct ring *)NULL;
                    265:   POLY f;
                    266:   POLY lRule[RULEMAX];
                    267:   POLY rRule[RULEMAX];
                    268:
                    269:   if (ff ISZERO) return(-1);
                    270:   tf = ff->m;
                    271:   if (tf->ringp != cr) {
                    272:     n = tf->ringp->n;
                    273:     m = tf->ringp->m;
                    274:     l = tf->ringp->l;
                    275:     c = tf->ringp->c;
                    276:     nn = tf->ringp->nn;
                    277:     mm = tf->ringp->mm;
                    278:     ll = tf->ringp->ll;
                    279:     cc = tf->ringp->cc;
                    280:     cr = tf->ringp;
                    281:   }
                    282:
                    283:   lRule[0] = cdd(1,0,1,ff->m->ringp);  /* h */
                    284:   rRule[0] = cxx(1,0,0,ff->m->ringp);  /* 1 */
                    285:   k = 1;
                    286:   if ( c-cc + l-ll + m-mm + n -nn >= RULEMAX-1){
                    287:     fprintf(stderr,"redm.c: RULEMAX is small.\n");
                    288:     exit(1);
                    289:   }
                    290:   for (i=cc; i<c; i++,k++) {
                    291:     lRule[k] = cdd(1,i,1,ff->m->ringp);
                    292:     rRule[k] = ZERO;
                    293:   }
                    294:   for (i=ll; i<l; i++,k++) {
                    295:     lRule[k] = cdd(1,i,1,ff->m->ringp);
                    296:     rRule[k] = cxx(1,0,0,ff->m->ringp); /* Qe = 1???? */
                    297:   }
                    298:   for (i=mm; i<m; i++,k++) {
                    299:     lRule[k] = cdd(1,i,1,ff->m->ringp);
                    300:     rRule[k] = cxx(1,0,0,ff->m->ringp); /* Ee = 1 */
                    301:   }
                    302:   for (i=nn; i<n; i++,k++) {
                    303:     lRule[k] = cdd(1,i,1,ff->m->ringp);
                    304:     rRule[k] = ZERO;   /* De = 0 */
                    305:   }
                    306:   f = replace(ff,lRule,rRule,k);
                    307:
                    308:
                    309:   if (f ISZERO) return(-1);
                    310:   for (i=cc; i<c; i++) {
                    311:     if (tf->e[i].x) return 0;
                    312:   }
                    313:   for (i=ll; i<l; i++) {
                    314:     if (tf->e[i].x) return 0;
                    315:   }
                    316:   for (i=mm; i<m; i++) {
                    317:     if (tf->e[i].x) return 0;
                    318:   }
                    319:   for (i=nn; i<n; i++) {
                    320:     if (tf->e[i].x) return 0;
                    321:   }
                    322:   return(1);
1.4       takayama  323: }
                    324:
                    325: /* Grading by the weight vector (0,1). Note 2003.07.10
                    326:    dGrade1 is the grade of the in(f).
                    327: */
                    328: int dGrade1(f)
                    329:      POLY f;
                    330: {
                    331:   int r;
                    332:   int i;
                    333:   MONOMIAL tf;
                    334:   static int nn,mm,ll,cc,n,m,l,c;
                    335:   static struct ring *cr = (struct ring *)NULL;
                    336:
                    337:   if (f ISZERO) return(-1);
                    338:   tf = f->m;
                    339:   if (tf->ringp != cr) {
                    340:     n = tf->ringp->n;
                    341:     m = tf->ringp->m;
                    342:     l = tf->ringp->l;
                    343:     c = tf->ringp->c;
                    344:     nn = tf->ringp->nn;
                    345:     mm = tf->ringp->mm;
                    346:     ll = tf->ringp->ll;
                    347:     cc = tf->ringp->cc;
                    348:     cr = tf->ringp;
                    349:   }
                    350:
                    351:   r = 0;
                    352:   for (i=m; i<nn; i++) {
                    353:     r += tf->e[i].D;
                    354:   }
                    355:   return(r);
                    356: }
                    357:
                    358: /* Grading by the weight vector (0,1). Note 2003.07.10
                    359: */
                    360: int dGrade(f)
                    361:      POLY f;
                    362: {
                    363:   int r, first, t;
                    364:   if (f ISZERO) return(-1);
                    365:   first = 1;
                    366:   while (f != POLYNULL) {
                    367:     if (first) {
                    368:          r = dGrade1(f);
                    369:          first = 0;
                    370:        }else{
                    371:          t = dGrade1(f);
                    372:          if (t > r) r = t;
                    373:        }
                    374:   }
                    375:   return r;
                    376: }
                    377:
                    378: /* Grading by the weight vector (u,v)
                    379:    and degree shift ds.  Note 2003.07.10
                    380:    uvGrade1 is the grade of the in(f).
                    381:    ei ( element index ). If it is < 0, then e[n-1]->x will be used,
                    382:                          else ei is used.
                    383: */
                    384: int uvGrade1(POLY f,int u[],int v[],int ds[],int dssize,int ei)
                    385: {
                    386:   int r;
                    387:   int i,t;
                    388:   MONOMIAL tf;
                    389:   static int nn,mm,ll,cc,n,m,l,c;
                    390:   static struct ring *cr = (struct ring *)NULL;
                    391:
                    392:   if (f ISZERO) return(-1);
                    393:   tf = f->m;
                    394:   if (tf->ringp != cr) {
                    395:     n = tf->ringp->n;
                    396:     m = tf->ringp->m;
                    397:     l = tf->ringp->l;
                    398:     c = tf->ringp->c;
                    399:     nn = tf->ringp->nn;
                    400:     mm = tf->ringp->mm;
                    401:     ll = tf->ringp->ll;
                    402:     cc = tf->ringp->cc;
                    403:     cr = tf->ringp;
                    404:   }
                    405:
                    406:   r = 0;
                    407:   for (i=0; i<n; i++) {
                    408:     r += (tf->e[i].x)*u[i];
                    409:     r += (tf->e[i].D)*v[i];
                    410:   }
                    411:   /* Degree shift */
                    412:   if (ei <0) {
                    413:        t = tf->e[n-1].x;
                    414:        if ((t <dssize) && (t >= 0)) {
                    415:          r += ds[t];
                    416:        }else{
1.5     ! takayama  417:          /* Warning! ds[t] is assumed to be zero. */
1.4       takayama  418:        }
                    419:   }else{
                    420:        t = ei;
                    421:        if ((t <dssize) && (t >= 0)) {
                    422:          r += ds[t];
                    423:        }else{
1.5     ! takayama  424:          /* Warning! ds[t] is assumed to be zero. */
1.4       takayama  425:        }
                    426:   }
                    427:   return(r);
                    428: }
                    429:
                    430: /* Grading by the weight vector (u,v)
                    431:    and degree shift ds.  Note 2003.07.10
                    432: */
                    433: int uvGrade(POLY f,int u[],int v[],int ds[],int dssize,int ei)
                    434: {
                    435:   int r, first, t;
                    436:   if (f ISZERO) return(LARGE_NEGATIVE_NUMBER);
                    437:   first = 1;
                    438:   while (f != POLYNULL) {
                    439:     if (first) {
                    440:          r = uvGrade1(f,u,v,ds,dssize,ei);
                    441:          first = 0;
                    442:        }else{
                    443:          t = uvGrade1(f,u,v,ds,dssize,ei);
                    444:          if (t > r) r = t;
                    445:        }
                    446:   }
                    447:   return r;
1.1       maekawa   448: }
                    449:

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>