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

Annotation of OpenXM/src/kan96xx/Kan/order.c, Revision 1.8

1.8     ! takayama    1: /* $OpenXM: OpenXM/src/kan96xx/Kan/order.c,v 1.7 2003/06/26 08:14:46 takayama Exp $ */
1.1       maekawa     2: #include <stdio.h>
                      3: #include "datatype.h"
                      4: #include "stackm.h"
                      5: #include "extern.h"
                      6: #include "extern2.h"
                      7:
                      8: /* The format of order.
                      9:    Example:   graded lexicographic order
                     10:    x_{N-1}  x_{N-2}  ...  x_0  D_{N-1}  ....  D_{0}
                     11:     1        1             1    1              1
                     12:     1        0             0    0              0
                     13:     0        1             0    0              0
                     14:     ..............................................
                     15:
                     16:    (ringp->order)[i][j] should be (ringp->order)[i*2*N+j].
                     17:    All order matrix is generated by functions in smacro.sm1
                     18: */
                     19:
                     20: static void warningOrder(char *s);
                     21: static void errorOrder(char *s);
                     22:
                     23: void setOrderByMatrix(order,n,c,l,omsize)
1.4       takayama   24:      int order[];
                     25:      int n,c,l,omsize;
1.1       maekawa    26: {
                     27:   int i,j;
                     28:   int *Order;
                     29:   extern struct ring *CurrentRingp;
                     30:
                     31:   switch_mmLarger("default");
1.4       takayama   32:   /* q-case */
1.1       maekawa    33:   if ( l-c > 0) {
                     34:     switch_mmLarger("qmatrix");
                     35:   }
                     36:
                     37:   Order = (int *)sGC_malloc(sizeof(int)*(2*n)*(omsize));
                     38:   if (Order == (int *)NULL) errorOrder("No memory.");
                     39:   CurrentRingp->order = Order;
                     40:   CurrentRingp->orderMatrixSize = omsize;
                     41:   for (i=0; i<omsize; i++) {
                     42:     for (j=0; j<2*n; j++) {
                     43:       Order[i*2*n+j] = order[i*2*n+j];
                     44:     }
                     45:   }
                     46: }
                     47:
                     48: void showRing(level,ringp)
1.4       takayama   49:      int level;
                     50:      struct ring *ringp;
1.1       maekawa    51: {
                     52:   int i,j;
                     53:   FILE *fp;
                     54:   char tmp[100];
                     55:   int N,M,L,C,NN,MM,LL,CC;
                     56:   char **TransX,**TransD;
                     57:   int *Order;
                     58:   int P;
                     59:   char *mtype;
                     60:   extern char *F_isSameComponent;
1.5       takayama   61:   POLY f;
1.6       takayama   62:   POLY fx;
                     63:   POLY fd;
                     64:   POLY rf;
1.1       maekawa    65:   fp = stdout;
                     66:
                     67:   N=ringp->n; M = ringp->m; L = ringp->l; C = ringp->c;
                     68:   NN=ringp->nn; MM = ringp->mm; LL = ringp->ll; CC = ringp->cc;
                     69:   TransX = ringp->x; TransD = ringp->D;
                     70:   Order = ringp->order;
                     71:   P = ringp->p;
                     72:
                     73:
                     74:   fprintf(fp,"\n----------  the current ring ---- name: %s------\n",ringp->name);
                     75:   fprintf(fp,"Characteristic is %d. ",P);
                     76:   fprintf(fp,"N0=%d N=%d NN=%d M=%d MM=%d L=%d LL=%d C=%d CC=%d omsize=%d\n",N0,N,NN,M,MM,L,LL,C,CC,ringp->orderMatrixSize);
                     77:   fprintf(fp,"\n");
                     78:
                     79:   /* print identifier names */
                     80:   if (N-M >0) {
                     81:     fprintf(fp,"Differential variables: ");
                     82:     for (i=M; i<N; i++) fprintf(fp," %4s ",TransX[i]);
                     83:     for (i=M; i<N; i++) fprintf(fp," %4s ",TransD[i]);
                     84:     fprintf(fp,"\n");
                     85:     fprintf(fp,"where ");
                     86:     for (i=M; i<N; i++) {
1.6       takayama   87:       fx = cxx(1,i,1,ringp); fd = cdd(1,i,1,ringp);
                     88:          rf = ppSub(ppMult(fd,fx),ppMult(fx,fd));
                     89:       fprintf(fp," %s %s - %s %s = %s, ",TransD[i],TransX[i],
                     90:               TransX[i],TransD[i],POLYToString(rf,'*',0));
1.1       maekawa    91:     }
                     92:     fprintf(fp,"\n\n");
                     93:   }
                     94:   if (M-L >0) {
                     95:     fprintf(fp,"Difference  variables: ");
                     96:     for (i=L; i<M; i++) fprintf(fp," %4s ",TransX[i]);
                     97:     for (i=L; i<M; i++) fprintf(fp," %4s ",TransD[i]);
                     98:     fprintf(fp,"\n");
                     99:     fprintf(fp,"where ");
                    100:     for (i=L; i<M; i++) {
1.5       takayama  101:       fprintf(fp," %s %s - %s %s = ",TransD[i],TransX[i],
                    102:               TransX[i],TransD[i]);
                    103:       f=ppSub(ppMult(cdd(1,i,1,ringp),cxx(1,i,1,ringp)),
                    104:               ppMult(cxx(1,i,1,ringp),cdd(1,i,1,ringp)));
                    105:       fprintf(fp," %s, ",POLYToString(f,'*',0));
1.1       maekawa   106:     }
                    107:     fprintf(fp,"\n\n");
                    108:   }
                    109:   if (L-C >0) {
                    110:     fprintf(fp,"q-Difference  variables: ");
                    111:     for (i=C; i<L; i++) fprintf(fp," %4s ",TransX[i]);
                    112:     for (i=C; i<L; i++) fprintf(fp," %4s ",TransD[i]);
                    113:     fprintf(fp,"\n");
                    114:     fprintf(fp,"where ");
                    115:     for (i=C; i<L; i++) {
                    116:       fprintf(fp," %s %s = %s %s %s, ",TransD[i],TransX[i],
1.4       takayama  117:               TransX[0],
                    118:               TransX[i],TransD[i]);
1.1       maekawa   119:     }
                    120:     fprintf(fp,"\n\n");
                    121:   }
                    122:   if (C>0) {
                    123:     fprintf(fp,"Commutative  variables: ");
                    124:     for (i=0; i<C; i++) fprintf(fp," %4s ",TransX[i]);
                    125:     for (i=0; i<C; i++) fprintf(fp," %4s ",TransD[i]);
                    126:     fprintf(fp,"\n\n");
                    127:   }
                    128:
                    129:   if (strcmp(F_isSameComponent,"x") == 0) {
                    130:     fprintf(fp,"Integral or summation or graduation variables are : ");
                    131:     for (i=CC; i<C; i++) fprintf(fp," %4s ",TransX[i]);
                    132:     for (i=LL; i<L; i++) fprintf(fp," %4s ",TransX[i]);
                    133:     for (i=MM; i<M; i++) fprintf(fp," %4s ",TransX[i]);
                    134:     for (i=NN; i<N; i++) fprintf(fp," %4s ",TransX[i]);
                    135:     fprintf(fp,"\n");
                    136:   }else if (strcmp(F_isSameComponent,"xd") == 0) {
                    137:     fprintf(fp,"Graduation variables are : ");
                    138:     for (i=CC; i<C; i++) fprintf(fp," %4s ",TransX[i]);
                    139:     for (i=LL; i<L; i++) fprintf(fp," %4s ",TransX[i]);
                    140:     for (i=MM; i<M; i++) fprintf(fp," %4s ",TransX[i]);
                    141:     for (i=NN; i<N; i++) fprintf(fp," %4s ",TransX[i]);
                    142:     for (i=CC; i<C; i++) fprintf(fp," %4s ",TransD[i]);
                    143:     for (i=LL; i<L; i++) fprintf(fp," %4s ",TransD[i]);
                    144:     for (i=MM; i<M; i++) fprintf(fp," %4s ",TransD[i]);
                    145:     for (i=NN; i<N; i++) fprintf(fp," %4s ",TransD[i]);
                    146:     fprintf(fp,"\n");
                    147:   }else {
                    148:     fprintf(fp,"Unknown graduation variable specification.\n\n");
                    149:   }
                    150:   fprintf(fp,"The homogenization variable is : ");
                    151:   fprintf(fp," %4s ",TransD[0]);
                    152:   fprintf(fp,"\n");
                    153:
                    154:
                    155:
                    156:   fprintf(fp,"-------------------------------------------\n");
                    157:   fprintf(fp,"Output order : ");
                    158:   for (i=0; i<2*N; i++) {
                    159:     if (ringp->outputOrder[i] < N) {
                    160:       fprintf(fp,"%s ",TransX[ringp->outputOrder[i]]);
                    161:     }else{
                    162:       fprintf(fp,"%s ",TransD[(ringp->outputOrder[i])-N]);
                    163:     }
                    164:   }
                    165:   fprintf(fp,"\n");
                    166:
                    167:   if (ringp->multiplication == mpMult_poly) {
                    168:     mtype = "poly";
                    169:   }else if  (ringp->multiplication == mpMult_diff) {
                    170:     mtype = "diff";
                    171:   }else if  (ringp->multiplication == mpMult_difference) {
                    172:     mtype = "difference";
                    173:   }else {
                    174:     mtype = "unknown";
                    175:   }
                    176:   fprintf(fp,"Multiplication function --%s(%xH).\n",
1.4       takayama  177:           mtype,(unsigned int) ringp->multiplication);
1.1       maekawa   178:   if (ringp->schreyer) {
                    179:     fprintf(fp,"schreyer=1, gbListTower=");
                    180:     printObjectList((struct object *)(ringp->gbListTower));
                    181:     fprintf(fp,"\n");
                    182:   }
1.7       takayama  183:   if (ringp->degreeShiftSize) {
1.8     ! takayama  184:     fprintf(fp,"degreeShift vector (N=%d,Size=%d)= \n[\n",ringp->degreeShiftN,ringp->degreeShiftSize);
1.7       takayama  185:     {
1.8     ! takayama  186:       int i,j;
        !           187:       for (i=0; i<ringp->degreeShiftN; i++) {
        !           188:         fprintf(fp," [");
        !           189:         for (j=0; j< ringp->degreeShiftSize; j++) {
        !           190:           fprintf(fp," %d ",ringp->degreeShift[i*(ringp->degreeShiftSize)+j]);
        !           191:         }
        !           192:         fprintf(fp,"]\n");
1.7       takayama  193:       }
                    194:     }
                    195:     fprintf(fp,"]\n");
                    196:   }
                    197:   fprintf(fp,"---  weight vectors ---\n");
1.1       maekawa   198:   if (level) printOrder(ringp);
                    199:
                    200:   if (ringp->next != (struct ring *)NULL) {
                    201:     fprintf(fp,"\n\n-------- The next ring is .... --------------\n");
                    202:     showRing(level,ringp->next);
                    203:   }
                    204: }
                    205:
                    206: /***************************************************************
                    207:    functions related to order
                    208: ******************************************************************/
                    209: #define xtoi(k) ((N-1)-(k))
                    210: #define dtoi(k) ((2*N-1)-(k))
                    211: #define itox(k) ((N-1)-(k))
                    212: #define itod(k) ((2*N-1)-(k))
                    213: #define isX(i) (i<N? 1: 0)
                    214: #define isD(i) (i<N? 0: 1)
                    215: /****************************************************
                    216: i : 0       1         N-1       N           2N-1
                    217: x :x_{N-1} x_{N-2}   x_0
                    218: d :                          D_{N-1}        D_{0}
                    219: if (isX(i))  x_{itox(i)}
                    220: if (isD(i))  D_{itod(i)}
                    221: ******************************************************/
                    222: /* xtoi(0):N-1   xtoi(1):N-2  ....
                    223:    dtoi(0):2N-1  dtoi(1):2N-2 ...
                    224:    itod(N):N-1   dtoi(N-1):N ...
                    225: */
                    226:
                    227: void printOrder(ringp)
1.4       takayama  228:      struct ring *ringp;
1.1       maekawa   229: {
                    230:   int i,j;
                    231:   FILE *fp;
                    232:   char tmp[100];
                    233:   int N,M,L,C,NN,MM,LL,CC;
                    234:   char **TransX,**TransD;
                    235:   int *Order;
                    236:   int P;
                    237:   int omsize;
                    238:   extern char *F_isSameComponent;
                    239:
                    240:   N=ringp->n; M = ringp->m; L = ringp->l; C = ringp->c;
                    241:   NN=ringp->nn; MM = ringp->mm; LL = ringp->ll; CC = ringp->cc;
                    242:   TransX = ringp->x; TransD = ringp->D;
                    243:   Order = ringp->order;
                    244:   P = ringp->p;
                    245:   omsize = ringp->orderMatrixSize;
                    246:
                    247:   fp = stdout;
                    248:
                    249:
                    250:   for (i=0; i<2*N; i++) printf("%4d",i);
                    251:   fprintf(fp,"\n");
                    252:
                    253:   /* print variables names */
                    254:   for (i=0; i<N; i++) {
                    255:     sprintf(tmp,"x%d",N-1-i);
                    256:     fprintf(fp,"%4s",tmp);
                    257:   }
                    258:   for (i=0; i<N; i++) {
                    259:     sprintf(tmp,"D%d",N-1-i);
                    260:     fprintf(fp,"%4s",tmp);
                    261:   }
                    262:   fprintf(fp,"\n");
                    263:
                    264:   /* print identifier names */
                    265:   for (i=0; i<N; i++) fprintf(fp,"%4s",TransX[itox(i)]);
                    266:   for (i=N; i<2*N; i++) fprintf(fp,"%4s",TransD[itod(i)]);
                    267:   fprintf(fp,"\n");
                    268:
                    269:   /* print D: differential     DE: differential, should be eliminated
1.4       takayama  270:      E: difference
                    271:      Q: q-difference
                    272:      C: commutative
1.1       maekawa   273:   */
                    274:   if (strcmp(F_isSameComponent,"x")== 0 || strcmp(F_isSameComponent,"xd")==0) {
                    275:     for (i=0; i<N; i++) {
                    276:       if ((NN<=itox(i)) && (itox(i)<N)) fprintf(fp,"%4s","DE");
                    277:       if ((M<=itox(i)) && (itox(i)<NN)) fprintf(fp,"%4s","D");
                    278:       if ((MM<=itox(i)) && (itox(i)<M)) fprintf(fp,"%4s","EE");
                    279:       if ((L<=itox(i)) && (itox(i)<MM)) fprintf(fp,"%4s","E");
                    280:       if ((LL<=itox(i)) && (itox(i)<L)) fprintf(fp,"%4s","QE");
                    281:       if ((C<=itox(i)) && (itox(i)<LL)) fprintf(fp,"%4s","Q");
                    282:       if ((CC<=itox(i)) && (itox(i)<C)) fprintf(fp,"%4s","CE");
                    283:       if ((0<=itox(i)) && (itox(i)<CC)) fprintf(fp,"%4s","C");
                    284:     }
                    285:   }
                    286:   if (strcmp(F_isSameComponent,"x")==0) {
                    287:     for (i=N; i<2*N; i++) {
                    288:       if ((M<=itod(i)) && (itod(i)<N)) fprintf(fp,"%4s","D");
                    289:       if ((L<=itod(i)) && (itod(i)<M)) fprintf(fp,"%4s","E");
                    290:       if ((C<=itod(i)) && (itod(i)<L)) fprintf(fp,"%4s","Q");
                    291:       if ((0<=itod(i)) && (itod(i)<C)) fprintf(fp,"%4s","C");
                    292:     }
                    293:   }else if (strcmp(F_isSameComponent,"xd")==0) {
                    294:     for (i=N; i<2*N; i++) {
                    295:       if ((NN<=itod(i)) && (itod(i)<N)) fprintf(fp,"%4s","DE");
                    296:       if ((M<=itod(i)) && (itod(i)<NN)) fprintf(fp,"%4s","D");
                    297:       if ((MM<=itod(i)) && (itod(i)<M)) fprintf(fp,"%4s","EE");
                    298:       if ((L<=itod(i)) && (itod(i)<MM)) fprintf(fp,"%4s","E");
                    299:       if ((LL<=itod(i)) && (itod(i)<L)) fprintf(fp,"%4s","QE");
                    300:       if ((C<=itod(i)) && (itod(i)<LL)) fprintf(fp,"%4s","Q");
                    301:       if ((CC<=itod(i)) && (itod(i)<C)) fprintf(fp,"%4s","CE");
                    302:       if ((0<=itod(i)) && (itod(i)<CC)) fprintf(fp,"%4s","C");
                    303:     }
                    304:   } else {
                    305:     fprintf(fp,"Unknown graduation variable type.\n");
                    306:   }
                    307:   fprintf(fp,"\n");
                    308:
                    309:   for (i=0; i< omsize; i++) {
                    310:     for (j=0; j<2*N; j++) {
                    311:       fprintf(fp,"%4d", Order[i*2*N+j]);
                    312:     }
                    313:     fprintf(fp,"\n");
                    314:   }
                    315:   fprintf(fp,"\n");
                    316:
                    317: }
                    318:
                    319: struct object oGetOrderMatrix(struct ring *ringp)
                    320: {
                    321:   struct object rob,ob2;
                    322:   int n,i,j,m;
                    323:   int *om;
                    324:   n = ringp->n;
                    325:   m = ringp->orderMatrixSize;
                    326:   om = ringp->order;
                    327:   if (m<=0) m = 1;
                    328:   rob = newObjectArray(m);
                    329:   for (i=0; i<m; i++) {
                    330:     ob2 = newObjectArray(2*n);
                    331:     for (j=0; j<2*n; j++) {
                    332:       putoa(ob2,j,KpoInteger(om[2*n*i+j]));
                    333:     }
                    334:     putoa(rob,i,ob2);
                    335:   }
                    336:   return(rob);
                    337: }
                    338:
                    339:
                    340: int mmLarger_matrix(ff,gg)
1.4       takayama  341:      POLY ff; POLY gg;
1.1       maekawa   342: {
                    343:   int exp[2*N0]; /* exponents */
                    344:   int i,k;
                    345:   int sum,flag;
                    346:   int *Order;
                    347:   int N;
                    348:   MONOMIAL f,g;
                    349:   struct ring *rp;
                    350:   int in2;
                    351:   int *from, *to;
                    352:   int omsize;
1.7       takayama  353:   int dssize;
1.8     ! takayama  354:   int dsn;
1.7       takayama  355:   int *degreeShiftVector;
1.1       maekawa   356:
                    357:   if (ff == POLYNULL ) {
                    358:     if (gg == POLYNULL) return( 2 );
                    359:     else return( 0 );
                    360:   }
                    361:   if (gg == POLYNULL) {
                    362:     if (ff == POLYNULL) return( 2 );
                    363:     else return( 1 );
                    364:   }
                    365:   f = ff->m; g=gg->m;
                    366:
                    367:   rp = f->ringp;
                    368:   Order = rp->order;
                    369:   N = rp->n;
                    370:   from = rp->from;
                    371:   to = rp->to;
                    372:   omsize = rp->orderMatrixSize;
1.7       takayama  373:   if (dssize = rp->degreeShiftSize) {
                    374:        degreeShiftVector = rp->degreeShift;  /* Note. 2003.06.26 */
1.8     ! takayama  375:        dsn = rp->degreeShiftN;
1.7       takayama  376:   }
1.1       maekawa   377:
                    378:   flag = 1;
                    379:   for (i=N-1,k=0; i>=0; i--,k++) {
                    380:     exp[k] = (f->e[i].x) - (g->e[i].x);
                    381:     exp[k+N] = (f->e[i].D) - (g->e[i].D);
                    382:     if ((exp[k] != 0) || (exp[k+N] != 0)) flag =0;
                    383:   }
                    384:   if (flag==1) return(2);
                    385:   /* exp > 0   <--->  f>g
                    386:      exp = 0   <--->  f=g
                    387:      exp < 0   <--->  f<g
                    388:   */
                    389:   for (i=0; i< omsize; i++) {
                    390:     sum = 0; in2 = i*2*N;
                    391:     /* for (k=0; k<2*N; k++) sum += exp[k]*Order[in2+k]; */
                    392:     for (k=from[i]; k<to[i]; k++) sum += exp[k]*Order[in2+k];
1.8     ! takayama  393:     if (dssize && ( i < dsn)) { /* Note, 2003.06.26 */
1.7       takayama  394:       if ((f->e[N-1].x < dssize) && (f->e[N-1].x >= 0) &&
                    395:           (g->e[N-1].x < dssize) && (g->e[N-1].x >= 0)) {
1.8     ! takayama  396:         sum += degreeShiftVector[i*dssize+ (f->e[N-1].x)]
        !           397:               -degreeShiftVector[i*dssize+ (g->e[N-1].x)];
1.7       takayama  398:       }else{
                    399:         warningOrder("Size mismatch in the degree shift vector. It is ignored.");
                    400:       }
                    401:     }
1.1       maekawa   402:     if (sum > 0) return(1);
                    403:     if (sum < 0) return(0);
                    404:   }
                    405:   return(2);
                    406: }
                    407:
                    408: /* This should be used in case of q */
                    409: int mmLarger_qmatrix(ff,gg)
1.4       takayama  410:      POLY ff; POLY gg;
1.1       maekawa   411: {
                    412:   int exp[2*N0]; /* exponents */
                    413:   int i,k;
                    414:   int sum,flag;
                    415:   int *Order;
                    416:   int N;
                    417:   MONOMIAL f,g;
                    418:   int omsize;
                    419:
                    420:   if (ff == POLYNULL ) {
                    421:     if (gg == POLYNULL) return( 2 );
                    422:     else return( 0 );
                    423:   }
                    424:   if (gg == POLYNULL) {
                    425:     if (ff == POLYNULL) return( 2 );
                    426:     else return( 1 );
                    427:   }
                    428:   f = ff->m; g = gg->m;
                    429:   Order = f->ringp->order;
                    430:   N = f->ringp->n;
                    431:   omsize = f->ringp->orderMatrixSize;
                    432:
                    433:   flag = 1;
                    434:   for (i=N-1,k=0; i>=0; i--,k++) {
                    435:     exp[k] = (f->e[i].x) - (g->e[i].x);
                    436:     exp[k+N] = (f->e[i].D) - (g->e[i].D);
                    437:     if ((exp[k] != 0) || (exp[k+N] != 0)) flag =0;
                    438:   }
                    439:   if (flag==1) return(2);
                    440:   /* exp > 0   <--->  f>g
                    441:      exp = 0   <--->  f=g
                    442:      exp < 0   <--->  f<g
                    443:   */
                    444:   for (i=0; i< omsize; i++) {
                    445:     sum = 0;
                    446:     /* In case of q, you should do as follows */
                    447:     for (k=0; k<N-1; k++) sum += exp[k]*Order[i*2*N+k]; /* skip k= N-1 -->q */
                    448:     for (k=N; k<2*N-1; k++) sum += exp[k]*Order[i*2*N+k]; /* SKip k= 2*N-1 */
                    449:     if (sum > 0) return(1);
                    450:     else if (sum < 0) return(0);
                    451:   }
                    452:   if (exp[N-1] > 0) return(1);
                    453:   else if (exp[N-1] < 0) return(0);
                    454:   else return(2);
                    455: }
                    456:
                    457: /* x(N-1)>x(N-2)>....>D(N-1)>....>D(0) */
                    458: mmLarger_pureLexicographic(f,g)
1.4       takayama  459:      POLY f;
                    460:      POLY g;
1.1       maekawa   461: {
                    462:   int i,r;
                    463:   int n;
                    464:   MONOMIAL fm,gm;
                    465:   /* Note that this function ignores the order matrix of the given
                    466:      ring. */
                    467:   if (f == POLYNULL ) {
                    468:     if (g == POLYNULL) return( 2 );
                    469:     else return( 0 );
                    470:   }
                    471:   if (g == POLYNULL) {
                    472:     if (f == POLYNULL) return( 2 );
                    473:     else return( 1 );
                    474:   }
                    475:
                    476:
                    477:   fm = f->m; gm = g->m;
                    478:   n = fm->ringp->n;
                    479:   for (i=n-1; i>=0; i--) {
                    480:     r = (fm->e[i].x) - (gm->e[i].x);
                    481:     if (r > 0) return(1);
                    482:     else if (r < 0) return(0);
                    483:     else ;
                    484:   }
                    485:
                    486:   for (i=n-1; i>=0; i--) {
                    487:     r = (fm->e[i].D) - (gm->e[i].D);
                    488:     if (r > 0) return(1);
                    489:     else if (r < 0) return(0);
                    490:     else ;
                    491:   }
                    492:
                    493:   return(2);
                    494:
                    495: }
                    496:
                    497:
                    498: void setFromTo(ringp)
1.4       takayama  499:      struct ring *ringp;
1.1       maekawa   500: {
                    501:   int n;
                    502:   int i,j,oasize;
                    503:   if (ringp->order == (int *)NULL) errorOrder("setFromTo(); no order matrix.");
                    504:   n = (ringp->n)*2;
                    505:   oasize = ringp->orderMatrixSize;
                    506:   ringp->from = (int *)sGC_malloc(sizeof(int)*oasize);
                    507:   ringp->to = (int *)sGC_malloc(sizeof(int)*oasize);
                    508:   if (ringp->from == (int *)NULL  || ringp->to == (int *)NULL) {
                    509:     errorOrder("setFromTo(): No memory.");
                    510:   }
                    511:   for (i=0; i<oasize; i++) {
                    512:     ringp->from[i] = 0; ringp->to[i] = n;
                    513:     for (j=0; j<n; j++) {
                    514:       if (ringp->order[i*n+j] != 0) {
1.4       takayama  515:         ringp->from[i] = j;
                    516:         break;
1.1       maekawa   517:       }
                    518:     }
                    519:     for (j=n-1; j>=0; j--) {
                    520:       if (ringp->order[i*n+j] != 0) {
1.4       takayama  521:         ringp->to[i] = j+1;
                    522:         break;
1.1       maekawa   523:       }
                    524:     }
                    525:   }
                    526: }
                    527:
                    528: /* It ignores h and should be used with mmLarger_tower */
                    529: /* cf. mmLarger_matrix.  h always must be checked at last. */
                    530: static int mmLarger_matrix_schreyer(ff,gg)
1.4       takayama  531:      POLY ff; POLY gg;
1.1       maekawa   532: {
                    533:   int exp[2*N0]; /* exponents */
                    534:   int i,k;
                    535:   int sum,flag;
                    536:   int *Order;
                    537:   int N;
                    538:   MONOMIAL f,g;
                    539:   struct ring *rp;
                    540:   int in2;
                    541:   int *from, *to;
                    542:   int omsize;
                    543:
                    544:   if (ff == POLYNULL ) {
                    545:     if (gg == POLYNULL) return( 2 );
                    546:     else return( 0 );
                    547:   }
                    548:   if (gg == POLYNULL) {
                    549:     if (ff == POLYNULL) return( 2 );
                    550:     else return( 1 );
                    551:   }
                    552:   f = ff->m; g=gg->m;
                    553:
                    554:   rp = f->ringp;
                    555:   Order = rp->order;
                    556:   N = rp->n;
                    557:   from = rp->from;
                    558:   to = rp->to;
                    559:   omsize = rp->orderMatrixSize;
                    560:
                    561:   flag = 1;
                    562:   for (i=N-1,k=0; i>0; i--,k++) {
                    563:     exp[k] = (f->e[i].x) - (g->e[i].x);
                    564:     exp[k+N] = (f->e[i].D) - (g->e[i].D);
                    565:     if ((exp[k] != 0) || (exp[k+N] != 0)) flag =0;
                    566:   }
                    567:   exp[N-1] = (f->e[0].x) - (g->e[0].x);
                    568:   exp[2*N-1] = 0;  /* f->e[0].D - g->e[0].D.  Ignore h! */
                    569:   if ((exp[N-1] != 0) || (exp[2*N-1] != 0)) flag =0;
                    570:
                    571:   if (flag==1) return(2);
                    572:   /* exp > 0   <--->  f>g
                    573:      exp = 0   <--->  f=g
                    574:      exp < 0   <--->  f<g
                    575:   */
                    576:   for (i=0; i< omsize; i++) {
                    577:     sum = 0; in2 = i*2*N;
                    578:     /* for (k=0; k<2*N; k++) sum += exp[k]*Order[in2+k]; */
                    579:     for (k=from[i]; k<to[i]; k++) sum += exp[k]*Order[in2+k];
                    580:     if (sum > 0) return(1);
                    581:     if (sum < 0) return(0);
                    582:   }
                    583:   return(2);
                    584: }
                    585:
                    586: int mmLarger_tower(POLY f,POLY g) {
                    587:   struct object *gbList;
                    588:   int r;
                    589:   if (f == POLYNULL) {
                    590:     if (g == POLYNULL)  return(2);
                    591:     else return(0);
                    592:   }
                    593:   if (g == POLYNULL) {
                    594:     if (f == POLYNULL) return(2);
                    595:     else return(1);
                    596:   }
                    597:   if (!(f->m->ringp->schreyer) || !(g->m->ringp->schreyer))
                    598:     return(mmLarger_matrix(f,g));
1.4       takayama  599:   /* modifiable: mmLarger_qmatrix */
1.1       maekawa   600:   gbList = (struct object *)(g->m->ringp->gbListTower);
                    601:   if (gbList == NULL) return(mmLarger_matrix(f,g));
1.4       takayama  602:   /* modifiable: mmLarger_qmatrix */
1.1       maekawa   603:   if (gbList->tag != Slist) {
                    604:     warningOrder("mmLarger_tower(): gbList must be in Slist.\n");
                    605:     return(1);
                    606:   }
                    607:   if (klength(gbList) ==0) return(mmLarger_matrix(f,g));
1.4       takayama  608:   /* modifiable: mmLarger_qmatrix */
1.1       maekawa   609:
                    610:   r = mmLarger_tower3(f,g,gbList);
                    611:   /* printf("mmLarger_tower3(%s,%s) -->  %d\n",POLYToString(head(f),'*',1),POLYToString(head(g),'*',1),r); */
                    612:   if (r == 2) { /* Now, compare by h */
                    613:     if (f->m->e[0].D > g->m->e[0].D) return(1);
                    614:     else if (f->m->e[0].D < g->m->e[0].D) return(0);
                    615:     else return(2);
                    616:   }else{
                    617:     return(r);
                    618:   }
                    619: }
                    620:
                    621: int mmLarger_tower3(POLY f,POLY g,struct object *gbList)
                    622: { /* gbList is assumed to be Slist */
                    623:   int n,fv,gv,t,r,nn;
                    624:   POLY fm;
                    625:   POLY gm;
                    626:   struct object gb;
                    627:
                    628:   if (f == POLYNULL) {
                    629:     if (g == POLYNULL)  return(2);
                    630:     else return(0);
                    631:   }
                    632:   if (g == POLYNULL) {
                    633:     if (f == POLYNULL) return(2);
                    634:     else return(1);   /* It assumes the zero is the minimum element!! */
                    635:   }
                    636:   n = f->m->ringp->n;
                    637:   nn = f->m->ringp->nn;
                    638:   /* critical and modifiable */  /* m e_u > m e_v <==> m g_u > m g_v */
1.4       takayama  639:   /*                  or equal and u < v */
1.1       maekawa   640:   fv = f->m->e[nn].x ; /* extract component (vector) number of f! */
                    641:   gv = g->m->e[nn].x ;
                    642:   if (fv == gv) { /* They have the same component number. */
                    643:     return(mmLarger_matrix_schreyer(f,g));
                    644:   }
                    645:
                    646:   if (gbList == NULL) return(mmLarger_matrix_schreyer(f,g));
1.4       takayama  647:   /* modifiable: mmLarger_qmatrix */
1.1       maekawa   648:   if (gbList->tag != Slist) {
                    649:     warningOrder("mmLarger_tower(): gbList must be in Slist.\n");
                    650:     return(1);
                    651:   }
                    652:   if (klength(gbList) ==0) return(mmLarger_matrix(f,g));
1.4       takayama  653:   /* modifiable: mmLarger_qmatrix */
1.1       maekawa   654:   gb = car(gbList);  /* each entry must be monomials */
                    655:   if (gb.tag != Sarray) {
                    656:     warningOrder("mmLarger_tower3(): car(gbList) must be an array.\n");
                    657:     return(1);
                    658:   }
                    659:   t = getoaSize(gb);
                    660:   if (t == 0) return(mmLarger_tower3(f,g,cdr(gbList)));
                    661:
                    662:   fm = pmCopy(head(f)); fm->m->e[nn].x = 0; /* f is not modified. */
                    663:   gm = pmCopy(head(g)); gm->m->e[nn].x = 0;
                    664:   if (fv >= t || gv >= t) {
                    665:     warningOrder("mmLarger_tower3(): incompatible input and gbList.\n");
                    666:     printf("Length of gb is %d, f is %s, g is %s\n",t,KPOLYToString(f),
1.4       takayama  667:            KPOLYToString(g));
1.3       takayama  668:     KSexecuteString(" show_ring ");
1.1       maekawa   669:     return(1);
                    670:   }
                    671:   /* mpMult_poly is too expensive to call. @@@*/
                    672:   r = mmLarger_tower3(mpMult_poly(fm,KopPOLY(getoa(gb,fv))),
                    673:                       mpMult_poly(gm,KopPOLY(getoa(gb,gv))),
                    674:                       cdr(gbList));
                    675:   if (r != 2) return(r);
                    676:   else if (fv == gv) return(2);
                    677:   else if (fv > gv) return(0); /* modifiable */
                    678:   else if (fv < gv) return(1); /* modifiable */
                    679: }
                    680:
                    681: static void warningOrder(s)
1.4       takayama  682:      char *s;
1.1       maekawa   683: {
                    684:   fprintf(stderr,"Warning in order.c: %s\n",s);
                    685: }
                    686:
                    687: static void errorOrder(s)
1.4       takayama  688:      char *s;
1.1       maekawa   689: {
                    690:   fprintf(stderr,"order.c: %s\n",s);
                    691:   exit(14);
                    692: }
                    693:
                    694:

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