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