[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.7

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

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