![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to dist.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM_contrib2 / asir2000 / engine|
Return to dist.c CVS log | Up to [local] / OpenXM_contrib2 / asir2000 / engine |
1.8 noro 1: /*
2: * Copyright (c) 1994-2000 FUJITSU LABORATORIES LIMITED
3: * All rights reserved.
4: *
5: * FUJITSU LABORATORIES LIMITED ("FLL") hereby grants you a limited,
6: * non-exclusive and royalty-free license to use, copy, modify and
7: * redistribute, solely for non-commercial and non-profit purposes, the
8: * computer program, "Risa/Asir" ("SOFTWARE"), subject to the terms and
9: * conditions of this Agreement. For the avoidance of doubt, you acquire
10: * only a limited right to use the SOFTWARE hereunder, and FLL or any
11: * third party developer retains all rights, including but not limited to
12: * copyrights, in and to the SOFTWARE.
13: *
14: * (1) FLL does not grant you a license in any way for commercial
15: * purposes. You may use the SOFTWARE only for non-commercial and
16: * non-profit purposes only, such as academic, research and internal
17: * business use.
18: * (2) The SOFTWARE is protected by the Copyright Law of Japan and
19: * international copyright treaties. If you make copies of the SOFTWARE,
20: * with or without modification, as permitted hereunder, you shall affix
21: * to all such copies of the SOFTWARE the above copyright notice.
22: * (3) An explicit reference to this SOFTWARE and its copyright owner
23: * shall be made on your publication or presentation in any form of the
24: * results obtained by use of the SOFTWARE.
25: * (4) In the event that you modify the SOFTWARE, you shall notify FLL by
1.9 noro 26: * e-mail at risa-admin@sec.flab.fujitsu.co.jp of the detailed specification
1.8 noro 27: * for such modification or the source code of the modified part of the
28: * SOFTWARE.
29: *
30: * THE SOFTWARE IS PROVIDED AS IS WITHOUT ANY WARRANTY OF ANY KIND. FLL
31: * MAKES ABSOLUTELY NO WARRANTIES, EXPRESSED, IMPLIED OR STATUTORY, AND
32: * EXPRESSLY DISCLAIMS ANY IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS
33: * FOR A PARTICULAR PURPOSE OR NONINFRINGEMENT OF THIRD PARTIES'
34: * RIGHTS. NO FLL DEALER, AGENT, EMPLOYEES IS AUTHORIZED TO MAKE ANY
35: * MODIFICATIONS, EXTENSIONS, OR ADDITIONS TO THIS WARRANTY.
36: * UNDER NO CIRCUMSTANCES AND UNDER NO LEGAL THEORY, TORT, CONTRACT,
37: * OR OTHERWISE, SHALL FLL BE LIABLE TO YOU OR ANY OTHER PERSON FOR ANY
38: * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, PUNITIVE OR CONSEQUENTIAL
39: * DAMAGES OF ANY CHARACTER, INCLUDING, WITHOUT LIMITATION, DAMAGES
40: * ARISING OUT OF OR RELATING TO THE SOFTWARE OR THIS AGREEMENT, DAMAGES
41: * FOR LOSS OF GOODWILL, WORK STOPPAGE, OR LOSS OF DATA, OR FOR ANY
42: * DAMAGES, EVEN IF FLL SHALL HAVE BEEN INFORMED OF THE POSSIBILITY OF
43: * SUCH DAMAGES, OR FOR ANY CLAIM BY ANY OTHER PARTY. EVEN IF A PART
44: * OF THE SOFTWARE HAS BEEN DEVELOPED BY A THIRD PARTY, THE THIRD PARTY
45: * DEVELOPER SHALL HAVE NO LIABILITY IN CONNECTION WITH THE USE,
46: * PERFORMANCE OR NON-PERFORMANCE OF THE SOFTWARE.
47: *
1.13 ! noro 48: * $OpenXM: OpenXM_contrib2/asir2000/engine/dist.c,v 1.12 2000/12/11 02:00:41 noro Exp $
1.8 noro 49: */
1.1 noro 50: #include "ca.h"
51:
52: #define ORD_REVGRADLEX 0
53: #define ORD_GRADLEX 1
54: #define ORD_LEX 2
55: #define ORD_BREVGRADLEX 3
56: #define ORD_BGRADLEX 4
57: #define ORD_BLEX 5
58: #define ORD_BREVREV 6
59: #define ORD_BGRADREV 7
60: #define ORD_BLEXREV 8
61: #define ORD_ELIM 9
1.12 noro 62: #define ORD_WEYL_ELIM 10
1.13 ! noro 63: #define ORD_HOMO_WW_DRL 11
1.1 noro 64:
65: int (*cmpdl)()=cmpdl_revgradlex;
66: int (*primitive_cmpdl[3])() = {cmpdl_revgradlex,cmpdl_gradlex,cmpdl_lex};
67:
1.2 noro 68: void comm_muld(VL,DP,DP,DP *);
69: void weyl_muld(VL,DP,DP,DP *);
1.10 noro 70: void weyl_muldm(VL,MP,DP,DP *);
71: void weyl_mulmm(VL,MP,MP,int,struct cdl *,int);
72: void comm_muld_tab(VL,int,struct cdl *,int,struct cdl *,int,struct cdl *);
73:
1.2 noro 74: void mkwc(int,int,Q *);
75:
1.12 noro 76: int cmpdl_weyl_elim();
1.13 ! noro 77: int cmpdl_homo_ww_drl();
1.12 noro 78:
1.2 noro 79: int do_weyl;
80:
1.1 noro 81: int dp_nelim,dp_fcoeffs;
82: struct order_spec dp_current_spec;
83: int *dp_dl_work;
84:
85: int has_fcoef(DP);
86: int has_fcoef_p(P);
87:
88: int has_fcoef(f)
89: DP f;
90: {
91: MP t;
92:
93: if ( !f )
94: return 0;
95: for ( t = BDY(f); t; t = NEXT(t) )
96: if ( has_fcoef_p(t->c) )
97: break;
98: return t ? 1 : 0;
99: }
100:
101: int has_fcoef_p(f)
102: P f;
103: {
104: DCP dc;
105:
106: if ( !f )
107: return 0;
108: else if ( NUM(f) )
109: return (NID((Num)f) == N_LM || NID((Num)f) == N_GF2N) ? 1 : 0;
110: else {
111: for ( dc = DC(f); dc; dc = NEXT(dc) )
112: if ( has_fcoef_p(COEF(dc)) )
113: return 1;
114: return 0;
115: }
116: }
117:
118: void initd(spec)
119: struct order_spec *spec;
120: {
121: switch ( spec->id ) {
122: case 2:
123: cmpdl = cmpdl_matrix;
124: dp_dl_work = (int *)MALLOC_ATOMIC(spec->nv*sizeof(int));
125: break;
126: case 1:
127: cmpdl = cmpdl_order_pair;
128: break;
129: default:
130: switch ( spec->ord.simple ) {
131: case ORD_REVGRADLEX:
132: cmpdl = cmpdl_revgradlex; break;
133: case ORD_GRADLEX:
134: cmpdl = cmpdl_gradlex; break;
135: case ORD_BREVGRADLEX:
136: cmpdl = cmpdl_brevgradlex; break;
137: case ORD_BGRADLEX:
138: cmpdl = cmpdl_bgradlex; break;
139: case ORD_BLEX:
140: cmpdl = cmpdl_blex; break;
141: case ORD_BREVREV:
142: cmpdl = cmpdl_brevrev; break;
143: case ORD_BGRADREV:
144: cmpdl = cmpdl_bgradrev; break;
145: case ORD_BLEXREV:
146: cmpdl = cmpdl_blexrev; break;
147: case ORD_ELIM:
148: cmpdl = cmpdl_elim; break;
1.12 noro 149: case ORD_WEYL_ELIM:
150: cmpdl = cmpdl_weyl_elim; break;
1.13 ! noro 151: case ORD_HOMO_WW_DRL:
! 152: cmpdl = cmpdl_homo_ww_drl; break;
1.1 noro 153: case ORD_LEX: default:
154: cmpdl = cmpdl_lex; break;
155: }
156: break;
157: }
158: dp_current_spec = *spec;
159: }
160:
161: void ptod(vl,dvl,p,pr)
162: VL vl,dvl;
163: P p;
164: DP *pr;
165: {
166: int isconst = 0;
167: int n,i;
168: VL tvl;
169: V v;
170: DL d;
171: MP m;
172: DCP dc;
173: DP r,s,t,u;
174: P x,c;
175:
176: if ( !p )
177: *pr = 0;
178: else {
179: for ( n = 0, tvl = dvl; tvl; tvl = NEXT(tvl), n++ );
180: if ( NUM(p) ) {
181: NEWDL(d,n);
182: NEWMP(m); m->dl = d; C(m) = p; NEXT(m) = 0; MKDP(n,m,*pr); (*pr)->sugar = 0;
183: } else {
184: for ( i = 0, tvl = dvl, v = VR(p);
185: tvl && tvl->v != v; tvl = NEXT(tvl), i++ );
186: if ( !tvl ) {
187: for ( dc = DC(p), s = 0, MKV(v,x); dc; dc = NEXT(dc) ) {
188: ptod(vl,dvl,COEF(dc),&t); pwrp(vl,x,DEG(dc),&c);
189: muldc(vl,t,c,&r); addd(vl,r,s,&t); s = t;
190: }
191: *pr = s;
192: } else {
193: for ( dc = DC(p), s = 0; dc; dc = NEXT(dc) ) {
194: ptod(vl,dvl,COEF(dc),&t);
195: NEWDL(d,n); d->td = QTOS(DEG(dc)); d->d[i] = d->td;
196: NEWMP(m); m->dl = d; C(m) = (P)ONE; NEXT(m) = 0; MKDP(n,m,u); u->sugar = d->td;
1.2 noro 197: comm_muld(vl,t,u,&r); addd(vl,r,s,&t); s = t;
1.1 noro 198: }
199: *pr = s;
200: }
201: }
202: }
203: if ( !dp_fcoeffs && has_fcoef(*pr) )
204: dp_fcoeffs = 1;
205: }
206:
207: void dtop(vl,dvl,p,pr)
208: VL vl,dvl;
209: DP p;
210: P *pr;
211: {
212: int n,i;
213: DL d;
214: MP m;
215: P r,s,t,u,w;
216: Q q;
217: VL tvl;
218:
219: if ( !p )
220: *pr = 0;
221: else {
222: for ( n = p->nv, m = BDY(p), s = 0; m; m = NEXT(m) ) {
223: t = C(m);
224: if ( NUM(t) && NID((Num)t) == N_M ) {
225: mptop(t,&u); t = u;
226: }
227: for ( i = 0, d = m->dl, tvl = dvl;
228: i < n; tvl = NEXT(tvl), i++ ) {
229: MKV(tvl->v,r); STOQ(d->d[i],q); pwrp(vl,r,q,&u);
230: mulp(vl,t,u,&w); t = w;
231: }
232: addp(vl,s,t,&u); s = u;
233: }
234: *pr = s;
235: }
236: }
237:
238: void nodetod(node,dp)
239: NODE node;
240: DP *dp;
241: {
242: NODE t;
243: int len,i,td;
244: Q e;
245: DL d;
246: MP m;
247: DP u;
248:
249: for ( t = node, len = 0; t; t = NEXT(t), len++ );
250: NEWDL(d,len);
251: for ( t = node, i = 0, td = 0; i < len; t = NEXT(t), i++ ) {
252: e = (Q)BDY(t);
253: if ( !e )
254: d->d[i] = 0;
255: else if ( !NUM(e) || !RATN(e) || !INT(e) )
256: error("nodetod : invalid input");
257: else {
258: d->d[i] = QTOS((Q)e); td += d->d[i];
259: }
260: }
261: d->td = td;
262: NEWMP(m); m->dl = d; C(m) = (P)ONE; NEXT(m) = 0;
263: MKDP(len,m,u); u->sugar = td; *dp = u;
264: }
265:
266: int sugard(m)
267: MP m;
268: {
269: int s;
270:
271: for ( s = 0; m; m = NEXT(m) )
272: s = MAX(s,m->dl->td);
273: return s;
274: }
275:
276: void addd(vl,p1,p2,pr)
277: VL vl;
278: DP p1,p2,*pr;
279: {
280: int n;
281: MP m1,m2,mr,mr0;
282: P t;
283:
284: if ( !p1 )
285: *pr = p2;
286: else if ( !p2 )
287: *pr = p1;
288: else {
289: for ( n = NV(p1), m1 = BDY(p1), m2 = BDY(p2), mr0 = 0; m1 && m2; )
290: switch ( (*cmpdl)(n,m1->dl,m2->dl) ) {
291: case 0:
292: addp(vl,C(m1),C(m2),&t);
293: if ( t ) {
294: NEXTMP(mr0,mr); mr->dl = m1->dl; C(mr) = t;
295: }
296: m1 = NEXT(m1); m2 = NEXT(m2); break;
297: case 1:
298: NEXTMP(mr0,mr); mr->dl = m1->dl; C(mr) = C(m1);
299: m1 = NEXT(m1); break;
300: case -1:
301: NEXTMP(mr0,mr); mr->dl = m2->dl; C(mr) = C(m2);
302: m2 = NEXT(m2); break;
303: }
304: if ( !mr0 )
305: if ( m1 )
306: mr0 = m1;
307: else if ( m2 )
308: mr0 = m2;
309: else {
310: *pr = 0;
311: return;
312: }
313: else if ( m1 )
314: NEXT(mr) = m1;
315: else if ( m2 )
316: NEXT(mr) = m2;
317: else
318: NEXT(mr) = 0;
319: MKDP(NV(p1),mr0,*pr);
320: if ( *pr )
321: (*pr)->sugar = MAX(p1->sugar,p2->sugar);
322: }
323: }
324:
325: /* for F4 symbolic reduction */
326:
327: void symb_addd(p1,p2,pr)
328: DP p1,p2,*pr;
329: {
330: int n;
331: MP m1,m2,mr,mr0;
332: P t;
333:
334: if ( !p1 )
335: *pr = p2;
336: else if ( !p2 )
337: *pr = p1;
338: else {
339: for ( n = NV(p1), m1 = BDY(p1), m2 = BDY(p2), mr0 = 0; m1 && m2; ) {
340: NEXTMP(mr0,mr); C(mr) = (P)ONE;
341: switch ( (*cmpdl)(n,m1->dl,m2->dl) ) {
342: case 0:
343: mr->dl = m1->dl;
344: m1 = NEXT(m1); m2 = NEXT(m2); break;
345: case 1:
346: mr->dl = m1->dl;
347: m1 = NEXT(m1); break;
348: case -1:
349: mr->dl = m2->dl;
350: m2 = NEXT(m2); break;
351: }
352: }
353: if ( !mr0 )
354: if ( m1 )
355: mr0 = m1;
356: else if ( m2 )
357: mr0 = m2;
358: else {
359: *pr = 0;
360: return;
361: }
362: else if ( m1 )
363: NEXT(mr) = m1;
364: else if ( m2 )
365: NEXT(mr) = m2;
366: else
367: NEXT(mr) = 0;
368: MKDP(NV(p1),mr0,*pr);
369: if ( *pr )
370: (*pr)->sugar = MAX(p1->sugar,p2->sugar);
1.3 noro 371: }
372: }
373:
374: /*
375: * destructive merge of two list
376: *
377: * p1, p2 : list of DL
378: * return : a merged list
379: */
380:
381: NODE symb_merge(m1,m2,n)
382: NODE m1,m2;
383: int n;
384: {
385: NODE top,prev,cur,m,t;
386:
387: if ( !m1 )
388: return m2;
389: else if ( !m2 )
390: return m1;
391: else {
392: switch ( (*cmpdl)(n,(DL)BDY(m1),(DL)BDY(m2)) ) {
393: case 0:
394: top = m1; m = NEXT(m2);
395: break;
396: case 1:
397: top = m1; m = m2;
398: break;
399: case -1:
400: top = m2; m = m1;
401: break;
402: }
403: prev = top; cur = NEXT(top);
404: /* BDY(prev) > BDY(m) always holds */
405: while ( cur && m ) {
406: switch ( (*cmpdl)(n,(DL)BDY(cur),(DL)BDY(m)) ) {
407: case 0:
408: m = NEXT(m);
409: prev = cur; cur = NEXT(cur);
410: break;
411: case 1:
412: t = NEXT(cur); NEXT(cur) = m; m = t;
413: prev = cur; cur = NEXT(cur);
414: break;
415: case -1:
416: NEXT(prev) = m; m = cur;
417: prev = NEXT(prev); cur = NEXT(prev);
418: break;
419: }
420: }
421: if ( !cur )
422: NEXT(prev) = m;
423: return top;
1.1 noro 424: }
425: }
426:
427: void subd(vl,p1,p2,pr)
428: VL vl;
429: DP p1,p2,*pr;
430: {
431: DP t;
432:
433: if ( !p2 )
434: *pr = p1;
435: else {
436: chsgnd(p2,&t); addd(vl,p1,t,pr);
437: }
438: }
439:
440: void chsgnd(p,pr)
441: DP p,*pr;
442: {
443: MP m,mr,mr0;
444:
445: if ( !p )
446: *pr = 0;
447: else {
448: for ( mr0 = 0, m = BDY(p); m; m = NEXT(m) ) {
449: NEXTMP(mr0,mr); chsgnp(C(m),&C(mr)); mr->dl = m->dl;
450: }
451: NEXT(mr) = 0; MKDP(NV(p),mr0,*pr);
452: if ( *pr )
453: (*pr)->sugar = p->sugar;
454: }
455: }
456:
457: void muld(vl,p1,p2,pr)
458: VL vl;
459: DP p1,p2,*pr;
460: {
1.2 noro 461: if ( ! do_weyl )
462: comm_muld(vl,p1,p2,pr);
463: else
464: weyl_muld(vl,p1,p2,pr);
465: }
466:
467: void comm_muld(vl,p1,p2,pr)
468: VL vl;
469: DP p1,p2,*pr;
470: {
1.1 noro 471: MP m;
472: DP s,t,u;
1.5 noro 473: int i,l,l1;
474: static MP *w;
475: static int wlen;
1.1 noro 476:
477: if ( !p1 || !p2 )
478: *pr = 0;
479: else if ( OID(p1) <= O_P )
480: muldc(vl,p2,(P)p1,pr);
481: else if ( OID(p2) <= O_P )
482: muldc(vl,p1,(P)p2,pr);
483: else {
1.5 noro 484: for ( m = BDY(p1), l1 = 0; m; m = NEXT(m), l1++ );
1.4 noro 485: for ( m = BDY(p2), l = 0; m; m = NEXT(m), l++ );
1.5 noro 486: if ( l1 < l ) {
487: t = p1; p1 = p2; p2 = t;
488: l = l1;
489: }
490: if ( l > wlen ) {
491: if ( w ) GC_free(w);
492: w = (MP *)MALLOC(l*sizeof(MP));
493: wlen = l;
494: }
1.4 noro 495: for ( m = BDY(p2), i = 0; i < l; m = NEXT(m), i++ )
496: w[i] = m;
497: for ( s = 0, i = l-1; i >= 0; i-- ) {
498: muldm(vl,p1,w[i],&t); addd(vl,s,t,&u); s = u;
1.1 noro 499: }
1.5 noro 500: bzero(w,l*sizeof(MP));
1.1 noro 501: *pr = s;
502: }
503: }
504:
505: void muldm(vl,p,m0,pr)
506: VL vl;
507: DP p;
508: MP m0;
509: DP *pr;
510: {
511: MP m,mr,mr0;
512: P c;
513: DL d;
514: int n;
515:
516: if ( !p )
517: *pr = 0;
518: else {
519: for ( mr0 = 0, m = BDY(p), c = C(m0), d = m0->dl, n = NV(p);
520: m; m = NEXT(m) ) {
521: NEXTMP(mr0,mr);
522: if ( NUM(C(m)) && RATN(C(m)) && NUM(c) && RATN(c) )
523: mulq((Q)C(m),(Q)c,(Q *)&C(mr));
524: else
525: mulp(vl,C(m),c,&C(mr));
526: adddl(n,m->dl,d,&mr->dl);
527: }
528: NEXT(mr) = 0; MKDP(NV(p),mr0,*pr);
529: if ( *pr )
530: (*pr)->sugar = p->sugar + m0->dl->td;
1.2 noro 531: }
532: }
533:
534: void weyl_muld(vl,p1,p2,pr)
535: VL vl;
536: DP p1,p2,*pr;
537: {
538: MP m;
539: DP s,t,u;
1.4 noro 540: int i,l;
1.5 noro 541: static MP *w;
542: static int wlen;
1.2 noro 543:
544: if ( !p1 || !p2 )
545: *pr = 0;
546: else if ( OID(p1) <= O_P )
547: muldc(vl,p2,(P)p1,pr);
548: else if ( OID(p2) <= O_P )
549: muldc(vl,p1,(P)p2,pr);
550: else {
1.10 noro 551: for ( m = BDY(p1), l = 0; m; m = NEXT(m), l++ );
1.5 noro 552: if ( l > wlen ) {
553: if ( w ) GC_free(w);
554: w = (MP *)MALLOC(l*sizeof(MP));
555: wlen = l;
556: }
1.10 noro 557: for ( m = BDY(p1), i = 0; i < l; m = NEXT(m), i++ )
1.4 noro 558: w[i] = m;
559: for ( s = 0, i = l-1; i >= 0; i-- ) {
1.10 noro 560: weyl_muldm(vl,w[i],p2,&t); addd(vl,s,t,&u); s = u;
1.2 noro 561: }
1.5 noro 562: bzero(w,l*sizeof(MP));
1.2 noro 563: *pr = s;
564: }
565: }
566:
1.10 noro 567: /* monomial * polynomial */
568:
569: void weyl_muldm(vl,m0,p,pr)
1.2 noro 570: VL vl;
1.10 noro 571: MP m0;
1.2 noro 572: DP p;
573: DP *pr;
574: {
575: DP r,t,t1;
576: MP m;
1.10 noro 577: DL d0;
578: int n,n2,l,i,j,tlen;
579: static MP *w,*psum;
580: static struct cdl *tab;
1.5 noro 581: static int wlen;
1.10 noro 582: static int rtlen;
1.2 noro 583:
584: if ( !p )
585: *pr = 0;
586: else {
1.4 noro 587: for ( m = BDY(p), l = 0; m; m = NEXT(m), l++ );
1.5 noro 588: if ( l > wlen ) {
589: if ( w ) GC_free(w);
590: w = (MP *)MALLOC(l*sizeof(MP));
591: wlen = l;
592: }
1.4 noro 593: for ( m = BDY(p), i = 0; i < l; m = NEXT(m), i++ )
594: w[i] = m;
1.10 noro 595:
596: n = NV(p); n2 = n>>1;
597: d0 = m0->dl;
598: for ( i = 0, tlen = 1; i < n2; i++ )
599: tlen *= d0->d[n2+i]+1;
600: if ( tlen > rtlen ) {
601: if ( tab ) GC_free(tab);
602: if ( psum ) GC_free(psum);
603: rtlen = tlen;
604: tab = (struct cdl *)MALLOC(rtlen*sizeof(struct cdl));
605: psum = (MP *)MALLOC(rtlen*sizeof(MP));
606: }
607: bzero(psum,tlen*sizeof(MP));
608: for ( i = l-1; i >= 0; i-- ) {
609: bzero(tab,tlen*sizeof(struct cdl));
610: weyl_mulmm(vl,m0,w[i],n,tab,tlen);
611: for ( j = 0; j < tlen; j++ ) {
612: if ( tab[j].c ) {
613: NEWMP(m); m->dl = tab[j].d; C(m) = tab[j].c; NEXT(m) = psum[j];
614: psum[j] = m;
615: }
616: }
1.2 noro 617: }
1.10 noro 618: for ( j = tlen-1, r = 0; j >= 0; j-- )
619: if ( psum[j] ) {
620: MKDP(n,psum[j],t); addd(vl,r,t,&t1); r = t1;
621: }
1.2 noro 622: if ( r )
623: r->sugar = p->sugar + m0->dl->td;
624: *pr = r;
625: }
626: }
627:
1.10 noro 628: /* m0 = x0^d0*x1^d1*... * dx0^e0*dx1^e1*... */
629: /* rtab : array of length (e0+1)*(e1+1)*... */
1.2 noro 630:
1.10 noro 631: void weyl_mulmm(vl,m0,m1,n,rtab,rtablen)
1.2 noro 632: VL vl;
633: MP m0,m1;
634: int n;
1.10 noro 635: struct cdl *rtab;
636: int rtablen;
1.2 noro 637: {
638: MP m,mr,mr0;
639: DP r,t,t1;
640: P c,c0,c1,cc;
1.10 noro 641: DL d,d0,d1,dt;
642: int i,j,a,b,k,l,n2,s,min,curlen;
643: struct cdl *p;
644: static Q *ctab;
645: static struct cdl *tab;
1.5 noro 646: static int tablen;
1.10 noro 647: static struct cdl *tmptab;
648: static int tmptablen;
1.2 noro 649:
1.10 noro 650:
651: if ( !m0 || !m1 ) {
652: rtab[0].c = 0;
653: rtab[0].d = 0;
654: return;
655: }
656: c0 = C(m0); c1 = C(m1);
657: mulp(vl,c0,c1,&c);
658: d0 = m0->dl; d1 = m1->dl;
659: n2 = n>>1;
660: curlen = 1;
661: NEWDL(d,n);
662: if ( n & 1 )
663: /* offset of h-degree */
664: d->td = d->d[n-1] = d0->d[n-1]+d1->d[n-1];
665: else
666: d->td = 0;
667: rtab[0].c = c;
668: rtab[0].d = d;
669:
670: if ( rtablen > tmptablen ) {
671: if ( tmptab ) GC_free(tmptab);
672: tmptab = (struct cdl *)MALLOC(rtablen*sizeof(struct cdl));
673: tmptablen = rtablen;
674: }
675: for ( i = 0; i < n2; i++ ) {
676: a = d0->d[i]; b = d1->d[n2+i];
677: k = d0->d[n2+i]; l = d1->d[i];
678: if ( !k || !l ) {
679: a += l;
680: b += k;
681: s = a+b;
682: for ( j = 0, p = rtab; j < curlen; j++, p++ ) {
683: if ( p->c ) {
684: dt = p->d;
685: dt->d[i] = a;
686: dt->d[n2+i] = b;
687: dt->td += s;
1.5 noro 688: }
1.10 noro 689: }
690: curlen *= k+1;
691: continue;
692: }
693: if ( k+1 > tablen ) {
694: if ( tab ) GC_free(tab);
695: if ( ctab ) GC_free(ctab);
696: tablen = k+1;
697: tab = (struct cdl *)MALLOC(tablen*sizeof(struct cdl));
698: ctab = (Q *)MALLOC(tablen*sizeof(Q));
699: }
700: /* degree of xi^a*(Di^k*xi^l)*Di^b */
701: s = a+k+l+b;
702: /* compute xi^a*(Di^k*xi^l)*Di^b */
703: min = MIN(k,l);
704: mkwc(k,l,ctab);
705: bzero(tab,(k+1)*sizeof(struct cdl));
706: if ( n & 1 )
707: for ( j = 0; j <= min; j++ ) {
708: NEWDL(d,n);
709: d->d[i] = l-j+a; d->d[n2+i] = k-j+b;
710: d->td = s;
711: d->d[n-1] = s-(d->d[i]+d->d[n2+i]);
712: tab[j].d = d;
713: tab[j].c = (P)ctab[j];
714: }
715: else
716: for ( j = 0; j <= min; j++ ) {
717: NEWDL(d,n);
718: d->d[i] = l-j+a; d->d[n2+i] = k-j+b;
719: d->td = d->d[i]+d->d[n2+i]; /* XXX */
720: tab[j].d = d;
721: tab[j].c = (P)ctab[j];
722: }
723: bzero(ctab,(min+1)*sizeof(Q));
724: comm_muld_tab(vl,n,rtab,curlen,tab,k+1,tmptab);
725: curlen *= k+1;
726: bcopy(tmptab,rtab,curlen*sizeof(struct cdl));
727: }
728: }
729:
730: /* direct product of two cdl tables
731: rt[] = [
732: t[0]*t1[0],...,t[n-1]*t1[0],
733: t[0]*t1[1],...,t[n-1]*t1[1],
734: ...
735: t[0]*t1[n1-1],...,t[n-1]*t1[n1-1]
736: ]
737: */
738:
739: void comm_muld_tab(vl,nv,t,n,t1,n1,rt)
740: VL vl;
741: int nv;
742: struct cdl *t;
743: int n;
744: struct cdl *t1;
745: int n1;
746: struct cdl *rt;
747: {
748: int i,j;
749: struct cdl *p;
750: P c;
751: DL d;
752:
753: bzero(rt,n*n1*sizeof(struct cdl));
754: for ( j = 0, p = rt; j < n1; j++ ) {
755: c = t1[j].c;
756: d = t1[j].d;
757: if ( !c )
758: break;
759: for ( i = 0; i < n; i++, p++ ) {
760: if ( t[i].c ) {
761: mulp(vl,t[i].c,c,&p->c);
762: adddl(nv,t[i].d,d,&p->d);
763: }
1.6 noro 764: }
1.1 noro 765: }
766: }
767:
768: void muldc(vl,p,c,pr)
769: VL vl;
770: DP p;
771: P c;
772: DP *pr;
773: {
774: MP m,mr,mr0;
775:
776: if ( !p || !c )
777: *pr = 0;
778: else if ( NUM(c) && UNIQ((Q)c) )
779: *pr = p;
780: else if ( NUM(c) && MUNIQ((Q)c) )
781: chsgnd(p,pr);
782: else {
783: for ( mr0 = 0, m = BDY(p); m; m = NEXT(m) ) {
784: NEXTMP(mr0,mr);
785: if ( NUM(C(m)) && RATN(C(m)) && NUM(c) && RATN(c) )
786: mulq((Q)C(m),(Q)c,(Q *)&C(mr));
787: else
788: mulp(vl,C(m),c,&C(mr));
789: mr->dl = m->dl;
790: }
791: NEXT(mr) = 0; MKDP(NV(p),mr0,*pr);
792: if ( *pr )
793: (*pr)->sugar = p->sugar;
794: }
795: }
796:
797: void divsdc(vl,p,c,pr)
798: VL vl;
799: DP p;
800: P c;
801: DP *pr;
802: {
803: MP m,mr,mr0;
804:
805: if ( !c )
806: error("disvsdc : division by 0");
807: else if ( !p )
808: *pr = 0;
809: else {
810: for ( mr0 = 0, m = BDY(p); m; m = NEXT(m) ) {
811: NEXTMP(mr0,mr); divsp(vl,C(m),c,&C(mr)); mr->dl = m->dl;
812: }
813: NEXT(mr) = 0; MKDP(NV(p),mr0,*pr);
814: if ( *pr )
815: (*pr)->sugar = p->sugar;
816: }
817: }
818:
819: void adddl(n,d1,d2,dr)
820: int n;
821: DL d1,d2;
822: DL *dr;
823: {
824: DL dt;
825: int i;
826:
827: if ( !d1->td )
828: *dr = d2;
829: else if ( !d2->td )
830: *dr = d1;
831: else {
832: *dr = dt = (DL)MALLOC_ATOMIC((n+1)*sizeof(int));
833: dt->td = d1->td + d2->td;
834: for ( i = 0; i < n; i++ )
835: dt->d[i] = d1->d[i]+d2->d[i];
836: }
1.11 noro 837: }
838:
839: /* d1 += d2 */
840:
841: void adddl_destructive(n,d1,d2)
842: int n;
843: DL d1,d2;
844: {
845: DL dt;
846: int i;
847:
848: d1->td += d2->td;
849: for ( i = 0; i < n; i++ )
850: d1->d[i] += d2->d[i];
1.1 noro 851: }
852:
853: int compd(vl,p1,p2)
854: VL vl;
855: DP p1,p2;
856: {
857: int n,t;
858: MP m1,m2;
859:
860: if ( !p1 )
861: return p2 ? -1 : 0;
862: else if ( !p2 )
863: return 1;
864: else {
865: for ( n = NV(p1), m1 = BDY(p1), m2 = BDY(p2);
866: m1 && m2; m1 = NEXT(m1), m2 = NEXT(m2) )
867: if ( (t = (*cmpdl)(n,m1->dl,m2->dl)) ||
868: (t = compp(vl,C(m1),C(m2)) ) )
869: return t;
870: if ( m1 )
871: return 1;
872: else if ( m2 )
873: return -1;
874: else
875: return 0;
876: }
877: }
878:
879: int cmpdl_lex(n,d1,d2)
880: int n;
881: DL d1,d2;
882: {
883: int i;
884:
885: for ( i = 0; i < n && d1->d[i] == d2->d[i]; i++ );
886: return i == n ? 0 : (d1->d[i] > d2->d[i] ? 1 : -1);
887: }
888:
889: int cmpdl_revlex(n,d1,d2)
890: int n;
891: DL d1,d2;
892: {
893: int i;
894:
895: for ( i = n - 1; i >= 0 && d1->d[i] == d2->d[i]; i-- );
896: return i < 0 ? 0 : (d1->d[i] < d2->d[i] ? 1 : -1);
897: }
898:
899: int cmpdl_gradlex(n,d1,d2)
900: int n;
901: DL d1,d2;
902: {
903: if ( d1->td > d2->td )
904: return 1;
905: else if ( d1->td < d2->td )
906: return -1;
907: else
908: return cmpdl_lex(n,d1,d2);
909: }
910:
911: int cmpdl_revgradlex(n,d1,d2)
912: int n;
913: DL d1,d2;
914: {
1.7 noro 915: register int i;
916: register int *p1,*p2;
917:
1.1 noro 918: if ( d1->td > d2->td )
919: return 1;
920: else if ( d1->td < d2->td )
921: return -1;
1.7 noro 922: else {
923: for ( i= n - 1, p1 = d1->d+n-1, p2 = d2->d+n-1;
924: i >= 0 && *p1 == *p2; i--, p1--, p2-- );
925: return i < 0 ? 0 : (*p1 < *p2 ? 1 : -1);
926: }
1.1 noro 927: }
928:
929: int cmpdl_blex(n,d1,d2)
930: int n;
931: DL d1,d2;
932: {
933: int c;
934:
935: if ( c = cmpdl_lex(n-1,d1,d2) )
936: return c;
937: else {
938: c = d1->d[n-1] - d2->d[n-1];
939: return c > 0 ? 1 : c < 0 ? -1 : 0;
940: }
941: }
942:
943: int cmpdl_bgradlex(n,d1,d2)
944: int n;
945: DL d1,d2;
946: {
947: int e1,e2,c;
948:
949: e1 = d1->td - d1->d[n-1]; e2 = d2->td - d2->d[n-1];
950: if ( e1 > e2 )
951: return 1;
952: else if ( e1 < e2 )
953: return -1;
954: else {
955: c = cmpdl_lex(n-1,d1,d2);
956: if ( c )
957: return c;
958: else
959: return d1->td > d2->td ? 1 : d1->td < d2->td ? -1 : 0;
960: }
961: }
962:
963: int cmpdl_brevgradlex(n,d1,d2)
964: int n;
965: DL d1,d2;
966: {
967: int e1,e2,c;
968:
969: e1 = d1->td - d1->d[n-1]; e2 = d2->td - d2->d[n-1];
970: if ( e1 > e2 )
971: return 1;
972: else if ( e1 < e2 )
973: return -1;
974: else {
975: c = cmpdl_revlex(n-1,d1,d2);
976: if ( c )
977: return c;
978: else
979: return d1->td > d2->td ? 1 : d1->td < d2->td ? -1 : 0;
980: }
981: }
982:
983: int cmpdl_brevrev(n,d1,d2)
984: int n;
985: DL d1,d2;
986: {
987: int e1,e2,f1,f2,c,i;
988:
989: for ( i = 0, e1 = 0, e2 = 0; i < dp_nelim; i++ ) {
990: e1 += d1->d[i]; e2 += d2->d[i];
991: }
992: f1 = d1->td - e1; f2 = d2->td - e2;
993: if ( e1 > e2 )
994: return 1;
995: else if ( e1 < e2 )
996: return -1;
997: else {
998: c = cmpdl_revlex(dp_nelim,d1,d2);
999: if ( c )
1000: return c;
1001: else if ( f1 > f2 )
1002: return 1;
1003: else if ( f1 < f2 )
1004: return -1;
1005: else {
1006: for ( i = n - 1; i >= dp_nelim && d1->d[i] == d2->d[i]; i-- );
1007: return i < dp_nelim ? 0 : (d1->d[i] < d2->d[i] ? 1 : -1);
1008: }
1009: }
1010: }
1011:
1012: int cmpdl_bgradrev(n,d1,d2)
1013: int n;
1014: DL d1,d2;
1015: {
1016: int e1,e2,f1,f2,c,i;
1017:
1018: for ( i = 0, e1 = 0, e2 = 0; i < dp_nelim; i++ ) {
1019: e1 += d1->d[i]; e2 += d2->d[i];
1020: }
1021: f1 = d1->td - e1; f2 = d2->td - e2;
1022: if ( e1 > e2 )
1023: return 1;
1024: else if ( e1 < e2 )
1025: return -1;
1026: else {
1027: c = cmpdl_lex(dp_nelim,d1,d2);
1028: if ( c )
1029: return c;
1030: else if ( f1 > f2 )
1031: return 1;
1032: else if ( f1 < f2 )
1033: return -1;
1034: else {
1035: for ( i = n - 1; i >= dp_nelim && d1->d[i] == d2->d[i]; i-- );
1036: return i < dp_nelim ? 0 : (d1->d[i] < d2->d[i] ? 1 : -1);
1037: }
1038: }
1039: }
1040:
1041: int cmpdl_blexrev(n,d1,d2)
1042: int n;
1043: DL d1,d2;
1044: {
1045: int e1,e2,f1,f2,c,i;
1046:
1047: for ( i = 0, e1 = 0, e2 = 0; i < dp_nelim; i++ ) {
1048: e1 += d1->d[i]; e2 += d2->d[i];
1049: }
1050: f1 = d1->td - e1; f2 = d2->td - e2;
1051: c = cmpdl_lex(dp_nelim,d1,d2);
1052: if ( c )
1053: return c;
1054: else if ( f1 > f2 )
1055: return 1;
1056: else if ( f1 < f2 )
1057: return -1;
1058: else {
1059: for ( i = n - 1; i >= dp_nelim && d1->d[i] == d2->d[i]; i-- );
1060: return i < dp_nelim ? 0 : (d1->d[i] < d2->d[i] ? 1 : -1);
1061: }
1062: }
1063:
1064: int cmpdl_elim(n,d1,d2)
1065: int n;
1066: DL d1,d2;
1067: {
1068: int e1,e2,i;
1069:
1070: for ( i = 0, e1 = 0, e2 = 0; i < dp_nelim; i++ ) {
1071: e1 += d1->d[i]; e2 += d2->d[i];
1072: }
1073: if ( e1 > e2 )
1074: return 1;
1075: else if ( e1 < e2 )
1076: return -1;
1077: else
1078: return cmpdl_revgradlex(n,d1,d2);
1.12 noro 1079: }
1080:
1081: int cmpdl_weyl_elim(n,d1,d2)
1082: int n;
1083: DL d1,d2;
1084: {
1085: int e1,e2,i;
1086:
1087: for ( i = 1, e1 = 0, e2 = 0; i <= dp_nelim; i++ ) {
1088: e1 += d1->d[n-i]; e2 += d2->d[n-i];
1089: }
1090: if ( e1 > e2 )
1091: return 1;
1092: else if ( e1 < e2 )
1093: return -1;
1094: else if ( d1->td > d2->td )
1095: return 1;
1096: else if ( d1->td < d2->td )
1097: return -1;
1098: else return -cmpdl_revlex(n,d1,d2);
1.13 ! noro 1099: }
! 1100:
! 1101: /*
! 1102: a special ordering
! 1103: 1. total order
! 1104: 2. (-w,w) for the first 2*m variables
! 1105: 3. DRL for the first 2*m variables
! 1106: */
! 1107:
! 1108: extern int *current_weight_vector;
! 1109:
! 1110: int cmpdl_homo_ww_drl(n,d1,d2)
! 1111: int n;
! 1112: DL d1,d2;
! 1113: {
! 1114: int e1,e2,m,i;
! 1115: int *p1,*p2;
! 1116:
! 1117: if ( d1->td > d2->td )
! 1118: return 1;
! 1119: else if ( d1->td < d2->td )
! 1120: return -1;
! 1121:
! 1122: m = n>>1;
! 1123: for ( i = 0, e1 = e2 = 0; i < m; i++ ) {
! 1124: e1 += current_weight_vector[i]*(d1->d[m+i] - d1->d[i]);
! 1125: e2 += current_weight_vector[i]*(d2->d[m+i] - d2->d[i]);
! 1126: }
! 1127: if ( e1 > e2 )
! 1128: return 1;
! 1129: else if ( e1 < e2 )
! 1130: return -1;
! 1131:
! 1132: e1 = d1->td - d1->d[n-1];
! 1133: e2 = d2->td - d2->d[n-1];
! 1134: if ( e1 > e2 )
! 1135: return 1;
! 1136: else if ( e1 < e2 )
! 1137: return -1;
! 1138:
! 1139: for ( i= n - 1, p1 = d1->d+n-1, p2 = d2->d+n-1;
! 1140: i >= 0 && *p1 == *p2; i--, p1--, p2-- );
! 1141: return i < 0 ? 0 : (*p1 < *p2 ? 1 : -1);
1.1 noro 1142: }
1143:
1144: int cmpdl_order_pair(n,d1,d2)
1145: int n;
1146: DL d1,d2;
1147: {
1148: int e1,e2,i,j,l;
1149: int *t1,*t2;
1150: int len;
1151: struct order_pair *pair;
1152:
1153: len = dp_current_spec.ord.block.length;
1154: pair = dp_current_spec.ord.block.order_pair;
1155:
1156: for ( i = 0, t1 = d1->d, t2 = d2->d; i < len; i++ ) {
1157: l = pair[i].length;
1158: switch ( pair[i].order ) {
1159: case 0:
1160: for ( j = 0, e1 = e2 = 0; j < l; j++ ) {
1161: e1 += t1[j]; e2 += t2[j];
1162: }
1163: if ( e1 > e2 )
1164: return 1;
1165: else if ( e1 < e2 )
1166: return -1;
1167: else {
1168: for ( j = l - 1; j >= 0 && t1[j] == t2[j]; j-- );
1169: if ( j >= 0 )
1170: return t1[j] < t2[j] ? 1 : -1;
1171: }
1172: break;
1173: case 1:
1174: for ( j = 0, e1 = e2 = 0; j < l; j++ ) {
1175: e1 += t1[j]; e2 += t2[j];
1176: }
1177: if ( e1 > e2 )
1178: return 1;
1179: else if ( e1 < e2 )
1180: return -1;
1181: else {
1182: for ( j = 0; j < l && t1[j] == t2[j]; j++ );
1183: if ( j < l )
1184: return t1[j] > t2[j] ? 1 : -1;
1185: }
1186: break;
1187: case 2:
1188: for ( j = 0; j < l && t1[j] == t2[j]; j++ );
1189: if ( j < l )
1190: return t1[j] > t2[j] ? 1 : -1;
1191: break;
1192: default:
1193: error("cmpdl_order_pair : invalid order"); break;
1194: }
1195: t1 += l; t2 += l;
1196: }
1197: return 0;
1198: }
1199:
1200: int cmpdl_matrix(n,d1,d2)
1201: int n;
1202: DL d1,d2;
1203: {
1204: int *v,*w,*t1,*t2;
1205: int s,i,j,len;
1206: int **matrix;
1207:
1208: for ( i = 0, t1 = d1->d, t2 = d2->d, w = dp_dl_work; i < n; i++ )
1209: w[i] = t1[i]-t2[i];
1210: len = dp_current_spec.ord.matrix.row;
1211: matrix = dp_current_spec.ord.matrix.matrix;
1212: for ( j = 0; j < len; j++ ) {
1213: v = matrix[j];
1214: for ( i = 0, s = 0; i < n; i++ )
1215: s += v[i]*w[i];
1216: if ( s > 0 )
1217: return 1;
1218: else if ( s < 0 )
1219: return -1;
1220: }
1221: return 0;
1222: }