![[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.12 ! noro 48: * $OpenXM: OpenXM_contrib2/asir2000/engine/dist.c,v 1.11 2000/12/05 06:59:16 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.1 noro 63:
64: int (*cmpdl)()=cmpdl_revgradlex;
65: int (*primitive_cmpdl[3])() = {cmpdl_revgradlex,cmpdl_gradlex,cmpdl_lex};
66:
1.2 noro 67: void comm_muld(VL,DP,DP,DP *);
68: void weyl_muld(VL,DP,DP,DP *);
1.10 noro 69: void weyl_muldm(VL,MP,DP,DP *);
70: void weyl_mulmm(VL,MP,MP,int,struct cdl *,int);
71: void comm_muld_tab(VL,int,struct cdl *,int,struct cdl *,int,struct cdl *);
72:
1.2 noro 73: void mkwc(int,int,Q *);
74:
1.12 ! noro 75: int cmpdl_weyl_elim();
! 76:
1.2 noro 77: int do_weyl;
78:
1.1 noro 79: int dp_nelim,dp_fcoeffs;
80: struct order_spec dp_current_spec;
81: int *dp_dl_work;
82:
83: int has_fcoef(DP);
84: int has_fcoef_p(P);
85:
86: int has_fcoef(f)
87: DP f;
88: {
89: MP t;
90:
91: if ( !f )
92: return 0;
93: for ( t = BDY(f); t; t = NEXT(t) )
94: if ( has_fcoef_p(t->c) )
95: break;
96: return t ? 1 : 0;
97: }
98:
99: int has_fcoef_p(f)
100: P f;
101: {
102: DCP dc;
103:
104: if ( !f )
105: return 0;
106: else if ( NUM(f) )
107: return (NID((Num)f) == N_LM || NID((Num)f) == N_GF2N) ? 1 : 0;
108: else {
109: for ( dc = DC(f); dc; dc = NEXT(dc) )
110: if ( has_fcoef_p(COEF(dc)) )
111: return 1;
112: return 0;
113: }
114: }
115:
116: void initd(spec)
117: struct order_spec *spec;
118: {
119: switch ( spec->id ) {
120: case 2:
121: cmpdl = cmpdl_matrix;
122: dp_dl_work = (int *)MALLOC_ATOMIC(spec->nv*sizeof(int));
123: break;
124: case 1:
125: cmpdl = cmpdl_order_pair;
126: break;
127: default:
128: switch ( spec->ord.simple ) {
129: case ORD_REVGRADLEX:
130: cmpdl = cmpdl_revgradlex; break;
131: case ORD_GRADLEX:
132: cmpdl = cmpdl_gradlex; break;
133: case ORD_BREVGRADLEX:
134: cmpdl = cmpdl_brevgradlex; break;
135: case ORD_BGRADLEX:
136: cmpdl = cmpdl_bgradlex; break;
137: case ORD_BLEX:
138: cmpdl = cmpdl_blex; break;
139: case ORD_BREVREV:
140: cmpdl = cmpdl_brevrev; break;
141: case ORD_BGRADREV:
142: cmpdl = cmpdl_bgradrev; break;
143: case ORD_BLEXREV:
144: cmpdl = cmpdl_blexrev; break;
145: case ORD_ELIM:
146: cmpdl = cmpdl_elim; break;
1.12 ! noro 147: case ORD_WEYL_ELIM:
! 148: cmpdl = cmpdl_weyl_elim; break;
1.1 noro 149: case ORD_LEX: default:
150: cmpdl = cmpdl_lex; break;
151: }
152: break;
153: }
154: dp_current_spec = *spec;
155: }
156:
157: void ptod(vl,dvl,p,pr)
158: VL vl,dvl;
159: P p;
160: DP *pr;
161: {
162: int isconst = 0;
163: int n,i;
164: VL tvl;
165: V v;
166: DL d;
167: MP m;
168: DCP dc;
169: DP r,s,t,u;
170: P x,c;
171:
172: if ( !p )
173: *pr = 0;
174: else {
175: for ( n = 0, tvl = dvl; tvl; tvl = NEXT(tvl), n++ );
176: if ( NUM(p) ) {
177: NEWDL(d,n);
178: NEWMP(m); m->dl = d; C(m) = p; NEXT(m) = 0; MKDP(n,m,*pr); (*pr)->sugar = 0;
179: } else {
180: for ( i = 0, tvl = dvl, v = VR(p);
181: tvl && tvl->v != v; tvl = NEXT(tvl), i++ );
182: if ( !tvl ) {
183: for ( dc = DC(p), s = 0, MKV(v,x); dc; dc = NEXT(dc) ) {
184: ptod(vl,dvl,COEF(dc),&t); pwrp(vl,x,DEG(dc),&c);
185: muldc(vl,t,c,&r); addd(vl,r,s,&t); s = t;
186: }
187: *pr = s;
188: } else {
189: for ( dc = DC(p), s = 0; dc; dc = NEXT(dc) ) {
190: ptod(vl,dvl,COEF(dc),&t);
191: NEWDL(d,n); d->td = QTOS(DEG(dc)); d->d[i] = d->td;
192: NEWMP(m); m->dl = d; C(m) = (P)ONE; NEXT(m) = 0; MKDP(n,m,u); u->sugar = d->td;
1.2 noro 193: comm_muld(vl,t,u,&r); addd(vl,r,s,&t); s = t;
1.1 noro 194: }
195: *pr = s;
196: }
197: }
198: }
199: if ( !dp_fcoeffs && has_fcoef(*pr) )
200: dp_fcoeffs = 1;
201: }
202:
203: void dtop(vl,dvl,p,pr)
204: VL vl,dvl;
205: DP p;
206: P *pr;
207: {
208: int n,i;
209: DL d;
210: MP m;
211: P r,s,t,u,w;
212: Q q;
213: VL tvl;
214:
215: if ( !p )
216: *pr = 0;
217: else {
218: for ( n = p->nv, m = BDY(p), s = 0; m; m = NEXT(m) ) {
219: t = C(m);
220: if ( NUM(t) && NID((Num)t) == N_M ) {
221: mptop(t,&u); t = u;
222: }
223: for ( i = 0, d = m->dl, tvl = dvl;
224: i < n; tvl = NEXT(tvl), i++ ) {
225: MKV(tvl->v,r); STOQ(d->d[i],q); pwrp(vl,r,q,&u);
226: mulp(vl,t,u,&w); t = w;
227: }
228: addp(vl,s,t,&u); s = u;
229: }
230: *pr = s;
231: }
232: }
233:
234: void nodetod(node,dp)
235: NODE node;
236: DP *dp;
237: {
238: NODE t;
239: int len,i,td;
240: Q e;
241: DL d;
242: MP m;
243: DP u;
244:
245: for ( t = node, len = 0; t; t = NEXT(t), len++ );
246: NEWDL(d,len);
247: for ( t = node, i = 0, td = 0; i < len; t = NEXT(t), i++ ) {
248: e = (Q)BDY(t);
249: if ( !e )
250: d->d[i] = 0;
251: else if ( !NUM(e) || !RATN(e) || !INT(e) )
252: error("nodetod : invalid input");
253: else {
254: d->d[i] = QTOS((Q)e); td += d->d[i];
255: }
256: }
257: d->td = td;
258: NEWMP(m); m->dl = d; C(m) = (P)ONE; NEXT(m) = 0;
259: MKDP(len,m,u); u->sugar = td; *dp = u;
260: }
261:
262: int sugard(m)
263: MP m;
264: {
265: int s;
266:
267: for ( s = 0; m; m = NEXT(m) )
268: s = MAX(s,m->dl->td);
269: return s;
270: }
271:
272: void addd(vl,p1,p2,pr)
273: VL vl;
274: DP p1,p2,*pr;
275: {
276: int n;
277: MP m1,m2,mr,mr0;
278: P t;
279:
280: if ( !p1 )
281: *pr = p2;
282: else if ( !p2 )
283: *pr = p1;
284: else {
285: for ( n = NV(p1), m1 = BDY(p1), m2 = BDY(p2), mr0 = 0; m1 && m2; )
286: switch ( (*cmpdl)(n,m1->dl,m2->dl) ) {
287: case 0:
288: addp(vl,C(m1),C(m2),&t);
289: if ( t ) {
290: NEXTMP(mr0,mr); mr->dl = m1->dl; C(mr) = t;
291: }
292: m1 = NEXT(m1); m2 = NEXT(m2); break;
293: case 1:
294: NEXTMP(mr0,mr); mr->dl = m1->dl; C(mr) = C(m1);
295: m1 = NEXT(m1); break;
296: case -1:
297: NEXTMP(mr0,mr); mr->dl = m2->dl; C(mr) = C(m2);
298: m2 = NEXT(m2); break;
299: }
300: if ( !mr0 )
301: if ( m1 )
302: mr0 = m1;
303: else if ( m2 )
304: mr0 = m2;
305: else {
306: *pr = 0;
307: return;
308: }
309: else if ( m1 )
310: NEXT(mr) = m1;
311: else if ( m2 )
312: NEXT(mr) = m2;
313: else
314: NEXT(mr) = 0;
315: MKDP(NV(p1),mr0,*pr);
316: if ( *pr )
317: (*pr)->sugar = MAX(p1->sugar,p2->sugar);
318: }
319: }
320:
321: /* for F4 symbolic reduction */
322:
323: void symb_addd(p1,p2,pr)
324: DP p1,p2,*pr;
325: {
326: int n;
327: MP m1,m2,mr,mr0;
328: P t;
329:
330: if ( !p1 )
331: *pr = p2;
332: else if ( !p2 )
333: *pr = p1;
334: else {
335: for ( n = NV(p1), m1 = BDY(p1), m2 = BDY(p2), mr0 = 0; m1 && m2; ) {
336: NEXTMP(mr0,mr); C(mr) = (P)ONE;
337: switch ( (*cmpdl)(n,m1->dl,m2->dl) ) {
338: case 0:
339: mr->dl = m1->dl;
340: m1 = NEXT(m1); m2 = NEXT(m2); break;
341: case 1:
342: mr->dl = m1->dl;
343: m1 = NEXT(m1); break;
344: case -1:
345: mr->dl = m2->dl;
346: m2 = NEXT(m2); break;
347: }
348: }
349: if ( !mr0 )
350: if ( m1 )
351: mr0 = m1;
352: else if ( m2 )
353: mr0 = m2;
354: else {
355: *pr = 0;
356: return;
357: }
358: else if ( m1 )
359: NEXT(mr) = m1;
360: else if ( m2 )
361: NEXT(mr) = m2;
362: else
363: NEXT(mr) = 0;
364: MKDP(NV(p1),mr0,*pr);
365: if ( *pr )
366: (*pr)->sugar = MAX(p1->sugar,p2->sugar);
1.3 noro 367: }
368: }
369:
370: /*
371: * destructive merge of two list
372: *
373: * p1, p2 : list of DL
374: * return : a merged list
375: */
376:
377: NODE symb_merge(m1,m2,n)
378: NODE m1,m2;
379: int n;
380: {
381: NODE top,prev,cur,m,t;
382:
383: if ( !m1 )
384: return m2;
385: else if ( !m2 )
386: return m1;
387: else {
388: switch ( (*cmpdl)(n,(DL)BDY(m1),(DL)BDY(m2)) ) {
389: case 0:
390: top = m1; m = NEXT(m2);
391: break;
392: case 1:
393: top = m1; m = m2;
394: break;
395: case -1:
396: top = m2; m = m1;
397: break;
398: }
399: prev = top; cur = NEXT(top);
400: /* BDY(prev) > BDY(m) always holds */
401: while ( cur && m ) {
402: switch ( (*cmpdl)(n,(DL)BDY(cur),(DL)BDY(m)) ) {
403: case 0:
404: m = NEXT(m);
405: prev = cur; cur = NEXT(cur);
406: break;
407: case 1:
408: t = NEXT(cur); NEXT(cur) = m; m = t;
409: prev = cur; cur = NEXT(cur);
410: break;
411: case -1:
412: NEXT(prev) = m; m = cur;
413: prev = NEXT(prev); cur = NEXT(prev);
414: break;
415: }
416: }
417: if ( !cur )
418: NEXT(prev) = m;
419: return top;
1.1 noro 420: }
421: }
422:
423: void subd(vl,p1,p2,pr)
424: VL vl;
425: DP p1,p2,*pr;
426: {
427: DP t;
428:
429: if ( !p2 )
430: *pr = p1;
431: else {
432: chsgnd(p2,&t); addd(vl,p1,t,pr);
433: }
434: }
435:
436: void chsgnd(p,pr)
437: DP p,*pr;
438: {
439: MP m,mr,mr0;
440:
441: if ( !p )
442: *pr = 0;
443: else {
444: for ( mr0 = 0, m = BDY(p); m; m = NEXT(m) ) {
445: NEXTMP(mr0,mr); chsgnp(C(m),&C(mr)); mr->dl = m->dl;
446: }
447: NEXT(mr) = 0; MKDP(NV(p),mr0,*pr);
448: if ( *pr )
449: (*pr)->sugar = p->sugar;
450: }
451: }
452:
453: void muld(vl,p1,p2,pr)
454: VL vl;
455: DP p1,p2,*pr;
456: {
1.2 noro 457: if ( ! do_weyl )
458: comm_muld(vl,p1,p2,pr);
459: else
460: weyl_muld(vl,p1,p2,pr);
461: }
462:
463: void comm_muld(vl,p1,p2,pr)
464: VL vl;
465: DP p1,p2,*pr;
466: {
1.1 noro 467: MP m;
468: DP s,t,u;
1.5 noro 469: int i,l,l1;
470: static MP *w;
471: static int wlen;
1.1 noro 472:
473: if ( !p1 || !p2 )
474: *pr = 0;
475: else if ( OID(p1) <= O_P )
476: muldc(vl,p2,(P)p1,pr);
477: else if ( OID(p2) <= O_P )
478: muldc(vl,p1,(P)p2,pr);
479: else {
1.5 noro 480: for ( m = BDY(p1), l1 = 0; m; m = NEXT(m), l1++ );
1.4 noro 481: for ( m = BDY(p2), l = 0; m; m = NEXT(m), l++ );
1.5 noro 482: if ( l1 < l ) {
483: t = p1; p1 = p2; p2 = t;
484: l = l1;
485: }
486: if ( l > wlen ) {
487: if ( w ) GC_free(w);
488: w = (MP *)MALLOC(l*sizeof(MP));
489: wlen = l;
490: }
1.4 noro 491: for ( m = BDY(p2), i = 0; i < l; m = NEXT(m), i++ )
492: w[i] = m;
493: for ( s = 0, i = l-1; i >= 0; i-- ) {
494: muldm(vl,p1,w[i],&t); addd(vl,s,t,&u); s = u;
1.1 noro 495: }
1.5 noro 496: bzero(w,l*sizeof(MP));
1.1 noro 497: *pr = s;
498: }
499: }
500:
501: void muldm(vl,p,m0,pr)
502: VL vl;
503: DP p;
504: MP m0;
505: DP *pr;
506: {
507: MP m,mr,mr0;
508: P c;
509: DL d;
510: int n;
511:
512: if ( !p )
513: *pr = 0;
514: else {
515: for ( mr0 = 0, m = BDY(p), c = C(m0), d = m0->dl, n = NV(p);
516: m; m = NEXT(m) ) {
517: NEXTMP(mr0,mr);
518: if ( NUM(C(m)) && RATN(C(m)) && NUM(c) && RATN(c) )
519: mulq((Q)C(m),(Q)c,(Q *)&C(mr));
520: else
521: mulp(vl,C(m),c,&C(mr));
522: adddl(n,m->dl,d,&mr->dl);
523: }
524: NEXT(mr) = 0; MKDP(NV(p),mr0,*pr);
525: if ( *pr )
526: (*pr)->sugar = p->sugar + m0->dl->td;
1.2 noro 527: }
528: }
529:
530: void weyl_muld(vl,p1,p2,pr)
531: VL vl;
532: DP p1,p2,*pr;
533: {
534: MP m;
535: DP s,t,u;
1.4 noro 536: int i,l;
1.5 noro 537: static MP *w;
538: static int wlen;
1.2 noro 539:
540: if ( !p1 || !p2 )
541: *pr = 0;
542: else if ( OID(p1) <= O_P )
543: muldc(vl,p2,(P)p1,pr);
544: else if ( OID(p2) <= O_P )
545: muldc(vl,p1,(P)p2,pr);
546: else {
1.10 noro 547: for ( m = BDY(p1), l = 0; m; m = NEXT(m), l++ );
1.5 noro 548: if ( l > wlen ) {
549: if ( w ) GC_free(w);
550: w = (MP *)MALLOC(l*sizeof(MP));
551: wlen = l;
552: }
1.10 noro 553: for ( m = BDY(p1), i = 0; i < l; m = NEXT(m), i++ )
1.4 noro 554: w[i] = m;
555: for ( s = 0, i = l-1; i >= 0; i-- ) {
1.10 noro 556: weyl_muldm(vl,w[i],p2,&t); addd(vl,s,t,&u); s = u;
1.2 noro 557: }
1.5 noro 558: bzero(w,l*sizeof(MP));
1.2 noro 559: *pr = s;
560: }
561: }
562:
1.10 noro 563: /* monomial * polynomial */
564:
565: void weyl_muldm(vl,m0,p,pr)
1.2 noro 566: VL vl;
1.10 noro 567: MP m0;
1.2 noro 568: DP p;
569: DP *pr;
570: {
571: DP r,t,t1;
572: MP m;
1.10 noro 573: DL d0;
574: int n,n2,l,i,j,tlen;
575: static MP *w,*psum;
576: static struct cdl *tab;
1.5 noro 577: static int wlen;
1.10 noro 578: static int rtlen;
1.2 noro 579:
580: if ( !p )
581: *pr = 0;
582: else {
1.4 noro 583: for ( m = BDY(p), l = 0; m; m = NEXT(m), l++ );
1.5 noro 584: if ( l > wlen ) {
585: if ( w ) GC_free(w);
586: w = (MP *)MALLOC(l*sizeof(MP));
587: wlen = l;
588: }
1.4 noro 589: for ( m = BDY(p), i = 0; i < l; m = NEXT(m), i++ )
590: w[i] = m;
1.10 noro 591:
592: n = NV(p); n2 = n>>1;
593: d0 = m0->dl;
594: for ( i = 0, tlen = 1; i < n2; i++ )
595: tlen *= d0->d[n2+i]+1;
596: if ( tlen > rtlen ) {
597: if ( tab ) GC_free(tab);
598: if ( psum ) GC_free(psum);
599: rtlen = tlen;
600: tab = (struct cdl *)MALLOC(rtlen*sizeof(struct cdl));
601: psum = (MP *)MALLOC(rtlen*sizeof(MP));
602: }
603: bzero(psum,tlen*sizeof(MP));
604: for ( i = l-1; i >= 0; i-- ) {
605: bzero(tab,tlen*sizeof(struct cdl));
606: weyl_mulmm(vl,m0,w[i],n,tab,tlen);
607: for ( j = 0; j < tlen; j++ ) {
608: if ( tab[j].c ) {
609: NEWMP(m); m->dl = tab[j].d; C(m) = tab[j].c; NEXT(m) = psum[j];
610: psum[j] = m;
611: }
612: }
1.2 noro 613: }
1.10 noro 614: for ( j = tlen-1, r = 0; j >= 0; j-- )
615: if ( psum[j] ) {
616: MKDP(n,psum[j],t); addd(vl,r,t,&t1); r = t1;
617: }
1.2 noro 618: if ( r )
619: r->sugar = p->sugar + m0->dl->td;
620: *pr = r;
621: }
622: }
623:
1.10 noro 624: /* m0 = x0^d0*x1^d1*... * dx0^e0*dx1^e1*... */
625: /* rtab : array of length (e0+1)*(e1+1)*... */
1.2 noro 626:
1.10 noro 627: void weyl_mulmm(vl,m0,m1,n,rtab,rtablen)
1.2 noro 628: VL vl;
629: MP m0,m1;
630: int n;
1.10 noro 631: struct cdl *rtab;
632: int rtablen;
1.2 noro 633: {
634: MP m,mr,mr0;
635: DP r,t,t1;
636: P c,c0,c1,cc;
1.10 noro 637: DL d,d0,d1,dt;
638: int i,j,a,b,k,l,n2,s,min,curlen;
639: struct cdl *p;
640: static Q *ctab;
641: static struct cdl *tab;
1.5 noro 642: static int tablen;
1.10 noro 643: static struct cdl *tmptab;
644: static int tmptablen;
1.2 noro 645:
1.10 noro 646:
647: if ( !m0 || !m1 ) {
648: rtab[0].c = 0;
649: rtab[0].d = 0;
650: return;
651: }
652: c0 = C(m0); c1 = C(m1);
653: mulp(vl,c0,c1,&c);
654: d0 = m0->dl; d1 = m1->dl;
655: n2 = n>>1;
656: curlen = 1;
657: NEWDL(d,n);
658: if ( n & 1 )
659: /* offset of h-degree */
660: d->td = d->d[n-1] = d0->d[n-1]+d1->d[n-1];
661: else
662: d->td = 0;
663: rtab[0].c = c;
664: rtab[0].d = d;
665:
666: if ( rtablen > tmptablen ) {
667: if ( tmptab ) GC_free(tmptab);
668: tmptab = (struct cdl *)MALLOC(rtablen*sizeof(struct cdl));
669: tmptablen = rtablen;
670: }
671: for ( i = 0; i < n2; i++ ) {
672: a = d0->d[i]; b = d1->d[n2+i];
673: k = d0->d[n2+i]; l = d1->d[i];
674: if ( !k || !l ) {
675: a += l;
676: b += k;
677: s = a+b;
678: for ( j = 0, p = rtab; j < curlen; j++, p++ ) {
679: if ( p->c ) {
680: dt = p->d;
681: dt->d[i] = a;
682: dt->d[n2+i] = b;
683: dt->td += s;
1.5 noro 684: }
1.10 noro 685: }
686: curlen *= k+1;
687: continue;
688: }
689: if ( k+1 > tablen ) {
690: if ( tab ) GC_free(tab);
691: if ( ctab ) GC_free(ctab);
692: tablen = k+1;
693: tab = (struct cdl *)MALLOC(tablen*sizeof(struct cdl));
694: ctab = (Q *)MALLOC(tablen*sizeof(Q));
695: }
696: /* degree of xi^a*(Di^k*xi^l)*Di^b */
697: s = a+k+l+b;
698: /* compute xi^a*(Di^k*xi^l)*Di^b */
699: min = MIN(k,l);
700: mkwc(k,l,ctab);
701: bzero(tab,(k+1)*sizeof(struct cdl));
702: if ( n & 1 )
703: for ( j = 0; j <= min; j++ ) {
704: NEWDL(d,n);
705: d->d[i] = l-j+a; d->d[n2+i] = k-j+b;
706: d->td = s;
707: d->d[n-1] = s-(d->d[i]+d->d[n2+i]);
708: tab[j].d = d;
709: tab[j].c = (P)ctab[j];
710: }
711: else
712: for ( j = 0; j <= min; j++ ) {
713: NEWDL(d,n);
714: d->d[i] = l-j+a; d->d[n2+i] = k-j+b;
715: d->td = d->d[i]+d->d[n2+i]; /* XXX */
716: tab[j].d = d;
717: tab[j].c = (P)ctab[j];
718: }
719: bzero(ctab,(min+1)*sizeof(Q));
720: comm_muld_tab(vl,n,rtab,curlen,tab,k+1,tmptab);
721: curlen *= k+1;
722: bcopy(tmptab,rtab,curlen*sizeof(struct cdl));
723: }
724: }
725:
726: /* direct product of two cdl tables
727: rt[] = [
728: t[0]*t1[0],...,t[n-1]*t1[0],
729: t[0]*t1[1],...,t[n-1]*t1[1],
730: ...
731: t[0]*t1[n1-1],...,t[n-1]*t1[n1-1]
732: ]
733: */
734:
735: void comm_muld_tab(vl,nv,t,n,t1,n1,rt)
736: VL vl;
737: int nv;
738: struct cdl *t;
739: int n;
740: struct cdl *t1;
741: int n1;
742: struct cdl *rt;
743: {
744: int i,j;
745: struct cdl *p;
746: P c;
747: DL d;
748:
749: bzero(rt,n*n1*sizeof(struct cdl));
750: for ( j = 0, p = rt; j < n1; j++ ) {
751: c = t1[j].c;
752: d = t1[j].d;
753: if ( !c )
754: break;
755: for ( i = 0; i < n; i++, p++ ) {
756: if ( t[i].c ) {
757: mulp(vl,t[i].c,c,&p->c);
758: adddl(nv,t[i].d,d,&p->d);
759: }
1.6 noro 760: }
1.1 noro 761: }
762: }
763:
764: void muldc(vl,p,c,pr)
765: VL vl;
766: DP p;
767: P c;
768: DP *pr;
769: {
770: MP m,mr,mr0;
771:
772: if ( !p || !c )
773: *pr = 0;
774: else if ( NUM(c) && UNIQ((Q)c) )
775: *pr = p;
776: else if ( NUM(c) && MUNIQ((Q)c) )
777: chsgnd(p,pr);
778: else {
779: for ( mr0 = 0, m = BDY(p); m; m = NEXT(m) ) {
780: NEXTMP(mr0,mr);
781: if ( NUM(C(m)) && RATN(C(m)) && NUM(c) && RATN(c) )
782: mulq((Q)C(m),(Q)c,(Q *)&C(mr));
783: else
784: mulp(vl,C(m),c,&C(mr));
785: mr->dl = m->dl;
786: }
787: NEXT(mr) = 0; MKDP(NV(p),mr0,*pr);
788: if ( *pr )
789: (*pr)->sugar = p->sugar;
790: }
791: }
792:
793: void divsdc(vl,p,c,pr)
794: VL vl;
795: DP p;
796: P c;
797: DP *pr;
798: {
799: MP m,mr,mr0;
800:
801: if ( !c )
802: error("disvsdc : division by 0");
803: else if ( !p )
804: *pr = 0;
805: else {
806: for ( mr0 = 0, m = BDY(p); m; m = NEXT(m) ) {
807: NEXTMP(mr0,mr); divsp(vl,C(m),c,&C(mr)); mr->dl = m->dl;
808: }
809: NEXT(mr) = 0; MKDP(NV(p),mr0,*pr);
810: if ( *pr )
811: (*pr)->sugar = p->sugar;
812: }
813: }
814:
815: void adddl(n,d1,d2,dr)
816: int n;
817: DL d1,d2;
818: DL *dr;
819: {
820: DL dt;
821: int i;
822:
823: if ( !d1->td )
824: *dr = d2;
825: else if ( !d2->td )
826: *dr = d1;
827: else {
828: *dr = dt = (DL)MALLOC_ATOMIC((n+1)*sizeof(int));
829: dt->td = d1->td + d2->td;
830: for ( i = 0; i < n; i++ )
831: dt->d[i] = d1->d[i]+d2->d[i];
832: }
1.11 noro 833: }
834:
835: /* d1 += d2 */
836:
837: void adddl_destructive(n,d1,d2)
838: int n;
839: DL d1,d2;
840: {
841: DL dt;
842: int i;
843:
844: d1->td += d2->td;
845: for ( i = 0; i < n; i++ )
846: d1->d[i] += d2->d[i];
1.1 noro 847: }
848:
849: int compd(vl,p1,p2)
850: VL vl;
851: DP p1,p2;
852: {
853: int n,t;
854: MP m1,m2;
855:
856: if ( !p1 )
857: return p2 ? -1 : 0;
858: else if ( !p2 )
859: return 1;
860: else {
861: for ( n = NV(p1), m1 = BDY(p1), m2 = BDY(p2);
862: m1 && m2; m1 = NEXT(m1), m2 = NEXT(m2) )
863: if ( (t = (*cmpdl)(n,m1->dl,m2->dl)) ||
864: (t = compp(vl,C(m1),C(m2)) ) )
865: return t;
866: if ( m1 )
867: return 1;
868: else if ( m2 )
869: return -1;
870: else
871: return 0;
872: }
873: }
874:
875: int cmpdl_lex(n,d1,d2)
876: int n;
877: DL d1,d2;
878: {
879: int i;
880:
881: for ( i = 0; i < n && d1->d[i] == d2->d[i]; i++ );
882: return i == n ? 0 : (d1->d[i] > d2->d[i] ? 1 : -1);
883: }
884:
885: int cmpdl_revlex(n,d1,d2)
886: int n;
887: DL d1,d2;
888: {
889: int i;
890:
891: for ( i = n - 1; i >= 0 && d1->d[i] == d2->d[i]; i-- );
892: return i < 0 ? 0 : (d1->d[i] < d2->d[i] ? 1 : -1);
893: }
894:
895: int cmpdl_gradlex(n,d1,d2)
896: int n;
897: DL d1,d2;
898: {
899: if ( d1->td > d2->td )
900: return 1;
901: else if ( d1->td < d2->td )
902: return -1;
903: else
904: return cmpdl_lex(n,d1,d2);
905: }
906:
907: int cmpdl_revgradlex(n,d1,d2)
908: int n;
909: DL d1,d2;
910: {
1.7 noro 911: register int i;
912: register int *p1,*p2;
913:
1.1 noro 914: if ( d1->td > d2->td )
915: return 1;
916: else if ( d1->td < d2->td )
917: return -1;
1.7 noro 918: else {
919: for ( i= n - 1, p1 = d1->d+n-1, p2 = d2->d+n-1;
920: i >= 0 && *p1 == *p2; i--, p1--, p2-- );
921: return i < 0 ? 0 : (*p1 < *p2 ? 1 : -1);
922: }
1.1 noro 923: }
924:
925: int cmpdl_blex(n,d1,d2)
926: int n;
927: DL d1,d2;
928: {
929: int c;
930:
931: if ( c = cmpdl_lex(n-1,d1,d2) )
932: return c;
933: else {
934: c = d1->d[n-1] - d2->d[n-1];
935: return c > 0 ? 1 : c < 0 ? -1 : 0;
936: }
937: }
938:
939: int cmpdl_bgradlex(n,d1,d2)
940: int n;
941: DL d1,d2;
942: {
943: int e1,e2,c;
944:
945: e1 = d1->td - d1->d[n-1]; e2 = d2->td - d2->d[n-1];
946: if ( e1 > e2 )
947: return 1;
948: else if ( e1 < e2 )
949: return -1;
950: else {
951: c = cmpdl_lex(n-1,d1,d2);
952: if ( c )
953: return c;
954: else
955: return d1->td > d2->td ? 1 : d1->td < d2->td ? -1 : 0;
956: }
957: }
958:
959: int cmpdl_brevgradlex(n,d1,d2)
960: int n;
961: DL d1,d2;
962: {
963: int e1,e2,c;
964:
965: e1 = d1->td - d1->d[n-1]; e2 = d2->td - d2->d[n-1];
966: if ( e1 > e2 )
967: return 1;
968: else if ( e1 < e2 )
969: return -1;
970: else {
971: c = cmpdl_revlex(n-1,d1,d2);
972: if ( c )
973: return c;
974: else
975: return d1->td > d2->td ? 1 : d1->td < d2->td ? -1 : 0;
976: }
977: }
978:
979: int cmpdl_brevrev(n,d1,d2)
980: int n;
981: DL d1,d2;
982: {
983: int e1,e2,f1,f2,c,i;
984:
985: for ( i = 0, e1 = 0, e2 = 0; i < dp_nelim; i++ ) {
986: e1 += d1->d[i]; e2 += d2->d[i];
987: }
988: f1 = d1->td - e1; f2 = d2->td - e2;
989: if ( e1 > e2 )
990: return 1;
991: else if ( e1 < e2 )
992: return -1;
993: else {
994: c = cmpdl_revlex(dp_nelim,d1,d2);
995: if ( c )
996: return c;
997: else if ( f1 > f2 )
998: return 1;
999: else if ( f1 < f2 )
1000: return -1;
1001: else {
1002: for ( i = n - 1; i >= dp_nelim && d1->d[i] == d2->d[i]; i-- );
1003: return i < dp_nelim ? 0 : (d1->d[i] < d2->d[i] ? 1 : -1);
1004: }
1005: }
1006: }
1007:
1008: int cmpdl_bgradrev(n,d1,d2)
1009: int n;
1010: DL d1,d2;
1011: {
1012: int e1,e2,f1,f2,c,i;
1013:
1014: for ( i = 0, e1 = 0, e2 = 0; i < dp_nelim; i++ ) {
1015: e1 += d1->d[i]; e2 += d2->d[i];
1016: }
1017: f1 = d1->td - e1; f2 = d2->td - e2;
1018: if ( e1 > e2 )
1019: return 1;
1020: else if ( e1 < e2 )
1021: return -1;
1022: else {
1023: c = cmpdl_lex(dp_nelim,d1,d2);
1024: if ( c )
1025: return c;
1026: else if ( f1 > f2 )
1027: return 1;
1028: else if ( f1 < f2 )
1029: return -1;
1030: else {
1031: for ( i = n - 1; i >= dp_nelim && d1->d[i] == d2->d[i]; i-- );
1032: return i < dp_nelim ? 0 : (d1->d[i] < d2->d[i] ? 1 : -1);
1033: }
1034: }
1035: }
1036:
1037: int cmpdl_blexrev(n,d1,d2)
1038: int n;
1039: DL d1,d2;
1040: {
1041: int e1,e2,f1,f2,c,i;
1042:
1043: for ( i = 0, e1 = 0, e2 = 0; i < dp_nelim; i++ ) {
1044: e1 += d1->d[i]; e2 += d2->d[i];
1045: }
1046: f1 = d1->td - e1; f2 = d2->td - e2;
1047: c = cmpdl_lex(dp_nelim,d1,d2);
1048: if ( c )
1049: return c;
1050: else if ( f1 > f2 )
1051: return 1;
1052: else if ( f1 < f2 )
1053: return -1;
1054: else {
1055: for ( i = n - 1; i >= dp_nelim && d1->d[i] == d2->d[i]; i-- );
1056: return i < dp_nelim ? 0 : (d1->d[i] < d2->d[i] ? 1 : -1);
1057: }
1058: }
1059:
1060: int cmpdl_elim(n,d1,d2)
1061: int n;
1062: DL d1,d2;
1063: {
1064: int e1,e2,i;
1065:
1066: for ( i = 0, e1 = 0, e2 = 0; i < dp_nelim; i++ ) {
1067: e1 += d1->d[i]; e2 += d2->d[i];
1068: }
1069: if ( e1 > e2 )
1070: return 1;
1071: else if ( e1 < e2 )
1072: return -1;
1073: else
1074: return cmpdl_revgradlex(n,d1,d2);
1.12 ! noro 1075: }
! 1076:
! 1077: int cmpdl_weyl_elim(n,d1,d2)
! 1078: int n;
! 1079: DL d1,d2;
! 1080: {
! 1081: int e1,e2,i;
! 1082:
! 1083: for ( i = 1, e1 = 0, e2 = 0; i <= dp_nelim; i++ ) {
! 1084: e1 += d1->d[n-i]; e2 += d2->d[n-i];
! 1085: }
! 1086: if ( e1 > e2 )
! 1087: return 1;
! 1088: else if ( e1 < e2 )
! 1089: return -1;
! 1090: else if ( d1->td > d2->td )
! 1091: return 1;
! 1092: else if ( d1->td < d2->td )
! 1093: return -1;
! 1094: else return -cmpdl_revlex(n,d1,d2);
1.1 noro 1095: }
1096:
1097: int cmpdl_order_pair(n,d1,d2)
1098: int n;
1099: DL d1,d2;
1100: {
1101: int e1,e2,i,j,l;
1102: int *t1,*t2;
1103: int len;
1104: struct order_pair *pair;
1105:
1106: len = dp_current_spec.ord.block.length;
1107: pair = dp_current_spec.ord.block.order_pair;
1108:
1109: for ( i = 0, t1 = d1->d, t2 = d2->d; i < len; i++ ) {
1110: l = pair[i].length;
1111: switch ( pair[i].order ) {
1112: case 0:
1113: for ( j = 0, e1 = e2 = 0; j < l; j++ ) {
1114: e1 += t1[j]; e2 += t2[j];
1115: }
1116: if ( e1 > e2 )
1117: return 1;
1118: else if ( e1 < e2 )
1119: return -1;
1120: else {
1121: for ( j = l - 1; j >= 0 && t1[j] == t2[j]; j-- );
1122: if ( j >= 0 )
1123: return t1[j] < t2[j] ? 1 : -1;
1124: }
1125: break;
1126: case 1:
1127: for ( j = 0, e1 = e2 = 0; j < l; j++ ) {
1128: e1 += t1[j]; e2 += t2[j];
1129: }
1130: if ( e1 > e2 )
1131: return 1;
1132: else if ( e1 < e2 )
1133: return -1;
1134: else {
1135: for ( j = 0; j < l && t1[j] == t2[j]; j++ );
1136: if ( j < l )
1137: return t1[j] > t2[j] ? 1 : -1;
1138: }
1139: break;
1140: case 2:
1141: for ( j = 0; j < l && t1[j] == t2[j]; j++ );
1142: if ( j < l )
1143: return t1[j] > t2[j] ? 1 : -1;
1144: break;
1145: default:
1146: error("cmpdl_order_pair : invalid order"); break;
1147: }
1148: t1 += l; t2 += l;
1149: }
1150: return 0;
1151: }
1152:
1153: int cmpdl_matrix(n,d1,d2)
1154: int n;
1155: DL d1,d2;
1156: {
1157: int *v,*w,*t1,*t2;
1158: int s,i,j,len;
1159: int **matrix;
1160:
1161: for ( i = 0, t1 = d1->d, t2 = d2->d, w = dp_dl_work; i < n; i++ )
1162: w[i] = t1[i]-t2[i];
1163: len = dp_current_spec.ord.matrix.row;
1164: matrix = dp_current_spec.ord.matrix.matrix;
1165: for ( j = 0; j < len; j++ ) {
1166: v = matrix[j];
1167: for ( i = 0, s = 0; i < n; i++ )
1168: s += v[i]*w[i];
1169: if ( s > 0 )
1170: return 1;
1171: else if ( s < 0 )
1172: return -1;
1173: }
1174: return 0;
1175: }