Return to noro_grcrt.rr CVS log

Up to [local] / OpenXM / src / asir-contrib / packages / src

Fixed a bug in noro_grcrt.f4_chr() when a sequential execution.
Added description for inttorat() in the users manual.

module noro_grcrt$

localf f4_chr, gr_chr_d, f4_chr_d, store_history, read_history, store_bv,
store_bvn, store_bvn3, nd_f4_p2, nd_gr_recompute_trace_p,
nd_gr_gentrace_p, comp_by_ht, intdpltoratdpl2, intdptoratdp,
dp_mulmod, dp_chrem2, monic_gb, dp_monic_mod,
calcb, sp_sqrt, init_pprocs, nd_gbcheck, gbcheck_p, elimination$
localf iso_eq_mod, iso_eq_gentrace, iso_eq_mod, elim_top,
iso_eq_d2, iso_c1eq_mod, iso_c1eq_d2, iso_eq_gentrace2,
iso_eq_mod2, iso_eq_d2new, iso_sat_gentrace, iso_sat_mod, iso_sat_d2$

static GB_History,GB_B,GB_V,GB_N,GB_H$
static GB_N1,GB_N2,GB_N3$
static GB_NZ$

def f4_chr(B,V,O)
{
	dp_ord(O);
	Proc = getopt(proc);
	NZ = getopt(nz);
	Prev = getopt(prev);
	Homo = getopt(homo);
	Elim = getopt(elim);
	Weight = getopt(weight);
	if ( type(Prev) == -1 ) Prev = 0;
	if ( type(Homo) == -1 ) Homo = 0;
	if ( type(Elim) == -1 ) Elim = -1;
	if ( type(Weight) == -1 ) Weight = 0;
	OldWeight = dp_set_weight();
	dp_set_weight(Weight);
	if ( type(NZ) == -1 )
	  NZ = nd_f4(B,V,lprime(0),O|gentrace=1);
	if ( type(Proc) != -1 ) {
	 	G = f4_chr_d(B,V,O,Proc,NZ,Prev,Homo,Elim,Weight);
	    dp_set_weight(OldWeight);
	    return G;
	}
	B = map(ptozp,B);
	Remain = 1; /* XXX */
	for ( I = 0, N = 0, Mod = 1; Remain; I++ ) {
		P = lprime(I);
		GM = nd_f4(B,V,P,O|dp=1,trace=NZ);
		if ( !GM ) continue;
		if ( Elim >= 0 ) GM = elimination(GM,Elim);
		if ( !N ) {
			Remain = N = length(GM);
			Stat = vector(N);
			G = vector(N);
		}
		L = monic_gb(GM,V,O,P); GM = L[0];
T0 = time();
		Fail = dp_chrem2(G,Mod,GM,P,Stat);
		Remain += Fail;
T1 = time(); CRTime += (T1[0]-T0[0])+(T1[1]-T0[1]);
		Mod *= P;
		if ( !(I%3) ) {
T0 = time();
			New = intdpltoratdpl2(G,Mod,Stat);
T1 = time(); IRTime += (T1[0]-T0[0])+(T1[1]-T0[1]);
			Remain -= New;
		}
	}
	print(["CRT",CRTime,"IR",IRTime,"#P",I]);
	G = vtol(map(dp_dtop,G,V));
	dp_set_weight(OldWeight);
	return G;
}

/* Prev = [G,Stat,I,Mod] */

def f4_chr_d(B,V,O,Proc,NZ,Prev,Homo,Elim,Weight)
{
	map(ox_reset,Proc);
	B = map(ptozp,B);
	NProc = length(Proc);
	CRTime = 0; IRTime = 0;
	/* gentrace */
	map(ox_rpc,Proc,"dp_set_weight",Weight);
	map(ox_pop_local,Proc);
	map(ox_rpc,Proc,"noro_grcrt.store_bvn",B,V,NZ,Homo);
	map(ox_pop_local,Proc);
	if ( Prev ) {
		G = Prev[0];
		N = length(N);
		Stat = Prev[1];
		for ( J = 0, Remain = 0; J < N; J++ )
			if ( Stat[J] != 2 ) Remain++;
		I = Prev[2];
		Mod = Prev[3];
	} else {
		I = 0;
		N = 0;
		Remain = 1; /* dummy */
		Mod = 1;
	}
	for ( T = Proc; T != []; T = cdr(T), I++ )
		ox_rpc(car(T),"noro_grcrt.nd_f4_p2",lprime(I),O);
	while ( Remain ) {
		for ( T = Proc; T != []; T = cdr(T), I++ ) {
			print(["from",car(T)],2);
			L = ox_pop_local(car(T)); GM = L[0]; P = L[1];
			if ( Elim >= 0 ) GM = elimination(GM,Elim);
			print(" done");
			ox_rpc(car(T),"noro_grcrt.nd_f4_p2",lprime(I),O);
			if ( GM ) {
				L = monic_gb(GM,V,O,P); GM = L[0];
				if ( !N ) {
					Remain = N = length(GM);
					Stat = vector(N);
					G = vector(N);
				}
T0 = time();
				Fail = dp_chrem2(G,Mod,GM,P,Stat);
				Remain += Fail;
T1 = time(); CRTime += (T1[0]-T0[0])+(T1[1]-T0[1]);
				Mod *= P;
			}
		}
T0 = time();
		New = intdpltoratdpl2(G,Mod,Stat);
T1 = time(); IRTime += (T1[0]-T0[0])+(T1[1]-T0[1]);
		Remain -= New;
		print((N-Remain)/N*100.0,0); print("% done");
	}
	map(ox_reset,Proc);
	print(["Template",TTime,"CRT",CRTime,"IR",IRTime,"#P",I]);
	return vtol(map(dp_dtop,G,V));
}

def store_history(D)
{
	GB_History=D;
	return 1;
}

def read_history(Dname)
{
	GB_History=bload(Dname);
	return 1;
}


def store_bvn(B,V,N,H)
{
	GB_B=B;
	GB_V=V;
	if ( type(N) == 7 )
		GB_N = bload(N);
	else
		GB_N=N;
	GB_H=H;
}

def store_bvn3(B,V,N1,N2,N3)
{
	GB_B=B;
	GB_V=V;
    GB_N1 = N1;
    GB_N2 = N2;
    GB_N3 = N3;
}


def nd_f4_p2(P,O)
{
	if ( GB_H )
		return [nd_f4(GB_B,GB_V,P,O|dp=1,trace=GB_N,nora=1),P];
	else
		return [nd_f4(GB_B,GB_V,P,O|dp=1,trace=GB_N),P];
}


def nd_gr_recompute_trace_p(B,V,P,O)
{
	T0 = time();
	R = nd_gr_recompute_trace(B,V,P,O,GB_History);
	T1 = time();
	Time = (T1[0]-T0[0])+(T1[1]-T0[1]);
	return [nd_gr_recompute_trace(B,V,P,O,GB_History),P,Time];
}

def nd_gr_gentrace_p(B,V,P,O)
{
	return [nd_gr(B,V,P,O|gentrace=1),P];
}

def comp_by_ht(A,B)
{
	HA = dp_ht(A); HB = dp_ht(B);
	if ( HA > HB )
		return 1;
	else if ( HA < HB )
		return -1;
	else
		return 0;
}

localf crv,intvtoratv,intvtoratv2$

/* CRT for vector */
def crv(V,M,VP,P)
{
  N = length(V);
  M1 = inv(M,P);
  for ( I = 0; I < N; I++ )
    V[I] += (VP[I]-V[I])*M*M1;
}

/* 
 *  int vector -> rat vector
 */

def intvtoratv(V,Mod)
{
  N = length(V);
  R = vector(N);
  M = calcb(Mod);
  for ( I = 0; I < N; I++ ) {
    T = inttorat(V[I],Mod,M);
    if ( T )
      R[I] = T[0]/T[1];
    else
      return 0;
  }
  return R;
}

/* 
 * int vector -> rat vector
 * This may be efficient if the LCM of denominators is not so larger
 * than the denominators.
 */

def intvtoratv2(V,Mod)
{
  N = length(V);
  R = vector(N);
  M = calcb(Mod);
  Den = 1;
  for ( I = 0; I < N; I++ ) {
    T = inttorat(V[I]*Den,Mod,M);
    if ( T ) {
      Nm = T[0]; Dn = T[1];
      if ( Dn != 1 ) {
        for ( J = 0; J < I; J++ ) R[J] *= Dn;
        Den *= Dn;
      }
      R[I] = Nm;
    } else
      return 0;
  }
  return R/Den;
}

def intdpltoratdpl2(G,Mod,Stat)
{
	N = size(G)[0];
	M = calcb(Mod);
	New = 0;
	Den = 1;
	for ( I = 0; I < N; I++ ) {
		if ( Stat[I] == 2 ) continue;
		if ( !I || dp_td(G[I]) != dp_td(G[I-1]) )
			Den = 1;
		T = intdptoratdp(G[I]*Den,Mod,M);
		if ( T ) {
			print([I],2);
			T = dp_ptozp(T); 
			Den = ilcm(Den,dp_hc(T));
			G[I] = T; Stat[I] = 2; New++;
		} else {
			print("("+rtostr(I)+")",2);
		}
	}
	print("");
	return New;
}

def intdptoratdp(F,Mod,M)
{
	for ( T = F, N = 0; T; T = dp_rest(T), N++ );
	C = newvect(N);
	for ( I = 0, T = F; I < N; T = dp_rest(T), I++ ) {
		L = inttorat(dp_hc(T)%Mod,Mod,M);
		if ( !L )
			return 0;
		else
			C[I] = (L[0]/L[1])*dp_ht(T);
	}
	for ( R = 0, I = N-1; I >= 0; I-- )
		R += C[I];
	return R;
}

def dp_mulmod(C,F,M)
{
	L = [];
	for ( T = F; T; T = dp_rest(T) ) {
		A = (dp_hc(T)*C)%M;
		L = cons(A*dp_ht(T),L);
	}
	for ( R = 0; L != []; L = cdr(L) )
		R += car(L);
	return R;
}

def dp_chrem2(G,Mod,GM,P,Stat)
{
	N = size(G)[0];
	setmod(P);
	M1 = ptomp(inv(Mod,P),P);
	Fail = 0;
	for ( I = 0; I < N; I++ ) {
		if ( Stat[I] == 2 ) {
			T = dp_mod(G[I],P,[]); T = dp_rat(T/dp_hc(T));
			if ( GM[I] != T ) {
				C = inv(dp_hc(G[I]),Mod);
				G[I] = dp_mulmod(C,G[I],Mod);
				if ( dp_hc(G[I]) != 1 )
					error("");
				Stat[I] = 0;
				Fail++;
			} else continue;
		}
		T = (dp_mod(GM[I],P,[])-dp_mod(G[I],P,[]))*M1;
		G[I] = G[I]+dp_rat(T)*Mod;
		Stat[I] = 1;
#if 0
		print("|"+rtostr(I),2);
#endif
	}
	return Fail;
#if 0
	print("");
#endif
}

def monic_gb(D,V,O,P)
{
	dp_ord(O); setmod(P);
/*	D = map(dp_ptod,G,V); */
	D = map(dp_monic_mod,D,P);
/*	D = vtol(qsort(newvect(length(D),D),comp_by_ht)); */
	return [D,map(dp_ht,D)];
}

def dp_monic_mod(F,P)
{
	FP = dp_mod(F,P,[]);
	return dp_rat(FP/dp_hc(FP));
}

def calcb(M) {
	N = 2*M;
	T = sp_sqrt(N);
	if ( T^2 <= N && N < (T+1)^2 )
		return idiv(T,2);
	else
		error("afo");
}

def sp_sqrt(A) {
	for ( J = 0, T = A; T >= 2^27; J++ ) {
		T = idiv(T,2^27)+1;
	}
	for ( I = 0; T >= 2; I++ ) {
		S = idiv(T,2);
		if ( T = S+S )
			T = S;
		else
			T = S+1;
	}
	X = (2^27)^idiv(J,2)*2^idiv(I,2);
	while ( 1 ) {
		if ( (Y=X^2) < A )
			X += X;
		else if ( Y == A )
			return X;
		else
			break;
	}
	while ( 1 )
		if ( (Y = X^2) <= A )
			return X;
		else
			X = idiv(A + Y,2*X);
}

def init_pprocs(L)
{
	R = [];
    if ( type(NoX=getopt(nox)) == -1 ) NoX = 0;
	for ( T = L; T != []; T = cdr(T) ) {
		Host = car(T)[0]; N = car(T)[1];
		if ( !Host ) {
			for ( I = 0; I < N; I++ ) {
				P = NoX ? ox_launch_nox() : ox_launch();
				R = cons(P,R);
			}
		} else {
			Lib = get_rootdir();
			Client = "ox_asir";
			for ( I = 0; I < N; I++ ) {
				P = NoX ? ox_launch_nox(Host,Lib,Client)
					: ox_launch(Host,Lib,Client);
				R = cons(P,R);
			}
		}
	}
	return reverse(R);
}

def nd_gbcheck(G,V,P,O)
{
	Proc = getopt(proc);
	if ( type(Proc) == -1 ) Proc = 0;
	F4 = getopt(f4);
	if ( type(F4) == -1 ) F4 = 0;
	/* XXX */
	S = getopt(splist);
	if ( type(S) == -1 ) {
		if ( type(G) == 7 )
			S = nd_gr(bload(G),V,lprime(0),O|splist=1);
		else
			S = nd_gr(G,V,lprime(0),O|splist=1);
	}
	if ( Proc ) {
		N = length(Proc);
		L = vector(N);
		for ( I = 0; I < N; I++ ) L[I] = [];
		for ( I = 0, T = S; T != []; T = cdr(T), I = (I+1)%N )
			L[I] = cons(car(T),L[I]);
		for ( I = 0; I < N; I++ )
			ox_rpc(Proc[I],"noro_grcrt.gbcheck_p",G,V,P,O,reverse(L[I]),F4);
		for ( I = 0; I < N; I++ )
			if ( !ox_pop_local(Proc[I]) ) return 0;
		return 1;
	} else {
		if ( F4 )
			R = nd_f4(G,V,P,O|check_splist=S);
		else 
			R = nd_gr(G,V,P,O|check_splist=S);
		return R;
	}
}

def gbcheck_p(G,V,P,O,S,F4)
{
	if ( type(G) == 7 )
		G = bload(G);
	if ( F4 )
		return nd_f4(G,V,P,O|check_splist=S);
	else
		return nd_gr(G,V,P,O|check_splist=S);
}

def elimination(L,Elim)
{
  if ( type(Elim) <= 1 ) {
  	for ( R = []; L != []; L = cdr(L) ) {
    	H = dp_etov(dp_ht(car(L)));
		for ( I = 0; I <= Pos && !H[I]; I++ );
		if ( I > Pos ) R = cons(car(L),R);
  	}
  } else {
  	for ( R = []; L != []; L = cdr(L) )
		if ( dp_ht(car(L)) <= Elim ) R = cons(car(L),R);
  }
  return reverse(R);
}

#if 0
def iso_eq_mod(Mod,UseNZ)
{
  B = GB_B; V = GB_V;

  /* V = [c1,bb,aa,b,a], W = [1,3,2,3,2,1] */
  W = [1,3,2,3,2,1];
  dp_set_weight(W);
  G1 = nd_f4(B,V,Mod,[[0,1],[0,4]]);
  V1 = cdr(V);
  G1 = noro_pd.elimination(G1,V1);
  D = res(x,x^3+a*x+b,3*x^2+a);
  G2 = nd_f4(cons(t*D-1,G1),cons(t,V1),Mod,[[0,1],[0,4]]);
  G2 = noro_pd.elimination(G2,V1);
  W1 = cdr(W);
  dp_set_weight(W1);
  if ( UseNZ )
    G3 = nd_f4(G2,V1,Mod,[[0,1],[0,3]]|dp=1,trace=GB_NZ);
  else {
    GB_NZ = nd_f4(G2,V1,Mod,[[0,1],[0,3]]|dp=1,gentrace=1);
	G3 = GB_NZ[0];
  }
  dp_ord([[0,1],[0,3]]);
#if 1
  for ( T = []; G3 != []; G3 = cdr(G3) )
    if ( dp_ht(car(G3)) < <<2,0,0,0>> ) T = cons(car(G3),T);
  return [reverse(T),Mod];
#endif
  return [G3,Mod];
}
#else

def iso_eq_gentrace(B,V,Mod)
{
  W = [1,3,2,3,2,1];

  dp_set_weight(W);
  N1 = nd_f4(B,V,Mod,[[0,1],[0,4]]|dp=1,nora=1,gentrace=1);
  G1 = N1[0];
  G1 = elim_top(G1,<<1,0,0,0,0>>);
  V1 = cdr(V);
  G1 = map(dp_dtop,G1,V);

  D = res(x,x^3+a*x+b,3*x^2+a);
  N2 = nd_f4(cons(t*D-1,G1),cons(t,V1),Mod,[[0,1],[0,4]]|dp=1,nora=1,gentrace=1);
  G2 = N2[0];
  G2 = elim_top(G2,<<1,0,0,0,0>>);
  G2 = map(dp_dtop,G2,cons(t,V1));

  W1 = cdr(W);
  dp_set_weight(W1);
  N3 = nd_f4(G2,V1,Mod,[[0,1],[0,3]]|dp=1,gentrace=1);
  return [N1,N2,N3];
}

def iso_eq_mod(Mod)
{
  V = [c1,bb,aa,b,a];
  W = [1,3,2,3,2,1];

  dp_set_weight(W);
  if ( GB_N1 )
    G1 = nd_f4(GB_B,V,Mod,[[0,1],[0,4]]|dp=1,nora=1,trace=GB_N1);
  else
    G1 = nd_f4(GB_B,V,Mod,[[0,1],[0,4]]|dp=1,nora=1);
  G1 = elim_top(G1,<<1,0,0,0,0>>);
  V1 = cdr(V);
  G1 = map(dp_dtop,G1,V);

  D = res(x,x^3+a*x+b,3*x^2+a);
  if ( GB_N2 )
    G2 = nd_f4(cons(t*D-1,G1),cons(t,V1),Mod,[[0,1],[0,4]]|dp=1,nora=1,trace=GB_N2);
  else
    G2 = nd_f4(cons(t*D-1,G1),cons(t,V1),Mod,[[0,1],[0,4]]|dp=1,nora=1);
  G2 = elim_top(G2,<<1,0,0,0,0>>);
  G2 = map(dp_dtop,G2,cons(t,V1));

  W1 = cdr(W);
  dp_set_weight(W1);
  if ( GB_N3 )
    G3 = nd_f4(G2,V1,Mod,[[0,1],[0,3]]|dp=1,trace=GB_N3);
  else
    G3 = nd_f4(G2,V1,Mod,[[0,1],[0,3]]|dp=1);
  G3 = elim_top(G3,<<2,0,0,0>>);
  return [G3,Mod];
}

def elim_top(G,H)
{
  N = length(dp_etov(dp_ht(G[0])));
  W = dp_set_weight();
  Ord = dp_ord();
  dp_set_weight(0);
  dp_ord([[0,1],[0,N-1]]);
  for ( T = []; G != []; G = cdr(G) )
    if ( dp_ht(car(G)) < H ) T = cons(car(G),T);
  dp_ord(Ord);
  dp_set_weight(W);
  return reverse(T);
}
#endif

def iso_eq_d2(L)
{
    Proc = getopt(proc);
    if ( type(Proc) == -1 ) {
      Proc = [];
      for ( I = 0; I < 10; I++ ) Proc = cons(ox_launch_nox(),Proc);
    } else if ( type(Proc) == 1 ) {
	  M = Proc;
      Proc = [];
      for ( I = 0; I < M; I++ ) Proc = cons(ox_launch_nox(),Proc);
	}
    F = generateF(L);
    A = polysys(F);
    A = simpsys(A);
    C = A[0]; B = A[1]; V = A[2]; W = A[3];

	map(ox_reset,Proc);
	B = map(ptozp,B);
	NProc = length(Proc);
	CRTime = 0; IRTime = 0;
	/* gentrace */
	L = iso_eq_gentrace(B,V,lprime(0));
	map(ox_rpc,Proc,"noro_grcrt.store_bvn3",B,V,L[0],L[1],L[2]);
	map(ox_pop_local,Proc);
	I = 0;
	N = 0;
	Remain = 1; /* dummy */
	Mod = 1;
	O = [[0,1],[0,3]];
	dp_ord(O);
	dp_set_weight(cdr(W));
	for ( T = Proc; T != []; T = cdr(T), I++ )
		ox_rpc(car(T),"noro_grcrt.iso_eq_mod",lprime(I));
	V1 = cdr(V);
	while ( Remain ) {
		for ( T = Proc; T != []; T = cdr(T), I++ ) {
			print(["from",car(T)],2);
			L = ox_pop_local(car(T)); GM = L[0]; P = L[1];
			print(" done");
			ox_rpc(car(T),"noro_grcrt.iso_eq_mod",lprime(I));
			if ( GM ) {
				L = monic_gb(GM,V1,O,P); GM = L[0];
				if ( !N ) {
					Remain = N = length(GM);
					Stat = vector(N);
					G = vector(N);
				}
T0 = time();
				Fail = dp_chrem2(G,Mod,GM,P,Stat);
				Remain += Fail;
T1 = time(); CRTime += (T1[0]-T0[0])+(T1[1]-T0[1]);
				Mod *= P;
			}
		}
T0 = time();
		New = intdpltoratdpl2(G,Mod,Stat);
T1 = time(); IRTime += (T1[0]-T0[0])+(T1[1]-T0[1]);
		Remain -= New;
		print((N-Remain)/N*100.0,0); print("% done");
	}
	map(ox_reset,Proc);
	print(["Template",TTime,"CRT",CRTime,"IR",IRTime,"#P",I]);
	return [vtol(map(dp_dtop,G,V1)),Proc];
}

def iso_c1eq_mod(Mod)
{
  V = [c1,bb,aa,b,a];
  W = [1,3,2,3,2,1];

  dp_set_weight(W);
  if ( GB_N1 )
    G1 = nd_f4(GB_B,V,Mod,[[0,1],[0,4]]|dp=1,nora=1,trace=GB_N1);
  else
    G1 = nd_f4(GB_B,V,Mod,[[0,1],[0,4]]|dp=1,nora=1);
  G1 = elim_top(G1,<<2,0,0,0,0>>);
  return [G1,Mod];
}

def iso_c1eq_d2(L)
{
    Proc = getopt(proc);
    if ( type(Proc) == -1 ) {
      Proc = [];
      for ( I = 0; I < 10; I++ ) Proc = cons(ox_launch_nox(),Proc);
    } else if ( type(Proc) == 1 ) {
	  M = Proc;
      Proc = [];
      for ( I = 0; I < M; I++ ) Proc = cons(ox_launch_nox(),Proc);
	}
    F = generateF(L);
    A = polysys(F);
    A = simpsys(A);
    C = A[0]; B = A[1]; V = A[2]; W = A[3];

	map(ox_reset,Proc);
	B = map(ptozp,B);
	NProc = length(Proc);
	CRTime = 0; IRTime = 0;
	/* gentrace */
    W = [1,3,2,3,2,1];
    dp_set_weight(W);
    N1 = nd_f4(B,V,lprime(0),[[0,1],[0,4]]|dp=1,nora=1,gentrace=1);
	map(ox_rpc,Proc,"noro_grcrt.store_bvn3",B,V,N1,0,0);
	map(ox_pop_local,Proc);
	I = 0;
	N = 0;
	Remain = 1; /* dummy */
	Mod = 1;
	O = [[0,1],[0,4]];
	dp_ord(O);
	for ( T = Proc; T != []; T = cdr(T), I++ )
		ox_rpc(car(T),"noro_grcrt.iso_c1eq_mod",lprime(I));
	V1 = cdr(V);
	while ( Remain ) {
		for ( T = Proc; T != []; T = cdr(T), I++ ) {
			print(["from",car(T)],2);
			L = ox_pop_local(car(T)); GM = L[0]; P = L[1];
			print(" done");
			ox_rpc(car(T),"noro_grcrt.iso_c1eq_mod",lprime(I));
			if ( GM ) {
				L = monic_gb(GM,V1,O,P); GM = L[0];
				if ( !N ) {
					Remain = N = length(GM);
					Stat = vector(N);
					G = vector(N);
				}
T0 = time();
				Fail = dp_chrem2(G,Mod,GM,P,Stat);
				Remain += Fail;
T1 = time(); CRTime += (T1[0]-T0[0])+(T1[1]-T0[1]);
				Mod *= P;
			}
		}
T0 = time();
		New = intdpltoratdpl2(G,Mod,Stat);
T1 = time(); IRTime += (T1[0]-T0[0])+(T1[1]-T0[1]);
		Remain -= New;
		print((N-Remain)/N*100.0,0); print("% done");
	}
	map(ox_reset,Proc);
	print(["Template",TTime,"CRT",CRTime,"IR",IRTime,"#P",I]);
	return [vtol(map(dp_dtop,G,V)),Proc];
}

def iso_eq_gentrace2(B,V,Mod)
{
  Wt = [1,1,3,2,3,2,1];
  Vt = cons(t,V);
  dp_set_weight(Wt);
  D = res(x,x^3+a*x+b,3*x^2+a);
  N1 = nd_f4(cons(t*D-1,B),Vt,Mod,[[0,1],[0,5]]|dp=1,nora=1,gentrace=1);
  G1 = N1[0];
  G1 = elim_top(G1,<<1,0,0,0,0,0>>);
  G1 = map(dp_dtop,G1,Vt);

  W = cdr(Wt);
  dp_set_weight(W);
  N2 = nd_f4(G1,V,Mod,[[0,1],[0,4]]|dp=1,nora=1,gentrace=1);
  G2 = N2[0];
  G2 = elim_top(G2,<<1,0,0,0,0>>);
  G2 = map(dp_dtop,G2,V);

  W1 = cdr(W);
  V1 = cdr(V);
  dp_set_weight(W1);
  N3 = nd_f4(G2,V1,Mod,[[0,1],[0,3]]|dp=1,gentrace=1);
  return [N1,N2,N3];
}

def iso_eq_mod2(Mod)
{
  V = [c1,bb,aa,b,a];
  Vt = cons(t,V);
  Wt = [1,1,3,2,3,2,1];
  dp_set_weight(Wt);
  D = res(x,x^3+a*x+b,3*x^2+a);
  if ( GB_N1 )
    G1 = nd_f4(cons(t*D-1,GB_B),Vt,Mod,[[0,1],[0,5]]|dp=1,nora=1,trace=GB_N1);
  else
    G1 = nd_f4(cons(t*D-1,GB_B),Vt,Mod,[[0,1],[0,5]]|dp=1,nora=1);
  G1 = elim_top(G1,<<1,0,0,0,0,0>>);
  G1 = map(dp_dtop,G1,Vt);

  W = cdr(Wt);
  dp_set_weight(W);
  if ( GB_N2 )
    G2 = nd_f4(G1,V,Mod,[[0,1],[0,4]]|dp=1,nora=1,trace=GB_N2);
  else
    G2 = nd_f4(G1,V,Mod,[[0,1],[0,4]]|dp=1,nora=1);
  G2 = elim_top(G2,<<1,0,0,0,0>>);
  G2 = map(dp_dtop,G2,V);

  W1 = cdr(W);
  V1 = cdr(V);
  dp_set_weight(W1);
  if ( GB_N3 )
    G3 = nd_f4(G2,V1,Mod,[[0,1],[0,3]]|dp=1,trace=GB_N3);
  else
    G3 = nd_f4(G2,V1,Mod,[[0,1],[0,3]]|dp=1);
  G3 = elim_top(G3,<<2,0,0,0>>);
  return [G3,Mod];
}

def iso_eq_d2new(L)
{
    Proc = getopt(proc);
    if ( type(Proc) == -1 ) {
      Proc = [];
      for ( I = 0; I < 10; I++ ) Proc = cons(ox_launch_nox(),Proc);
    } else if ( type(Proc) == 1 ) {
	  M = Proc;
      Proc = [];
      for ( I = 0; I < M; I++ ) Proc = cons(ox_launch_nox(),Proc);
	}
    F = generateF(L);
    A = polysys(F);
    A = simpsys(A);
    C = A[0]; B = A[1]; V = A[2]; W = A[3];

	map(ox_reset,Proc);
	B = map(ptozp,B);
	NProc = length(Proc);
	CRTime = 0; IRTime = 0;
	/* gentrace */
	L = iso_eq_gentrace2(B,V,lprime(0));
	map(ox_rpc,Proc,"noro_grcrt.store_bvn3",B,V,L[0],L[1],L[2]);
	map(ox_pop_local,Proc);
	I = 0;
	N = 0;
	Remain = 1; /* dummy */
	Mod = 1;
	O = [[0,1],[0,3]];
	dp_ord(O);
	dp_set_weight(cdr(W));
	for ( T = Proc; T != []; T = cdr(T), I++ )
		ox_rpc(car(T),"noro_grcrt.iso_eq_mod2",lprime(I));
	V1 = cdr(V);
	while ( Remain ) {
		for ( T = Proc; T != []; T = cdr(T), I++ ) {
			print(["from",car(T)],2);
			L = ox_pop_local(car(T)); GM = L[0]; P = L[1];
			print(" done");
			ox_rpc(car(T),"noro_grcrt.iso_eq_mod2",lprime(I));
			if ( GM ) {
				L = monic_gb(GM,V1,O,P); GM = L[0];
				if ( !N ) {
					Remain = N = length(GM);
					Stat = vector(N);
					G = vector(N);
				}
T0 = time();
				Fail = dp_chrem2(G,Mod,GM,P,Stat);
				Remain += Fail;
T1 = time(); CRTime += (T1[0]-T0[0])+(T1[1]-T0[1]);
				Mod *= P;
			}
		}
T0 = time();
		New = intdpltoratdpl2(G,Mod,Stat);
T1 = time(); IRTime += (T1[0]-T0[0])+(T1[1]-T0[1]);
		Remain -= New;
		print((N-Remain)/N*100.0,0); print("% done");
	}
	map(ox_reset,Proc);
	print(["Template",TTime,"CRT",CRTime,"IR",IRTime,"#P",I]);
	return [vtol(map(dp_dtop,G,V1)),Proc];
}

def iso_sat_gentrace(B,V,Mod,Wt,Wt2,Ord)
{
  Vt = cons(t,V);
  dp_set_weight(Wt);
  dp_gr_flags(["Reverse",1]);
  D = res(x,x^3+a*x+b,3*x^2+a);
  N1 = nd_f4(cons(t*D-1,B),Vt,Mod,Ord|dp=1,gentrace=1,sugarweight=Wt2);
  dp_gr_flags(["Reverse",0]);
  dp_set_weight(0);
  return N1;
}

def iso_sat_mod(Mod,V,Wt,Wt2,Ord)
{
  Vt = cons(t,V);
  D = res(x,x^3+a*x+b,3*x^2+a);
  dp_set_weight(Wt);
  dp_gr_flags(["Reverse",1]);
  if ( GB_N1 )
    G1 = nd_f4(cons(t*D-1,GB_B),Vt,Mod,Ord|dp=1,trace=GB_N1, sugarweight=Wt2);
  else
    G1 = nd_f4(cons(t*D-1,GB_B),Vt,Mod,Ord|dp=1,sugarweight=Wt2);
  dp_set_weight(0);
  dp_gr_flags(["Reverse",0]);
  G1 = elim_top(G1,<<1,0,0,0,0,0>>);
  return [G1,Mod];
}

def iso_sat_d2(L)
{
Tall0=time();
    Proc = getopt(proc);
    Sys = getopt(sys);
    if ( type(Proc) == -1 ) {
      Proc = [];
      for ( I = 0; I < 10; I++ ) Proc = cons(ox_launch_nox(),Proc);
    } else if ( type(Proc) == 1 ) {
	  M = Proc;
      Proc = [];
      for ( I = 0; I < M; I++ ) Proc = cons(ox_launch_nox(),Proc);
	}
	if ( type(Sys) == -1 ) {
      F = generateF(L);
       A = polysys(F);
       A = simpsys(A);
       C = A[0]; B = A[1]; V = A[2]; W = A[3];
	} else {
       C = Sys[0]; B = Sys[1]; V = Sys[2]; W = Sys[3];
	}

	map(ox_reset,Proc);
	B = map(ptozp,B);
	NProc = length(Proc);
	CRTime = 0; IRTime = 0;
	/* gentrace Wt,Ord */
	Wt = [1,3,2,1,3,2,1];
	Wt2 = [-6,3,2,1,3,2,1];
    Ord = [[0,1],[0,5]];
	V = [bb,aa,c1,b,a];
	Vt = cons(t,V);
	dp_ord(Ord);
	NZ = iso_sat_gentrace(B,V,lprime(0),Wt,Wt2,Ord);
	map(ox_rpc,Proc,"noro_grcrt.store_bvn3",B,V,NZ,0,0);
	map(ox_pop_local,Proc);
	I = 0;
	N = 0;
	Remain = 1; /* dummy */
	Mod = 1;
    dp_set_weight(cdr(Wt));
    Ord0 = 0;
	for ( T = Proc; T != []; T = cdr(T), I++ )
		ox_rpc(car(T),"noro_grcrt.iso_sat_mod",lprime(I),V,Wt,Wt2,Ord);
	while ( Remain ) {
		for ( T = Proc; T != []; T = cdr(T), I++ ) {
			print(["from",car(T)],2);
			L = ox_pop_local(car(T)); GM = L[0]; P = L[1];
			print(" done");
			ox_rpc(car(T),"noro_grcrt.iso_sat_mod",lprime(I),V,Wt,Wt2,Ord);
			if ( GM ) {
/*                bsave(GM,"gm4/"+rtostr(P)); */
				L = monic_gb(GM,Vt,Ord0,P); GM = L[0];
				if ( !N ) {
					Remain = N = length(GM);
					Stat = vector(N);
					G = vector(N);
				}
T0 = time();
				Fail = dp_chrem2(G,Mod,GM,P,Stat);
				Remain += Fail;
T1 = time(); CRTime += (T1[0]-T0[0])+(T1[1]-T0[1]);
				Mod *= P;
			}
		}
T0 = time();
		New = intdpltoratdpl2(G,Mod,Stat);
T1 = time(); IRTime += (T1[0]-T0[0])+(T1[1]-T0[1]);
		Remain -= New;
		print((N-Remain)/N*100.0,0); print("% done");
	}
	map(ox_reset,Proc);
	print(["Template",TTime,"CRT",CRTime,"IR",IRTime,"#P",I]);
Tall1 = time();
Tcpu = Tall1[0]-Tall0[0];
Tgc = Tall1[1]-Tall0[1];
Treal = Tall1[3]-Tall0[3];
	return [vtol(map(dp_dtop,G,Vt)),Proc,["Template",TTime,"CRT",CRTime,"IR",IRTime,"#P",I,"cpu",Tcpu,"gc",Tgc,"real",Treal]];
}

endmodule$

end$

/* old functions */

def gr_chrem(B,V,O)
{
	Proc = getopt(proc);
	Dname = getopt(dname);
	if ( type(Proc) != -1 ) {
		if ( type(Dname) != -1 )
			return gr_chr_d(B,V,O,Proc,Dname);
		else
			return gr_chrem_d(B,V,O,Proc);
	}

	B = map(ptozp,B);
	Mod = 1;
	D = nd_gr(B,V,lprime(0),O|gentrace=1);
	Remain = N = length(D[0]);
	Stat = vector(N);
	G = vector(N);
	for ( I = 1; Remain; I++ ) {
		P = lprime(I);
		GM = nd_gr_recompute_trace(B,V,P,O,D);
		if ( !GM ) continue;
		L = monic_gb(GM,V,O,P); GM = L[0];
T0 = time();
		dp_chrem2(G,Mod,GM,P,Stat);
T1 = time(); CRTime += (T1[0]-T0[0])+(T1[1]-T0[1]);
		Mod *= P;
		if ( !(I%3) ) {
T0 = time();
			New = intdpltoratdpl2(G,Mod,Stat);
T1 = time(); IRTime += (T1[0]-T0[0])+(T1[1]-T0[1]);
			Remain -= New;
		}
	}
	print(["CRT",CRTime,"IR",IRTime,"#P",I]);
	return vtol(map(dp_dtop,G,V));
}

/* NZ = [*,*,NZ,BPE] */

def f4_chrem(B,V,O)
{
	Proc = getopt(proc);
	NZ = getopt(nz);
	Prev = getopt(prev);
	Homo = getopt(homo);
	Elim = getopt(elim);
	Weight = getopt(weight);
	if ( type(NZ) == -1 ) NZ = 0;
	if ( type(Prev) == -1 ) Prev = 0;
	if ( type(Homo) == -1 ) Homo = 0;
	if ( type(Elim) == -1 ) Elim = -1;
	if ( type(Weight) == -1 ) Weight = 0;
	OldWeight = dp_set_weight();
	dp_set_weight(Weight);
	if ( type(Proc) != -1 ) {
		if ( NZ )
	 		G = f4_chr_d(B,V,O,Proc,NZ,Prev,Homo,Elim,Weight);
		else
	 		G = f4_chrem_d(B,V,O,Proc);
	    dp_set_weight(OldWeight);
		return G;
	}
	B = map(ptozp,B);
	Remain = 1; /* XXX */
	for ( I = 0, N = 0, Mod = 1; Remain; I++ ) {
		P = lprime(I);
		if ( NZ )
			GM = nd_f4(B,V,P,O|dp=1,trace=NZ);
		else 
			GM = nd_f4(B,V,P,O|dp=1);
		if ( !GM ) continue;
		if ( !N ) {
			Remain = N = length(GM);
			Stat = vector(N);
			G = vector(N);
		}
		L = monic_gb(GM,V,O,P); GM = L[0];
T0 = time();
		dp_chrem2(G,Mod,GM,P,Stat);
T1 = time(); CRTime += (T1[0]-T0[0])+(T1[1]-T0[1]);
		Mod *= P;
		if ( !(I%3) ) {
T0 = time();
			New = intdpltoratdpl2(G,Mod,Stat);
T1 = time(); IRTime += (T1[0]-T0[0])+(T1[1]-T0[1]);
			Remain -= New;
		}
	}
	print(["CRT",CRTime,"IR",IRTime,"#P",I]);
	G = vtol(map(dp_dtop,G,V));
	dp_set_weight(OldWeight);
	return G;
}

def gr_chrem_d(B,V,O,Proc)
{
	map(ox_reset,Proc);
	B = map(ptozp,B);
	NProc = length(Proc); D = vector(NProc); H = vector(NProc);
	CRTime = 0; IRTime = 0;
	/* gentrace */
	I = 0;
T0 = time();
	while ( 1 ) {
		for ( J = 0; J < NProc; J++, I++ )
			ox_rpc(Proc[J],"noro_grcrt.nd_gr_gentrace_p",B,V,lprime(I),O);
		for ( J = 0; J < NProc; J++, I++ ) {
			D[J] = ox_pop_local(Proc[J]);
			H[J] = map(dp_ptod,D[J][0][0],V);
		}
		for ( J = 1; J < NProc; J++ )
			if ( map(dp_ht,H[J]) != map(dp_ht,H[0]) ) break;
		if ( J == NProc ) break;
	}
T1 = time(); TTime += (T1[3]-T0[3]);
print(["Template",TTime]);
	map(ox_rpc,Proc,"noro_grcrt.store_history",D[0][0]); map(ox_pop_local,Proc);
	for ( J = 0; J < NProc; J++, I++ )
		ox_rpc(Proc[J],"noro_grcrt.nd_gr_recompute_trace_p",B,V,lprime(I),O);

	Remain = N = length(D[0][0][0]);
	Stat = vector(N); G = vector(N);
	Mod = 1;

	for ( J = 0; J < NProc; J++ ) {
		P = D[J][1];
		L = monic_gb(H[J],V,O,P); GM = L[0];
T0 = time();
		dp_chrem2(G,Mod,GM,P,Stat);
T1 = time(); CRTime += (T1[0]-T0[0])+(T1[1]-T0[1]);
		Mod *= P;
	}

	while ( Remain ) {
		for ( T = Proc; T != []; T = cdr(T), I++ ) {
			L = ox_pop_local(car(T)); GM = L[0]; P = L[1];
			ox_rpc(car(T),"noro_grcrt.nd_gr_recompute_trace_p",B,V,lprime(I),O);
			if ( GM ) {
				L = monic_gb(GM,V,O,P); GM = L[0];
T0 = time();
				dp_chrem2(G,Mod,GM,P,Stat);
T1 = time(); CRTime += (T1[0]-T0[0])+(T1[1]-T0[1]);
				Mod *= P;
			}
		}
T0 = time();
		New = intdpltoratdpl2(G,Mod,Stat);
T1 = time(); IRTime += (T1[0]-T0[0])+(T1[1]-T0[1]);
		Remain -= New;
		print((N-Remain)/N*100.0,0); print("% done");
	}
	print(["Template",TTime,"CRT",CRTime,"IR",IRTime,"#P",I-NProc]);
	return vtol(map(dp_dtop,G,V));
}

def gr_chr_d(B,V,O,Proc,Dname)
{
	map(ox_reset,Proc);
	B = map(ptozp,B);
	NProc = length(Proc); D = vector(NProc); H = vector(NProc);
	CRTime = 0; IRTime = 0;
	/* gentrace */
	map(ox_rpc,Proc,"noro_grcrt.read_history",Dname); map(ox_pop_local,Proc);
	for ( J = 0; J < NProc; J++, I++ )
		ox_rpc(Proc[J],"noro_grcrt.nd_gr_recompute_trace_p",B,V,lprime(I),O);

	Remain = N = length(D[0][0][0]);
	Stat = vector(N); G = vector(N);
	Mod = 1;

	for ( J = 0; J < NProc; J++ ) {
		P = D[J][1];
		L = monic_gb(H[J],V,O,P); GM = L[0];
T0 = time();
		dp_chrem2(G,Mod,GM,P,Stat);
T1 = time(); CRTime += (T1[0]-T0[0])+(T1[1]-T0[1]);
		Mod *= P;
	}

	while ( Remain ) {
		for ( T = Proc; T != []; T = cdr(T), I++ ) {
			L = ox_pop_local(car(T)); GM = L[0]; P = L[1];
			ox_rpc(car(T),"noro_grcrt.nd_gr_recompute_trace_p",B,V,lprime(I),O);
			if ( GM ) {
				L = monic_gb(GM,V,O,P); GM = L[0];
T0 = time();
				dp_chrem2(G,Mod,GM,P,Stat);
T1 = time(); CRTime += (T1[0]-T0[0])+(T1[1]-T0[1]);
				Mod *= P;
			}
		}
T0 = time();
		New = intdpltoratdpl2(G,Mod,Stat);
T1 = time(); IRTime += (T1[0]-T0[0])+(T1[1]-T0[1]);
		Remain -= New;
		print((N-Remain)/N*100.0,0); print("% done");
	}
	print(["CRT",CRTime,"IR",IRTime,"#P",I-NProc]);
	return vtol(map(dp_dtop,G,V));
}

def f4_chrem_d(B,V,O,Proc)
{
	map(ox_reset,Proc);
	B = map(ptozp,B);
	NProc = length(Proc); D = vector(NProc); H = vector(NProc);
	CRTime = 0; IRTime = 0;
	/* gentrace */
	I = 0;
	map(ox_rpc,Proc,"noro_grcrt.store_bv",B,V);
	map(ox_pop_local,Proc);
T0 = time();
	while ( 1 ) {
		for ( J = 0; J < NProc; J++, I++ )
			ox_rpc(Proc[J],"noro_grcrt.nd_f4_p",lprime(I),O);
		for ( J = 0; J < NProc; J++ ) {
			D[J] = ox_pop_local(Proc[J]);
			H[J] = D[J][0];
		}
		for ( J = 1; J < NProc; J++ )
			if ( map(dp_ht,H[J]) != map(dp_ht,H[0]) ) break;
		if ( J == NProc ) break;
	}
T1 = time(); TTime += (T1[3]-T0[3]);
print(["Template",TTime]);
	for ( J = 0; J < NProc; J++, I++ )
		ox_rpc(Proc[J],"noro_grcrt.nd_f4_p",lprime(I),O);

	Remain = N = length(D[0][0]);
	Stat = vector(N); G = vector(N);
	Mod = 1;

	for ( J = 0; J < NProc; J++ ) {
		P = D[J][1];
		L = monic_gb(H[J],V,O,P); GM = L[0];
T0 = time();
		dp_chrem2(G,Mod,GM,P,Stat);
T1 = time(); CRTime += (T1[0]-T0[0])+(T1[1]-T0[1]);
		Mod *= P;
	}

	while ( Remain ) {
		for ( T = Proc; T != []; T = cdr(T), I++ ) {
			L = ox_pop_local(car(T)); GM = L[0]; P = L[1];
			ox_rpc(car(T),"noro_grcrt.nd_f4_p",lprime(I),O);
			if ( GM ) {
				L = monic_gb(GM,V,O,P); GM = L[0];
T0 = time();
				dp_chrem2(G,Mod,GM,P,Stat);
T1 = time(); CRTime += (T1[0]-T0[0])+(T1[1]-T0[1]);
				Mod *= P;
			}
		}
T0 = time();
		New = intdpltoratdpl2(G,Mod,Stat);
T1 = time(); IRTime += (T1[0]-T0[0])+(T1[1]-T0[1]);
		Remain -= New;
		print((N-Remain)/N*100.0,0); print("% done");
	}
	print(["Template",TTime,"CRT",CRTime,"IR",IRTime,"#P",I-NProc]);
	return vtol(map(dp_dtop,G,V));
}

def nd_f4_p(P,O)
{
	return [nd_f4(GB_B,GB_V,P,O|dp=1),P];
}

def store_bv(B,V)
{
	GB_B=B;
	GB_V=V;
}