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

Annotation of OpenXM/src/asir-contrib/testing/noro/new_pd.rr, Revision 1.9

1.9     ! ohara       1: /* $OpenXM: OpenXM/src/asir-contrib/testing/noro/new_pd.rr,v 1.8 2011/11/01 00:35:56 noro Exp $ */
1.1       noro        2: import("gr")$
                      3: module noro_pd$
1.8       noro        4: static GBCheck,F4,EProcs,Procs,SatHomo,GBRat,SuccSat,RepColon$
1.1       noro        5:
1.8       noro        6: localf radical_membership_sat$
1.4       noro        7: localf witness$
                      8: localf get_lc,tomonic,aa,ideal_intersection_m,redbase$
1.8       noro        9: localf para_exec,nd_gr_rat,competitive_exec,call_func,call_func_serial$
1.1       noro       10: localf call_ideal_list_intersection$
1.3       noro       11: localf call_colon,call_prime_dec$
1.7       noro       12: localf prime_dec2, prime_dec_main2$
1.1       noro       13: localf first_second$
                     14: localf third$
                     15: localf locsat,iso_comp_para,extract_qj,colon_prime_dec,extract_comp$
                     16: localf separator$
1.4       noro       17: localf member,mingen,compute_gbsyz,redcoef,recompute_trace,dtop,topnum$
1.1       noro       18: localf prepost$
                     19: localf monodec0,monodec,prod$
                     20: localf extract_qd,primary_check$
                     21: localf second$
1.8       noro       22: localf gbrat,succsat,repcolon,comp_third_tdeg,comp_tord$
1.1       noro       23: localf power$
                     24:
                     25: localf syci_dec, syc_dec$
                     26: localf syca_dec,syc0_dec$
                     27:
                     28: localf find_si0,find_si1,find_si2$
                     29: localf find_ssi0,find_ssi1,find_ssi2$
                     30:
                     31: localf init_pprocs, init_eprocs, init_procs, kill_procs$
                     32:
                     33: localf sy_dec, pseudo_dec, iso_comp, prima_dec$
                     34:
                     35: localf prime_dec, prime_dec_main, lex_predec1, zprimedec, zprimadec$
                     36: localf complete_qdecomp, partial_qdecomp, partial_qdecomp0, complete_decomp$
                     37: localf partial_decomp, partial_decomp0, zprimacomp, zprimecomp$
                     38: localf fast_gb, incremental_gb, elim_gb, ldim, make_mod_subst$
                     39: localf rsgn, find_npos, gen_minipoly, indepset$
1.8       noro       40: localf maxindep, maxindep2, contraction, contraction_m, ideal_list_intersection, ideal_intersection$
1.1       noro       41: localf radical_membership, modular_radical_membership$
                     42: localf radical_membership_rep, ideal_product, saturation$
1.4       noro       43: localf sat, satind, sat_ind, colon, isat$
1.1       noro       44: localf ideal_colon, ideal_sat, ideal_inclusion, qd_simp_comp, qd_remove_redundant_comp$
1.7       noro       45: localf pd_simp_comp, remove_identical_comp$
1.1       noro       46: localf pd_remove_redundant_comp, ppart, sq, gen_fctr, gen_nf, gen_gb_comp$
                     47: localf gen_mptop, lcfactor, compute_deg0, compute_deg, member$
                     48: localf elimination, setintersection, setminus, sep_list$
                     49: localf first, comp_tdeg, comp_tdeg_first, tdeg, comp_by_ord, comp_by_second$
                     50: localf gbcheck,f4,sathomo,qd_check,qdb_check$
                     51:
                     52: SatHomo=0$
                     53: GBCheck=1$
                     54: GBRat=0$
1.8       noro       55: SuccSat=0$
                     56: RepColon=0$
1.1       noro       57:
                     58: #define MAX(a,b) ((a)>(b)?(a):(b))
                     59: #define ACCUM_TIME(C,R) {T1 = time(); C += (T1[0]-T0[0])+(T1[1]-T0[1]); R += (T1[3]-T0[3]); }
                     60:
                     61: def gbrat(A)
                     62: {
1.8       noro       63:        GBRat = A;
                     64: }
                     65:
                     66: def succsat(A)
                     67: {
                     68:        SuccSat = A;
                     69: }
                     70:
                     71: def repcolon(A)
                     72: {
                     73:        RepColon = A;
1.1       noro       74: }
                     75:
                     76: def gbcheck(A)
                     77: {
                     78:        if ( A ) GBCheck = 1;
                     79:        else GBCheck = -1;
                     80: }
                     81:
                     82: def f4(A)
                     83: {
                     84:        if ( A ) F4 = 1;
                     85:        else F4 = 0;
                     86: }
                     87:
                     88: def sathomo(A)
                     89: {
                     90:        if ( A ) SatHomo = 1;
                     91:        else SatHomo = 0;
                     92: }
                     93:
                     94: def init_eprocs()
                     95: {
                     96:        if ( type(NoX=getopt(nox)) == -1 ) NoX = 0;
                     97:        if ( !EProcs ) {
                     98:                if ( NoX ) {
                     99:                        P0 = ox_launch_nox();
                    100:                        P1 = ox_launch_nox();
                    101:                } else {
                    102:                        P0 = ox_launch();
                    103:                        P1 = ox_launch();
                    104:                }
                    105:                EProcs = [P0,P1];
                    106:        }
                    107: }
                    108:
                    109: def init_pprocs(N)
                    110: {
                    111:        if ( type(NoX=getopt(nox)) == -1 ) NoX = 0;
                    112:        for ( R = [], I = 0; I < N; I++ ) {
                    113:                P = NoX ? ox_launch_nox() : ox_launch();
                    114:                R = cons(P,R);
                    115:        }
                    116:        return reverse(R);
                    117: }
                    118:
                    119: def init_procs()
                    120: {
                    121:        if ( type(NoX=getopt(nox)) == -1 ) NoX = 0;
                    122:        if ( !Procs ) {
                    123:                if ( NoX ) {
                    124:                        P0 = ox_launch_nox();
                    125:                        P1 = ox_launch_nox();
                    126:                } else {
                    127:                        P0 = ox_launch();
                    128:                        P1 = ox_launch();
                    129:                }
                    130:                Procs = [P0,P1];
                    131:        }
                    132: }
                    133:
                    134: def kill_procs()
                    135: {
                    136:        if ( Procs ) {
                    137:                ox_shutdown(Procs[0]);
                    138:                ox_shutdown(Procs[1]);
                    139:                Procs = 0;
                    140:        }
                    141:        if ( EProcs ) {
                    142:                ox_shutdown(EProcs[0]);
                    143:                ox_shutdown(EProcs[1]);
                    144:                EProcs = 0;
                    145:        }
                    146: }
                    147:
                    148: def qd_check(B,V,QD)
                    149: {
                    150:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                    151:        G = nd_gr(B,V,Mod,0);
                    152:        Iso = ideal_list_intersection(map(first,QD[0]),V,0|mod=Mod);
                    153:        Emb = ideal_list_intersection(map(first,QD[1]),V,0|mod=Mod);
                    154:        GG = ideal_intersection(Iso,Emb,V,0|mod=Mod);
                    155:        return gen_gb_comp(G,GG,Mod);
                    156: }
                    157:
                    158: def primary_check(B,V)
                    159: {
                    160:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                    161:        G = nd_gr(B,V,Mod,0);
                    162:        PL = prime_dec(G,V|indep=1,mod=Mod);
                    163:        if ( length(PL) > 1 ) return 0;
                    164:        P = PL[0][0]; Y = PL[0][1];
                    165:        Z = setminus(V,Y);
                    166:        H = elim_gb(G,Z,Y,Mod,[[0,length(Z)],[0,length(Y)]]);
                    167:        H = contraction(H,Z|mod=Mod);
                    168:        H = nd_gr(H,V,Mod,0);
                    169:        if ( gen_gb_comp(G,H,Mod) ) return nd_gr(P,V,Mod,0);
                    170:        else return 0;
                    171: }
                    172:
                    173: def qdb_check(B,V,QD)
                    174: {
                    175:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                    176:        G = nd_gr(B,V,Mod,0);
                    177:        N = length(QD);
                    178:        for ( I = 0, Q = [1]; I < N; I++ )
                    179:                for ( J = 0, QL = map(first,QD[I]), L = length(QL);
                    180:                        J < L; J++ )
1.8       noro      181:                        Q = ideal_intersection_m(Q,QL[J],V,0|mod=Mod);
                    182:        Q = nd_gr(Q,V,0,0);
1.1       noro      183:        if ( !gen_gb_comp(G,Q,Mod) )
                    184:                return 0;
                    185:        for ( I = 0; I < N; I++ ) {
                    186:                T = QD[I];
                    187:                M = length(T);
                    188:                for ( J = 0; J < M; J++ ) {
                    189:                        P = primary_check(T[J][0],V|mod=Mod);
                    190:                        if ( !P ) return 0;
                    191:                        PP = nd_gr(T[J][1],V,Mod,0);
                    192:                        if ( !gen_gb_comp(P,PP,Mod) ) return 0;
                    193:                }
                    194:        }
                    195:        return 1;
                    196: }
                    197:
                    198: def extract_qd(QD,V,Ind)
                    199: {
                    200:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                    201:        N = length(Ind);
                    202:        for ( I = 0, Q = [1]; I < N; I++ )
                    203:                for ( J = 0, QL = map(first,QD[Ind[I]]), L = length(QL);
                    204:                        J < L; J++ )
                    205:                        Q = ideal_intersection(Q,QL[J],V,0|mod=Mod);
                    206:        return Q;
                    207: }
                    208:
                    209: /* SYC primary decomositions */
                    210:
                    211: def syc_dec(B,V)
                    212: {
                    213:        if ( type(SI=getopt(si)) == -1 ) SI = 2;
                    214:        SIFList=[find_ssi0, find_ssi1,find_ssi2];
                    215:        if ( SI<0 || SI>2 ) error("sycb_dec : si should be 0,1,2");
                    216:        SIF = SIFList[SI];
                    217:
                    218:        if ( type(MaxLevel=getopt(level)) == -1 ) MaxLevel = -1;
                    219:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                    220:        if ( type(Lexdec=getopt(lexdec)) == -1 ) Lexdec = 0;
                    221:        if ( type(Time=getopt(time)) == -1 ) Time = 0;
                    222:        if ( type(Iso=getopt(iso)) == -1 ) Iso = 0;
                    223:        if ( type(Colon=getopt(colon)) == -1 ) Colon = 1;
                    224:        Ord = 0;
                    225:        Tall = time();
                    226:        C = Gt = G = fast_gb(B,V,Mod,Ord|trace=1);
                    227:        Q = []; IntQ = [1]; First = 1;
                    228:        Tpd = Tiso = Tsep = 0;
                    229:        RTpd = RTiso = RTsep = 0;
                    230:        for ( Level = 0; MaxLevel < 0 || Level <= MaxLevel; Level++ ) {
                    231:                if ( type(Gt[0])==1 ) break;
                    232: T3 = T2 = T1 = T0 = time();
                    233:                if ( First ) {
                    234:                        PtR = prime_dec(C,V|indep=1,lexdec=Lexdec,mod=Mod,radical=1);
                    235:                        Pt = PtR[0]; IntPt = PtR[1];
                    236:                        if ( gen_gb_comp(Gt,IntPt,Mod) ) {
                    237:                                /* Gt is radical and Gt = cap Pt */
                    238:                                for ( T = Pt, Qt = []; T != []; T = cdr(T) )
                    239:                                        Qt = cons([car(T)[0],car(T)[0]],Qt);
                    240:                                return append(Q,[Qt]);
                    241:                        }
                    242:                }
                    243: T1 = time(); Tpd += (T1[0]-T0[0])+(T1[1]-T0[1]); RTpd += (T1[3]-T0[3]);
                    244:                Qt = iso_comp(Gt,Pt,V,Ord|mod=Mod,first=First,iso=Iso);
                    245:                Q = append(Q,[Qt]);
                    246:                for ( T = Qt; T != []; T = cdr(T) )
                    247:                        IntQ = ideal_intersection(IntQ,car(T)[0],V,Ord
                    248:                                |mod=Mod,
                    249:                                 gbblock=[[0,length(IntQ)],[length(IntQ),length(car(T)[0])]]);
                    250:                if ( First ) { IntP = IntPt; First = 0; }
                    251:                if ( gen_gb_comp(IntQ,G,Mod) ) break;
                    252:
                    253:                M = mingen(IntQ,V);
                    254:                for ( Pt = [], C = [1], T = M; T != []; T = cdr(T) ) {
                    255:                        Ci = colon(G,car(T),V|isgb=1);
                    256:                        if ( type(Ci[0]) != 1 ) {
                    257:                                Pi = prime_dec(Ci,V|indep=1,lexdec=Lexdec,radical=1,mod=Mod);
                    258:                                C = ideal_intersection(C,Pi[1],V,Ord);
                    259:                                Pt = append(Pt,Pi[0]);
                    260:                        }
                    261:                }
                    262:                Pt = pd_simp_comp(Pt,V|first=1,mod=Mod);
                    263:                if ( Colon ) C = ideal_colon(G,IntQ,V|mod=Mod);
                    264: T2 = time(); Tiso += (T2[0]-T1[0])+(T2[1]-T1[1]); RTiso += (T2[3]-T1[3]);
                    265:                Ok = (*SIF)(C,G,IntQ,IntP,V,Ord|mod=Mod);
                    266:                Gt = append(Ok,G);
                    267: T3 = time(); Tsep += (T3[0]-T2[0])+(T3[1]-T2[1]); RTsep += (T3[3]-T2[3]);
                    268:        }
                    269:        T4 = time(); RTall = (T4[3]-Tall[3]); Tall = (T4[0]-Tall[0])+(T3[1]-Tall[1]);
                    270:        if ( Time ) {
                    271:                print(["cpu","total",Tall,"pd",Tpd,"iso",Tiso,"sep",Tsep]);
                    272:                print(["elapsed","total",RTall,"pd",RTpd,"iso",RTiso,"sep",RTsep]);
                    273:        }
                    274:        return Q;
                    275: }
                    276:
                    277: static Tint2, RTint2$
                    278:
                    279: def syci_dec(B,V)
                    280: {
                    281:        if ( type(SI=getopt(si)) == -1 ) SI = 1;
                    282:        if ( SI<0 || SI>2 ) error("sycb_assdec : si should be 0,1,2");
                    283:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                    284:        if ( type(Lexdec=getopt(lexdec)) == -1 ) Lexdec = 0;
                    285:        if ( type(Time=getopt(time)) == -1 ) Time = 0;
                    286:        if ( type(Iso=getopt(iso)) == -1 ) Iso = 0;
                    287:        if ( type(Ass=getopt(ass)) == -1 ) Ass = 0;
                    288:        if ( type(Colon=getopt(colon)) == -1 ) Colon = 0;
                    289:        if ( type(Para=getopt(para)) == -1 ) Para = 0;
1.8       noro      290:        if ( type(Trace=getopt(trace)) == -1 ) Trace = 0;
1.1       noro      291:        Ord = 0;
                    292:        Tiso = Tint = Tpd = Text = Tint2 = 0;
                    293:        RTiso = RTint = RTpd = RText = RTint2 = 0;
                    294: T00 = time();
1.8       noro      295:        G = fast_gb(B,V,Mod,Ord|trace=Trace);
1.1       noro      296:        IntQ = [1]; QL = RL = []; First = 1;
                    297:        for ( Level = 0; ; Level++ ) {
                    298: T0 = time();
1.8       noro      299:                if ( !Level ) {
1.1       noro      300:                        PtR = prime_dec(G,V|indep=1,lexdec=Lexdec,mod=Mod,radical=1);
1.8       noro      301: ACCUM_TIME(Tfpd,RTfpd)
1.1       noro      302:                        Pt = PtR[0]; IntPt = PtR[1]; Rad = IntPt;
1.2       noro      303:                        if ( gen_gb_comp(G,Rad,Mod) ) {
                    304:                                /* Gt is radical and Gt = cap Pt */
                    305:                                for ( T = Pt, Qt = []; T != []; T = cdr(T) )
                    306:                                        Qt = cons([car(T)[0],car(T)[0],car(T)[1]],Qt);
                    307:                                return [reverse(Qt)];
                    308:                        }
1.1       noro      309:                } else
                    310:                        Pt = colon_prime_dec(G,IntQ,V|lexdec=Lexdec,mod=Mod,para=Para);
                    311: ACCUM_TIME(Tpd,RTpd)
                    312: T0 = time();
                    313:                Rt = iso_comp(G,Pt,V,Ord|mod=Mod,iso=Iso,para=Para,intq=IntQ);
                    314: ACCUM_TIME(Tiso,RTiso)
1.8       noro      315:                if ( !Level ) {
                    316:                        if ( Iso == 3 ) {
                    317:                                NI = length(Rt);
                    318:                                Q = IntQ;
                    319: T0 = time();
                    320:                                if ( Para ) {
                    321:                                        for ( J = 0, Task = []; J < NI; J++ ) {
                    322:                                                T = ["noro_pd.extract_qj",Q,V,Rt[J],Rad,Mod,SI,Colon,-1];
                    323:                                                Task = cons(T,Task);
                    324:                                        }
                    325:                                        Task = reverse(Task);
                    326:                                        print("comps:",2); print(length(Task),2);
                    327:                                        Rt = para_exec(Para,Task);
                    328:                                } else {
                    329:                                        for ( J = 0, T = []; J < NI; J++ ) {
                    330:                                                TJ = extract_qj(Q,V,Rt[J],Rad,Mod,SI,Colon,-1);
                    331:                                                T = cons(TJ,T);
                    332:                                        }
                    333:                                        Rt = reverse(T);
                    334:                                }
                    335: ACCUM_TIME(Text,RText)
                    336:                        }
                    337:                        print("");
                    338: T0 = time();
                    339:                        Int = Rad;
                    340:                        for ( T = Rt; T != []; T = cdr(T) )
                    341:                                if ( !gb_comp(car(T)[0],car(T)[1]) )
                    342:                                        Int = ideal_intersection_m(Int,car(T)[0],V,Ord|mod=Mod);
                    343:                        IntQ = nd_gr(Int,V,Mod,Ord);
                    344: ACCUM_TIME(Tint,RTint)
                    345:                        RL = append(RL,[Rt]);
                    346:                } else if ( Iso != 3 ) {
1.1       noro      347: T0 = time();
1.8       noro      348:                        IntQ = ideal_list_intersection(map(first,Rt),V,Ord|mod=Mod,isgb=1);
1.4       noro      349:                        RL = append(RL,[Rt]);
1.8       noro      350: ACCUM_TIME(Tint,RTint)
1.4       noro      351:                } else {
                    352:                        NI = length(Rt);
                    353:                        Q = IntQ;
1.8       noro      354:                        if ( Para ) {
                    355:                                for ( J = 0, Task = []; J < NI; J++ ) {
                    356:                                        T = ["noro_pd.extract_qj",Q,V,Rt[J],Rad,Mod,SI,Colon,-1];
                    357:                                        Task = cons(T,Task);
                    358:                                }
                    359:                                Task = reverse(Task);
                    360:                                print("comps:",2); print(length(Task),2);
                    361: T0 = time();
                    362:                                R = para_exec(Para,Task);
                    363: ACCUM_TIME(Text,RText)
                    364:                                print("");
                    365: T0 = time();
                    366:                                IntQ = ideal_list_intersection(cons(IntQ,map(first,R)),V,Ord|mod=Mod);
                    367: ACCUM_TIME(Tint,RTint)
                    368:                                RL = append(RL,[R]);
                    369:                        } else {
                    370:                                for ( J = 0, T = []; J < NI; J++ ) {
                    371: T0 = time();
                    372:                                        TJ = extract_qj(Q,V,Rt[J],Rad,Mod,SI,Colon,-1);
                    373: ACCUM_TIME(Text,RText)
                    374:                                        T = cons(TJ,T);
                    375: T0 = time();
                    376:                                        IntQ = ideal_intersection_m(IntQ,TJ[0],V,Ord|mod=Mod);
                    377: ACCUM_TIME(Tint,RTint)
                    378:                                }
                    379:                                print("");
                    380: T0 = time();
                    381:                                IntQ = nd_gr(IntQ,V,Mod,Ord);
                    382: ACCUM_TIME(Tint,RTint)
                    383:                                T = reverse(T); RL = append(RL,[T]);
1.4       noro      384:                        }
                    385:                }
1.1       noro      386:                QL = append(QL,[IntQ]);
                    387:                if ( gen_gb_comp(IntQ,G,Mod) ) break;
                    388:        }
                    389: T0 = time();
1.4       noro      390:        if ( Iso != 3 && !Ass )
1.1       noro      391:                RL = extract_comp(QL,RL,V,Rad|mod=Mod,para=Para,si=SI,colon=Colon,ass=Ass);
                    392: ACCUM_TIME(Text,RText)
                    393:        if ( Time ) {
                    394:                T1 = time();
                    395:                Tall = T1[0]-T00[0]+T1[1]-T00[1]; RTall += T1[3]-T00[3];
                    396:                Tass = Tall-Text; RTass = RTall-RText;
1.8       noro      397:                print(["total",Tall,"ass",Tass,"pd",Tpd,"(fpd)",Tfpd,"iso",Tiso,"int",Tint,"ext",Text]);
                    398:                print(["elapsed",RTall,"ass",RTass,"pd",RTpd,"(fpd)",RTfpd,"iso",RTiso,"int",RTint,"ext",RText]);
1.1       noro      399:        }
                    400:        return  RL;
                    401: }
                    402:
                    403: def extract_comp(QL,RL,V,Rad) {
                    404:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                    405:        if ( type(Para=getopt(para)) == -1 ) Para = 0;
                    406:        if ( type(Colon=getopt(colon)) == -1 ) Colon = 0;
                    407:        if ( type(SI=getopt(si)) == -1 ) SI = 1;
                    408:        if ( type(Ass=getopt(ass)) == -1 ) Ass = 0;
                    409:
                    410:        L = length(QL);
                    411:        if ( Para ) {
                    412:                for ( Task = [], I = 1; I < L; I++ ) {
                    413:                        QI = QL[I-1]; RI = RL[I]; NI = length(RI);
                    414:                        for ( J = 0, TI = []; J < NI; J++ ) {
                    415:                                T = ["noro_pd.extract_qj",QI,V,RI[J],Rad,Mod,SI,Colon,I];
                    416:                                Task = cons(T,Task);
                    417:                        }
                    418:                }
1.8       noro      419:                Task = reverse(Task);
1.1       noro      420:                print("comps:",2); print(length(Task),2); print("");
                    421:                R = para_exec(Para,Task);
                    422:                S = vector(L);
                    423:                for ( I = 1; I < L; I++ ) S[I] = [];
                    424:                S[0] = RL[0];
                    425:                for ( T = R; T != []; T = cdr(T) ) {
                    426:                        U = car(T); Level = U[0]; Body = U[1];
                    427:                        S[Level] = cons(Body,S[Level]);
                    428:                }
                    429:                return vtol(S);
                    430:        } else {
                    431:                TL = [RL[0]];
                    432:                for ( I = 1; I < L; I++ ) {
                    433:                        print("level:",2); print(I,2);
                    434:                        print(" comps:",2); print(length(RL[I]),2); print("");
                    435:                        QI = QL[I-1]; RI = RL[I]; NI = length(RI);
                    436:                        for ( J = 0, TI = []; J < NI; J++ ) {
                    437:                                TIJ = extract_qj(QI,V,RI[J],Rad,Mod,SI,Colon,-1);
                    438:                                TI = cons(TIJ,TI);
                    439:                        }
                    440:                        TI = reverse(TI); TL = cons(TI,TL);
                    441:                }
                    442:                TL = reverse(TL);
                    443:        }
                    444:        return TL;
                    445: }
                    446:
                    447: def colon_prime_dec(G,IntQ,V) {
                    448:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                    449:        if ( type(Lexdec=getopt(lexdec)) == -1 ) Lexdec = 0;
                    450:        if ( type(Para=getopt(para)) == -1 ) Para = 0;
1.3       noro      451:        if ( !Para ) {
                    452:                print("colon_pd:",2); print(length(IntQ),2);
                    453:        }
1.1       noro      454:        if ( !Mod ) M = mingen(IntQ,V);
                    455:        else M = IntQ;
                    456:        if ( Para ) {
                    457:                L = length(M);
1.3       noro      458:                for ( Task = [], J = 0; J < L; J++ )
1.1       noro      459:                        if ( gen_nf(M[J],G,V,Ord,Mod) ) {
1.3       noro      460:                                T = ["noro_pd.call_colon",G,M[J],V,Mod,1];
1.1       noro      461:                                Task = cons(T,Task);
                    462:                        }
                    463:                Task = reverse(Task);
                    464:                R = para_exec(Para,Task);
1.3       noro      465:                R = pd_simp_comp(R,V|mod=Mod); L = length(R);
                    466:
                    467:                for ( Task = [], J = 0; J < L; J++ ) {
                    468:                        T = ["noro_pd.call_prime_dec",R[J],V,1,Lexdec,Mod];
                    469:                        Task = cons(T,Task);
                    470:                }
                    471:                Task = reverse(Task);
                    472:                R = para_exec(Para,Task);
                    473:
1.1       noro      474:                for ( Pt = [], T = R; T != []; T = cdr(T) ) Pt = append(Pt,car(T));
                    475:        } else {
1.3       noro      476:                for ( R = [], T = M; T != []; T = cdr(T) ) {
                    477:                        Ci = colon(G,car(T),V|isgb=1,mod=Mod);
                    478:                        R = cons(Ci,R);
                    479:                }
                    480:                print("->",2); print(length(M),2);
                    481:                R = pd_simp_comp(R,V|mod=Mod);
                    482:                print("->",2); print(length(R));
1.8       noro      483: #if 1
1.3       noro      484:                for ( Pt = [], T = R; T != []; T = cdr(T) ) {
                    485:                        Pi = prime_dec(car(T),V|indep=1,lexdec=Lexdec,mod=Mod);
1.1       noro      486:                        Pt = append(Pt,Pi);
                    487:                }
1.8       noro      488: #else
                    489:                J = ideal_list_intersection(R,V,0|mod=Mod);
                    490:                Pt = prime_dec(J,V|indep=1,lexdec=Lexdec,mod=Mod);
                    491: #endif
1.1       noro      492:        }
1.8       noro      493: #if 1
1.1       noro      494:        Pt = pd_simp_comp(Pt,V|first=1,mod=Mod);
1.8       noro      495: #endif
1.1       noro      496:        return Pt;
                    497: }
                    498:
1.3       noro      499: def call_colon(G,F,V,Mod,IsGB)
                    500: {
                    501:        return colon(G,F,V|isgb=1,mod=Mod);
                    502: }
                    503:
                    504: def call_prime_dec(G,V,Indep,Lexdec,Mod)
1.1       noro      505: {
1.3       noro      506:        if ( type(G[0]) != 1 )
                    507:                Pi = prime_dec(G,V|indep=Indep,lexdec=Lexdec,mod=Mod);
1.1       noro      508:        else
                    509:                Pi = [];
                    510:        return Pi;
                    511: }
                    512:
                    513: def extract_qj(Q,V,QL,Rad,Mod,SI,Colon,Level)
                    514: {
                    515:        SIFList=[find_ssi0, find_ssi1,find_ssi2];
                    516:        SIF = SIFList[SI];
                    517:        G = QL[0]; P = QL[1]; PV = QL[2];
1.4       noro      518:        if ( Q != [1] ) {
                    519:                C = Colon ? ideal_colon(G,Q,V|mod=Mod) : P;
                    520:                Ok = (*SIF)(C,G,Q,Rad,V,0|mod=Mod);
                    521:        } else
                    522:                Ok = [];
1.1       noro      523:        V0 = setminus(V,PV);
                    524:        HJ = elim_gb(append(Ok,G),V0,PV,Mod,[[0,length(V0)],[0,length(PV)]]);
                    525:        HJ = contraction(HJ,V0|mod=Mod);
                    526:        IJ = nd_gr(HJ,V,Mod,Ord);
                    527:        return Level >= 0 ? [Level,[IJ,P]] : [IJ,P];
                    528: }
                    529:
                    530: def syca_dec(B,V)
                    531: {
                    532: T00 = time();
                    533:        if ( type(SI=getopt(si)) == -1 ) SI = 2;
                    534:        SIFList=[find_si0, find_si1,find_si2]; SIF = SIFList[SI];
                    535:        if ( !SIF ) error("syca_dec : si should be 0,1,2");
                    536:
                    537:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                    538:        if ( type(Lexdec=getopt(lexdec)) == -1 ) Lexdec = 0;
                    539:        if ( type(NoSimp=getopt(nosimp)) == -1 ) NoSimp = 0;
                    540:        if ( type(Time=getopt(time)) == -1 ) Time = 0;
                    541:        if ( type(Iso=getopt(iso)) == -1 ) Iso = 0;
                    542:        Ord = 0;
                    543:        Gt = G0 = G = fast_gb(B,V,Mod,Ord|trace=1);
                    544:        Q0 = Q = []; IntQ0 = IntQ = [1]; First = 1;
                    545:        C = 0;
                    546:
                    547:        Tass = Tiso = Tcolon = Tsep = Tirred = 0;
                    548:        Rass = Riso = Rcolon = Rsep = Rirred = 0;
                    549:        while ( 1 ) {
                    550:                if ( type(Gt[0])==1 ) break;
                    551:                T0 = time();
                    552:                PtR = prime_dec(Gt,V|indep=1,lexdec=Lexdec,mod=Mod,radical=1);
                    553:                T1 = time(); Tass += T1[0]-T0[0]+T1[1]-T0[1]; Rass += T1[3]-T0[3];
                    554:                Pt = PtR[0]; IntPt = PtR[1];
                    555:                if ( gen_gb_comp(Gt,IntPt,Mod) ) {
                    556:                        /* Gt is radical and Gt = cap Pt */
                    557:                        for ( T = Pt, Qt = []; T != []; T = cdr(T) )
                    558:                                Qt = cons([car(T)[0],car(T)[0]],Qt);
                    559:                        if ( First )
                    560:                                return [Qt,[]];
                    561:                        else
                    562:                                Q0 = append(Qt,Q0);
                    563:                        break;
                    564:                }
                    565:                T0 = time();
                    566:                Qt = iso_comp(Gt,Pt,V,Ord|mod=Mod,isgb=1,iso=Iso);
                    567:                T1 = time(); Tiso += T1[0]-T0[0]+T1[1]-T0[1]; Riso += T1[3]-T0[3];
                    568:                IntQt = ideal_list_intersection(map(first,Qt),V,Ord|mod=Mod);
                    569:                if ( First ) {
                    570:                        IntQ0 = IntQ = IntQt; IntP = IntPt; Qi = Qt; First = 0;
                    571:                } else {
                    572:                        IntQ1 = ideal_intersection(IntQ,IntQt,V,Ord|mod=Mod);
                    573:                        if ( gen_gb_comp(IntQ,IntQ1,Mod) ) {
                    574:                                G = Gt; IntP = IntPt; Q = []; IntQ = [1]; C = 0;
                    575:                                continue;
                    576:                        } else {
                    577:                                IntQ = IntQ1;
                    578:                                IntQ1 = ideal_intersection(IntQ0,IntQt,V,Ord|mod=Mod);
                    579:                                if ( !gen_gb_comp(IntQ0,IntQ1,Mod) ) {
                    580:                                        Q = append(Qt,Q);
                    581:                                        for ( T = Qt; T != []; T = cdr(T) )
                    582:                                                if ( !ideal_inclusion(IntQ0,car(T)[0],V,Ord|mod=Mod) )
                    583:                                                        Q0 = append(Q0,[car(T)]);
                    584:                                        IntQ0 = IntQ1;
                    585:                                }
                    586:                        }
                    587:                }
                    588:                if ( gen_gb_comp(IntQt,Gt,Mod) || gen_gb_comp(IntQ,G,Mod) || gen_gb_comp(IntQ0,G0,Mod) ) break;
                    589:                T0 = time();
                    590:                C1 = ideal_colon(G,IntQ,V|mod=Mod);
                    591:                T1 = time(); Tcolon += T1[0]-T0[0]+T1[1]-T0[1]; Rcolon += T1[3]-T0[3];
                    592:                if ( C && gen_gb_comp(C,C1,Mod) ) {
                    593:                        G = Gt; IntP = IntPt; Q = []; IntQ = [1]; C = 0;
                    594:                        continue;
                    595:                } else C = C1;
                    596:                T0 = time();
                    597:                Ok = (*SIF)(C,G,IntQ,IntP,V,Ord|mod=Mod);
                    598:                G1 = append(Ok,G);
                    599:                Gt1 = incremental_gb(G1,V,Ord|mod=Mod);
                    600:                T1 = time(); Tsep += T1[0]-T0[0]+T1[1]-T0[1]; Rsep += T1[3]-T0[3];
                    601:                Gt = Gt1;
                    602:        }
                    603:        T0 = time();
                    604:        if ( !NoSimp ) Q1 = qd_remove_redundant_comp(G0,Qi,Q0,V,Ord|mod=Mod);
                    605:        else Q1 = Q0;
                    606:        if ( Time ) {
                    607:                T1 = time(); Tirred += T1[0]-T0[0]+T1[1]-T0[1]; Rirred += T1[3]-T0[3];
                    608:                Tall = T1[0]-T00[0]+T1[1]-T00[1]; Rall += T1[3]-T00[3];
                    609:                print(["total",Tall,"ass",Tass,"iso",Tiso, "colon",Tcolon,"sep",Tsep,"irred",Tirred]);
                    610:                print(["Rtotal",Rall,"Rass",Rass,"Riso",Riso, "Rcolon",Rcolon,"Rsep",Rsep,"Rirred",Rirred]);
                    611:                print(["iso",length(Qi),"emb",length(Q0),"->",length(Q1)]);
                    612:        }
                    613:        return [Qi,Q1];
                    614: }
                    615:
                    616: def syc0_dec(B,V)
                    617: {
                    618: T00 = time();
                    619:        if ( type(SI=getopt(si)) == -1 ) SI = 1;
                    620:        SIFList=[find_si0, find_si1,find_si2,find_ssi0,find_ssi1,find_ssi2]; SIF = SIFList[SI];
                    621:        if ( !SIF ) error("syc0_dec : si should be 0,1,2");
                    622:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                    623:        if ( type(Lexdec=getopt(lexdec)) == -1 ) Lexdec = 0;
                    624:        if ( type(NoSimp=getopt(nosimp)) == -1 ) NoSimp = 0;
                    625:        if ( type(Time=getopt(time)) == -1 ) Time = 0;
                    626:        Ord = 0;
                    627:        G = fast_gb(B,V,Mod,Ord);
                    628:        Q = []; IntQ = [1]; Gt = G; First = 1;
                    629:        Tass = Tiso = Tcolon = Tsep = Tirred = 0;
                    630:        Rass = Riso = Rcolon = Rsep = Rirred = 0;
                    631:        while ( 1 ) {
                    632:                if ( type(Gt[0])==1 ) break;
                    633:                T0 = time();
                    634:                PtR = prime_dec(Gt,V|indep=1,lexdec=Lexdec,mod=Mod,radical=1);
                    635:                T1 = time(); Tass += T1[0]-T0[0]+T1[1]-T0[1]; Rass += T1[3]-T0[3];
                    636:                Pt = PtR[0]; IntPt = PtR[1];
                    637:                if ( gen_gb_comp(Gt,IntPt,Mod) ) {
                    638:                        /* Gt is radical and Gt = cap Pt */
                    639:                        for ( T = Pt, Qt = []; T != []; T = cdr(T) )
                    640:                                Qt = cons([car(T)[0],car(T)[0]],Qt);
                    641:                        if ( First )
                    642:                                return [Qt,[]];
                    643:                        else
                    644:                                Q = append(Qt,Q);
                    645:                        break;
                    646:                }
                    647:
                    648:                T0 = time();
                    649:                Qt = iso_comp(Gt,Pt,V,Ord|mod=Mod,isgb=1);
                    650:                T1 = time(); Tiso += T1[0]-T0[0]+T1[1]-T0[1]; Riso += T1[3]-T0[3];
                    651:                IntQt = ideal_list_intersection(map(first,Qt),V,Ord|mod=Mod);
                    652:                if ( First ) {
                    653:                        IntQ = IntQt; Qi = Qt; First = 0;
                    654:                } else {
                    655:                        IntQ1 = ideal_intersection(IntQ,IntQt,V,Ord|mod=Mod);
                    656:                        if ( !gen_gb_comp(IntQ1,IntQ,Mod) )
                    657:                                Q = append(Qt,Q);
                    658:                }
                    659:                if ( gen_gb_comp(IntQ,G,Mod) || gen_gb_comp(IntQt,Gt,Mod) )
                    660:                        break;
                    661:                T0 = time();
                    662:                C = ideal_colon(Gt,IntQt,V|mod=Mod);
                    663:                T1 = time(); Tcolon += T1[0]-T0[0]+T1[1]-T0[1]; Rcolon += T1[3]-T0[3];
                    664:                T0 = time();
                    665:                Ok = (*SIF)(C,Gt,IntQt,IntPt,V,Ord|mod=Mod);
                    666:                G1 = append(Ok,Gt);
                    667:                Gt = incremental_gb(G1,V,Ord|mod=Mod);
                    668:                T1 = time(); Tsep += T1[0]-T0[0]+T1[1]-T0[1]; Rsep += T1[3]-T0[3];
                    669:        }
                    670:        T0 = time();
                    671:        if ( !NoSimp ) Q1 = qd_remove_redundant_comp(G,Qi,Q,V,Ord|mod=Mod);
                    672:        else Q1 = Q;
                    673:        T1 = time(); Tirred += T1[0]-T0[0]+T1[1]-T0[1]; Rirred += T1[3]-T0[3];
                    674:        Tall = T1[0]-T00[0]+T1[1]-T00[1]; Rall += T1[3]-T00[3];
                    675:        if ( Time ) {
                    676:                print(["total",Tall,"ass",Tass,"iso",Tiso, "colon",Tcolon,"sep",Tsep,"irred",Tirred]);
                    677:                print(["Rtotal",Rall,"Rass",Rass,"Riso",Riso, "Rcolon",Rcolon,"Rsep",Rsep,"Rirred",Rirred]);
                    678:                print(["iso",length(Qi),"emb",length(Q),"->",length(Q1)]);
                    679:        }
                    680:        return [Qi,Q1];
                    681: }
                    682:
                    683: def power(A,I) { return A^I; }
                    684:
                    685:
                    686: /* functions for computating a separing ideal  */
                    687: /* C=G:Q, Rad=rad(Q), return J s.t. Q cap (G+J) = G */
                    688:
                    689: def find_si0(C,G,Q,Rad,V,Ord) {
                    690:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                    691:        for ( CI = C, I = 1; ; I++ ) {
                    692:                for ( T = CI, S = []; T != []; T = cdr(T) )
                    693:                        if ( gen_nf(car(T),Q,V,Ord,Mod) ) S = cons(car(T),S);
                    694:                if ( S == [] )
                    695:                        error("find_si0 : cannot happen");
                    696:                G1 = append(S,G);
                    697:                Int = ideal_intersection(G1,Q,V,Ord|mod=Mod);
                    698:                /* check whether (Q cap (G+S)) = G */
                    699:                if ( gen_gb_comp(Int,G,Mod) ) { print([0]); return reverse(S); }
                    700:                CI = ideal_product(CI,C,V|mod=Mod);
                    701:        }
                    702: }
                    703:
                    704: def find_si1(C,G,Q,Rad,V,Ord) {
                    705:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                    706:        for ( T = C, S = []; T != []; T = cdr(T) )
                    707:                if ( gen_nf(car(T),Q,V,Ord,Mod) ) S = cons(car(T),S);
                    708:        if ( S == [] )
                    709:                error("find_si1 : cannot happen");
                    710:        G1 = append(S,G);
                    711:        Int = ideal_intersection(G1,Q,V,Ord|mod=Mod);
                    712:        /* check whether (Q cap (G+S)) = G */
                    713:        if ( gen_gb_comp(Int,G,Mod) ) { print([0]); return reverse(S); }
                    714:
1.9     ! ohara     715:        C = qsort(C,noro_pd.comp_tdeg);
1.1       noro      716:
                    717:        Tmp = ttttt; TV = cons(Tmp,V); Ord1 = [[0,1],[Ord,length(V)]];
                    718:        Int0 = incremental_gb(append(vtol(ltov(G)*Tmp),vtol(ltov(Q)*(1-Tmp))),
                    719:                TV,Ord1|gbblock=[[0,length(G)]],mod=Mod);
                    720:        Dp = dp_gr_print(); dp_gr_print(0);
                    721:        for ( T = C, S = []; T != []; T = cdr(T) ) {
                    722:                if ( !gen_nf(car(T),Rad,V,Ord,Mod) ) continue;
                    723:                Ui = U = car(T);
                    724:                for ( I = 1; ; I++ ) {
                    725:                        G1 = cons(Ui,G);
                    726:                        Int = ideal_intersection(G1,Q,V,Ord|mod=Mod);
                    727:                        if ( gen_gb_comp(Int,G,Mod) ) break;
                    728:                        else
                    729:                                Ui = gen_nf(Ui*U,G,V,Ord,Mod);
                    730:                }
                    731:                print([length(T),I],2);
                    732:                Int1 = incremental_gb(append(Int0,[Tmp*Ui]),TV,Ord1
                    733:                        |gbblock=[[0,length(Int0)]],mod=Mod);
                    734:                Int = elimination(Int1,V);
                    735:                if ( !gen_gb_comp(Int,G,Mod) ) {
                    736:                        break;
                    737:                } else {
                    738:                        Int0 = Int1;
                    739:                        S = cons(Ui,S);
                    740:                }
                    741:        }
                    742:        print("");
                    743:        dp_gr_print(Dp);
                    744:        return reverse(S);
                    745: }
                    746:
                    747: def find_si2(C,G,Q,Rad,V,Ord) {
                    748:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                    749:        for ( T = C, S = []; T != []; T = cdr(T) )
                    750:                if ( gen_nf(car(T),Q,V,Ord,Mod) ) S = cons(car(T),S);
                    751:        if ( S == [] )
                    752:                error("find_si2 : cannot happen");
                    753:        G1 = append(S,G);
                    754:        Int = ideal_intersection(G1,Q,V,Ord|mod=Mod);
                    755:        /* check whether (Q cap (G+S)) = G */
                    756:        if ( gen_gb_comp(Int,G,Mod) ) { print([0]); return reverse(S); }
                    757:
1.9     ! ohara     758:        C = qsort(C,noro_pd.comp_tdeg);
1.1       noro      759:
                    760:        Dp = dp_gr_print(); dp_gr_print(0);
                    761:        Tmp = ttttt; TV = cons(Tmp,V); Ord1 = [[0,1],[Ord,length(V)]];
                    762:        Int0 = incremental_gb(append(vtol(ltov(G)*Tmp),vtol(ltov(Q)*(1-Tmp))),
                    763:                TV,Ord1|gbblock=[[0,length(G)]],mod=Mod);
                    764:        for ( T = C, S = []; T != []; T = cdr(T) ) {
                    765:                if ( !gen_nf(car(T),Rad,V,Ord,Mod) ) continue;
                    766:                Ui = U = car(T);
                    767:                for ( I = 1; ; I++ ) {
                    768:                        Int1 = incremental_gb(append(Int0,[Tmp*Ui]),TV,Ord1
                    769:                                        |gbblock=[[0,length(Int0)]],mod=Mod);
                    770:                        Int = elimination(Int1,V);
                    771:                        if ( gen_gb_comp(Int,G,Mod) ) break;
                    772:                        else
                    773:                                Ui = gen_nf(Ui*U,G,V,Ord,Mod);
                    774:                }
                    775:                print([length(T),I],2);
                    776:                S = cons(Ui,S);
                    777:        }
1.9     ! ohara     778:        S = qsort(S,noro_pd.comp_tdeg);
1.1       noro      779:        print("");
                    780:        End = Len = length(S);
                    781:
                    782:        Tmp = ttttt; TV = cons(Tmp,V); Ord1 = [[0,1],[Ord,length(V)]];
                    783:        Prev = 1;
                    784:        G1 = append(G,[S[0]]);
                    785:        Int0 = incremental_gb(append(vtol(ltov(G1)*Tmp),vtol(ltov(Q)*(1-Tmp))),
                    786:                TV,Ord1|gbblock=[[0,length(G)]],mod=Mod);
                    787:        if ( End > 1 ) {
                    788:                Cur = 2;
                    789:                while ( Prev < Cur ) {
                    790:                        for ( St = [], I = Prev; I < Cur; I++ ) St = cons(Tmp*S[I],St);
                    791:                        Int1 = incremental_gb(append(Int0,St),TV,Ord1
                    792:                                |gbblock=[[0,length(Int0)]],mod=Mod);
                    793:                        Int = elimination(Int1,V);
                    794:                        if ( gen_gb_comp(Int,G,Mod) ) {
                    795:                                print([Cur],2);
                    796:                                Prev = Cur;
                    797:                                Cur = Cur+idiv(End-Cur+1,2);
                    798:                                Int0 = Int1;
                    799:                        } else {
                    800:                                End = Cur;
                    801:                                Cur = Prev + idiv(Cur-Prev,2);
                    802:                        }
                    803:                }
                    804:                for ( St = [], I = 0; I < Prev; I++ ) St = cons(S[I],St);
                    805:        } else
                    806:                St = [S[0]];
                    807:        print("");
                    808:        for ( I = Prev; I < Len; I++ ) {
                    809:                Int1 = incremental_gb(append(Int0,[Tmp*S[I]]),TV,Ord1
                    810:                        |gbblock=[[0,length(Int0)]],mod=Mod);
                    811:                Int = elimination(Int1,V);
                    812:                if ( gen_gb_comp(Int,G,Mod) ) {
                    813:                        print([I],2);
                    814:                        St = cons(S[I],St);
                    815:                        Int0 = Int1;
                    816:                }
                    817:        }
                    818:        Ok = reverse(St);
                    819:        print("");
                    820:        print([length(S),length(Ok)]);
                    821:        dp_gr_print(Dp);
                    822:        return Ok;
                    823: }
                    824:
                    825: /* functions for computing a saturated separating ideal */
                    826:
                    827: def find_ssi0(C,G,Q,Rad,V,Ord) {
                    828:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                    829:        if ( type(Reduce=getopt(red)) == -1 ) Reduce = 0;
                    830:        for ( T = C, S = []; T != []; T = cdr(T) )
                    831:                if ( gen_nf(car(T),Q,V,Ord,Mod) ) S = cons(car(T),S);
                    832:        if ( S == [] )
                    833:                error("find_ssi0 : cannot happen");
                    834:        G1 = append(S,G);
                    835:        Int = ideal_intersection(G1,Q,V,Ord|mod=Mod);
                    836:        /* check whether (Q cap (G+S)) = G */
                    837:        if ( gen_gb_comp(Int,G,Mod) ) { print([0]); return reverse(S); }
                    838:
                    839:        if ( Reduce ) {
                    840:                for ( T = C, U = []; T != []; T = cdr(T) )
                    841:                        if ( gen_nf(car(T),Rad,V,Ord,Mod) ) U = cons(car(T),U);
                    842:                U = reverse(U);
                    843:        } else
                    844:                U = C;
                    845:
                    846:        for ( I = 1; ; I++ ) {
                    847:                print([I],2);
                    848:                S = map(power,U,I);
                    849:                G1 = append(S,G);
                    850:                Int = ideal_intersection(G1,Q,V,Ord|mod=Mod);
                    851:                /* check whether (Q cap (G+S)) = G */
                    852:                if ( gen_gb_comp(Int,G,Mod) ) { print(""); return reverse(S); }
                    853:        }
                    854: }
                    855:
                    856: def find_ssi1(C,G,Q,Rad,V,Ord) {
                    857:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                    858:        if ( type(Reduce=getopt(red)) == -1 ) Reduce = 0;
                    859:        for ( T = C, S = []; T != []; T = cdr(T) )
                    860:                if ( gen_nf(car(T),Q,V,Ord,Mod) ) S = cons(car(T),S);
                    861:        if ( S == [] )
                    862:                error("find_ssi1 : cannot happen");
                    863:        G1 = append(S,G);
                    864:        Int = ideal_intersection(G1,Q,V,Ord|mod=Mod);
                    865:        /* check whether (Q cap (G+S)) = G */
                    866:        if ( gen_gb_comp(Int,G,Mod) ) { print([0]); return reverse(S); }
                    867:
                    868:        dp_ord(Ord); DC = map(dp_ptod,C,V);
1.9     ! ohara     869:        DC = qsort(DC,noro_pd.comp_tord); C = map(dp_dtop,DC,V);
1.1       noro      870:        print(length(C),2);
                    871:        if ( Reduce ) {
                    872:                SC = map(sq,C,Mod);
                    873:                SC = reverse(SC); C = reverse(C);
                    874:                for ( T = C, C1 = [],  R1 = append(SC,Rad); T != []; T = cdr(T) ) {
                    875:                        R0 = car(R1); R1 = cdr(R1);
                    876:                        if ( !gen_nf(car(T),Rad,V,Ord,Mod) ) continue;
                    877:                        if ( radical_membership(R0,R1,V|mod=Mod)  ) {
                    878:                                C1 = cons(car(T),C1);
                    879:                                R1 = append(R1,[R0]);
                    880:                        }
                    881:                }
                    882:                print("->",0); print(length(C1),2);
                    883:                C = C1;
                    884:        }
                    885:        print(" ",2);
                    886:
                    887:        Tmp = ttttt; TV = cons(Tmp,V); Ord1 = [[0,1],[Ord,length(V)]];
                    888:        Int0 = incremental_gb(append(vtol(ltov(G)*Tmp),vtol(ltov(Q)*(1-Tmp))),
                    889:                TV,Ord1|gbblock=[[0,length(G)]],mod=Mod);
                    890:        Dp = dp_gr_print(); dp_gr_print(0);
                    891:        for ( J = 0, T = C, S = [], GS = G; T != []; T = cdr(T), J++ ) {
                    892:                if ( !gen_nf(car(T),Rad,V,Ord,Mod) ) continue;
                    893:                Ui = U = car(T);
                    894:                for ( I = 1; ; I++ ) {
                    895:                        Int1 = nd_gr(append(Int0,[Tmp*Ui]),TV,Mod,Ord1
                    896:                                |gbblock=[[0,length(Int0)]],newelim=1);
                    897:                        if ( Int1 ) {
                    898:                                Int = elimination(Int1,V);
                    899:                                if ( gen_gb_comp(Int,G,Mod) ) break;
                    900:                        }
                    901:                        print("x",2);
                    902:                        Ui = gen_nf(Ui*U,G,V,Ord,Mod);
                    903:                }
                    904:                print(J,2);
                    905:                Int0 = Int1;
                    906:                S = cons(Ui,S);
                    907:        }
                    908:        print("");
                    909:        dp_gr_print(Dp);
                    910:        return reverse(S);
                    911: }
                    912:
                    913: def find_ssi2(C,G,Q,Rad,V,Ord) {
                    914:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                    915:        if ( type(Reduce=getopt(red)) == -1 ) Reduce = 0;
                    916:        for ( T = C, S = []; T != []; T = cdr(T) )
                    917:                if ( gen_nf(car(T),Q,V,Ord,Mod) ) S = cons(car(T),S);
                    918:        if ( S == [] )
                    919:                error("find_ssi2 : cannot happen");
                    920:        G1 = append(S,G);
                    921:        Int = ideal_intersection(G1,Q,V,Ord|mod=Mod);
                    922:        /* check whether (Q cap (G+S)) = G */
                    923:        if ( gen_gb_comp(Int,G,Mod) ) { print([0]); return reverse(S); }
                    924:
                    925: #if 0
                    926:        dp_ord(Ord); DC = map(dp_ptod,C,V);
1.9     ! ohara     927:        DC = qsort(DC,noro_pd.comp_tord); C = map(dp_dtop,DC,V);
1.1       noro      928: #else
1.9     ! ohara     929:        C = qsort(C,noro_pd.comp_tdeg);
1.1       noro      930: #endif
                    931:        if ( Reduce ) {
                    932:                for ( T = C, C1 = [], R1 = Rad; T != []; T = cdr(T) ) {
                    933:                        if ( !gen_nf(car(T),Rad,V,Ord,Mod) ) continue;
1.4       noro      934:                        if ( radical_membership(car(T),R1,V|mod=Mod)  ) {
1.1       noro      935:                                C1 = cons(car(T),C1);
                    936:                                R1 = cons(sq(car(T),Mod),R1);
                    937:                        }
                    938:                }
                    939:                print(["C",length(C),"->",length(C1)]);
                    940:                C = reverse(C1);
                    941:        }
                    942:        for ( T = C, S = []; T != []; T = cdr(T) ) {
                    943:                if ( !gen_nf(car(T),Rad,V,Ord,Mod) ) continue;
                    944:                Ui = U = car(T);
                    945:                S = cons([Ui,U],S);
                    946:        }
1.9     ! ohara     947:        S = qsort(S,noro_pd.comp_tdeg_first);
1.1       noro      948:        print("");
                    949:
                    950:        Dp = dp_gr_print(); dp_gr_print(0);
                    951:        Tmp = ttttt; TV = cons(Tmp,V); Ord1 = [[0,1],[Ord,length(V)]];
                    952:        Int0 = incremental_gb(append(vtol(ltov(G)*Tmp),vtol(ltov(Q)*(1-Tmp))),
                    953:                TV,Ord1|gbblock=[[0,length(G)]],mod=Mod);
                    954:        OK = [];
                    955:        while ( S != [] ) {
                    956:                Len = length(S); print("remaining gens : ",0); print(Len);
                    957:                S1 = [];
                    958:                for ( Start = Prev = 0; Start < Len; Start = Prev ) {
                    959:                        Cur = Start+1;
                    960:                        print(Start,2);
                    961:                        while ( Prev < Len ) {
                    962:                                for ( St = [], I = Prev; I < Cur; I++ ) St = cons(Tmp*S[I][0],St);
                    963:                                Int1 = nd_gr(append(Int0,St),TV,Mod,Ord1|gbblock=[[0,length(Int0)]],newelim=1);
                    964:                                if ( !Int1 ) {
                    965:                                        print("x",0); break;
                    966:                                }
                    967:                                Int = elimination(Int1,V);
                    968:                                if ( gen_gb_comp(Int,G,Mod) ) {
                    969:                                        print([Prev,Cur-1],2);
                    970:                                        Prev = Cur;
                    971:                                        Cur += (Prev-Start)+1;
                    972:                                        if ( Cur > Len ) Cur = Len;
                    973:                                        Int0 = Int1;
                    974:                                } else
                    975:                                        break;
                    976:                        }
                    977:                        for ( I = Start; I < Prev; I++ ) OK = cons(S[I][0],OK);
                    978:                        if ( Prev == Start ) {
                    979:                                Ui = S[I][0]; U = S[I][1];
                    980:                                Ui = gen_nf(Ui*U,G,V,Ord,Mod);
                    981:                                S1 = cons([Ui,U],S1);
                    982:                                Prev++;
                    983:                        }
                    984:                }
                    985:                S = reverse(S1);
                    986:                print("");
                    987:        }
                    988:        print("");
                    989:        OK = reverse(OK);
                    990:        dp_gr_print(Dp);
                    991:        return OK;
                    992: }
                    993:
                    994: /* SY primary decompsition */
                    995:
                    996: def sy_dec(B,V)
                    997: {
                    998:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                    999:        if ( type(Lexdec=getopt(lexdec)) == -1 ) Lexdec = 0;
                   1000:        Ord = 0;
                   1001:        G = fast_gb(B,V,Mod,Ord);
                   1002:        Q = [];
                   1003:        IntQ = [1];
                   1004:        Gt = G;
                   1005:        First = 1;
                   1006:        while ( 1 ) {
                   1007:                if ( type(Gt[0]) == 1 ) break;
                   1008:                Pt = prime_dec(Gt,V|indep=1,lexdec=Lexdec,mod=Mod);
                   1009:                L = pseudo_dec(Gt,Pt,V,Ord|mod=Mod);
                   1010:                Qt = L[0]; Rt = L[1]; St = L[2];
                   1011:                IntQt = ideal_list_intersection(map(first,Qt),V,Ord|mod=Mod);
                   1012:                if ( First ) {
                   1013:                        IntQ = IntQt;
                   1014:                        Qi = Qt;
                   1015:                        First = 0;
                   1016:                } else {
                   1017:                        IntQ = ideal_intersection(IntQ,IntQt,V,Ord|mod=Mod);
                   1018:                        Q = append(Qt,Q);
                   1019:                }
                   1020:                if ( gen_gb_comp(IntQ,G,Mod) ) break;
                   1021:                for ( T = Rt; T != []; T = cdr(T) ) {
                   1022:                        if ( type(car(T)[0]) == 1 ) continue;
                   1023:                        U = sy_dec(car(T),V|lexdec=Lexdec,mod=Mod);
                   1024:                        IntQ = ideal_list_intersection(cons(IntQ,map(first,U)),
                   1025:                                V,Ord|mod=Mod);
                   1026:                        Q = append(U,Q);
                   1027:                        if ( gen_gb_comp(IntQ,G,Mod) ) break;
                   1028:                }
                   1029:                Gt = fast_gb(append(Gt,St),V,Mod,Ord);
                   1030:        }
                   1031:        Q = qd_remove_redundant_comp(G,Qi,Q,V,Ord|mod=Mod);
                   1032:        return append(Qi,Q);
                   1033: }
                   1034:
                   1035: def pseudo_dec(G,L,V,Ord)
                   1036: {
                   1037:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                   1038:        N = length(L);
                   1039:        S = vector(N);
                   1040:        Q = vector(N);
                   1041:        R = vector(N);
                   1042:        L0 = map(first,L);
                   1043:        for ( I = 0; I < N; I++ ) {
                   1044:                LI = setminus(L0,[L0[I]]);
                   1045:                PI = ideal_list_intersection(LI,V,Ord|mod=Mod);
1.9     ! ohara    1046:                PI = qsort(PI,noro_pd.comp_tdeg);
1.1       noro     1047:                for ( T = PI; T != []; T = cdr(T) )
                   1048:                        if ( gen_nf(car(T),L0[I],V,Ord,Mod) ) break;
                   1049:                if ( T == [] ) error("separator : cannot happen");
                   1050:                SI = satind(G,car(T),V|mod=Mod);
                   1051:                QI = SI[0];
                   1052:                S[I] = car(T)^SI[1];
                   1053:                PV = L[I][1];
                   1054:                V0 = setminus(V,PV);
                   1055: #if 0
                   1056:                GI = fast_gb(QI,append(V0,PV),Mod,
                   1057:                        [[Ord,length(V0)],[Ord,length(PV)]]);
                   1058: #else
                   1059:                GI = fast_gb(QI,append(V0,PV),Mod,
                   1060:                        [[2,length(V0)],[Ord,length(PV)]]);
                   1061: #endif
                   1062:                LCFI = lcfactor(GI,V0,Ord,Mod);
                   1063:                for ( F = 1, T = LCFI, Gt = QI; T != []; T = cdr(T) ) {
                   1064:                        St = satind(Gt,T[0],V|mod=Mod);
                   1065:                        Gt = St[0]; F *= T[0]^St[1];
                   1066:                }
                   1067:                Q[I] = [Gt,L0[I]];
                   1068:                R[I] = fast_gb(cons(F,QI),V,Mod,Ord);
                   1069:        }
                   1070:        return [vtol(Q),vtol(R),vtol(S)];
                   1071: }
                   1072:
                   1073: def iso_comp(G,L,V,Ord)
                   1074: {
                   1075:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                   1076:        if ( type(IsGB=getopt(isgb)) == -1 ) IsGB = 0;
                   1077:        if ( type(Iso=getopt(iso)) == -1 ) Iso = 0;
                   1078:        if ( type(Para=getopt(para)) == -1 ) Para = 0;
                   1079:        if ( type(Q=getopt(intq)) == -1 ) Q = 0;
1.4       noro     1080:        if ( type(S=getopt(sep)) == -1 ) S = 0;
1.1       noro     1081:
1.4       noro     1082:        if ( !S ) S = separator(L,V|mod=Mod);
1.1       noro     1083:        N = length(L);
                   1084:        print("comps : ",2); print(N); print("",2);
                   1085:        if ( Para ) {
                   1086:                Task = [];
                   1087:                for ( I = 0; I < N; I++ ) {
                   1088:                        T = ["noro_pd.locsat",G,V,L[I],S[I],Mod,IsGB,Iso,Q];
                   1089:                        Task = cons(T,Task);
                   1090:                }
                   1091:                Task = reverse(Task);
                   1092:                R = para_exec(Para,Task);
                   1093:                return R;
                   1094:        } else {
                   1095:                for ( I = 0, R = []; I < N; I++ ) {
                   1096:                        QI = locsat(G,V,L[I],S[I],Mod,IsGB,Iso,Q);
                   1097:                        if ( type(QI[0][0])==1 )
                   1098:                                error("iso_comp : cannot happen");
                   1099:                        print(".",2);
                   1100:                        R = cons(QI,R);
                   1101:                }
                   1102:                print("");
                   1103:                return reverse(R);
                   1104:        }
                   1105: }
                   1106:
                   1107: def locsat(G,V,L,S,Mod,IsGB,Iso,Q)
                   1108: {
                   1109:        P = L[0]; PV = L[1]; V0 = setminus(V,PV);
                   1110:        if ( Iso==1 ) {
                   1111:                QI = sat(G,S,V|isgb=IsGB,mod=Mod);
                   1112:                GI = elim_gb(QI,V0,PV,Mod,[[0,length(V0)],[0,length(PV)]]);
1.8       noro     1113:                GI = nd_gr(contraction(GI,V0|mod=Mod,allv=V),V,Mod,0);
1.1       noro     1114:        } else if ( Iso==0 ) {
                   1115:                HI = elim_gb(G,V0,PV,Mod,[[0,length(V0)],[0,length(PV)]]);
1.8       noro     1116:                GI = nd_gr(contraction(HI,V0|mod=Mod,allv=V),V,Mod,0);
1.1       noro     1117:                GI = sat(GI,S,V|isgb=IsGB,mod=Mod);
                   1118:        } else if ( Iso==2 ) {
                   1119:                HI = elim_gb(G,V0,PV,Mod,[[0,length(V0)],[0,length(PV)]]);
                   1120:                TV = ttttt;
                   1121:                if ( Mod )
                   1122:                        GI = nd_gr(cons(TV*S-1,HI),cons(TV,V0),Mod,[[0,1],[0,length(V0)]]);
                   1123:                else
                   1124:                        GI = nd_gr_trace(append(HI,[TV*S-1]),cons(TV,V0),
                   1125:                                1,1,[[0,1],[0,length(V0)]]|gbblock=[[0,length(HI)]]);
                   1126:                GI = elimination(GI,V);
1.8       noro     1127:                GI = nd_gr(contraction(GI,V0|mod=Mod,allv=V),V,Mod,0);
1.4       noro     1128:        } else if ( Iso==3 ) {
                   1129:                GI = sat(G,S,V|isgb=IsGB,mod=Mod);
1.1       noro     1130:        }
                   1131:        if ( Q )
                   1132:                GI = ideal_intersection(Q,GI,V,0|mod=Mod);
                   1133:        return [GI,P,PV];
                   1134: }
                   1135:
                   1136: /* GTZ primary decompsition */
                   1137:
                   1138: def prima_dec(B,V)
                   1139: {
                   1140:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                   1141:        if ( type(Ord=getopt(ord)) == -1 ) Ord = 0;
                   1142:        G0 = fast_gb(B,V,Mod,0);
                   1143:        G = fast_gb(G0,V,Mod,Ord);
                   1144:        IntP = [1];
                   1145:        QD = [];
                   1146:        while ( 1 ) {
                   1147:                if ( type(G[0])==1 || ideal_inclusion(IntP,G0,V,0|mod=Mod) )
                   1148:                        break;
                   1149:                W = maxindep(G,V,Ord); NP = length(W);
                   1150:                V0 = setminus(V,W); N = length(V0);
                   1151:                V1 = append(V0,W);
                   1152:                G1 = fast_gb(G,V1,Mod,[[Ord,N],[Ord,NP]]);
                   1153:                LCF = lcfactor(G1,V0,Ord,Mod);
                   1154:                L = zprimacomp(G,V0|mod=Mod);
                   1155:                F = 1;
                   1156:                for ( T = LCF, G2 = G; T != []; T = cdr(T) ) {
                   1157:                        S = satind(G2,T[0],V1|mod=Mod);
                   1158:                        G2 = S[0]; F *= T[0]^S[1];
                   1159:                }
                   1160:                for ( T = L, QL = []; T != []; T = cdr(T) )
                   1161:                        QL = cons(car(T)[0],QL);
                   1162:                Int = ideal_list_intersection(QL,V,0|mod=Mod);
                   1163:                IntP = ideal_intersection(IntP,Int,V,0|mod=Mod);
                   1164:                QD = append(QD,L);
                   1165:                F = gen_nf(F,G,V,0,Mod);
                   1166:                G = fast_gb(cons(F,G),V,Mod,Ord);
                   1167:        }
                   1168:        QD = qd_remove_redundant_comp(G0,[],QD,V,0);
                   1169:        return QD;
                   1170: }
                   1171:
                   1172: /* SL prime decomposition */
                   1173:
                   1174: def prime_dec(B,V)
                   1175: {
                   1176:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                   1177:        if ( type(Indep=getopt(indep)) == -1 ) Indep = 0;
1.7       noro     1178:        if ( type(LexDec=getopt(lexdec)) == -1 ) LexDec = 0;
1.1       noro     1179:        if ( type(Rad=getopt(radical)) == -1 ) Rad = 0;
                   1180:        B = map(sq,B,Mod);
                   1181:        if ( LexDec )
                   1182:                PD = lex_predec1(B,V|mod=Mod);
                   1183:        else
                   1184:                PD = [B];
                   1185:        if ( length(PD) > 1 ) {
                   1186:                G = ideal_list_intersection(PD,V,0|mod=Mod);
                   1187:                PD = pd_remove_redundant_comp(G,PD,V,0|mod=Mod);
                   1188:        }
1.8       noro     1189:        R = []; RL = [];
                   1190:        for ( T = PD; T != []; T = cdr(T) ) {
                   1191:                PDT = prime_dec_main(car(T),V|indep=Indep,mod=Mod);
                   1192:                R = append(R,PDT[0]);
                   1193:                GT = nd_gr(PDT[1],V,Mod,0);
                   1194:                RL = append(RL,[GT]);
                   1195:        }
                   1196:        if ( LexDec ) R = pd_simp_comp(R,V|first=Indep,mod=Mod);
                   1197:        if ( Rad ) {
                   1198:                G = ideal_list_intersection(RL,V,0|mod=Mod);
                   1199:                return [R,G];
                   1200:        } else return R;
1.7       noro     1201: }
                   1202:
                   1203: def prime_dec2(B,V)
                   1204: {
                   1205:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                   1206:        if ( type(Indep=getopt(indep)) == -1 ) Indep = 0;
                   1207:        if ( type(LexDec=getopt(lexdec)) == -1 ) LexDec = 0;
                   1208:        if ( type(Rad=getopt(radical)) == -1 ) Rad = 0;
                   1209:        if ( type(Para=getopt(para)) == -1 || type(Para) != 4 ) Para = [];
                   1210:        B = map(sq,B,Mod);
                   1211:        if ( LexDec )
                   1212:                PD = lex_predec1(B,V|mod=Mod);
                   1213:        else
                   1214:                PD = [B];
                   1215:        if ( length(PD) > 1 ) {
                   1216:                G = ideal_list_intersection(PD,V,0|mod=Mod);
                   1217:                PD = pd_remove_redundant_comp(G,PD,V,0|mod=Mod);
                   1218:        }
                   1219:        R = [];
                   1220:        for ( T = PD; T != []; T = cdr(T) )
                   1221:                R = append(prime_dec_main2(car(T),V|indep=Indep,mod=Mod,para=Para),R);
                   1222:        if ( Indep ) {
                   1223:                G = ideal_list_intersection(map(first,R),V,0|mod=Mod);
                   1224:                R = pd_simp_comp(R,V|first=1,mod=Mod);
                   1225:        } else {
                   1226:                G = ideal_list_intersection(R,V,0|mod=Mod);
                   1227:                R = pd_simp_comp(R,V|mod=Mod);
1.1       noro     1228:        }
                   1229:        return Rad ? [R,G] : R;
                   1230: }
                   1231:
1.8       noro     1232: /* returns [PD,rad(I)] */
                   1233:
1.1       noro     1234: def prime_dec_main(B,V)
                   1235: {
1.8       noro     1236:        Tpint = RTpint = 0;
1.1       noro     1237:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                   1238:        if ( type(Indep=getopt(indep)) == -1 ) Indep = 0;
                   1239:        G = fast_gb(B,V,Mod,0);
                   1240:        IntP = [1];
                   1241:        PD = [];
1.4       noro     1242:        DG = ltov(map(dp_ptod,G,V));
                   1243:        for ( Ind = [], I = length(G)-1; I >= 0; I-- ) Ind = cons(I,Ind);
                   1244:        if ( Mod ) DG = map(dp_mod,DG,Mod,[]);
1.1       noro     1245:        while ( 1 ) {
1.8       noro     1246:                print([length(PD)],2);
1.1       noro     1247:                /* rad(G) subset IntP */
                   1248:                /* check if IntP subset rad(G) */
1.4       noro     1249:                /* print([length(PD),length(IntP)],2); */
1.7       noro     1250:                for ( T = IntP; T != []; T = cdr(T) )
1.8       noro     1251:                        if ( (G0 = radical_membership_sat(car(T),G,V|mod=Mod,isgb=1,dg=[DG,Ind])) ) {
1.1       noro     1252:                                F = car(T);
                   1253:                                break;
                   1254:                        }
1.8       noro     1255:                if ( T == [] ) {
                   1256:                        print(["pint",Tpint,"rpint",RTpint]);
                   1257:                        return [PD,IntP];
                   1258:                }
1.1       noro     1259:                PD0 = zprimecomp(G0,V,Indep|mod=Mod);
1.7       noro     1260:                Int = ideal_list_intersection(Indep?map(first,PD0):PD0,V,0|mod=Mod);
                   1261:                PD = append(PD,PD0);
1.8       noro     1262: #if 1
                   1263: T0=time();
1.4       noro     1264:                IntP = ideal_intersection_m(IntP,Int,V,0|mod=Mod);
1.8       noro     1265:                dp_ord(0); DC = map(dp_ptod,IntP,V);
1.9     ! ohara    1266:                DC = qsort(DC,noro_pd.comp_tord); IntP = map(dp_dtop,DC,V);
1.8       noro     1267: ACCUM_TIME(Tpint,RTpint)
1.4       noro     1268: #else
1.7       noro     1269:                IntP = ideal_intersection(IntP,Int,V,0|mod=Mod,gbblock=[[0,length(IntP)]]);
1.4       noro     1270: #endif
1.1       noro     1271:        }
                   1272: }
                   1273:
1.8       noro     1274: localf callsat,callzcomp;
                   1275:
                   1276: def callsat(F,G,V,Mod,DG)
                   1277: {
                   1278:        return radical_membership(F,G,V|mod=Mod,isgb=1,dg=DG,sat=1);
                   1279: }
                   1280:
                   1281: def callzcomp(F,V,Indep,Mod)
                   1282: {
                   1283:        PD0 = zprimecomp(F,V,Indep|mod=Mod);
                   1284:        Int = ideal_list_intersection(Indep?map(first,PD0):PD0,V,0|mod=Mod);
                   1285:        return [PD0,Int];
                   1286: }
                   1287:
1.7       noro     1288: def prime_dec_main2(B,V)
                   1289: {
                   1290:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                   1291:        if ( type(Indep=getopt(indep)) == -1 ) Indep = 0;
                   1292:        if ( type(Para=getopt(para)) == -1 || type(Para) != 4 ) Para = [];
                   1293:        NPara = length(Para);
                   1294:
                   1295:        G = fast_gb(B,V,Mod,0);
                   1296:        IntP = [1];
                   1297:        PD = [];
                   1298:        DG = ltov(map(dp_ptod,G,V));
                   1299:        for ( Ind = [], I = length(G)-1; I >= 0; I-- ) Ind = cons(I,Ind);
                   1300:        if ( Mod ) DG = map(dp_mod,DG,Mod,[]);
1.8       noro     1301:        if ( NPara )
                   1302:                while ( 1 ) {
                   1303:                        IntPM = mingen(IntP,V);
                   1304:                        for ( T = IntPM, CallSat = []; T != []; T = cdr(T) )
                   1305:                                CallSat = cons(["noro_pd.callsat",car(T),G,V,Mod,[DG,Ind]],CallSat);
                   1306:                        CallSat = reverse(CallSat);
                   1307:                        /* SatL = [[..],0,[...],...] */
                   1308:                        SatL = para_exec(Para,CallSat);
                   1309:                        for ( T = SatL, Sat = []; T != []; T = cdr(T) ) if ( car(T) ) Sat = cons(car(T),Sat);
                   1310:                        if ( Sat == [] ) return PD;
                   1311:                        print(length(Sat),2); print("->",2);
                   1312:                        Sat = remove_identical_comp(Sat|mod=Mod);
                   1313:                        print(length(Sat));
                   1314:                        for ( T = Sat, CallComp = []; T != []; T = cdr(T) )
                   1315:                                CallComp = cons(["noro_pd.callzcomp",car(T),V,Indep,Mod],CallComp);
                   1316:                        CallComp = reverse(CallComp);
                   1317:                        /* PDL = [[PD0,Int],...] */
                   1318:                        PDL = para_exec(Para,CallComp);
                   1319:                        for ( T = PDL; T != []; T = cdr(T) ) PD = append(PD,car(T)[0]);
                   1320:                        Int = ideal_list_intersection(map(second,PDL),V,0|mod=Mod);
1.7       noro     1321:                        IntP = ideal_intersection(IntP,Int,V,0|mod=Mod,gbblock=[[0,length(IntP)]]);
                   1322:                }
1.8       noro     1323:        else
                   1324:                while ( 1 ) {
                   1325:                        /* rad(G) subset IntP */
                   1326:                        /* check if IntP subset rad(G) */
                   1327:                        /* print([length(PD),length(IntP)],2); */
                   1328:                        Sat = [];
                   1329:                        IntPM = mingen(IntP,V);
                   1330:                        for ( T = IntPM; T != [] && length(Sat) < 16; T = cdr(T) )
                   1331:                                if ( G0 = radical_membership(car(T),G,V|mod=Mod,isgb=1,dg=[DG,Ind],sat=1) )
                   1332:                                        Sat = cons(G0,Sat);
                   1333:                        if ( Sat == [] ) return PD;
                   1334:                        print(length(Sat),2); print("->",2);
                   1335:                        Sat = remove_identical_comp(Sat|mod=Mod);
                   1336:                        print(length(Sat));
                   1337:                        for ( T = Sat; T != []; T = cdr(T) ) {
                   1338:                                PD0 = zprimecomp(car(T),V,Indep|mod=Mod); PD = append(PD,PD0);
                   1339:                                Int = ideal_list_intersection(Indep?map(first,PD0):PD0,V,0|mod=Mod);
                   1340:                                IntP = ideal_intersection(IntP,Int,V,0|mod=Mod,gbblock=[[0,length(IntP)]]);
                   1341:                        }
                   1342:                }
1.7       noro     1343: }
                   1344:
1.1       noro     1345: /* pre-decomposition */
                   1346:
                   1347: def lex_predec1(B,V)
                   1348: {
                   1349:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                   1350:        G = fast_gb(B,V,Mod,2);
                   1351:        for ( T = G; T != []; T = cdr(T) ) {
                   1352:                F = gen_fctr(car(T),Mod);
                   1353:                if ( length(F) > 2 || length(F) == 2 && F[1][1] > 1 ) {
                   1354:                        for ( R = [], S = cdr(F); S != []; S = cdr(S) ) {
                   1355:                                Ft = car(S)[0];
                   1356:                                Gt = map(ptozp,map(gen_nf,G,[Ft],V,0,Mod));
                   1357:                                R1 = fast_gb(cons(Ft,Gt),V,Mod,0);
                   1358:                                R = cons(R1,R);
                   1359:                        }
                   1360:                        return R;
                   1361:                }
                   1362:        }
                   1363:        return [G];
                   1364: }
                   1365:
                   1366: /* zero-dimensional prime/primary decomosition */
                   1367:
                   1368: def zprimedec(B,V,Mod)
                   1369: {
                   1370:        L = partial_decomp(B,V,Mod);
                   1371:        P = L[0]; NP = L[1];
                   1372:        R = [];
                   1373:        for ( ; P != []; P = cdr(P) ) R = cons(car(car(P)),R);
                   1374:        for ( T = NP; T != []; T = cdr(T) ) {
                   1375:                R1 = complete_decomp(car(T),V,Mod);
                   1376:                R = append(R1,R);
                   1377:        }
                   1378:        return R;
                   1379: }
                   1380:
                   1381: def zprimadec(B,V,Mod)
                   1382: {
                   1383:        L = partial_qdecomp(B,V,Mod);
                   1384:        Q = L[0]; NQ = L[1];
                   1385:        R = [];
                   1386:        for ( ; Q != []; Q = cdr(Q) ) {
                   1387:                T = car(Q); R = cons([T[0],T[1]],R);
                   1388:        }
                   1389:        for ( T = NQ; T != []; T = cdr(T) ) {
                   1390:                R1 = complete_qdecomp(car(T),V,Mod);
                   1391:                R = append(R1,R);
                   1392:        }
                   1393:        return R;
                   1394: }
                   1395:
                   1396: def complete_qdecomp(GD,V,Mod)
                   1397: {
                   1398:        GQ = GD[0]; GP = GD[1]; D = GD[2];
                   1399:        W = vars(GP);
                   1400:        PV = setminus(W,V);
                   1401:        N = length(V); PN = length(PV);
                   1402:        U = find_npos([GP,D],V,PV,Mod);
                   1403:        NV = ttttt;
                   1404:        M = gen_minipoly(cons(NV-U,GQ),cons(NV,V),PV,0,NV,Mod);
                   1405:        M = ppart(M,NV,Mod);
1.6       noro     1406:        MF = Mod ? modfctr(M,Mod) : fctr(M);
1.1       noro     1407:        R = [];
                   1408:        for ( T = cdr(MF); T != []; T = cdr(T) ) {
                   1409:                S = car(T);
                   1410:                Mt = subst(S[0],NV,U);
                   1411:                GP1 = fast_gb(cons(Mt,GP),W,Mod,0);
                   1412:                GQ1 = fast_gb(cons(Mt^S[1],GQ),W,Mod,0);
                   1413:                if ( PV != [] ) {
                   1414:                        GP1 = elim_gb(GP1,V,PV,Mod,[[0,N],[0,PN]]);
                   1415:                        GQ1 = elim_gb(GQ1,V,PV,Mod,[[0,N],[0,PN]]);
                   1416:                }
                   1417:                R = cons([GQ1,GP1],R);
                   1418:        }
                   1419:        return R;
                   1420: }
                   1421:
                   1422: def partial_qdecomp(B,V,Mod)
                   1423: {
                   1424:        Elim = (Elim=getopt(elim))&&type(Elim)!=-1 ? 1 : 0;
                   1425:        N = length(V);
                   1426:        W = vars(B);
                   1427:        PV = setminus(W,V);
                   1428:        NP = length(PV);
                   1429:        W = append(V,PV);
                   1430:        if ( Elim && PV != [] ) Ord = [[0,N],[0,NP]];
                   1431:        else Ord = 0;
                   1432:        if ( Mod )
                   1433:                B = nd_f4(B,W,Mod,Ord);
                   1434:        else
                   1435:                B = nd_gr_trace(B,W,1,GBCheck,Ord);
                   1436:        Q = []; NQ = [[B,B,vector(N+1)]];
                   1437:        for ( I = length(V)-1; I >= 0; I-- ) {
                   1438:                NQ1 = [];
                   1439:                for ( T = NQ; T != []; T = cdr(T) ) {
                   1440:                        L = partial_qdecomp0(car(T),V,PV,Ord,I,Mod);
                   1441:                        Q = append(L[0],Q);
                   1442:                        NQ1 = append(L[1],NQ1);
                   1443:                }
                   1444:                NQ = NQ1;
                   1445:        }
                   1446:        return [Q,NQ];
                   1447: }
                   1448:
                   1449: def partial_qdecomp0(GD,V,PV,Ord,I,Mod)
                   1450: {
                   1451:        GQ = GD[0]; GP = GD[1]; D = GD[2];
                   1452:        N = length(V); PN = length(PV);
                   1453:        W = append(V,PV);
                   1454:        VI = V[I];
                   1455:        M = gen_minipoly(GQ,V,PV,Ord,VI,Mod);
                   1456:        M = ppart(M,VI,Mod);
                   1457:        if ( Mod )
                   1458:                MF = modfctr(M,Mod);
                   1459:        else
                   1460:                MF = fctr(M);
                   1461:        Q = []; NQ = [];
                   1462:        if ( length(MF) == 2 && MF[1][1] == 1 ) {
                   1463:                D1 = D*1; D1[I] = M;
                   1464:                GQelim = elim_gb(GQ,V,PV,Mod,Ord);
                   1465:                GPelim = elim_gb(GP,V,PV,Mod,Ord);
                   1466:                LD = ldim(GQelim,V);
                   1467:                if ( deg(M,VI) == LD )
                   1468:                        Q = cons([GQelim,GPelim,D1],Q);
                   1469:                else
                   1470:                        NQ = cons([GQelim,GPelim,D1],NQ);
                   1471:                return [Q,NQ];
                   1472:        }
                   1473:        for ( T = cdr(MF); T != []; T = cdr(T) ) {
                   1474:                S = car(T); Mt = S[0]; D1 = D*1; D1[I] = Mt;
                   1475:
                   1476:                GQ1 = fast_gb(cons(Mt^S[1],GQ),W,Mod,Ord);
                   1477:                GQelim = elim_gb(GQ1,V,PV,Mod,Ord);
                   1478:                GP1 = fast_gb(cons(Mt,GP),W,Mod,Ord);
                   1479:                GPelim = elim_gb(GP1,V,PV,Mod,Ord);
                   1480:
                   1481:                D1[N] = LD = ldim(GPelim,V);
                   1482:
                   1483:                for ( J = 0; J < N; J++ )
                   1484:                        if ( D1[J] && deg(D1[J],V[J]) == LD ) break;
                   1485:                if ( J < N )
                   1486:                        Q = cons([GQelim,GPelim,D1],Q);
                   1487:                else
                   1488:                        NQ = cons([GQelim,GPelim,D1],NQ);
                   1489:        }
                   1490:        return [Q,NQ];
                   1491: }
                   1492:
                   1493: def complete_decomp(GD,V,Mod)
                   1494: {
                   1495:        G = GD[0]; D = GD[1];
                   1496:        W = vars(G);
                   1497:        PV = setminus(W,V);
                   1498:        N = length(V); PN = length(PV);
                   1499:        U = find_npos(GD,V,PV,Mod);
                   1500:        NV = ttttt;
                   1501:        M = gen_minipoly(cons(NV-U,G),cons(NV,V),PV,0,NV,Mod);
                   1502:        M = ppart(M,NV,Mod);
1.6       noro     1503:        MF = Mod ? modfctr(M,Mod) : fctr(M);
1.1       noro     1504:        if ( length(MF) == 2 ) return [G];
                   1505:        R = [];
                   1506:        for ( T = cdr(MF); T != []; T = cdr(T) ) {
                   1507:                Mt = subst(car(car(T)),NV,U);
                   1508:                G1 = fast_gb(cons(Mt,G),W,Mod,0);
                   1509:                if ( PV != [] ) G1 = elim_gb(G1,V,PV,Mod,[[0,N],[0,PN]]);
                   1510:                R = cons(G1,R);
                   1511:        }
                   1512:        return R;
                   1513: }
                   1514:
                   1515: def partial_decomp(B,V,Mod)
                   1516: {
                   1517:        Elim = (Elim=getopt(elim))&&type(Elim)!=-1 ? 1 : 0;
                   1518:        N = length(V);
                   1519:        W = vars(B);
                   1520:        PV = setminus(W,V);
                   1521:        NP = length(PV);
                   1522:        W = append(V,PV);
                   1523:        if ( Elim && PV != [] ) Ord = [[0,N],[0,NP]];
                   1524:        else Ord = 0;
                   1525:        if ( Mod )
                   1526:                B = nd_f4(B,W,Mod,Ord);
                   1527:        else
                   1528:                B = nd_gr_trace(B,W,1,GBCheck,Ord);
                   1529:        P = []; NP = [[B,vector(N+1)]];
                   1530:        for ( I = length(V)-1; I >= 0; I-- ) {
                   1531:                NP1 = [];
                   1532:                for ( T = NP; T != []; T = cdr(T) ) {
                   1533:                        L = partial_decomp0(car(T),V,PV,Ord,I,Mod);
                   1534:                        P = append(L[0],P);
                   1535:                        NP1 = append(L[1],NP1);
                   1536:                }
                   1537:                NP = NP1;
                   1538:        }
                   1539:        return [P,NP];
                   1540: }
                   1541:
                   1542: def partial_decomp0(GD,V,PV,Ord,I,Mod)
                   1543: {
                   1544:        G = GD[0]; D = GD[1];
                   1545:        N = length(V); PN = length(PV);
                   1546:        W = append(V,PV);
                   1547:        VI = V[I];
                   1548:        M = gen_minipoly(G,V,PV,Ord,VI,Mod);
                   1549:        M = ppart(M,VI,Mod);
                   1550:        if ( Mod )
                   1551:                MF = modfctr(M,Mod);
                   1552:        else
                   1553:                MF = fctr(M);
                   1554:        if ( length(MF) == 2 && MF[1][1] == 1 ) {
                   1555:                D1 = D*1;
                   1556:                D1[I] = M;
                   1557:                Gelim = elim_gb(G,V,PV,Mod,Ord);
                   1558:                D1[N] = LD = ldim(Gelim,V);
                   1559:                GD1 = [Gelim,D1];
                   1560:                for ( J = 0; J < N; J++ )
                   1561:                        if ( D1[J] && deg(D1[J],V[J]) == LD )
                   1562:                                return [[GD1],[]];
                   1563:                return [[],[GD1]];
                   1564:        }
                   1565:        P = []; NP = [];
                   1566:        GI = elim_gb(G,V,PV,Mod,Ord);
                   1567:        for ( T = cdr(MF); T != []; T = cdr(T) ) {
                   1568:                Mt = car(car(T));
                   1569:                D1 = D*1;
                   1570:                D1[I] = Mt;
                   1571:                GIt = map(gen_nf,GI,[Mt],V,Ord,Mod);
                   1572:                G1 = cons(Mt,GIt);
                   1573:                Gelim = elim_gb(G1,V,PV,Mod,Ord);
                   1574:                D1[N] = LD = ldim(Gelim,V);
                   1575:                for ( J = 0; J < N; J++ )
                   1576:                        if ( D1[J] && deg(D1[J],V[J]) == LD ) break;
                   1577:                if ( J < N )
                   1578:                        P = cons([Gelim,D1],P);
                   1579:                else
                   1580:                        NP = cons([Gelim,D1],NP);
                   1581:        }
                   1582:        return [P,NP];
                   1583: }
                   1584:
                   1585: /* prime/primary components over rational function field */
                   1586:
                   1587: def zprimacomp(G,V) {
                   1588:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                   1589:        L = zprimadec(G,V,0|mod=Mod);
                   1590:        R = [];
                   1591:        dp_ord(0);
                   1592:        for ( T = L; T != []; T = cdr(T) ) {
                   1593:                S = car(T);
                   1594:                UQ = contraction(S[0],V|mod=Mod);
                   1595:                UP = contraction(S[1],V|mod=Mod);
                   1596:                R = cons([UQ,UP],R);
                   1597:        }
                   1598:        return R;
                   1599: }
                   1600:
                   1601: def zprimecomp(G,V,Indep) {
                   1602:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                   1603:        W = maxindep(G,V,0|mod=Mod);
                   1604:        V0 = setminus(V,W);
                   1605:        V1 = append(V0,W);
                   1606: #if 0
                   1607:        O1 = [[0,length(V0)],[0,length(W)]];
                   1608:        G1 = fast_gb(G,V1,Mod,O1);
                   1609:        dp_ord(0);
                   1610: #else
                   1611:        G1 = G;
                   1612: #endif
                   1613:        PD = zprimedec(G1,V0,Mod);
                   1614:        dp_ord(0);
                   1615:        R = [];
                   1616:        for ( T = PD; T != []; T = cdr(T) ) {
                   1617:                U = contraction(car(T),V0|mod=Mod);
                   1618:                U = nd_gr(U,V,Mod,0);
1.7       noro     1619:                R = cons(Indep?[U,W]:U,R);
1.1       noro     1620:        }
1.7       noro     1621:        return R;
1.1       noro     1622: }
                   1623:
                   1624: def fast_gb(B,V,Mod,Ord)
                   1625: {
                   1626:        if ( type(Block=getopt(gbblock)) == -1 ) Block = 0;
                   1627:        if ( type(NoRA=getopt(nora)) == -1 ) NoRA = 0;
                   1628:        if ( type(Trace=getopt(trace)) == -1 ) Trace = 0;
                   1629:        if ( Mod )
                   1630:                G = nd_f4(B,V,Mod,Ord|nora=NoRA);
                   1631:        else if ( F4 )
                   1632:                G = map(ptozp,f4_chrem(B,V,Ord));
                   1633:        else if ( Trace ) {
                   1634:                if ( Block )
                   1635:                        G = nd_gr_trace(B,V,1,1,Ord|nora=NoRA,gbblock=Block);
                   1636:                else
                   1637:                        G = nd_gr_trace(B,V,1,1,Ord|nora=NoRA);
                   1638:        } else {
                   1639:                if ( Block )
                   1640:                        G = nd_gr(B,V,0,Ord|nora=NoRA,gbblock=Block);
                   1641:                else
                   1642:                        G = nd_gr(B,V,0,Ord|nora=NoRA);
                   1643:        }
                   1644:        return G;
                   1645: }
                   1646:
                   1647: def incremental_gb(A,V,Ord)
                   1648: {
                   1649:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                   1650:        if ( type(Block=getopt(gbblock)) == -1 ) Block = 0;
                   1651:        if ( Mod ) {
                   1652:                if ( Block )
                   1653:                        G = nd_gr(A,V,Mod,Ord|gbblock=Block);
                   1654:                else
                   1655:                        G = nd_gr(A,V,Mod,Ord);
                   1656:        } else if ( Procs ) {
                   1657:                Arg0 = ["nd_gr",A,V,0,Ord];
                   1658:                Arg1 = ["nd_gr_trace",A,V,1,GBCheck,Ord];
                   1659:                G = competitive_exec(Procs,Arg0,Arg1);
                   1660:        } else if ( Block )
                   1661:                G = nd_gr(A,V,0,Ord|gbblock=Block);
                   1662:        else
                   1663:                G = nd_gr(A,V,0,Ord);
                   1664:        return G;
                   1665: }
                   1666:
                   1667: def elim_gb(G,V,PV,Mod,Ord)
                   1668: {
                   1669:        N = length(V); PN = length(PV);
                   1670:        O1 = [[0,N],[0,PN]];
                   1671:        if ( Ord == O1 )
                   1672:                Ord = Ord[0][0];
                   1673:        if ( Mod ) /* XXX */ {
                   1674:                for ( T = G, H = []; T != []; T = cdr(T) )
                   1675:                        if ( car(T) ) H = cons(car(T),H);
                   1676:                G = reverse(H);
                   1677:                G = dp_gr_mod_main(G,V,0,Mod,Ord);
                   1678:        } else if ( EProcs ) {
                   1679: #if 1
                   1680:                Arg0 = ["dp_gr_main",G,V,0,0,Ord];
                   1681: #else
                   1682:                Arg0 = ["nd_gr",G,V,0,Ord];
                   1683: #endif
                   1684:                Arg1 = ["noro_pd.nd_gr_rat",G,V,PV,O1,Ord];
                   1685:                G = competitive_exec(EProcs,Arg0,Arg1);
                   1686:        } else if ( GBRat ) {
                   1687:                G1 = nd_gr(G,append(V,PV),0,O1);
1.8       noro     1688:                if ( GBRat == 1 )
                   1689:                G1 = nd_gr_postproc(G1,V,0,Ord,0|nora=1);
1.1       noro     1690:                return G1;
                   1691:        } else
                   1692: #if 1
1.2       noro     1693: #if 0
1.1       noro     1694:                G = dp_gr_main(G,V,0,0,Ord);
                   1695: #else
                   1696:                G = nd_gr_trace(G,V,1,1,Ord);
                   1697: #endif
                   1698: #else
                   1699:                G = nd_gr(G,V,0,Ord);
                   1700: #endif
                   1701:        return G;
                   1702: }
                   1703:
                   1704: def ldim(G,V)
                   1705: {
                   1706:        O0 = dp_ord(); dp_ord(0);
                   1707:        D = length(dp_mbase(map(dp_ptod,G,V)));
                   1708:        dp_ord(O0);
                   1709:        return D;
                   1710: }
                   1711:
                   1712: /* over Q only */
                   1713:
                   1714: def make_mod_subst(GD,V,PV,HC)
                   1715: {
                   1716:        N = length(V);
                   1717:        PN = length(PV);
                   1718:        G = GD[0]; D = GD[1];
                   1719:        for ( I = 0; ; I = (I+1)%100 ) {
                   1720:                Mod = lprime(I);
                   1721:                S = [];
                   1722:                for ( J = PN-1; J >= 0; J-- )
                   1723:                        S = append([PV[J],random()%Mod],S);
                   1724:                for ( T = HC; T != []; T = cdr(T) )
                   1725:                        if ( !(subst(car(T),S)%Mod) ) break;
                   1726:                if ( T != [] ) continue;
                   1727:                for ( J = 0; J < N; J++ ) {
                   1728:                        M = subst(D[J],S);
                   1729:                        F = modsqfr(M,Mod);
                   1730:                        if ( length(F) != 2 || F[1][1] != 1 ) break;
                   1731:                }
                   1732:                if ( J < N ) continue;
                   1733:                G0 = map(subst,G,S);
                   1734:                return [G0,Mod];
                   1735:        }
                   1736: }
                   1737:
                   1738: def rsgn()
                   1739: {
                   1740:        return random()%2 ? 1 : -1;
                   1741: }
                   1742:
                   1743: def find_npos(GD,V,PV,Mod)
                   1744: {
                   1745:        N = length(V); PN = length(PV);
                   1746:        G = GD[0]; D = GD[1]; LD = D[N];
1.5       noro     1747:        DH = map(dp_dtop,map(dp_ht,map(dp_ptod,D,V)),V);
1.1       noro     1748:        Ord0 = dp_ord(); dp_ord(0);
                   1749:        HC = map(dp_hc,map(dp_ptod,G,V));
                   1750:        dp_ord(Ord0);
                   1751:        if ( !Mod ) {
                   1752:                W = append(V,PV);
                   1753:                G1 = nd_gr_trace(G,W,1,GBCheck,[[0,N],[0,PN]]);
                   1754:                L = make_mod_subst([G1,D],V,PV,HC);
                   1755:                return find_npos([L[0],D],V,[],L[1]);
                   1756:        }
                   1757:        N = length(V);
                   1758:        NV = ttttt;
                   1759:        for ( B = 2; ; B++ ) {
                   1760:                for ( J = N-2; J >= 0; J-- ) {
1.5       noro     1761:                        for ( U = 0, K = J; K < N; K++ ) {
                   1762:                                if ( DH[K] == V[K] ) continue;
1.1       noro     1763:                                U += rsgn()*((random()%B+1))*V[K];
1.5       noro     1764:                        }
1.6       noro     1765: #if 0
1.1       noro     1766:                        M = minipolym(G,V,0,U,NV,Mod);
1.6       noro     1767: #else
                   1768:                        M = gen_minipoly(cons(NV-U,G),cons(NV,V),PV,0,NV,Mod);
                   1769: #endif
1.1       noro     1770:                        if ( deg(M,NV) == LD ) return U;
                   1771:                }
                   1772:        }
                   1773: }
                   1774:
                   1775: def gen_minipoly(G,V,PV,Ord,VI,Mod)
                   1776: {
1.6       noro     1777:        O0 = dp_ord();
1.1       noro     1778:        if ( PV == [] ) {
                   1779:                NV = sssss;
                   1780:                if ( Mod )
                   1781:                        M = minipolym(G,V,Ord,VI,NV,Mod);
                   1782:                else
                   1783:                        M = minipoly(G,V,Ord,VI,NV);
1.6       noro     1784:                dp_ord(O0);
1.1       noro     1785:                return subst(M,NV,VI);
                   1786:        }
                   1787:        W = setminus(V,[VI]);
                   1788:        PV1 = cons(VI,PV);
                   1789: #if 0
                   1790:        while ( 1 ) {
                   1791:                V1 = append(W,PV1);
                   1792:                if ( Mod )
                   1793:                        G = nd_gr(G,V1,Mod,[[0,1],[0,length(V1)-1]]|nora=1);
                   1794:                else
                   1795:                        G = nd_gr_trace(G,V1,1,GBCheck,[[0,1],[0,length(V1)-1]]|nora=1);
                   1796:                if ( W == [] ) break;
                   1797:                else {
                   1798:                        W = cdr(W);
                   1799:                        G = elimination(G,cdr(V1));
                   1800:                }
                   1801:        }
1.8       noro     1802: #elif 1
1.1       noro     1803:        if ( Mod ) {
                   1804:                V1 = append(W,PV1);
                   1805:                G = nd_gr(G,V1,Mod,[[0,length(W)],[0,length(PV1)]]);
                   1806:                G = elimination(G,PV1);
                   1807:        } else {
                   1808:                PV2 = setminus(PV1,[PV1[length(PV1)-1]]);
                   1809:                V2 = append(W,PV2);
                   1810:                G = nd_gr_trace(G,V2,1,GBCheck,[[0,length(W)],[0,length(PV2)]]|nora=1);
                   1811:                G = elimination(G,PV1);
                   1812:        }
                   1813: #else
                   1814:        V1 = append(W,PV1);
                   1815:        if ( Mod )
                   1816:                G = nd_gr(G,V1,Mod,[[0,length(W)],[0,length(PV1)]]|nora=1);
                   1817:        else
                   1818:                G = nd_gr_trace(G,V1,1,GBCheck,[[0,length(W)],[0,length(PV1)]]|nora=1);
                   1819:        G = elimination(G,PV1);
                   1820: #endif
                   1821:        if ( Mod )
                   1822:                G = nd_gr(G,PV1,Mod,[[0,1],[0,length(PV)]]|nora=1);
                   1823:        else
                   1824:                G = nd_gr_trace(G,PV1,1,GBCheck,[[0,1],[0,length(PV)]]|nora=1);
                   1825:        for ( M = car(G), T = cdr(G); T != []; T = cdr(T) )
                   1826:                if ( deg(car(T),VI) < deg(M,VI) ) M = car(T);
1.6       noro     1827:        dp_ord(O0);
1.1       noro     1828:        return M;
                   1829: }
                   1830:
                   1831: def indepset(V,H)
                   1832: {
                   1833:        if ( H == [] ) return V;
                   1834:        N = -1;
                   1835:        for ( T = V; T != []; T = cdr(T) ) {
                   1836:                VI = car(T);
                   1837:                HI = [];
                   1838:                for ( S = H; S != []; S = cdr(S) )
                   1839:                        if ( !tdiv(car(S),VI) ) HI = cons(car(S),HI);
                   1840:                RI = indepset(setminus(V,[VI]),HI);
                   1841:                if ( length(RI) > N ) {
                   1842:                        R = RI; N = length(RI);
                   1843:                }
                   1844:        }
                   1845:        return R;
                   1846: }
                   1847:
                   1848: def maxindep(B,V,O)
                   1849: {
                   1850:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                   1851:        G = fast_gb(B,V,Mod,O);
                   1852:        Old = dp_ord();
                   1853:        dp_ord(O);
                   1854:        H = map(dp_dtop,map(dp_ht,map(dp_ptod,G,V)),V);
                   1855:        H = map(sq,H,0);
                   1856:        H = nd_gr(H,V,0,0);
                   1857:        H = monodec0(H,V);
                   1858:        N = length(V);
                   1859:        Dep = [];
                   1860:        for ( T = H, Len = N+1; T != []; T = cdr(T) ) {
                   1861:                M = length(car(T));
                   1862:                if ( M < Len ) {
                   1863:                        Dep = [car(T)];
                   1864:                        Len = M;
                   1865:                } else if ( M == Len )
                   1866:                        Dep = cons(car(T),Dep);
                   1867:        }
                   1868:        R = setminus(V,Dep[0]);
                   1869:        dp_ord(Old);
                   1870:        return R;
                   1871: }
                   1872:
1.7       noro     1873: def maxindep2(B,V,O)
                   1874: {
                   1875:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                   1876:        G = fast_gb(B,V,Mod,O);
                   1877:        Old = dp_ord();
                   1878:        dp_ord(O);
                   1879:        H = map(dp_dtop,map(dp_ht,map(dp_ptod,G,V)),V);
                   1880:        H = map(sq,H,0);
                   1881:        H = nd_gr(H,V,0,0);
                   1882:        H = monodec0(H,V);
                   1883:        N = length(V);
                   1884:        Dep = [];
                   1885:        for ( T = H, Len = N+1; T != []; T = cdr(T) ) {
                   1886:                M = length(car(T));
                   1887:                if ( M < Len ) {
                   1888:                        Dep = [car(T)];
                   1889:                        Len = M;
                   1890:                } else if ( M == Len )
                   1891:                        Dep = cons(car(T),Dep);
                   1892:        }
                   1893:        R = [];
                   1894:        for ( T = Dep; T != []; T = cdr(T) )
                   1895:                R = cons(setminus(V,car(T)),R);
                   1896:        dp_ord(Old);
                   1897:        return reverse(R);
                   1898: }
                   1899:
                   1900:
1.1       noro     1901: /* ideal operations */
                   1902: def contraction(G,V)
                   1903: {
1.8       noro     1904:        if ( type(AllV=getopt(allv)) == -1 ) AllV = 0;
1.1       noro     1905:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
1.8       noro     1906:
                   1907:        if ( RepColon ) return contraction_m(G,V|allv=AllV,mod=Mod);
                   1908:
1.1       noro     1909:        C = [];
                   1910:        for ( T = G; T != []; T = cdr(T) ) {
                   1911:                C1 = dp_hc(dp_ptod(car(T),V));
                   1912:                S = gen_fctr(C1,Mod);
                   1913:                for ( S = cdr(S); S != []; S = cdr(S) )
                   1914:                        if ( !member(S[0][0],C) ) C = cons(S[0][0],C);
                   1915:        }
                   1916:        W = vars(G);
                   1917:        PV = setminus(W,V);
1.8       noro     1918:        if ( AllV ) W = AllV;
                   1919:        else W = append(V,PV);
1.1       noro     1920:        NV = ttttt;
1.8       noro     1921:        if ( SuccSat ) {
                   1922:                W1 = cons(NV,W);
                   1923:                O1 = [[0,1],[0,length(W)]];
                   1924:                Block = [];
                   1925:                for ( T = C; T != []; T = cdr(T) ) {
                   1926:                        G1 = nd_gr(append(G,[NV*car(T)-1]),W1,Mod,O1|gbblock=Block);
                   1927:                        G = elimination(G1,W);
                   1928:                        Block = [[0,length(G)]];
                   1929:                }
                   1930:        } else {
                   1931:                for ( T = C, S = 1; T != []; T = cdr(T) )
                   1932:                        S *= car(T);
                   1933:                G = saturation([G,NV],S,W|mod=Mod);
                   1934:        }
1.1       noro     1935:        return G;
                   1936: }
                   1937:
1.8       noro     1938: def contraction_m(G,V)
                   1939: {
                   1940:        if ( type(AllV=getopt(allv)) == -1 ) AllV = 0;
                   1941:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                   1942:        C = [];
                   1943:        for ( T = G; T != []; T = cdr(T) ) {
                   1944:                C1 = dp_hc(dp_ptod(car(T),V));
                   1945:                S = gen_fctr(C1,Mod);
                   1946:                for ( S = cdr(S); S != []; S = cdr(S) )
                   1947:                        if ( !member(S[0][0],C) ) C = cons(S[0][0],C);
                   1948:        }
                   1949:        W = vars(G);
                   1950:        PV = setminus(W,V);
                   1951:        if ( AllV ) W = AllV;
                   1952:        else W = append(V,PV);
                   1953:        H = H0 = G;
                   1954:        while ( 1 ) {
                   1955:                for ( T = C; T != []; T = cdr(T) )
                   1956:                        H = map(sdiv,ideal_intersection_m([car(T)],H,W,0),car(T));
                   1957:                H = nd_gr(H,W,0,0);
                   1958:                if ( gb_comp(H0,H) ) break;
                   1959:                else H0 = H;
                   1960:        }
                   1961:        return H;
                   1962: }
                   1963:
1.1       noro     1964: def ideal_list_intersection(L,V,Ord)
                   1965: {
                   1966:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
1.4       noro     1967:        if ( type(IsGB=getopt(isgb)) == -1 ) IsGB = 0;
1.1       noro     1968:        N = length(L);
                   1969:        if ( N == 0 ) return [1];
1.4       noro     1970:        if ( N == 1 )
                   1971:                return IsGB ? L[0] : fast_gb(L[0],V,Mod,Ord);
1.8       noro     1972:        else {
1.4       noro     1973:                for ( I = 0, T = [1]; I < N; I++ )
                   1974:                        T = ideal_intersection_m(T,L[I],V,Ord|mod=Mod);
                   1975:                T = nd_gr(T,V,Mod,Ord);
                   1976:                return T;
1.1       noro     1977:        }
                   1978: }
                   1979:
1.4       noro     1980: def call_ideal_list_intersection(L,V,Mod,Ord,IsGB)
1.1       noro     1981: {
1.4       noro     1982:        return ideal_list_intersection(L,V,Ord|mod=Mod,isgb=IsGB);
1.1       noro     1983: }
                   1984:
                   1985: def ideal_intersection(A,B,V,Ord)
                   1986: {
                   1987:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                   1988:        if ( type(Block=getopt(gbblock)) == -1 ) Block = 0;
                   1989:        T = ttttt;
                   1990:        if ( Mod ) {
                   1991:                if ( Block )
                   1992:                        G = nd_gr(append(vtol(ltov(A)*T),vtol(ltov(B)*(1-T))),
                   1993:                                cons(T,V),Mod,[[0,1],[Ord,length(V)]]|gbblock=Block,nora=0);
                   1994:                else
                   1995:                        G = nd_gr(append(vtol(ltov(A)*T),vtol(ltov(B)*(1-T))),
                   1996:                                cons(T,V),Mod,[[0,1],[Ord,length(V)]]|nora=0);
                   1997:        } else
                   1998:        if ( Procs ) {
                   1999:                Arg0 = ["nd_gr",
                   2000:                        append(vtol(ltov(A)*T),vtol(ltov(B)*(1-T))),
                   2001:                        cons(T,V),0,[[0,1],[Ord,length(V)]]];
                   2002:                Arg1 = ["nd_gr_trace",
                   2003:                        append(vtol(ltov(A)*T),vtol(ltov(B)*(1-T))),
                   2004:                        cons(T,V),1,GBCheck,[[0,1],[Ord,length(V)]]];
                   2005:                G = competitive_exec(Procs,Arg0,Arg1);
                   2006:        } else {
                   2007:                if ( Block )
                   2008:                        G = nd_gr(append(vtol(ltov(A)*T),vtol(ltov(B)*(1-T))),
                   2009:                                cons(T,V),0,[[0,1],[Ord,length(V)]]|gbblock=Block,nora=0);
                   2010:                else
                   2011:                        G = nd_gr(append(vtol(ltov(A)*T),vtol(ltov(B)*(1-T))),
                   2012:                                cons(T,V),0,[[0,1],[Ord,length(V)]]|nora=0);
                   2013:        }
                   2014:        G0 = elimination(G,V);
                   2015:        if ( 0 && !Procs )
                   2016:                G0 = nd_gr_postproc(G0,V,Mod,Ord,0);
                   2017:        return G0;
                   2018: }
                   2019:
1.4       noro     2020:
                   2021: def aa(A) { return [A,A]; }
                   2022:
                   2023: def ideal_intersection_m(A,B,V,Ord)
                   2024: {
                   2025:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                   2026:
                   2027:        dp_ord(Ord);
                   2028:        DA = map(dp_ptod,A,V); DB = ltov(map(dp_ptod,B,V));
                   2029:        if ( Mod ) {
                   2030:                DA = map(dp_mod,DA,Mod,[]); DB = map(dp_mod,DB,Mod,[]);
                   2031:                setmod(Mod);
                   2032:        }
                   2033:        N = length(B);
                   2034:        for ( Ind = [], I = N-1; I >= 0; I-- ) Ind = cons(I,Ind);
                   2035:        for ( T = DA, C = []; T != []; T = cdr(T) ) {
                   2036:                L = Mod?dp_true_nf_mod(Ind,car(T),DB,1,Mod):dp_true_nf(Ind,car(T),DB,1);
                   2037:                R = dp_dtop(L[0],V); Q = dp_dtop(car(T)*L[1]-L[0],V);
                   2038:                C = cons([R,-Q],C);
                   2039:        }
                   2040:        G = nd_gr(append(C,map(aa,B)),V,Mod,[1,Ord]|intersect=1);
                   2041:        G = map(second,G);
                   2042:        return G;
                   2043: }
                   2044:
1.1       noro     2045: /* returns GB if F notin rad(G) */
                   2046:
                   2047: def radical_membership(F,G,V) {
                   2048:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                   2049:        if ( type(IsGB=getopt(isgb)) == -1 ) IsGB = 0;
1.4       noro     2050:        if ( type(L=getopt(dg)) == -1 ) L = 0;
1.7       noro     2051:        if ( type(Sat=getopt(sat)) == -1 ) Sat = 0;
1.4       noro     2052:        dp_ord(0);
                   2053:        if ( L ) { DG = L[0]; Ind = L[1]; }
                   2054:        else {
                   2055:                DG = ltov(map(dp_ptod,G,V));
                   2056:                if ( Mod ) DG = map(dp_mod,DG,Mod,[]);
                   2057:                for ( Ind = [], I = length(G)-1; I >= 0; I-- ) Ind = cons(I,Ind);
                   2058:        }
                   2059:        DF = dp_ptod(F,V); DFI = dp_ptod(1,V);
                   2060:        if ( Mod ) {
                   2061:                DF = dp_mod(DF,Mod,[]); DFI = dp_mod(DFI,Mod,[]);
                   2062:                setmod(Mod);
                   2063:        }
                   2064:        for ( I = 0; I < 3; I++ ) {
                   2065:                DFI = Mod?dp_nf_mod(Ind,DF*DFI,DG,0,Mod):dp_nf(Ind,DF*DFI,DG,0);
                   2066:                if ( !DFI ) return 0;
                   2067:        }
1.1       noro     2068:        NV = ttttt;
                   2069:        if ( IsGB )
                   2070:                T = nd_gr(append(G,[NV*F-1]),cons(NV,V),Mod,0
                   2071:                        |gbblock=[[0,length(G)]]);
                   2072:        else
                   2073:                T = nd_gr(append(G,[NV*F-1]),cons(NV,V),Mod,0);
1.7       noro     2074:        if ( type(car(T)) == 1 ) return 0;
                   2075:        else if ( Sat ) {
                   2076:                G1 = fast_gb(T,cons(NV,V),Mod,[[0,1],[0,length(V)]]);
                   2077:                G0 = elimination(G1,V);
                   2078:                return G0;
                   2079:        } else return [T,NV];
1.1       noro     2080: }
                   2081:
1.8       noro     2082: def radical_membership_sat(F,G,V) {
                   2083:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                   2084:        if ( type(IsGB=getopt(isgb)) == -1 ) IsGB = 0;
                   2085:        if ( type(L=getopt(dg)) == -1 ) L = 0;
                   2086:        dp_ord(0);
                   2087:        if ( L ) { DG = L[0]; Ind = L[1]; }
                   2088:        else {
                   2089:                DG = ltov(map(dp_ptod,G,V));
                   2090:                if ( Mod ) DG = map(dp_mod,DG,Mod,[]);
                   2091:                for ( Ind = [], I = length(G)-1; I >= 0; I-- ) Ind = cons(I,Ind);
                   2092:        }
                   2093:        DF = dp_ptod(F,V); DFI = dp_ptod(1,V);
                   2094:        if ( Mod ) {
                   2095:                DF = dp_mod(DF,Mod,[]); DFI = dp_mod(DFI,Mod,[]);
                   2096:                setmod(Mod);
                   2097:        }
                   2098:        for ( I = 0; I < 3; I++ ) {
                   2099:                DFI = Mod?dp_nf_mod(Ind,DF*DFI,DG,0,Mod):dp_nf(Ind,DF*DFI,DG,0);
                   2100:                if ( !DFI ) return 0;
                   2101:        }
                   2102:        NV = ttttt;
                   2103:        if ( IsGB )
                   2104:                T = nd_gr(append(G,[NV*F-1]),cons(NV,V),Mod,[[0,1],[0,length(V)]]
                   2105:                        |gbblock=[[0,length(G)]]);
                   2106:        else
                   2107:                T = nd_gr(append(G,[NV*F-1]),cons(NV,V),Mod,[[0,1],[0,length(V)]]);
                   2108:        if ( type(car(T)) == 1 ) return 0;
                   2109:        G0 = elimination(T,V);
                   2110:        return G0;
                   2111: }
                   2112:
1.1       noro     2113: def modular_radical_membership(F,G,V) {
                   2114:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                   2115:        if ( Mod )
                   2116:                return radical_membership(F,G,V|mod=Mod);
                   2117:
                   2118:        F = gen_nf(F,G,V,0,0);
                   2119:        if ( !F ) return 0;
                   2120:        NV = ttttt;
                   2121:        for ( J = 0; ; J++ ) {
                   2122:                Mod = lprime(J);
                   2123:                H = map(dp_hc,map(dp_ptod,G,V));
                   2124:                for ( ; H != []; H = cdr(H) ) if ( !(car(H)%Mod) ) break;
                   2125:                if ( H != [] ) continue;
                   2126:
                   2127:                T = nd_f4(cons(NV*F-1,G),cons(NV,V),Mod,0);
                   2128:                if ( type(car(T)) == 1 ) {
                   2129:                        I = radical_membership_rep(F,G,V,-1,0,Mod);
                   2130:                        I1 = radical_membership_rep(F,G,V,I,0,0);
                   2131:                        if ( I1 > 0 ) return 0;
                   2132:                }
                   2133:                return radical_membership(F,G,V);
                   2134:        }
                   2135: }
                   2136:
                   2137: def radical_membership_rep(F,G,V,Max,Ord,Mod) {
                   2138:        Ft = F;
                   2139:        I = 1;
                   2140:        while ( Max < 0 || I <= Max ) {
                   2141:                Ft = gen_nf(Ft,G,V,Ord,Mod);
                   2142:                if ( !Ft ) return I;
                   2143:                Ft *= F;
                   2144:                I++;
                   2145:        }
                   2146:        return -1;
                   2147: }
                   2148:
                   2149: def ideal_product(A,B,V)
                   2150: {
                   2151:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                   2152:        dp_ord(0);
                   2153:        DA = map(dp_ptod,A,V);
                   2154:        DB = map(dp_ptod,B,V);
                   2155:        DegA = map(dp_td,DA);
                   2156:        DegB = map(dp_td,DB);
                   2157:        for ( PA = [], T = A, DT = DegA; T != []; T = cdr(T), DT = cdr(DT) )
                   2158:                PA = cons([car(T),car(DT)],PA);
                   2159:        PA = reverse(PA);
                   2160:        for ( PB = [], T = B, DT = DegB; T != []; T = cdr(T), DT = cdr(DT) )
                   2161:                PB = cons([car(T),car(DT)],PB);
                   2162:        PB = reverse(PB);
                   2163:        R = [];
                   2164:        for ( T = PA; T != []; T = cdr(T) )
                   2165:                for ( S = PB; S != []; S = cdr(S) )
                   2166:                        R = cons([car(T)[0]*car(S)[0],car(T)[1]+car(S)[1]],R);
1.9     ! ohara    2167:        T = qsort(R,noro_pd.comp_by_second);
1.1       noro     2168:        T = map(first,T);
                   2169:        Len = length(A)>length(B)?length(A):length(B);
                   2170:        Len *= 2;
                   2171:        L = sep_list(T,Len); B0 = L[0]; B1 = L[1];
                   2172:        R = fast_gb(B0,V,Mod,0);
                   2173:        while ( B1 != [] ) {
                   2174:                print(length(B1));
                   2175:                L = sep_list(B1,Len);
                   2176:                B0 = L[0]; B1 = L[1];
                   2177:                R = fast_gb(append(R,B0),V,Mod,0|gbblock=[[0,length(R)]],nora=1);
                   2178:        }
                   2179:        return R;
                   2180: }
                   2181:
                   2182: def saturation(GNV,F,V)
                   2183: {
                   2184:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                   2185:        G = GNV[0]; NV = GNV[1];
                   2186:        if ( Mod )
                   2187:                G1 = nd_gr(cons(NV*F-1,G),cons(NV,V),Mod,[[0,1],[0,length(V)]]);
                   2188:        else if ( Procs ) {
                   2189:                Arg0 = ["nd_gr_trace",
                   2190:                cons(NV*F-1,G),cons(NV,V),0,GBCheck,[[0,1],[0,length(V)]]];
                   2191:                Arg1 = ["nd_gr_trace",
                   2192:                cons(NV*F-1,G),cons(NV,V),1,GBCheck,[[0,1],[0,length(V)]]];
                   2193:                G1 = competitive_exec(Procs,Arg0,Arg1);
                   2194:        } else
                   2195:                G1 = nd_gr(cons(NV*F-1,G),cons(NV,V),0,[[0,1],[0,length(V)]]);
                   2196:        return elimination(G1,V);
                   2197: }
                   2198:
                   2199: def sat(G,F,V)
                   2200: {
                   2201:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                   2202:        if ( type(IsGB=getopt(isgb)) == -1 ) IsGB = 0;
                   2203:        NV = ttttt;
                   2204:        if ( Mod )
                   2205:                G1 = nd_gr(cons(NV*F-1,G),cons(NV,V),Mod,[[0,1],[0,length(V)]]);
                   2206:        else if ( Procs ) {
                   2207:                Arg0 = ["nd_gr_trace",
                   2208:                cons(NV*F-1,G),cons(NV,V),0,GBCheck,[[0,1],[0,length(V)]]];
                   2209:                Arg1 = ["nd_gr_trace",
                   2210:                cons(NV*F-1,G),cons(NV,V),1,GBCheck,[[0,1],[0,length(V)]]];
                   2211:                G1 = competitive_exec(Procs,Arg0,Arg1);
                   2212:        } else {
                   2213:                B1 = append(G,[NV*F-1]);
                   2214:                V1 = cons(NV,V);
                   2215:                Ord1 = [[0,1],[0,length(V)]];
                   2216:                if ( IsGB )
                   2217:                        G1 = nd_gr(B1,V1,0,Ord1|gbblock=[[0,length(G)]]);
                   2218:                else
                   2219:                        G1 = nd_gr(B1,V1,0,Ord1);
                   2220:        }
                   2221:        return elimination(G1,V);
                   2222: }
                   2223:
1.4       noro     2224: def isat(B,S,V)
                   2225: {
                   2226:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                   2227:        if ( type(IsGB=getopt(isgb)) == -1 ) IsGB = 0;
                   2228:        F = cdr(fctr(S));
                   2229:        R = B;
                   2230:        for ( T = F; T != []; T = cdr(T) )
                   2231:                R = sat(R,car(T)[0],V|mod=Mod,isgb=IsGB);
                   2232:        return R;
                   2233: }
                   2234:
1.1       noro     2235: def satind(G,F,V)
                   2236: {
                   2237:        if ( type(Block=getopt(gbblock)) == -1 ) Block = 0;
                   2238:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                   2239:        NV = ttttt;
                   2240:        N = length(V);
                   2241:        B = append(G,[NV*F-1]);
                   2242:        V1 = cons(NV,V);
                   2243:        Ord1 = [[0,1],[0,N]];
                   2244:        if ( Mod )
                   2245:                if ( Block )
                   2246:                        D = nd_gr(B,V1,Mod,Ord1|nora=1,gentrace=1,gbblock=Block);
                   2247:                else
                   2248:                        D = nd_gr(B,V1,Mod,Ord1|nora=1,gentrace=1);
                   2249:        else
                   2250:                if ( Block )
                   2251:                        D = nd_gr_trace(B,V1,SatHomo,GBCheck,Ord1
                   2252:                                |nora=1,gentrace=1,gbblock=Block);
                   2253:                else
                   2254:                        D = nd_gr_trace(B,V1,SatHomo,GBCheck,Ord1
                   2255:                                |nora=1,gentrace=1);
                   2256:        G1 = D[0];
                   2257:        Len = length(G1);
                   2258:        Deg = compute_deg(B,V1,NV,D);
                   2259:        D1 = 0;
                   2260:        R = [];
                   2261:        M = length(B);
                   2262:        for ( I = 0; I < Len; I++ ) {
                   2263:                if ( !member(NV,vars(G1[I])) ) {
                   2264:                        for ( J = 1; J < M; J++ )
                   2265:                                D1 = MAX(D1,Deg[I][J]);
                   2266:                        R = cons(G1[I],R);
                   2267:                }
                   2268:        }
                   2269:        return [reverse(R),D1];
                   2270: }
                   2271:
                   2272: def sat_ind(G,F,V)
                   2273: {
                   2274:        if ( type(Ord=getopt(ord)) == -1 ) Ord = 0;
                   2275:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                   2276:        NV = ttttt;
                   2277:        F = gen_nf(F,G,V,Ord,Mod);
                   2278:        for ( I = 0, GI = G; ; I++ ) {
                   2279:                G1 = colon(GI,F,V|mod=Mod,ord=Ord);
                   2280:                if ( ideal_inclusion(G1,GI,V,Ord|mod=Mod) )  {
                   2281:                        return [GI,I];
                   2282:                }
                   2283:                else GI = G1;
                   2284:        }
                   2285: }
                   2286:
                   2287: def colon(G,F,V)
                   2288: {
                   2289:        if ( type(Ord=getopt(ord)) == -1 ) Ord = 0;
                   2290:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                   2291:        if ( type(IsGB=getopt(isgb)) == -1 ) IsGB = 0;
                   2292:        F = gen_nf(F,G,V,Ord,Mod);
                   2293:        if ( !F ) return [1];
                   2294:        if ( IsGB )
                   2295:                T = ideal_intersection(G,[F],V,Ord|gbblock=[[0,length(G)]],mod=Mod);
                   2296:        else
                   2297:                T = ideal_intersection(G,[F],V,Ord|mod=Mod);
1.4       noro     2298:        Gen = Mod?map(sdivm,T,F,Mod):map(ptozp,map(sdiv,T,F));
                   2299:        return nd_gr(Gen,V,Mod,Ord);
1.1       noro     2300: }
                   2301:
                   2302: #if 1
                   2303: def ideal_colon(G,F,V)
                   2304: {
                   2305:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                   2306:        G = nd_gr(G,V,Mod,0);
                   2307:        C = [1];
                   2308:        TV = ttttt;
1.9     ! ohara    2309:        F = qsort(F,noro_pd.comp_tdeg);
1.1       noro     2310:        for ( T = F; T != []; T = cdr(T) ) {
                   2311:                S = colon(G,car(T),V|isgb=1,mod=Mod);
                   2312:                if ( type(S[0])!= 1 ) {
                   2313:                        C = nd_gr(append(vtol(ltov(C)*TV),vtol(ltov(S)*(1-TV))),
                   2314:                                cons(TV,V),Mod,[[0,1],[Ord,length(V)]]|gbblock=[[0,length(C)]]);
                   2315:                        C = elimination(C,V);
                   2316:                }
                   2317:        }
                   2318:        return C;
                   2319: }
                   2320: #else
                   2321: def ideal_colon(G,F,V)
                   2322: {
                   2323:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                   2324:        G = nd_gr(G,V,Mod,0);
                   2325:        for ( T = F, L = []; T != []; T = cdr(T) ) {
                   2326:                C = colon(G,car(T),V|isgb=1,mod=Mod);
                   2327:                if ( type(C[0]) != 1 ) L = cons(C,L);
                   2328:        }
                   2329:        L = reverse(L);
                   2330:        return ideal_list_intersection(L,V,0|mod=Mod);
                   2331: }
                   2332:
                   2333: #endif
                   2334:
                   2335: def member(A,L)
                   2336: {
                   2337:        for ( ; L != []; L = cdr(L) )
                   2338:                if ( car(L) == A ) return 1;
                   2339:        return 0;
                   2340: }
                   2341:
                   2342: def mingen(B,V) {
                   2343:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                   2344:        Data = nd_gr(B,V,Mod,O|gentrace=1,gensyz=1);
1.4       noro     2345:     G = Data[0]; STrace = Data[6];
1.1       noro     2346:        N = length(G);
1.4       noro     2347:        S = compute_gbsyz(N,V,STrace,Mod);
                   2348:        for ( T = S, R = []; T != []; T = cdr(T) ) {
                   2349:                for ( A = car(T); A1 = dp_rest(A); A = A1);
                   2350:                if ( type(dp_hc(A)) ==1 ) R = cons(dp_etov(A)[0],R);
                   2351:        }
                   2352:        for ( I = 0, U = []; I < N; I++ ) if ( !member(I,R) ) U = cons(G[I],U);
1.1       noro     2353:        return U;
                   2354: }
                   2355:
1.4       noro     2356: def compute_gbsyz(N,V,Trace,Mod)
1.1       noro     2357: {
                   2358:        P = vector(N);
1.4       noro     2359:        for ( I = 0; I < N; I++ ) P[I] = dp_ptod(x^I,[x]);
                   2360:        for ( U = [], T = Trace; T != []; T = cdr(T) ) {
1.1       noro     2361:                Ti = car(T);
                   2362:                if ( Ti[0] != -1 ) error("Input is not a GB");
1.4       noro     2363:                R = recompute_trace(Ti[1],P,V,Mod);
                   2364:                U = cons(R,U);
1.1       noro     2365:        }
                   2366:        return reverse(U);
                   2367: }
                   2368:
1.4       noro     2369: def recompute_trace(Ti,P,V,Mod)
1.1       noro     2370: {
                   2371:   for ( Num = 0, Den = 1; Ti != []; Ti = cdr(Ti) ) {
1.4       noro     2372:     Sj = car(Ti); Dj = Sj[0]; Ij =Sj[1]; Mj = dp_dtop(Sj[2],V); Cj = Sj[3];
1.1       noro     2373:     /* Num/Den <- (Dj*Num+Den*Mj*P[Ij])/(Den*Cj) */
1.4       noro     2374:     if ( Dj ) Num = (Dj*Num+Den*Mj*P[Ij]);
1.1       noro     2375:     Den *= Cj;
                   2376:   }
1.4       noro     2377:   return Num;
1.1       noro     2378: }
                   2379:
                   2380: def ideal_sat(G,F,V)
                   2381: {
                   2382:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                   2383:        G = nd_gr(G,V,Mod,0);
                   2384:        for ( T = F, L = []; T != []; T = cdr(T) )
                   2385:                L = cons(sat(G,car(T),V|mod=Mod),L);
                   2386:        L = reverse(L);
                   2387:        return ideal_list_intersection(L,V,0|mod=Mod);
                   2388: }
                   2389:
                   2390: def ideal_inclusion(F,G,V,O)
                   2391: {
                   2392:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                   2393:        for ( T = F; T != []; T = cdr(T) )
                   2394:                if ( gen_nf(car(T),G,V,O,Mod) ) return 0;
                   2395:        return 1;
                   2396: }
                   2397:
                   2398: /* remove redundant components */
                   2399:
                   2400: def qd_simp_comp(QP,V)
                   2401: {
                   2402:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                   2403:        R = ltov(QP);
                   2404:        N = length(R);
                   2405:        for ( I = 0; I < N; I++ ) {
                   2406:                if ( R[I] ) {
                   2407:                        QI = R[I][0]; PI = R[I][1];
                   2408:                        for ( J = I+1; J < N; J++ )
                   2409:                                if ( R[J] && gen_gb_comp(PI,R[J][1],Mod) ) {
                   2410:                                        QI = ideal_intersection(QI,R[J][0],V,0|mod=Mod);
                   2411:                                        R[J] = 0;
                   2412:                                }
                   2413:                        R[I] = [QI,PI];
                   2414:                }
                   2415:        }
                   2416:        for ( I = N-1, S = []; I >= 0; I-- )
                   2417:                if ( R[I] ) S = cons(R[I],S);
                   2418:        return S;
                   2419: }
                   2420:
                   2421: def qd_remove_redundant_comp(G,Iso,Emb,V,Ord)
                   2422: {
                   2423:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                   2424:        IsoInt = ideal_list_intersection(map(first,Iso),V,Ord|mod=Mod);
                   2425:        Emb = qd_simp_comp(Emb,V|mod=Mod);
                   2426:        Emb = reverse(qsort(Emb));
                   2427:        A = ltov(Emb); N = length(A);
                   2428:        Pre = IsoInt; Post = vector(N+1);
                   2429:        for ( Post[N] = IsoInt, I = N-1; I >= 1; I-- )
                   2430:                Post[I] = ideal_intersection(Post[I+1],A[I][0],V,Ord|mod=Mod);
                   2431:        for ( I = 0; I < N; I++ ) {
                   2432:                print(".",2);
                   2433:                Int = ideal_intersection(Pre,Post[I+1],V,Ord|mod=Mod);
                   2434:                if ( gen_gb_comp(Int,G,Mod) ) A[I] = 0;
                   2435:                else
                   2436:                        Pre = ideal_intersection(Pre,A[I][0],V,Ord|mod=Mod);
                   2437:        }
                   2438:        for ( T = [], I = 0; I < N; I++ )
                   2439:                if ( A[I] ) T = cons(A[I],T);
                   2440:        return reverse(T);
                   2441: }
                   2442:
                   2443: def pd_simp_comp(PL,V)
                   2444: {
                   2445:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                   2446:        if ( type(First=getopt(first)) == -1 ) First = 0;
                   2447:        A = ltov(PL); N = length(A);
                   2448:        if ( N == 1 )  return PL;
                   2449:        for ( I = 0; I < N; I++ ) {
                   2450:                if ( !A[I] ) continue;
                   2451:                AI = First?A[I][0]:A[I];
                   2452:                for ( J = 0; J < N; J++ ) {
                   2453:                        if ( J == I || !A[J] ) continue;
                   2454:                        AJ = First?A[J][0]:A[J];
                   2455:                        if ( gen_gb_comp(AI,AJ,Mod) || ideal_inclusion(AI,AJ,V,Ord|mod=Mod) )
                   2456:                                A[J] = 0;
                   2457:                }
                   2458:        }
                   2459:        for ( I = 0, T = []; I < N; I++ ) if ( A[I] ) T = cons(A[I],T);
                   2460:        return reverse(T);
                   2461: }
                   2462:
                   2463: def pd_remove_redundant_comp(G,P,V,Ord)
                   2464: {
                   2465:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                   2466:        if ( type(First=getopt(first)) == -1 ) First = 0;
                   2467:        if ( length(P) == 1 )  return P;
                   2468:
                   2469:        A = ltov(P); N = length(A);
                   2470:        for ( I = 0; I < N; I++ ) {
                   2471:                if ( !A[I] ) continue;
                   2472:                for ( J = I+1; J < N; J++ )
                   2473:                        if ( A[J] &&
                   2474:                                gen_gb_comp(First?A[I][0]:A[I],First?A[J][0]:A[J],Mod) ) A[J] = 0;
                   2475:        }
                   2476:        for ( I = 0, T = []; I < N; I++ ) if ( A[I] ) T = cons(A[I],T);
                   2477:        A = ltov(reverse(T)); N = length(A);
                   2478:        Pre = [1]; Post = vector(N+1);
                   2479:        for ( Post[N] = [1], I = N-1; I >= 1; I-- )
                   2480:                Post[I] = ideal_intersection(Post[I+1],First?A[I][0]:A[I],V,Ord|mod=Mod);
                   2481:        for ( I = 0; I < N; I++ ) {
                   2482:                Int = ideal_intersection(Pre,Post[I+1],V,Ord|mod=Mod);
                   2483:                if ( gen_gb_comp(Int,G,Mod) ) A[I] = 0;
                   2484:                else
                   2485:                        Pre = ideal_intersection(Pre,First?A[I][0]:A[I],V,Ord|mod=Mod);
                   2486:        }
                   2487:        for ( T = [], I = 0; I < N; I++ ) if ( A[I] ) T = cons(A[I],T);
                   2488:        return reverse(T);
                   2489: }
                   2490:
1.7       noro     2491: def remove_identical_comp(L)
                   2492: {
                   2493:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                   2494:        if ( length(L) == 1 )  return L;
                   2495:
                   2496:        A = ltov(L); N = length(A);
                   2497:        for ( I = 0; I < N; I++ ) {
                   2498:                if ( !A[I] ) continue;
                   2499:                for ( J = I+1; J < N; J++ )
                   2500:                        if ( A[J] &&
                   2501:                                gen_gb_comp(A[I],A[J],Mod) ) A[J] = 0;
                   2502:        }
                   2503:        for ( I = 0, T = []; I < N; I++ ) if ( A[I] ) T = cons(A[I],T);
                   2504:        return reverse(T);
                   2505: }
                   2506:
1.1       noro     2507: /* polynomial operations */
                   2508:
                   2509: def ppart(F,V,Mod)
                   2510: {
                   2511:        if ( !Mod )
                   2512:                G = nd_gr([F],[V],0,0);
                   2513:        else
                   2514:                G = dp_gr_mod_main([F],[V],0,Mod,0);
                   2515:        return G[0];
                   2516: }
                   2517:
                   2518:
                   2519: def sq(F,Mod)
                   2520: {
                   2521:        if ( !F ) return 0;
                   2522:        A = cdr(gen_fctr(F,Mod));
                   2523:        for ( R = 1; A != []; A = cdr(A) )
                   2524:                R *= car(car(A));
                   2525:        return R;
                   2526: }
                   2527:
                   2528: def lcfactor(G,V,O,Mod)
                   2529: {
                   2530:        O0 = dp_ord(); dp_ord(O);
                   2531:        C = [];
                   2532:        for ( T = G; T != []; T = cdr(T) ) {
                   2533:                C1 = dp_hc(dp_ptod(car(T),V));
                   2534:                S = gen_fctr(C1,Mod);
                   2535:                for ( S = cdr(S); S != []; S = cdr(S) )
                   2536:                        if ( !member(S[0][0],C) ) C = cons(S[0][0],C);
                   2537:        }
                   2538:        dp_ord(O0);
                   2539:        return C;
                   2540: }
                   2541:
                   2542: def gen_fctr(F,Mod)
                   2543: {
                   2544:        if ( Mod ) return modfctr(F,Mod);
                   2545:        else return fctr(F);
                   2546: }
                   2547:
                   2548: def gen_mptop(F)
                   2549: {
                   2550:        if ( !F ) return F;
                   2551:        else if ( type(F)==1 )
                   2552:                if ( ntype(F)==5 ) return mptop(F);
                   2553:                else return F;
                   2554:        else {
                   2555:                V = var(F);
                   2556:                D = deg(F,V);
                   2557:                for ( R = 0, I = 0; I <= D; I++ )
                   2558:                        if ( C = coef(F,I,V) ) R += gen_mptop(C)*V^I;
                   2559:                return R;
                   2560:        }
                   2561: }
                   2562:
                   2563: def gen_nf(F,G,V,Ord,Mod)
                   2564: {
                   2565:        if ( !Mod ) return p_nf(F,G,V,Ord);
                   2566:
                   2567:        setmod(Mod);
                   2568:        dp_ord(Ord); DF = dp_mod(dp_ptod(F,V),Mod,[]);
                   2569:        N = length(G); DG = newvect(N);
                   2570:        for ( I = N-1, IL = []; I >= 0; I-- ) {
                   2571:                DG[I] = dp_mod(dp_ptod(G[I],V),Mod,[]);
                   2572:                IL = cons(I,IL);
                   2573:        }
                   2574:        T = dp_nf_mod(IL,DF,DG,1,Mod);
                   2575:        for ( R = 0; T; T = dp_rest(T) )
                   2576:                R += gen_mptop(dp_hc(T))*dp_dtop(dp_ht(T),V);
                   2577:        return R;
                   2578: }
                   2579:
                   2580: /* Ti = [D,I,M,C] */
                   2581:
                   2582: def compute_deg0(Ti,P,V,TV)
                   2583: {
                   2584:        N = length(P[0]);
                   2585:        Num = vector(N);
                   2586:        for ( I = 0; I < N; I++ ) Num[I] = -1;
                   2587:        for ( ; Ti != []; Ti = cdr(Ti) ) {
                   2588:                Sj = car(Ti);
                   2589:                Dj = Sj[0];
                   2590:                Ij =Sj[1];
                   2591:                Mj = deg(type(Sj[2])==9?dp_dtop(Sj[2],V):Sj[2],TV);
                   2592:                Pj = P[Ij];
                   2593:                if ( Dj )
                   2594:                        for ( I = 0; I < N; I++ )
                   2595:                                if ( Pj[I] >= 0 ) {
                   2596:                                        T = Mj+Pj[I];
                   2597:                                        Num[I] = MAX(Num[I],T);
                   2598:                                }
                   2599:        }
                   2600:        return Num;
                   2601: }
                   2602:
                   2603: def compute_deg(B,V,TV,Data)
                   2604: {
                   2605:        GB = Data[0];
                   2606:        Homo = Data[1];
                   2607:        Trace = Data[2];
                   2608:        IntRed = Data[3];
                   2609:        Ind = Data[4];
                   2610:        DB = map(dp_ptod,B,V);
                   2611:        if ( Homo ) {
                   2612:                DB = map(dp_homo,DB);
                   2613:                V0 = append(V,[hhh]);
                   2614:        } else
                   2615:                V0 = V;
                   2616:        Perm = Trace[0]; Trace = cdr(Trace);
                   2617:        for ( I = length(Perm)-1, T = Trace; T != []; T = cdr(T) )
                   2618:                if ( (J=car(T)[0]) > I ) I = J;
                   2619:        N = I+1;
                   2620:        N0 = length(B);
                   2621:        P = vector(N);
                   2622:        for ( T = Perm, I = 0; T != []; T = cdr(T), I++ ) {
                   2623:                Pi = car(T);
                   2624:                C = vector(N0);
                   2625:                for ( J = 0; J < N0; J++ ) C[J] = -1;
                   2626:                C[Pi[1]] = 0;
                   2627:                P[Pi[0]] = C;
                   2628:        }
                   2629:        for ( T = Trace; T != []; T = cdr(T) ) {
                   2630:                Ti = car(T); P[Ti[0]] = compute_deg0(Ti[1],P,V0,TV);
                   2631:        }
                   2632:        M = length(Ind);
                   2633:        for ( T = IntRed; T != []; T = cdr(T) ) {
                   2634:                Ti = car(T); P[Ti[0]] = compute_deg0(Ti[1],P,V,TV);
                   2635:        }
                   2636:        R = [];
                   2637:        for ( J = 0; J < M; J++ ) {
                   2638:                U = P[Ind[J]];
                   2639:                R = cons(U,R);
                   2640:        }
                   2641:        return reverse(R);
                   2642: }
                   2643:
                   2644: /* set theoretic functions */
                   2645:
                   2646: def member(A,S)
                   2647: {
                   2648:        for ( ; S != []; S = cdr(S) )
                   2649:                if ( car(S) == A ) return 1;
                   2650:        return 0;
                   2651: }
                   2652:
                   2653: def elimination(G,V) {
                   2654:        for ( R = [], T = G; T != []; T = cdr(T) )
                   2655:                if ( setminus(vars(car(T)),V) == [] ) R =cons(car(T),R);
                   2656:        return R;
                   2657: }
                   2658:
                   2659: def setintersection(A,B)
                   2660: {
                   2661:        for ( L = []; A != []; A = cdr(A) )
                   2662:                if ( member(car(A),B) )
                   2663:                        L = cons(car(A),L);
                   2664:        return L;
                   2665: }
                   2666:
                   2667: def setminus(A,B) {
                   2668:        for ( T = reverse(A), R = []; T != []; T = cdr(T) ) {
                   2669:                for ( S = B, M = car(T); S != []; S = cdr(S) )
                   2670:                        if ( car(S) == M ) break;
                   2671:                if ( S == [] ) R = cons(M,R);
                   2672:        }
                   2673:        return R;
                   2674: }
                   2675:
                   2676: def sep_list(L,N)
                   2677: {
                   2678:        if ( length(L) <= N ) return [L,[]];
                   2679:        R = [];
                   2680:        for ( T = L, I = 0; I < N; I++, T = cdr(T) )
                   2681:                R = cons(car(T),R);
                   2682:        return [reverse(R),T];
                   2683: }
                   2684:
                   2685: def first(L)
                   2686: {
                   2687:        return L[0];
                   2688: }
                   2689:
                   2690: def second(L)
                   2691: {
                   2692:        return L[1];
                   2693: }
                   2694:
                   2695: def third(L)
                   2696: {
                   2697:        return L[2];
                   2698: }
                   2699:
                   2700: def first_second(L)
                   2701: {
                   2702:        return [L[0],L[1]];
                   2703: }
                   2704:
                   2705: def comp_tord(A,B)
                   2706: {
                   2707:        DA = dp_ht(A);
                   2708:        DB = dp_ht(B);
                   2709:        if ( DA > DB ) return 1;
                   2710:        else if ( DA < DB ) return -1;
                   2711:        else return 0;
                   2712: }
                   2713:
                   2714: def comp_tdeg(A,B)
                   2715: {
                   2716:        DA = tdeg(A);
                   2717:        DB = tdeg(B);
                   2718:        if ( DA > DB ) return 1;
                   2719:        else if ( DA < DB ) return -1;
                   2720:        else return 0;
                   2721: }
                   2722:
                   2723: def comp_tdeg_first(A,B)
                   2724: {
                   2725:        DA = tdeg(A[0]);
                   2726:        DB = tdeg(B[0]);
                   2727:        if ( DA > DB ) return 1;
                   2728:        else if ( DA < DB ) return -1;
                   2729:        else return 0;
                   2730: }
                   2731:
                   2732: def comp_third_tdeg(A,B)
                   2733: {
                   2734:        if ( A[2] > B[2] ) return 1;
                   2735:        if ( A[2] < B[2] ) return -1;
                   2736:        DA = tdeg(A[0]);
                   2737:        DB = tdeg(B[0]);
                   2738:        if ( DA > DB ) return 1;
                   2739:        else if ( DA < DB ) return -1;
                   2740:        else return 0;
                   2741: }
                   2742:
                   2743: def tdeg(P)
                   2744: {
                   2745:        dp_ord(0);
                   2746:        return dp_td(dp_ptod(P,vars(P)));
                   2747: }
                   2748:
                   2749: def comp_by_ord(A,B)
                   2750: {
                   2751:        if ( dp_ht(A) > dp_ht(B) ) return 1;
                   2752:        else if ( dp_ht(A) < dp_ht(B) ) return -1;
                   2753:        else return 0;
                   2754: }
                   2755:
                   2756: def comp_by_second(A,B)
                   2757: {
                   2758:        if ( A[1] > B[1] ) return 1;
                   2759:        else if ( A[1] < B[1] ) return -1;
                   2760:        else return 0;
                   2761: }
                   2762:
                   2763: def get_lc(F)
                   2764: {
                   2765:        if ( type(F)==1 ) return F;
                   2766:        V = var(F);
                   2767:        D = deg(F,V);
                   2768:        return get_lc(coef(F,D,V));
                   2769: }
                   2770:
                   2771: def tomonic(F,Mod)
                   2772: {
                   2773:        C = get_lc(F);
                   2774:        IC = inv(C,Mod);
                   2775:        return (IC*F)%Mod;
                   2776: }
                   2777:
                   2778: def gen_gb_comp(A,B,Mod)
                   2779: {
                   2780:        if ( !Mod ) return gb_comp(A,B);
                   2781:        LA = length(A); LB = length(B);
                   2782:        if ( LA != LB ) return 0;
                   2783:        A = map(tomonic,A,Mod);
                   2784:        B = map(tomonic,B,Mod);
                   2785:        A = qsort(A); B = qsort(B);
                   2786:        if ( A != B ) return 0;
                   2787:        return 1;
                   2788: }
                   2789:
                   2790: def prod(L)
                   2791: {
                   2792:        for ( R = 1; L != []; L = cdr(L) )
                   2793:                R *= car(L);
                   2794:        return R;
                   2795: }
                   2796:
                   2797: def monodec0(B,V)
                   2798: {
                   2799:        M = monodec(B,V);
                   2800:        return map(vars,M);
                   2801: }
                   2802:
                   2803: def monodec(B,V)
                   2804: {
                   2805:        B = map(sq,B,0);
                   2806:        G = nd_gr_postproc(B,V,0,0,0);
                   2807:        V = vars(G);
                   2808:        N = length(V);
                   2809:        if ( N == 0 ) return G == [] ? [[]] : [];
                   2810:        if ( N == 1 ) return G;
                   2811:        if ( N < 20 ) {
                   2812:                T = dp_mono_raddec(G,V);
                   2813:                return map(prod,T);
                   2814:        }
                   2815:        X = car(V); W = cdr(V);
                   2816:        D0 = monodec(map(subst,B,X,0),W);
                   2817:        T0 = map(dp_ptod,D0,W);
                   2818:        D1 = monodec(map(subst,B,X,1),W);
                   2819:        T1 = map(dp_ptod,D1,W);
1.4       noro     2820: #if 0
1.1       noro     2821:        for ( T = T1; T != []; T = cdr(T) ) {
                   2822:                for ( M = car(T), S1 = [], S = T0; S != []; S = cdr(S) )
                   2823:                        if ( !dp_redble(car(S),M) ) S1= cons(car(S),S1);
                   2824:                T0 = S1;
                   2825:        }
1.4       noro     2826: #else
                   2827:        T0 = dp_mono_reduce(T0,T1);
                   2828: #endif
1.1       noro     2829:        D0 = map(dp_dtop,T0,W);
                   2830:        D0 = vtol(X*ltov(D0));
                   2831:        return append(D0,D1);
                   2832: }
                   2833:
                   2834: def separator(P,V)
                   2835: {
                   2836:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
                   2837:        N = length(P);
1.4       noro     2838:        dp_ord(0);
                   2839:        DP = vector(N);
1.9     ! ohara    2840:        for ( I = 0; I < N; I++ ) DP[I] = qsort(ltov(map(dp_ptod,P[I][0],V)),noro_pd.comp_tord);
1.4       noro     2841:        if ( Mod )
                   2842:                for ( I = 0; I < N; I++ ) DP[I] = map(dp_mod,DP[I],Mod,[]);
                   2843:        Ind = vector(N);
                   2844:        for ( I = 0; I < N; I++ ) {
                   2845:                for ( K = [], J = length(DP[I])-1; J >= 0; J-- ) K = cons(J,K);
                   2846:                Ind[I] = K;
                   2847:        }
                   2848:        S = vector(N);
                   2849:        for ( I = 0; I < N; I++ ) S[I] = 1;
1.1       noro     2850:        for ( I = 0; I < N; I++ ) {
1.4       noro     2851:                print(".",2);
1.1       noro     2852:                for ( J = 0; J < N; J++ ) {
                   2853:                        if ( J == I ) continue;
1.4       noro     2854:                        T = DP[I]; L = length(T);
                   2855:                        if ( Mod ) {
                   2856:                                for ( K = 0; K < L; K++ )
                   2857:                                        if ( dp_nf_mod(Ind[J],T[K],DP[J],0,Mod) ) break;
                   2858:                        } else {
                   2859:                                for ( K = 0; K < L; K++ )
                   2860:                                        if ( dp_nf(Ind[J],T[K],DP[J],0) ) break;
                   2861:                        }
                   2862:                        S[J] = lcm(S[J],dp_dtop(T[K],V));
1.1       noro     2863:                }
                   2864:        }
1.4       noro     2865:        print("");
1.1       noro     2866:        return S;
                   2867: }
                   2868:
                   2869: def prepost(PL,V)
1.4       noro     2870: {
                   2871:        if ( type(Mod=getopt(mod)) == -1 ) Mod = 0;
1.1       noro     2872:        A = ltov(PL); N = length(A);
                   2873:        Pre = vector(N);
                   2874:        Post = vector(N);
                   2875:        R = vector(N);
                   2876:        Pre[0] = [1];
                   2877:        print("pre ",2);
                   2878:        for ( I = 1; I < N; I++, print(".",2) )
1.4       noro     2879:                Pre[I] = ideal_intersection_m(Pre[I-1],A[I-1],V,0|mod=Mod);
1.1       noro     2880:        print("done");
                   2881:        print("post ",2);
                   2882:        Post[N-1] = [1];
                   2883:        for ( I = N-2; I >= 0; I--, print(".",2) )
1.4       noro     2884:                Post[I] = ideal_intersection_m(Post[I+1],A[I+1],V,0|mod=Mod);
1.1       noro     2885:        print("done");
                   2886:        print("int ",2);
                   2887:        for ( I = 0; I < N; I++, print(".",2) )
1.4       noro     2888:                R[I] = ideal_intersection_m(Pre[I],Post[I],V,0|mod=Mod);
1.1       noro     2889:        print("done");
                   2890:        return R;
                   2891: }
                   2892:
                   2893: /* XXX */
                   2894:
                   2895: def call_func(Arg)
                   2896: {
                   2897:        F = car(Arg);
                   2898:        return call(strtov(F),cdr(Arg));
                   2899: }
                   2900:
1.8       noro     2901: def call_func_serial(Arg,Serial)
                   2902: {
                   2903:        F = car(Arg);
                   2904:        return [call(strtov(F),cdr(Arg)),Serial];
                   2905: }
                   2906:
1.1       noro     2907: def competitive_exec(P,Arg0,Arg1)
                   2908: {
                   2909:        P0 = P[0]; P1 = P[1];
                   2910:        ox_cmo_rpc(P0,"noro_pd.call_func",Arg0|sync=1);
                   2911:        ox_cmo_rpc(P1,"noro_pd.call_func",Arg1|sync=1);
                   2912:        F = ox_select(P);
                   2913:        R = ox_get(F[0]);
                   2914:        if ( length(F) == 2 ) {
                   2915:                ox_get(F[1]);
                   2916:        } else {
                   2917:                U = setminus(P,F);
                   2918:                ox_reset(U[0]);
                   2919:        }
                   2920:        return R;
                   2921: }
                   2922:
                   2923:
                   2924: def nd_gr_rat(B,V,PV,Ord1,Ord)
                   2925: {
                   2926:        G = nd_gr(B,append(V,PV),0,Ord1);
                   2927:        G1 = nd_gr_postproc(G,V,0,Ord,0);
                   2928:        return G1;
                   2929: }
                   2930:
                   2931: /* Task[i] = [fname,[arg0,...,argn]] */
                   2932:
                   2933: def para_exec(Proc,Task) {
                   2934:        Free = Proc;
                   2935:        N = length(Task);
                   2936:        R = [];
1.8       noro     2937:        print([N],2); print("->",2);
                   2938:        Serial = 0;
1.1       noro     2939:        while ( N ) {
                   2940:                while ( Task != [] && Free != [] ) {
                   2941:                        T = car(Task); Task = cdr(Task);
1.8       noro     2942:                        ox_rpc(car(Free),"noro_pd.call_func_serial",T,Serial++);
1.1       noro     2943:                        ox_push_cmd(car(Free),258); Free = cdr(Free);
                   2944:                }
                   2945:                Finish0 = Finish = ox_select(Proc);
                   2946:                for ( ; Finish != []; Finish = cdr(Finish) ) {
                   2947:                        print(".",2);
                   2948:                        L = ox_get(car(Finish));
                   2949:                        R = cons(L,R);
                   2950:                        N--;
                   2951:                }
1.8       noro     2952:                print([N],2);
1.1       noro     2953:                Free = append(Free,Finish0);
                   2954:        }
                   2955:        print("");
1.9     ! ohara    2956:        R = qsort(R,noro_pd.comp_by_second);
1.8       noro     2957:        R = map(first,R);
                   2958:        return R;
1.1       noro     2959: }
1.4       noro     2960:
                   2961: def redbase(B,V,Mod,Ord)
                   2962: {
                   2963:        M = nd_gr_postproc(B,V,Mod,Ord,0);
                   2964:        dp_ord(Ord);
                   2965:        DM = ltov(map(dp_ptod,M,V));
                   2966:        if ( Mod ) DM = map(dp_mod,DM,Mod,[]);
                   2967:        N = length(DM);
                   2968:        for ( Ind = [], I = N-1; I >= 0; I-- ) Ind = cons(I,Ind);
                   2969:        for ( T = B, R = vtol(DM); T != []; T = cdr(T) ) {
                   2970:                D = dp_ptod(car(T),V);
                   2971:                if ( Mod ) D = dp_mod(D,Mod,[]);
                   2972:                D = Mod?dp_nf_mod(Ind,D,DM,1,Mod):dp_nf(Ind,D,DM,1);
                   2973:                if ( D ) R = cons(D,R);
                   2974:        }
1.9     ! ohara    2975:        D = qsort(R,noro_pd.comp_tord);
1.4       noro     2976:        return map(dp_dtop,D,V);
                   2977: }
                   2978:
                   2979: def witness(A,B,V)
                   2980: {
                   2981:        G = nd_gr(B,V,0,Mod);
                   2982:        L = length(A);
                   2983:        QL = []; PL = [];
                   2984:        for ( I = L-1; I >= 0; I-- ) {
                   2985:                QL = append(map(first,A[I]),QL);
                   2986:                PL = append(map(second,A[I]),PL);
                   2987:        }
                   2988:        N = length(QL);
                   2989:        Qhat = prepost(QL,V);
                   2990:        for ( I = 0, W = []; I < N; I++ ) {
                   2991:                for ( T = Qhat[I]; T != []; T = cdr(T) )
                   2992:                        if ( gen_nf(car(T),QL[I],V,0,Mod) ) break;
                   2993:                Ai = car(T);
                   2994:                Ji = colon(G,Ai,V|isgb=1,mod=Mod);
                   2995:                Ji = nd_gr(Ji,V,Mod,0);
                   2996:                if ( gen_gb_comp(Ji,PL[I],Mod) ) Bi = 1;
                   2997:                else {
                   2998:                        Ki = ideal_colon(Ji,PL[I],V|mod=Mod);
                   2999:                        for ( T = Ki; T != []; T = cdr(T) )
                   3000:                                if ( gen_nf(car(T),Ji,V,0,Mod) ) break;
                   3001:                        Bi = car(T);
                   3002:                }
                   3003:                W = cons(Ai*Bi,W);
                   3004:                Li = colon(G,W[0],V|isgb=1,mod=Mod);
                   3005:                Li = nd_gr(Li,V,Mod,0);
                   3006:                if ( !gen_gb_comp(Li,PL[I],Mod) )
                   3007:                        error("afo");
                   3008:        }
                   3009:        return reverse(W);
                   3010: }
1.1       noro     3011: endmodule$
                   3012: end$

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