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