[BACK]Return to module_syz.rr CVS log [TXT][DIR] Up to [local] / OpenXM / src / asir-contrib / testing / noro

Annotation of OpenXM/src/asir-contrib/testing/noro/module_syz.rr, Revision 1.7

1.1       noro        1: module newsyz;
                      2:
1.4       noro        3: localf module_syz, module_syz_old;
1.3       noro        4: localf simplify_syz, icont, mod, remove_cont,ordcheck;
                      5: localf complsb, complsb_sd, sortlsb, find_pos, find_pos, reduce, lres_setup, dpm_sort1, comp_pos;
                      6: localf fres,minres,sres,minsres,lres, create_base_ord, simplify_k, simplify_by_k, remove_k, remove_k1, extract_nonzero;
                      7: localf nonzero, phi, syz_check, renumber_pos, compress, compress_h;
                      8: localf syz_check0,phi0,todpmlist,dpmlisttollist;
1.1       noro        9:
                     10: /* F : a list of (lists or polynomials),
                     11:    V : a variable list, H >1=> over GF(H), H=0,1=> over Q
                     12:    O : term order
                     13:    return: [GS,G]
                     14:    GS : a GB of syz(F) wrt [1,O] (POT), G: a GB of F wrt [1,O]
                     15: */
                     16:
1.3       noro       17: // return [dpmlist F,rank N]
                     18: def todpmlist(F,V)
1.1       noro       19: {
1.3       noro       20:   K = length(F);
                     21:   for ( I = 0; I < K; I++ ) if ( F[I] ) break;
                     22:   if ( I == K ) return [];
                     23:   if ( type(F[I]) <= 2 ) {
                     24:     // F is a polynimial list
                     25:     F = map(dp_ptod,F,V);
                     26:     F = map(dpm_dptodpm,F,1);
                     27:     N = 1;
                     28:   } else if ( type(F[I]) == 9 ) {
                     29:     // F is a dpoly list
                     30:     F = map(dpm_dptodpm,F,1);
                     31:     N = 1;
                     32:   } else if ( type(F[I]) == 4 ) {
                     33:     // F is a list of poly lists
                     34:     N = length(F[0]);
                     35:     F = map(dpm_ltod,F,V);
                     36:   } else if ( type(F[I]) == 26 ) {
                     37:     // F is a DPM list
                     38:     for ( N = 0, T = F; T != []; T = cdr(T) ) {
                     39:       for ( A = car(T); A; A = dpm_rest(A) ) {
                     40:         N1 = dpm_hp(A);
                     41:         if ( N1 > N ) N = N1;
                     42:       }
                     43:     }
                     44:   } else {
                     45:     error("todpmlist: arugument type is invalid.");
                     46:   }
                     47:   return [F,N];
                     48: }
                     49:
                     50: def module_syz(F,V,H,Ord)
                     51: {
                     52:   if ( type(Weyl=getopt(weyl)) == -1 ) Weyl = 0;
                     53:   if ( type(DP=getopt(dp)) == -1 ) DP = 0;
                     54:   if ( type(F4=getopt(f4)) == -1 ) F4 = 0;
                     55:   dp_ord(Ord);
                     56:   K = length(F);
                     57:   for ( I = 0; I < K; I++ ) if ( F[I] ) break;
                     58:   if ( I == K ) return [[],[],[]];
                     59:   L = todpmlist(F,V);
                     60:   F = L[0]; N = L[1];
                     61:   dp_ord([1,Ord]);
                     62:   B = [];
                     63:   for ( I = 0; I < K; I++ ) {
                     64:     B = cons(F[I]+dpm_dptodpm(dp_ptod(1,V),N+I+1),B);
                     65:   }
                     66:   B = reverse(B);
1.4       noro       67:   if ( H >= 2 ) {
                     68:     // finite field
                     69:     if ( Weyl )
                     70:       G = nd_weyl_gr(B,V,H,[1,Ord]|dp=1);
                     71:     else if ( F4 )
                     72:       G = nd_f4(B,V,H,[1,Ord]|dp=1);
                     73:     else
                     74:       G = nd_gr(B,V,H,[1,Ord]|dp=1);
                     75:   } else {
                     76:     if ( Weyl )
                     77:       G = nd_weyl_gr(B,V,0,[1,Ord]|dp=1,homo=H);
1.7     ! noro       78:     else {
1.4       noro       79:       Ind = 0;
                     80:       while ( 1 ) {
1.7     ! noro       81:         if ( F4 )
        !            82:           G = nd_f4_trace(B,V,H,-lprime(Ind),[1,Ord]|dp=1);
        !            83:         else
        !            84:           G = nd_gr_trace(B,V,H,-lprime(Ind),[1,Ord]|dp=1);
1.4       noro       85:         if ( G ) break;
                     86:         else Ind++;
                     87:       }
1.7     ! noro       88:     }
1.4       noro       89:   }
1.3       noro       90:   G0 = []; S0 = []; Gen0 = [];
                     91:   for ( T = G; T != []; T = cdr(T) ) {
                     92:     H = car(T);
                     93:     if ( dpm_hp(H) > N ) {
                     94:       S0 = cons(dpm_shift(H,N),S0);
                     95:     } else {
                     96:       L = dpm_split(H,N);
                     97:       G0 = cons(L[0],G0);
                     98:       Gen0 = cons(dpm_shift(L[1],N),Gen0);
1.1       noro       99:        }
1.3       noro      100:   }
                    101: #if 0
                    102:   S0 = reverse(S0); G0 = reverse(G0); Gen0 = reverse(Gen0);
                    103: #endif
                    104:   if ( !DP ) {
                    105:     S0 = map(dpm_dtol,S0,V); G0 = map(dpm_dtol,G0,V); Gen0 = map(dpm_dtol,Gen0,V);
                    106:   }
                    107:   return [S0,G0,Gen0];
                    108: }
                    109:
1.4       noro      110: def module_syz_old(F,V,H,O)
                    111: {
                    112:        Weyl = type(getopt(weyl)) != -1 ? 1 : 0;
                    113:        K = length(F);
                    114:        if ( type(F[0]) <= 2 ) {
                    115:                for ( T = [], S = F; S != []; S = cdr(S) )
                    116:                        T = cons([car(S)],T);
                    117:                F = reverse(T);
                    118:        }
                    119:        N = length(F[0]);
                    120:        B = [];
                    121:        for ( I = 0; I < K; I++ ) {
                    122:                E = vector(N+K);
                    123:                for ( J = 0; J < N; J++ ) E[J] = F[I][J];
                    124:                E[N+I] = 1;
                    125:                B = cons(vtol(E),B);
                    126:        }
                    127:        B = reverse(B);
                    128:        if ( H >= 2 ) {
                    129:                if ( Weyl )
                    130:                        G = nd_weyl_gr(B,V,H,[1,O]);
                    131:                else
                    132:                        G = nd_gr(B,V,H,[1,O]);
                    133:        } else {
                    134:                if ( Weyl )
                    135:                        G = nd_weyl_gr_trace(B,V,H,-1,[1,O]);
                    136:                else
                    137:                        G = nd_gr_trace(B,V,H,-1,[1,O]);
                    138:        }
                    139:        G0 = []; S0 = []; Gen0 = [];
                    140:        for ( T = G; T != []; T = cdr(T) ) {
                    141:                H = car(T);
                    142:                for ( J = 0; J < N; J++ ) if ( H[J] ) break;
                    143:                if ( J == N ) {
                    144:                        H1 = vector(K);
                    145:                        for ( J = 0; J < K; J++ ) H1[J] = H[N+J];
                    146:                        S0 = cons(vtol(H1),S0);
                    147:                } else {
                    148:                        H1 = vector(N);
                    149:                        for ( J = 0; J < N; J++ ) H1[J] = H[J];
                    150:                        G0 = cons(vtol(H1),G0);
                    151:                        H1 = vector(K);
                    152:                        for ( J = 0; J < K; J++ ) H1[J] = H[N+J];
                    153:                        Gen0 = cons(vtol(H1),Gen0);
                    154:                }
                    155:        }
                    156:        return [S0,G0,Gen0];
                    157: }
                    158:
1.3       noro      159: def fres(F,V,H,O)
                    160: {
                    161:   if ( type(Weyl=getopt(weyl)) == -1 ) Weyl = 0;
                    162:   if ( type(F4=getopt(f4)) == -1 ) F4 = 0;
                    163:   if ( type(DP=getopt(dp)) == -1 ) DP = 0;
                    164:   L = todpmlist(F,V); F = L[0];
                    165:   R = [F];
                    166:   while ( 1 ) {
                    167:     if ( Weyl )
                    168:       L = module_syz(car(R),V,H,O|weyl=1,dp=1,f4=F4);
                    169:     else
                    170:       L = module_syz(car(R),V,H,O|dp=1,f4=F4);
                    171:     L = L[0];
                    172:     L = ordcheck(L,V);
                    173:     if ( L == [] ) {
1.5       noro      174:       R = reverse(R);
1.3       noro      175:       if ( DP ) return R;
                    176:       else return map(dpmlisttollist,R,V);
                    177:     }
                    178:     R = cons(L,R);
                    179:   }
                    180: }
                    181:
                    182: def minres(F,V,H,O)
                    183: {
                    184:   if ( type(Weyl=getopt(weyl)) == -1 ) Weyl = 0;
                    185:   if ( type(F4=getopt(f4)) == -1 ) F4 = 0;
                    186:   if ( type(DP=getopt(dp)) == -1 ) DP = 0;
                    187:   L = todpmlist(F,V); F = L[0];
                    188:   R = [F];
                    189:   while ( 1 ) {
                    190:     if ( Weyl )
                    191:       L = module_syz(car(R),V,H,O|weyl=1,dp=1,f4=F4);
                    192:     else
                    193:       L = module_syz(car(R),V,H,O|dp=1,f4=F4);
                    194:     L = L[0];
                    195:     L = ordcheck(L,V);
                    196:     if ( L == [] ) break;
                    197:     S = dpm_simplify_syz(L,R[0]);
                    198:     if ( S[0] == [] && S[1] == [] ) {
                    199:       R = cdr(R); break;
                    200:     }
                    201:     R = append([S[0],S[1]],cdr(R));
                    202:     if ( R[0] == [] ) {
                    203:       R = cdr(R); break;
                    204:     }
                    205:   }
1.5       noro      206:   R = reverse(R);
1.3       noro      207:   if ( DP ) return R;
                    208:   else return map(dpmlisttollist,R,V);
                    209: }
                    210:
                    211: def dpmlisttollist(F,V)
                    212: {
                    213:   return map(dpm_dtol,F,V);
                    214: }
                    215:
                    216: def sres(F,V,H,Ord)
                    217: {
                    218:   if ( type(DP=getopt(dp)) == -1 ) DP = 0;
                    219:   dpm_set_schreyer(0);
                    220:   dp_ord(Ord);
                    221:   K = length(F);
                    222:   K = length(F);
                    223:   for ( I = 0; I < K; I++ ) if ( F[I] ) break;
                    224:   if ( I == K ) return [[],[],[]];
                    225:   L = todpmlist(F,V);
                    226:   F = L[0]; N = L[1];
1.6       noro      227: #if 0
1.3       noro      228:   G = nd_gr(F,V,H,[0,Ord]|dp=1);
1.6       noro      229: #else
                    230:   G = nd_gr_trace(F,V,H,1,[0,Ord]|dp=1);
                    231: #endif
1.3       noro      232:   G = reverse(G);
                    233:   R = [G];
                    234:   dp_ord([0,Ord]);
                    235:   while ( 1 ) {
                    236:     S = dpm_schreyer_base(R[0]);
1.7     ! noro      237:     if ( dp_gr_print() ) print(["length",length(S)]);
1.3       noro      238:     if ( S == [] ) break;
                    239:     else R = cons(S,R);
                    240:   }
                    241:   dp_ord([0,0]);
1.5       noro      242:   R = reverse(R);
1.3       noro      243:   if ( DP ) return R;
                    244:   else return map(dpmlisttollist,R,V);
                    245: }
                    246:
                    247: def minsres(F,V,H,Ord)
                    248: {
                    249:   if ( type(DP=getopt(dp)) == -1 ) DP = 0;
                    250:   R = sres(F,V,H,Ord|dp=1);
1.5       noro      251:   R = ltov(reverse(R));
1.3       noro      252:   M = length(R);
                    253:   for ( I = 0; I < M; I++ ) R[I] = map(dpm_sort,R[I]);
                    254:   R = vtol(R);
                    255:   for ( T = R, U = []; length(T) >= 2; ) {
                    256:     Z = dpm_simplify_syz(T[0],T[1]);
                    257:     U = cons(Z[0],U);
                    258:     T = cons(Z[1],cdr(cdr(T)));
                    259:   }
                    260:   U = cons(T[0],U);
                    261:   if ( DP ) return U;
                    262:   else return map(dpmlisttollist,U,V);
                    263: }
                    264:
                    265: def ordcheck(D,V)
                    266: {
                    267:   B=map(dpm_dtol,D,V);
                    268:   dp_ord([1,0]);
                    269:   D = map(dpm_sort,D);
                    270:   D1 = map(dpm_ltod,B,V);
                    271:   if ( D != D1 )
                    272:     print("afo");
                    273:   return D1;
                    274: }
                    275:
                    276: def complsb(A,B)
                    277: {
                    278:   AL = A[3]; AD = A[4];
                    279:   BL = B[3]; BD = B[4];
                    280:   if ( AD > BD ) return 1;
                    281:   else if ( AD < BD ) return -1;
                    282:   else if ( AL < BL ) return 1;
                    283:   else if ( AL > BL ) return -1;
                    284:   else return 0;
                    285: }
                    286:
                    287: def complsb_sd(A,B)
                    288: {
                    289:   AL = A[3]; AD = A[4];
                    290:   BL = B[3]; BD = B[4];
                    291:   if ( AD-AL > BD-BL ) return 1;
                    292:   else if ( AD-AL < BD-BL ) return -1;
                    293:   else if ( AL > BL ) return 1;
                    294:   else if ( AL < BL ) return -1;
                    295:   else return 0;
                    296: }
                    297:
                    298: def sortlsb(A)
                    299: {
                    300:   S = [];
                    301:   N = length(A);
                    302:   for ( I = 0; I < N; I++ ) S = append(cdr(vtol(A[I])),S);
                    303: //  S = qsort(S,newsyz.complsb_sd);
                    304:   S = qsort(S,newsyz.complsb);
                    305:   return S;
                    306: }
                    307: /* D=[in,sum,deg,lev,ind] */
                    308: /* B=[0 B1 B2 ...] */
                    309: /* C=[0 C1 C2 ...] */
                    310: /* H=[0 H1 H2 ...] */
                    311: /* Z=[0 Z1 Z2 ...] */
                    312: /* Zi=[0 L1 L2 ...] */
                    313: /* Lj=[I1,I2,...] */
                    314: /* One=<<0,...,0>> */
                    315:
                    316: extern Rtime,Stime,Ptime$
                    317:
                    318: // B is sorted wrt positon
                    319: def find_pos(HF,B)
                    320: {
                    321:   Len = length(B);
                    322:   Pos = dpm_hp(HF);
                    323:   First = 0; Last = Len-1;
                    324:   if ( B[First][0] == HF ) return B[First][2];
                    325:   if ( B[Last][0] == HF ) return B[Last][2];
                    326:   while ( 1 ) {
                    327:     Mid = idiv(First+Last,2);
                    328:     PosM = dpm_hp(B[Mid][0]);
                    329:     if ( PosM == Pos ) break;
                    330:     else if ( PosM < Pos )
                    331:       First = Mid;
                    332:     else
                    333:       Last = Mid;
                    334:   }
                    335:   for ( I = Mid; I < Len && dpm_hp(B[I][0]) == Pos; I++ )
                    336:     if ( HF == B[I][0] ) return B[I][2];
                    337:   for ( I = Mid-1; I >= 1 && dpm_hp(B[I][0]) == Pos; I-- )
                    338:     if ( HF == B[I][0] ) return B[I][2];
                    339:   error("find_pos : cannot happen");
                    340: }
                    341:
                    342: def reduce(D,B,Bpos,C,H,Z,K,Kind,G,One,Top)
                    343: {
                    344:   M = D[0]; Ind = D[2]; I = D[3];
                    345:   if ( I == 1 ) {
                    346:     C[I][Ind] = G[Ind];
                    347:     dpm_insert_to_zlist(Z[1],dpm_hp(G[Ind]),Ind);
                    348:     H[I][Ind] = G[Ind];
                    349:   } else {
                    350:     /* M is in F(I-1) => phi(M) is in F(I-2) */
                    351:     /* reduction in F(I-2) */
                    352:     T0 = time()[0];
                    353:     dpm_set_schreyer_level(I-2);
                    354:     CI = C[I-1]; ZI = Z[I-1]; BI = B[I-1]; BposI = Bpos[I-1];
                    355:     Len = size(CI);
                    356:     T=dpm_hc(M); EM=dpm_hp(M);
                    357:     XiM = T*dpm_ht(CI[EM]);
                    358:     EXiM = dpm_hp(XiM);
                    359:     ZIE = ZI[EXiM];
                    360:     for ( ZIE = ZI[EXiM]; ZIE != []; ZIE = cdr(ZIE) ) {
                    361:       J = car(ZIE);
                    362:       if ( J > EM && dpm_redble(XiM,dpm_ht(CI[J])) ) break;
                    363:     }
                    364:     Ptime += time()[0]-T0;
                    365:     T0 = time()[0];
                    366:     QR = dpm_sp_nf(CI,ZI,EM,J|top=Top);
                    367:     Rtime += time()[0]-T0;
                    368:     G = QR[0]; F = QR[1];
                    369:     if ( F ) {
                    370:       HF = dpm_ht(F); EF = dpm_hp(HF);
                    371:       /* find HF in B[I-1] */
                    372:     T0 = time()[0];
                    373:     J = find_pos(HF,BposI);
                    374:     Stime += time()[0]-T0;
                    375:       /* F=Ret[0]*Ret[1] */
                    376:       Ret = dpm_remove_cont(F);
                    377:       CI[J] = Ret[1];
                    378:       Kind[I-1][J] = 2;
                    379:       dpm_insert_to_zlist(ZI,EF,J);
                    380:       dpm_set_schreyer_level(I-1);
                    381:       Tail = -Ret[0]*dpm_dptodpm(One,J);
                    382:       G += Tail;
                    383:       dpm_set_schreyer_level(0);
                    384:       Ret = dpm_remove_cont(G); G = Ret[1];
                    385:       C[I][Ind] = G;
                    386:       Kind[I][Ind] = 1;
                    387:       K[I] = cons([G,Tail],K[I]);
                    388:       dpm_insert_to_zlist(Z[I],EM,Ind);
                    389:       /* level <- 0 */
                    390:       BI[J][3] = 0;
                    391:     } else {
                    392:       Kind[I][Ind] = 0;
                    393:       Ret = dpm_remove_cont(G); G = Ret[1];
                    394:       H[I][Ind] = G;
                    395:       C[I][Ind] = G;
                    396:       dpm_insert_to_zlist(Z[I],EM,Ind);
                    397:     }
                    398:   }
                    399: }
                    400:
                    401: def lres_setup(F,V,H,Ord)
                    402: {
                    403:   dpm_set_schreyer(0);
                    404:   dp_ord(Ord);
                    405:   K = length(F);
                    406:   if ( type(F[0]) <= 2 ) {
                    407:     // F is a polynimial list
                    408:     F = map(dp_ptod,F,V);
                    409:     F = map(dpm_dptodpm,F,1);
                    410:     N = 1;
                    411:   } else if ( type(F[0]) == 9 ) {
                    412:     // F is a dpoly list
                    413:     F = map(dpm_dptodpm,F,1);
                    414:     N = 1;
                    415:   } else if ( type(F[0]) == 4 ) {
                    416:     // F is a list of poly lists
                    417:     N = length(F[0]);
                    418:     F = map(dpm_ltod,F,V);
                    419:   } else if ( type(F[0]) == 26 ) {
                    420:     // F is a DPM list
                    421:     for ( N = 0, T = F; T != []; T = cdr(T) ) {
                    422:       for ( A = car(T); A; A = dpm_rest(A) ) {
                    423:         N1 = dpm_hp(A);
                    424:         if ( N1 > N ) N = N1;
                    425:       }
                    426:     }
                    427:   } else {
                    428:     error("lres_setup: arugument type is invalid.");
                    429:   }
1.6       noro      430:   dp_ord([0,Ord]);
                    431:   F = map(dpm_sort,F);
                    432: #if 0
1.3       noro      433:   G = nd_gr(F,V,H,[0,Ord]|dp=1);
1.6       noro      434: #else
                    435:   G = nd_gr_trace(F,V,H,1,[0,Ord]|dp=1);
                    436: #endif
1.3       noro      437:   G = reverse(G);
                    438:   dp_ord([0,Ord]);
                    439:   One = dp_ptod(1,V);
                    440:   return [G,One];
                    441: }
                    442:
                    443: def dpm_sort1(L)
                    444: {
                    445:   return [dpm_sort(L[0]),L[1]];
                    446: }
                    447:
                    448: def comp_pos(A,B)
                    449: {
                    450:   PA = dpm_hp(A[0]); PB = dpm_hp(B[0]);
                    451:   if ( PA > PB ) return 1;
                    452:   else if ( PA < PB ) return -1;
                    453:   else return 0;
                    454: }
                    455:
                    456: def lres(F,V,H,Ord)
                    457: {
                    458:   T0 = time();
                    459:   if ( type(Top=getopt(top)) == -1 ) Top = 0;
1.5       noro      460:   if ( type(DP=getopt(dp)) == -1 ) DP = 0;
1.3       noro      461:   if ( type(NoSimpK=getopt(nosimpk)) == -1 ) NoSimpK = 0;
                    462:   if ( type(NoPreProj=getopt(nopreproj)) == -1 ) NoPreProj = 0;
                    463:   Rtime = Stime = Ptime = 0;
                    464:   L = lres_setup(F,V,H,Ord);
                    465:   G = L[0];
                    466:   One = L[1];
                    467:   F = dpm_schreyer_frame(G);
                    468:   G = ltov(cons(0,L[0]));
                    469:   F = reverse(F);
                    470:   F = ltov(F);
                    471:   N = length(F);
                    472:   for ( I = 0; I < N; I++ ) {
                    473:     FI = F[I]; FI[0] = [];
                    474:     FI = map(ltov,FI);
                    475:     F[I] = FI;
                    476:   }
                    477:   R = sortlsb(F);
                    478:   B = vector(N+1);
                    479:   Bpos = vector(N+1);
                    480:   C = vector(N+1);
                    481:   H = vector(N+1);
                    482:   Z = vector(N+1);
                    483:   K = vector(N+1);
                    484:   L = vector(N+1);
                    485:   K = vector(N+1);
                    486:   D = vector(N+1);
                    487:   Kind = vector(N+1);
                    488:
                    489:   for ( I = 1; I <= N; I++ ) {
                    490:     FI = F[I-1]; Len = length(FI);
                    491:     B[I] = FI;
                    492:     T = vector(Len-1);
                    493:     for ( J = 1; J < Len; J++ ) T[J-1] = FI[J];
                    494:     Bpos[I] = qsort(T,newsyz.comp_pos);
                    495:     C[I] = vector(Len);
                    496:     H[I] = vector(Len);
                    497:     Kind[I] = vector(Len);
                    498:     K[I] = [];
                    499:     Max = 0;
                    500:     for ( J = 1; J < Len; J++ )
                    501:       if ( (Pos = dpm_hp(FI[J][0])) > Max ) Max = Pos;
                    502:     Z[I] = ZI = vector(Max+1);
                    503:     for ( J = 1; J <= Max; J++ ) ZI[J] = [];
                    504:   }
                    505:   T1 = time(); Ftime = T1[0]-T0[0];
                    506:   R = ltov(R); Len = length(R);
1.7     ! noro      507:   if ( dp_gr_print() ) print(["Len",Len]);
1.3       noro      508:   for ( I = 0, NF = 0; I < Len; I++ ) {
1.7     ! noro      509:     if ( dp_gr_print() ) {
        !           510:       if ( !((I+1)%100) ) print(".",2);
        !           511:       if ( !((I+1)%10000) ) print(I+1);
        !           512:     }
1.3       noro      513:     if ( !R[I][3] ) continue;
                    514:     NF++;
                    515:     reduce(R[I],B,Bpos,C,H,Z,K,Kind,G,One,Top);
                    516:   }
1.7     ! noro      517:   if ( dp_gr_print() ) {
        !           518:     print("");
        !           519:     print(["NF",NF]);
        !           520:   }
1.3       noro      521:   T0 = time();
                    522:   dpm_set_schreyer_level(0);
                    523:   D[1] = map(dpm_sort,H[1]);
                    524:   for ( I = 2; I <= N; I++ ) {
                    525:     // HTT = [Head,Tab,TailTop]
                    526:     HTT = create_base_ord(K[I],length(Kind[I-1]));
                    527:     Head = HTT[0]; Tab = HTT[1]; TailTopPos = HTT[2];
                    528:     if ( !NoPreProj )
                    529:       Tab = map(remove_k,map(dpm_sort,Tab),Kind[I-1]);
                    530:     else
                    531:       Tab = map(dpm_sort,Tab);
                    532:     TailTop = dpm_dptodpm(One,TailTopPos);
                    533:     if ( !NoSimpK ) {
1.7     ! noro      534:       if ( dp_gr_print() ) print("simplify_k "+rtostr(I)+"...",2);
1.3       noro      535:       simplify_k(Head,Tab,TailTop,One);
1.7     ! noro      536:       if ( dp_gr_print() ) print("done");
1.3       noro      537:     }
                    538:     HI = map(remove_k,map(dpm_sort,H[I]),Kind[I-1]);
                    539:     Len = length(HI);
1.7     ! noro      540:     if ( dp_gr_print() ) print("simplify_by_k "+rtostr(I)+"...",2);
1.3       noro      541:     D[I] = vector(Len);
                    542:     for ( J = 0; J < Len; J++ ) {
                    543:       D[I][J] = simplify_by_k(HI[J],Tab,TailTop,One);
                    544:       if ( NoPreProj )
                    545:         D[I][J] = remove_k(D[I][J],Kind[I-1]);
                    546:     }
1.7     ! noro      547:     if ( dp_gr_print() ) print("done");
1.3       noro      548:   }
                    549:   dp_ord([1,0]);
                    550:   T1 = time();
1.7     ! noro      551:   if ( dp_gr_print() ) print(["Frame",Ftime,"Prep",Ptime,"Reduce",Rtime,"Search",Stime,"Minimalize",T1[0]-T0[0]]);
1.3       noro      552: //  return [C,H,K,Kind,D];
                    553:   D = compress_h(D);
1.5       noro      554:   if ( DP ) return D;
                    555:   else return vtol(map(dpmlisttollist,D,V));
1.3       noro      556: }
                    557:
                    558: def create_base_ord(K,N)
                    559: {
                    560:   Tab = vector(N);
                    561:   Ks = [];
                    562:   for ( T = K; T != []; T = cdr(T) ) {
                    563:     Ks = cons(I=dpm_hp(car(T)[1]),Ks);
                    564:     Tab[I] = car(T)[0];
                    565:   }
                    566:   Others = [];
                    567:   for ( I = N-1; I >= 1; I-- )
                    568:     if ( !Tab[I] ) Others = cons(I,Others);
                    569:   Ks = reverse(Ks);
                    570:   dp_ord([4,append(Ks,Others),0]);
                    571:   return [ltov(Ks),Tab,car(Others)];
                    572: }
                    573:
                    574: /* Head = [i1,i2,...], Tab[i1] = K[0], Tab[i2] = K[1],... */
                    575:
                    576: def simplify_k(Head,Tab,TailTop,One)
                    577: {
                    578:   N = length(Tab);
                    579:   Len = length(Head);
                    580:   for ( I = Len-1; I >= 0; I-- ) {
                    581:     M = 1;
                    582:     R = Tab[Head[I]];
                    583:     H = dpm_hm(R); R = dpm_rest(R);
                    584:     while ( R && dpm_dptodpm(One,dpm_hp(R)) > TailTop ) {
                    585:       Pos = dpm_hp(R); Red = Tab[Pos];
                    586:       CRed = dp_hc(dpm_hc(Red));
                    587:       CR = dpm_extract(R,Pos);
                    588:       L = dpm_remove_cont(CRed*R-CR*Red);
                    589:       R = L[1]; M *= CRed/L[0];
                    590:     }
                    591:     Tab[Head[I]] = M*H+R;
                    592:   }
                    593: }
                    594:
                    595: def simplify_by_k(F,Tab,TailTop,One)
                    596: {
                    597:   R = F;
                    598:   M = 1;
                    599:   while ( R && dpm_dptodpm(One,dpm_hp(R)) > TailTop ) {
                    600:     Pos = dpm_hp(R); Red = Tab[Pos];
                    601:     CRed = dp_hc(dpm_hc(Red));
                    602:     CR = dpm_extract(R,Pos);
                    603:     L = dpm_remove_cont(CRed*R-CR*Red);
                    604:     R = L[1]; M *= CRed/L[0];
                    605:   }
                    606:   return (1/M)*R;
                    607: }
                    608:
                    609: /* Kind[I]=0 => phi(ei)\in H, Kind[I]=1 => phi(ei)\in K */
                    610: def remove_k(F,Kind)
                    611: {
                    612:   R = [];
                    613:   for ( T = F; T; T = dpm_rest(T) )
                    614:     if ( Kind[dpm_hp(T)] != 1 ) R = cons(dpm_hm(T),R);
                    615:   for ( S = 0; R != []; R = cdr(R) )
                    616:     S += car(R);
                    617:   return S;
                    618: }
                    619:
                    620: def remove_k1(F,Kind)
                    621: {
                    622:   return [remove_k(F[0],Kind),F[1]];
                    623: }
                    624:
                    625: def extract_nonzero(A)
                    626: {
                    627:   N = length(A);
                    628:   R = [];
                    629:   for ( C = I = 0; I < N; I++ )
                    630:     if ( A[I] ) R=cons(A[I],R);
                    631:   return reverse(R);;
                    632: }
                    633:
                    634: def nonzero(A)
                    635: {
                    636:   N = length(A);
                    637:   for ( C = I = 0; I < N; I++ )
                    638:     if ( A[I] ) C++;
                    639:   return C;
                    640: }
                    641:
                    642: def phi(C,F)
                    643: {
                    644:   R = 0;
                    645:   for ( T = F; T; T = dpm_rest(T) ) {
                    646:     Coef = dpm_hc(T); Pos = dpm_hp(T);
1.6       noro      647:     R += Coef*C[Pos-1];
1.3       noro      648:   }
                    649:   return R;
1.1       noro      650: }
                    651:
1.3       noro      652: def syz_check(H,I)
1.1       noro      653: {
1.3       noro      654:   HI = H[I];
                    655: //  dpm_set_schreyer_level(I-1);
                    656:   HI1 = H[I+1];
                    657:   Len = size(HI1)[0];
                    658:   for ( J = 1; J < Len; J++ ) {
                    659:     F = HI1[J];
                    660:     R = phi(HI,F);
                    661:     if ( R ) print([J,"NG"]);
                    662:   }
1.1       noro      663: }
                    664:
1.3       noro      665: // for compressed C
                    666: def phi0(C,F)
1.1       noro      667: {
1.3       noro      668:   R = 0;
                    669:   for ( T = F; T; T = dpm_rest(T) ) {
                    670:     Coef = dpm_hc(T); Pos = dpm_hp(T);
                    671:     R += Coef*C[Pos-1];
                    672:   }
                    673:   return R;
1.1       noro      674: }
                    675:
1.3       noro      676: // for compressed H
                    677: def syz_check0(H,I)
1.1       noro      678: {
1.3       noro      679:   HI = H[I];
                    680: //  dpm_set_schreyer_level(I-1);
                    681:   HI1 = H[I+1];
                    682:   Len = length(HI1);
                    683:   for ( J = 0; J < Len; J++ ) {
                    684:     F = HI1[J];
                    685:     R = phi0(HI,F);
                    686:     if ( R ) print([J,"NG"]);
                    687:   }
1.1       noro      688: }
                    689:
1.3       noro      690: // renumber position
                    691: def renumber_pos(F,Tab)
1.1       noro      692: {
1.3       noro      693:   L = [];
                    694:   for ( T = F; T; T = dpm_rest(T) )
                    695:     L = cons(dpm_hm(T),L);
                    696:   R = 0;
                    697:   for ( T = L; T != []; T = cdr(T) )
                    698:     R += dpm_dptodpm(dpm_hc(car(T)),Tab[dpm_hp(car(T))]);
                    699:   return R;
1.1       noro      700: }
                    701:
1.3       noro      702: // compress H1 and renumber H
                    703: def compress(H,H1)
1.1       noro      704: {
1.3       noro      705:   // create index table for H1
                    706:   L1 = length(H1);
                    707:   Tmp = vector(L1);
                    708:   Tab = vector(L1);
                    709:   for ( I = 1, J = 1; I < L1; I++ )
                    710:     if ( H1[I] ) {
                    711:       Tab[I] = J;
                    712:       Tmp[J++] = H1[I];
                    713:     }
                    714:   NH1 = vector(J);
                    715:   for ( I = 1; I < J; I++ )
                    716:     NH1[I] = Tmp[I];
                    717:   if ( H )
                    718:     H = map(renumber_pos,H,Tab);
                    719:   return [H,NH1];
1.1       noro      720: }
                    721:
1.3       noro      722: def compress_h(H)
1.1       noro      723: {
1.3       noro      724:   // H = [0,H[1],...,H[L-1]]
                    725:   L = length(H);
                    726:   NH = vector(L-1);
                    727:   H1 = H[1];
                    728:   for ( I = 2; I < L; I++ ) {
                    729:     R = compress(H[I],H1);
                    730:     H1 = R[0];
                    731:     NH[I-2] = cdr(vtol(R[1]));
                    732:   }
                    733:   R = compress(0,H1);
                    734:   NH[L-2] = cdr(vtol(R[1]));
                    735:   return NH;
1.1       noro      736: }
1.3       noro      737: endmodule$
1.1       noro      738: end$

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