Loading...
Searching...
No Matches
walk.h File Reference
`#include "kernel/structs.h"`

Go to the source code of this file.

## Functions

ideal | MwalkInitialForm (ideal G, intvec *curr_weight)
intvec * | MwalkNextWeight (intvec *curr_weight, intvec *target_weight, ideal G)
int | MivSame (intvec *u, intvec *v)
int | M3ivSame (intvec *next_weight, intvec *u, intvec *v)
intvec * | Mivdp (int nR)
intvec * | Mivlp (int nR)
intvec * | MivMatrixOrder (intvec *iv)
intvec * | MivMatrixOrderdp (int iv)
intvec * | MPertVectors (ideal G, intvec *ivtarget, int pdeg)
intvec * | MPertVectorslp (ideal G, intvec *ivtarget, int pdeg)
intvec * | MivMatrixOrderlp (int nV)
intvec * | Mfpertvector (ideal G, intvec *iv)
intvec * | MivUnit (int nV)
intvec * | MivWeightOrderlp (intvec *ivstart)
intvec * | MivWeightOrderdp (intvec *ivstart)
ideal | MidLift (ideal Gomega, ideal M)
ideal | MLiftLmalG (ideal L, ideal G)
ideal | MLiftLmalGNew (ideal Gomega, ideal M, ideal G)
ideal | MLiftLmalGMin (ideal L, ideal G)
intvec * | MkInterRedNextWeight (intvec *iva, intvec *ivb, ideal G)
intvec * | MPertNextWeight (intvec *iva, ideal G, int deg)
intvec * | Mivperttarget (ideal G, int ndeg)
intvec * | MSimpleIV (intvec *iv)
ideal | Mwalk (ideal Go, intvec *orig_M, intvec *target_M, ring baseRing, int reduction, int printout)
ideal | Mrwalk (ideal Go, intvec *orig_M, intvec *target_M, int weight_rad, int pert_deg, int reduction, int printout)
ideal | Mpwalk (ideal Go, int op_deg, int tp_deg, intvec *curr_weight, intvec *target_weight, int nP, int reduction, int printout)
ideal | Mprwalk (ideal Go, intvec *orig_M, intvec *target_M, int weight_rad, int op_deg, int tp_deg, int nP, int reduction, int printout)
ideal | Mfwalk (ideal G, intvec *ivstart, intvec *ivtarget, int reduction, int printout)
ideal | Mfrwalk (ideal G, intvec *ivstart, intvec *ivtarget, int weight_rad, int reduction, int printout)
intvec * | TranMPertVectorslp (ideal G)
ideal | TranMImprovwalk (ideal Go, intvec *curr_weight, intvec *target_weight, int nP)
ideal | MAltwalk1 (ideal G, int op, int tp, intvec *curr_weight, intvec *target_weight)
ideal | MAltwalk2 (ideal G, intvec *curr_weight, intvec *target_weight)

## Function Documentation

## M3ivSame()

int M3ivSame | ( | intvec * | next_weight,
|  | intvec * | u,
|  | intvec * | v )

Definition at line 915 of file walk.cc.

{
assume(temp->length() == u->length() && u->length() == v->length());
if((MivSame(temp, u)) == 1)
{
return 0;
}
if((MivSame(temp, v)) == 1)
{
return 1;
}
return 2;
}
intvec::length
int length() const
Definition intvec.h:95
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition facBivar.h:39
assume
#define assume(x)
Definition mod2.h:389
MivSame
int MivSame(intvec *u, intvec *v)
Definition walk.cc:894

## MAltwalk1()

ideal MAltwalk1 | ( | ideal | G,
|  | int | op,
|  | int | tp,
|  | intvec * | curr_weight,
|  | intvec * | target_weight )

Definition at line 9672 of file walk.cc.

{
Set_Error(FALSE );
Overflow_Error = FALSE;
#ifdef TIME_TEST
BOOLEAN nOverflow_Error = FALSE;
#endif
// Print("// pSetm_Error = (%d)", ErrorCheck());
#ifdef TIME_TEST
xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0; xtextra=0;
xftinput = clock();
clock_t tostd, tproc;
#endif
nstep = 0;
int i, nV = currRing->N;
int nwalk=0, endwalks=0;
int op_tmp = op_deg;
ideal Gomega, M, F, G, Gomega1, Gomega2, M1, F1;
ring newRing, oldRing;
intvec* next_weight;
intvec* iv_M_dp;
intvec* ivNull = new intvec(nV);
intvec* iv_dp = MivUnit(nV);// define (1,1,...,1)
intvec* exivlp = Mivlp(nV);
//intvec* extra_curr_weight = new intvec(nV);
#ifndef BUCHBERGER_ALG
intvec* hilb_func;
#endif
intvec* cw_tmp = curr_weight;
// to avoid (1,0,...,0) as the target vector
intvec* last_omega = new intvec(nV);
for(i=nV-1; i>0; i--)
{
(*last_omega)[i] = 1;
}
(*last_omega)[0] = 10000;
ring XXRing = currRing;
#ifdef TIME_TEST
to=clock();
#endif
/* compute a pertubed weight vector of the original weight vector.
The perturbation degree is recursive decrease until that vector
stays inn the correct cone. */
while(1)
{
if(Overflow_Error == FALSE)
{
if(MivComp(curr_weight, iv_dp) == 1)
{
//rOrdStr(currRing) = "dp"
if(op_tmp == op_deg)
{
G = MstdCC(Go);
if(op_deg != 1)
{
iv_M_dp = MivMatrixOrderdp(nV);
}
}
}
}
else
{
if(op_tmp == op_deg)
{
//rOrdStr(currRing) = (a(...),lp,C)
if (rParameter(currRing) != NULL)
{
DefRingPar(cw_tmp);
}
else
{
rChangeCurrRing(VMrDefault(cw_tmp));
}
G = idrMoveR(Go, XXRing,currRing);
G = MstdCC(G);
if(op_deg != 1)
iv_M_dp = MivMatrixOrder(cw_tmp);
}
}
Overflow_Error = FALSE;
if(op_deg != 1)
{
curr_weight = MPertVectors(G, iv_M_dp, op_deg);
}
else
{
curr_weight = cw_tmp;
break;
}
if(Overflow_Error == FALSE)
{
break;
}
Overflow_Error = TRUE;
op_deg --;
}
#ifdef TIME_TEST
tostd=clock()-to;
#endif
if(op_tmp != 1 )
delete iv_M_dp;
delete iv_dp;
if(currRing->order[0] == ringorder_a)
goto NEXT_VECTOR;
while(1)
{
nwalk ++;
nstep ++;
#ifdef TIME_TEST
to = clock();
#endif
// compute an initial form ideal of <G> w.r.t. "curr_vector"
Gomega = MwalkInitialForm(G, curr_weight);
#ifdef TIME_TEST
xtif=xtif+clock()-to;
#endif
#if 0
if(Overflow_Error == TRUE)
{
for(i=nV-1; i>=0; i--)
(*curr_weight)[i] = (*extra_curr_weight)[i];
delete extra_curr_weight;
newRing = currRing;
goto MSTD_ALT1;
}
#endif
#ifndef BUCHBERGER_ALG
if(isNolVector(curr_weight) == 0)
{
hilb_func = hFirstSeries(Gomega,NULL,NULL,curr_weight,currRing);
}
else
{
hilb_func = hFirstSeries(Gomega,NULL,NULL,last_omega,currRing);
}
#endif // BUCHBERGER_ALG
oldRing = currRing;
// define a new ring which ordering is "(a(curr_weight),lp)
if (rParameter(currRing) != NULL)
{
DefRingPar(curr_weight);
}
else
{
rChangeCurrRing(VMrDefault(curr_weight));
}
newRing = currRing;
Gomega1 = idrMoveR(Gomega, oldRing,currRing);
#ifdef TIME_TEST
to=clock();
#endif
// compute a reduced Groebner basis of <Gomega> w.r.t. "newRing"
#ifdef BUCHBERGER_ALG
M = MstdhomCC(Gomega1);
#else
M=kStd2(Gomega1,NULL,isHomog,NULL,hilb_func,0,NULL,curr_weight);
delete hilb_func;
#endif // BUCHBERGER_ALG
#ifdef TIME_TEST
xtstd=xtstd+clock()-to;
#endif
// change the ring to oldRing
rChangeCurrRing(oldRing);
M1 = idrMoveR(M, newRing,currRing);
Gomega2 = idrMoveR(Gomega1, newRing,currRing);
#ifdef TIME_TEST
to=clock();
#endif
// compute a reduced Groebner basis of <G> w.r.t. "newRing" by the lifting process
F = MLifttwoIdeal(Gomega2, M1, G);
#ifdef TIME_TEST
xtlift=xtlift+clock()-to;
#endif
idDelete(&M1);
idDelete(&Gomega2);
idDelete(&G);
// change the ring to newRing
rChangeCurrRing(newRing);
F1 = idrMoveR(F, oldRing,currRing);
if (oldRing!=IDRING(currRingHdl)) rDelete(oldRing); // do not delete the global currRing
oldRing=NULL;
#ifdef TIME_TEST
to=clock();
#endif
// reduce the Groebner basis <G> w.r.t. new ring
G = kInterRedCC(F1, NULL);
#ifdef TIME_TEST
xtred=xtred+clock()-to;
#endif
idDelete(&F1);
if(endwalks == 1)
{
break;
}
NEXT_VECTOR:
#ifdef TIME_TEST
to=clock();
#endif
// compute a next weight vector
next_weight = MkInterRedNextWeight(curr_weight,target_weight, G);
#ifdef TIME_TEST
xtnw=xtnw+clock()-to;
#endif
#ifdef PRINT_VECTORS
MivString(curr_weight, target_weight, next_weight);
#endif
if(Overflow_Error == TRUE)
{
newRing = currRing;
if (rParameter(currRing) != NULL)
{
DefRingPar(target_weight);
}
else
{
rChangeCurrRing(VMrDefault(target_weight));
}
F1 = idrMoveR(G, newRing,currRing);
G = MstdCC(F1);
idDelete(&F1);
newRing = currRing;
break; //for while
}
/* G is the wanted Groebner basis if next_weight == curr_weight */
if(MivComp(next_weight, ivNull) == 1)
{
newRing = currRing;
delete next_weight;
break; //for while
}
if(MivComp(next_weight, target_weight) == 1)
{
if(tp_deg == 1 || MivSame(target_weight, exivlp) == 0)
endwalks = 1;
else
{
// MSTD_ALT1:
#ifdef TIME_TEST
nOverflow_Error = Overflow_Error;
tproc = clock()-xftinput;
#endif
//Print("\n// main routine takes %d steps and calls \"Mpwalk\" (1,%d):", nwalk, tp_deg);
// compute the red. GB of <G> w.r.t. the lex order by the "recursive-modified" perturbation walk alg (1,tp_deg)
G = Mpwalk_MAltwalk1(G, curr_weight, tp_deg);
delete next_weight;
break; // for while
}
}
//NOT Changed, to free memory
for(i=nV-1; i>=0; i--)
{
//(*extra_curr_weight)[i] = (*curr_weight)[i];
(*curr_weight)[i] = (*next_weight)[i];
}
delete next_weight;
}//while
rChangeCurrRing(XXRing);
ideal result = idrMoveR(G, newRing,currRing);
id_Delete(&G, newRing);
delete ivNull;
if(op_deg != 1 )
{
delete curr_weight;
}
delete exivlp;
#ifdef TIME_TEST
/*
Print("\n// \"Main procedure\" took %d steps, %.2f sec. and Overflow_Error(%d)",
nwalk, ((double) tproc)/1000000, nOverflow_Error);
TimeStringFractal(xftinput, tostd, xtif, xtstd,xtextra, xtlift, xtred, xtnw);
*/
// Print("\n// pSetm_Error = (%d)", ErrorCheck());
// Print("\n// Overflow_Error? (%d)", Overflow_Error);
// Print("\n// Awalk1 took %d steps.\n", nstep);
#endif
return(result);
}
BOOLEAN
int BOOLEAN
Definition auxiliary.h:88
TRUE
#define TRUE
Definition auxiliary.h:101
FALSE
#define FALSE
Definition auxiliary.h:97
i
int i
Definition cfEzgcd.cc:132
intvec
Definition intvec.h:24
result
return result
Definition facAbsBiFact.cc:76
hFirstSeries
intvec * hFirstSeries(ideal A, intvec *module_w, ideal Q, intvec *wdegree)
Definition hilb.cc:1514
idDelete
#define idDelete(H)
delete an ideal
Definition ideals.h:29
currRingHdl
VAR idhdl currRingHdl
Definition ipid.cc:57
IDRING
#define IDRING(a)
Definition ipid.h:127
G
STATIC_VAR TreeM * G
Definition janet.cc:31
kStd2
ideal kStd2(ideal F, ideal Q, tHomog h, intvec **w, bigintmat *hilb, int syzComp, int newIdeal, intvec *vw, s_poly_proc_t sp)
generic interface to GB/SB computations, large hilbert vectors
Definition kstd1.cc:2607
NULL
#define NULL
Definition omList.c:12
rChangeCurrRing
void rChangeCurrRing(ring r)
Definition polys.cc:16
currRing
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition polys.cc:13
idrMoveR
ideal idrMoveR(ideal &id, ring src_r, ring dest_r)
Definition prCopy.cc:248
rDelete
void rDelete(ring r)
unconditionally deletes fields in r
Definition ring.cc:454
ringorder_a
@ ringorder_a
Definition ring.h:71
rParameter
static char const ** rParameter(const ring r)
(r->cf->parameter)
Definition ring.h:631
id_Delete
void id_Delete(ideal *h, ring r)
deletes an ideal/module/matrix
Definition simpleideals.cc:123
M
#define M
Definition sirandom.c:25
isHomog
@ isHomog
Definition structs.h:33
kInterRedCC
static ideal kInterRedCC(ideal F, ideal Q)
Definition walk.cc:269
MivUnit
intvec * MivUnit(int nV)
Definition walk.cc:1497
nstep
VAR int nstep
kstd2.cc
Definition walk.cc:80
MstdhomCC
static ideal MstdhomCC(ideal G)
Definition walk.cc:948
MivComp
static int MivComp(intvec *iva, intvec *ivb)
Definition walk.cc:1799
MivMatrixOrderdp
intvec * MivMatrixOrderdp(int nV)
Definition walk.cc:1418
MPertVectors
intvec * MPertVectors(ideal G, intvec *ivtarget, int pdeg)
Definition walk.cc:1089
MivMatrixOrder
intvec * MivMatrixOrder(intvec *iv)
Definition walk.cc:964
Set_Error
void Set_Error(BOOLEAN f)
Definition walk.cc:86
Mpwalk_MAltwalk1
static ideal Mpwalk_MAltwalk1(ideal Go, intvec *curr_weight, int tp_deg)
Definition walk.cc:9378
MLifttwoIdeal
static ideal MLifttwoIdeal(ideal Gw, ideal M, ideal G)
Definition walk.cc:1722
VMrDefault
static ring VMrDefault(intvec *va)
Definition walk.cc:2681
Overflow_Error
VAR BOOLEAN Overflow_Error
Definition walk.cc:88
Mivlp
intvec * Mivlp(int nR)
Definition walk.cc:1023
MwalkInitialForm
ideal MwalkInitialForm(ideal G, intvec *ivw)
Definition walk.cc:762
MkInterRedNextWeight
intvec * MkInterRedNextWeight(intvec *iva, intvec *ivb, ideal G)
Definition walk.cc:2571
DefRingPar
static void DefRingPar(intvec *va)
Definition walk.cc:2940
MstdCC
static ideal MstdCC(ideal G)
Definition walk.cc:933

## MAltwalk2()

ideal MAltwalk2 | ( | ideal | G,
|  | intvec * | curr_weight,
|  | intvec * | target_weight )

Definition at line 4281 of file walk.cc.

{
Set_Error(FALSE);
Overflow_Error = FALSE;
//BOOLEAN nOverflow_Error = FALSE;
//Print("// pSetm_Error = (%d)", ErrorCheck());
#ifdef TIME_TEST
xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0; xtextra=0;
xftinput = clock();
clock_t tostd, tproc;
#endif
nstep = 0;
int i, nV = currRing->N;
int nwalk=0, endwalks=0;
// int nhilb = 1;
ideal Gomega, M, F, Gomega1, Gomega2, M1, F1, G;
//ideal G1;
//ring endRing;
ring newRing, oldRing;
intvec* ivNull = new intvec(nV);
intvec* next_weight;
//intvec* extra_curr_weight = new intvec(nV);
//intvec* hilb_func;
intvec* exivlp = Mivlp(nV);
ring XXRing = currRing;
//Print("\n// ring r_input = %s;", rString(currRing));
#ifdef TIME_TEST
to = clock();
#endif
/* compute the reduced Groebner basis of the given ideal w.r.t.
a "fast" monomial order, e.g. degree reverse lex. order (dp) */
G = MstdCC(Go);
#ifdef TIME_TEST
tostd=clock()-to;
Print("\n// Computation of the first std took = %.2f sec",
((double) tostd)/1000000);
#endif
if(currRing->order[0] == ringorder_a)
{
goto NEXT_VECTOR;
}
while(1)
{
nwalk ++;
nstep ++;
#ifdef TIME_TEST
to = clock();
#endif
/* compute an initial form ideal of <G> w.r.t. "curr_vector" */
Gomega = MwalkInitialForm(G, curr_weight);
#ifdef TIME_TEST
xtif=xtif+clock()-to;
#endif
/*
if(Overflow_Error == TRUE)
{
for(i=nV-1; i>=0; i--)
(*curr_weight)[i] = (*extra_curr_weight)[i];
delete extra_curr_weight;
goto LAST_GB_ALT2;
}
*/
oldRing = currRing;
/* define a new ring that its ordering is "(a(curr_weight),lp) */
if (rParameter(currRing) != NULL)
{
DefRingPar(curr_weight);
}
else
{
rChangeCurrRing(VMrDefault(curr_weight));
}
newRing = currRing;
Gomega1 = idrMoveR(Gomega, oldRing,currRing);
#ifdef TIME_TEST
to = clock();
#endif
/* compute a reduced Groebner basis of <Gomega> w.r.t. "newRing" */
M = MstdhomCC(Gomega1);
#ifdef TIME_TEST
xtstd=xtstd+clock()-to;
#endif
/* change the ring to oldRing */
rChangeCurrRing(oldRing);
M1 = idrMoveR(M, newRing,currRing);
Gomega2 = idrMoveR(Gomega1, newRing,currRing);
#ifdef TIME_TEST
to = clock();
#endif
/* compute the reduced Groebner basis of <G> w.r.t. "newRing"
by the liftig process */
F = MLifttwoIdeal(Gomega2, M1, G);
#ifdef TIME_TEST
xtlift=xtlift+clock()-to;
#endif
idDelete(&M1);
idDelete(&Gomega2);
idDelete(&G);
/* change the ring to newRing */
rChangeCurrRing(newRing);
F1 = idrMoveR(F, oldRing,currRing);
#ifdef TIME_TEST
to = clock();
#endif
/* reduce the Groebner basis <G> w.r.t. newRing */
G = kInterRedCC(F1, NULL);
#ifdef TIME_TEST
xtred=xtred+clock()-to;
#endif
idDelete(&F1);
if(endwalks == 1)
break;
NEXT_VECTOR:
#ifdef TIME_TEST
to = clock();
#endif
/* compute a next weight vector */
next_weight = MkInterRedNextWeight(curr_weight,target_weight, G);
#ifdef TIME_TEST
xtnw=xtnw+clock()-to;
#endif
#ifdef PRINT_VECTORS
MivString(curr_weight, target_weight, next_weight);
#endif
if(Overflow_Error == TRUE)
{
/*
ivString(next_weight, "omega");
PrintS("\n// ** The weight vector does NOT stay in Cone!!\n");
*/
#ifdef TEST_OVERFLOW
goto TEST_OVERFLOW_OI;
#endif
newRing = currRing;
if (rParameter(currRing) != NULL)
{
DefRingPar(target_weight);
}
else
{
rChangeCurrRing(VMrDefault(target_weight)); // Aenderung
}
F1 = idrMoveR(G, newRing,currRing);
G = MstdCC(F1);
idDelete(&F1);
newRing = currRing;
break;
}
if(MivComp(next_weight, ivNull) == 1)
{
newRing = currRing;
delete next_weight;
break;
}
if(MivComp(next_weight, target_weight) == 1)
{
if(MivSame(target_weight, exivlp)==1)
{
// LAST_GB_ALT2:
//nOverflow_Error = Overflow_Error;
#ifdef TIME_TEST
tproc = clock()-xftinput;
#endif
//Print("\n// takes %d steps and calls the recursion of level 2:", nwalk);
/* call the changed perturbation walk algorithm with degree 2 */
G = Rec_LastGB(G, curr_weight, target_weight, 2,1);
newRing = currRing;
delete next_weight;
break;
}
endwalks = 1;
}
for(i=nV-1; i>=0; i--)
{
//(*extra_curr_weight)[i] = (*curr_weight)[i];
(*curr_weight)[i] = (*next_weight)[i];
}
delete next_weight;
}
#ifdef TEST_OVERFLOW
TEST_OVERFLOW_OI:
#endif
rChangeCurrRing(XXRing);
G = idrMoveR(G, newRing,currRing);
delete ivNull;
delete exivlp;
#ifdef TIME_TEST
/*Print("\n// \"Main procedure\" took %d steps dnd %.2f sec. Overflow_Error (%d)",
nwalk, ((double) tproc)/1000000, nOverflow_Error);
*/
TimeStringFractal(xftinput, tostd, xtif, xtstd, xtextra,xtlift, xtred,xtnw);
//Print("\n// pSetm_Error = (%d)", ErrorCheck());
//Print("\n// Overflow_Error? (%d)", nOverflow_Error);
//Print("\n// Awalk2 took %d steps!!", nstep);
#endif
return(G);
}
Print
#define Print
Definition emacs.cc:80
Rec_LastGB
static ideal Rec_LastGB(ideal G, intvec *curr_weight, intvec *orig_target_weight, int tp_deg, int npwinc)
Definition walk.cc:3934

## Mfpertvector()

intvec * Mfpertvector | ( | ideal | G,
|  | intvec * | iv )

Definition at line 1513 of file walk.cc.

{
int i, j, nG = IDELEMS(G);
int nV = currRing->N;
int niv = nV*nV;
// Calculate maxA = Max(A2) + Max(A3) + ... + Max(AnV),
// where the Ai are the i-te rows of the matrix 'targer_ord'.
int ntemp, maxAi, maxA=0;
for(i=1; i<nV; i++)
{
maxAi = (*ivtarget)[i*nV];
if(maxAi<0)
{
maxAi = -maxAi;
}
for(j=i*nV+1; j<(i+1)*nV; j++)
{
ntemp = (*ivtarget)[j];
if(ntemp < 0)
{
ntemp = -ntemp;
}
if(ntemp > maxAi)
{
maxAi = ntemp;
}
}
maxA = maxA + maxAi;
}
intvec* ivUnit = Mivdp(nV);
// Calculate inveps = 1/eps, where 1/eps > deg(p)*maxA for all p in G.
mpz_t tot_deg; mpz_init(tot_deg);
mpz_t maxdeg; mpz_init(maxdeg);
mpz_t inveps; mpz_init(inveps);
for(i=nG-1; i>=0; i--)
{
mpz_set_ui(maxdeg, MwalkWeightDegree(G->m[i], ivUnit));
if (mpz_cmp(maxdeg, tot_deg) > 0 )
{
mpz_set(tot_deg, maxdeg);
}
}
delete ivUnit;
//inveps = (tot_deg * maxA) + 1;
mpz_mul_ui(inveps, tot_deg, maxA);
mpz_add_ui(inveps, inveps, 1);
// takes "small" inveps
#ifdef INVEPS_SMALL_IN_FRACTAL
if(mpz_cmp_ui(inveps, nV)>0 && nV > 3)
{
mpz_cdiv_q_ui(inveps, inveps, nV);
}
// choose the small inverse epsilon
#endif
// PrintLn(); mpz_out_str(stdout, 10, inveps);
// Calculate the perturbed target orders:
mpz_t *ivtemp=(mpz_t *)omAlloc(nV*sizeof(mpz_t));
mpz_t *pert_vector=(mpz_t *)omAlloc(niv*sizeof(mpz_t));
for(i=0; i < nV; i++)
{
mpz_init_set_si(ivtemp[i], (*ivtarget)[i]);
mpz_init_set_si(pert_vector[i], (*ivtarget)[i]);
}
mpz_t ztmp; mpz_init(ztmp);
// BOOLEAN isneg = FALSE;
for(i=1; i<nV; i++)
{
for(j=0; j<nV; j++)
{
mpz_mul(ztmp, inveps, ivtemp[j]);
if((*ivtarget)[i*nV+j]<0)
{
mpz_sub_ui(ivtemp[j], ztmp, -(*ivtarget)[i*nV+j]);
}
else
{
mpz_add_ui(ivtemp[j], ztmp,(*ivtarget)[i*nV+j]);
}
}
for(j=0; j<nV; j++)
{
mpz_init_set(pert_vector[i*nV+j],ivtemp[j]);
}
}
// 2147483647 is max. integer representation in SINGULAR
mpz_t sing_int;
mpz_init_set_ui(sing_int, 2147483647);
intvec* result = new intvec(niv);
BOOLEAN nflow = FALSE;
// computes gcd
mpz_set(ztmp, pert_vector[0]);
for(i=0; i<niv; i++)
{
mpz_gcd(ztmp, ztmp, pert_vector[i]);
if(mpz_cmp_si(ztmp, 1)==0)
{
break;
}
}
for(i=0; i<niv; i++)
{
mpz_divexact(pert_vector[i], pert_vector[i], ztmp);
(* result)[i] = mpz_get_si(pert_vector[i]);
}
//CHECK_OVERFLOW:
for(i=0; i<niv; i++)
{
if(mpz_cmp(pert_vector[i], sing_int)>0)
{
if(nflow == FALSE)
{
Xnlev = i / nV;
nflow = TRUE;
Overflow_Error = TRUE;
Print("\n// Xlev = %d and the %d-th element is", Xnlev, i+1);
PrintS("\n// ** OVERFLOW in \"Mfpertvector\": ");
mpz_out_str( stdout, 10, pert_vector[i]);
PrintS(" is greater than 2147483647 (max. integer representation)");
Print("\n// So vector[%d] := %d is wrong!!", i+1, (*result)[i]);
}
}
}
if(Overflow_Error == TRUE)
{
ivString(result, "new_vector");
}
omFree(pert_vector);
omFree(ivtemp);
mpz_clear(ztmp);
mpz_clear(tot_deg);
mpz_clear(maxdeg);
mpz_clear(inveps);
mpz_clear(sing_int);
rComplete(currRing);
for(j=0; j<IDELEMS(G); j++)
{
poly p=G->m[j];
while(p!=NULL)
{
p_Setm(p,currRing);
pIter(p);
}
}
return result;
}
p
int p
Definition cfModGcd.cc:4086
j
int j
Definition facHensel.cc:110
pIter
#define pIter(p)
Definition monomials.h:37
omAlloc
#define omAlloc(size)
Definition omAllocDecl.h:210
omFree
#define omFree(addr)
Definition omAllocDecl.h:261
p_Setm
static void p_Setm(poly p, const ring r)
Definition p_polys.h:235
PrintS
void PrintS(const char *s)
Definition reporter.cc:288
rComplete
BOOLEAN rComplete(ring r, int force)
this needs to be called whenever a new ring is created: new fields in ring are created (like VarOffse...
Definition ring.cc:3527
IDELEMS
#define IDELEMS(i)
Definition simpleideals.h:23
ivString
static void ivString(intvec *iv, const char *ch)
Definition walk.cc:493
Xnlev
VAR int Xnlev
Definition walk.cc:1512
MwalkWeightDegree
static int MwalkWeightDegree(poly p, intvec *weight_vector)
Definition walk.cc:669
Mivdp
intvec * Mivdp(int nR)
Definition walk.cc:1008

## Mfrwalk()

ideal Mfrwalk | ( | ideal | G,
|  | intvec * | ivstart,
|  | intvec * | ivtarget,
|  | int | weight_rad,
|  | int | reduction,
|  | int | printout )

Definition at line 8213 of file walk.cc.

{
BITSET save1 = si_opt_1; // save current options
//check that weight radius is valid
if(weight_rad < 0)
{
WerrorS("Invalid radius.\n");
return NULL;
}
if(reduction == 0)
{
si_opt_1 &= (~Sy_bit(OPT_REDSB)); // no reduced Groebner basis
si_opt_1 &= (~Sy_bit(OPT_REDTAIL)); // not tail reductions
}
Set_Error(FALSE);
Overflow_Error = FALSE;
//Print("// pSetm_Error = (%d)", ErrorCheck());
//Print("\n// ring ro = %s;", rString(currRing));
nnflow = 0;
Xngleich = 0;
Xcall = 0;
#ifdef TIME_TEST
xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0; xtextra=0;
xftinput = clock();
#endif
ring oldRing = currRing;
int i, nV = currRing->N;
XivNull = new intvec(nV);
Xivinput = ivtarget;
ngleich = 0;
#ifdef TIME_TEST
to=clock();
#endif
ideal I = MstdCC(G);
G = NULL;
#ifdef TIME_TEST
xftostd=clock()-to;
#endif
Xsigma = ivstart;
Xnlev=nV;
#ifdef FIRST_STEP_FRACTAL
ideal Gw = MwalkInitialForm(I, ivstart);
for(i=IDELEMS(Gw)-1; i>=0; i--)
{
if((Gw->m[i]!=NULL) // len >=0
&& (Gw->m[i]->next!=NULL) // len >=1
&& (Gw->m[i]->next->next!=NULL)) // len >=2
{
intvec* iv_dp = MivUnit(nV); // define (1,1,...,1)
intvec* Mdp;
if(ivstart->length() == nV)
{
if(MivSame(ivstart, iv_dp) != 1)
Mdp = MivWeightOrderdp(ivstart);
else
Mdp = MivMatrixOrderdp(nV);
}
else
{
Mdp = ivstart;
}
Xsigma = Mfpertvector(I, Mdp);
Overflow_Error = FALSE;
delete Mdp;
delete iv_dp;
break;
}
}
idDelete(&Gw);
#endif
ideal I1;
intvec* Mlp;
Xivlp = Mivlp(nV);
if(ivtarget->length() == nV)
{
if(MivComp(ivtarget, Xivlp) != 1)
{
if (rParameter(currRing) != NULL)
DefRingPar(ivtarget);
else
rChangeCurrRing(VMrDefault(ivtarget));
I1 = idrMoveR(I, oldRing,currRing);
Mlp = MivWeightOrderlp(ivtarget);
Xtau = Mfpertvector(I1, Mlp);
}
else
{
if (rParameter(currRing) != NULL)
DefRingParlp();
else
VMrDefaultlp();
I1 = idrMoveR(I, oldRing,currRing);
Mlp = MivMatrixOrderlp(nV);
Xtau = Mfpertvector(I1, Mlp);
}
}
else
{
rChangeCurrRing(VMatrDefault(ivtarget));
I1 = idrMoveR(I,oldRing,currRing);
Mlp = ivtarget;
Xtau = Mfpertvector(I1, Mlp);
}
delete Mlp;
Overflow_Error = FALSE;
//ivString(Xsigma, "Xsigma");
//ivString(Xtau, "Xtau");
id_Delete(&I, oldRing);
ring tRing = currRing;
if(ivtarget->length() == nV)
{
/*
if (rParameter(currRing) != NULL)
DefRingPar(ivstart);
else
rChangeCurrRing(VMrDefault(ivstart));
*/
rChangeCurrRing(VMrRefine(ivtarget,ivstart));
}
else
{
//rChangeCurrRing(VMatrDefault(ivstart));
rChangeCurrRing(VMatrRefine(ivtarget,ivstart));
}
I = idrMoveR(I1,tRing,currRing);
#ifdef TIME_TEST
to=clock();
#endif
ideal J = MstdCC(I);
idDelete(&I);
#ifdef TIME_TEST
xftostd=xftostd+clock()-to;
#endif
ideal resF;
ring helpRing = currRing;
J = rec_r_fractal_call(J,1,ivtarget,weight_rad,reduction,printout);
//idString(J,"//*** Mfrwalk: J");
//Print("\n//** Mfrwalk hier (1)\n");
rChangeCurrRing(oldRing);
//Print("\n//** Mfrwalk hier (2)\n");
resF = idrMoveR(J, helpRing,currRing);
//Print("\n//** Mfrwalk hier (3)\n");
//idSkipZeroes(resF);
//Print("\n//** Mfrwalk hier (4)\n");
si_opt_1 = save1; //set original options, e. g. option(RedSB)
delete Xivlp;
//delete Xsigma;
delete Xtau;
delete XivNull;
//Print("\n//** Mfrwalk hier (5)\n");
#ifdef TIME_TEST
TimeStringFractal(xftinput, xftostd, xtif, xtstd, xtextra,
xtlift, xtred, xtnw);
// Print("\n// pSetm_Error = (%d)", ErrorCheck());
Print("\n// Overflow_Error? (%d)\n", Overflow_Error);
Print("\n// the numbers of Overflow_Error (%d)", nnflow);
#endif
//Print("\n//** Mfrwalk hier (6)\n");
//idString(resF,"resF");
//Print("\n//** Mfrwalk hier (7)\n");
return(resF);
}
BITSET
#define BITSET
Definition auxiliary.h:85
WerrorS
void WerrorS(const char *s)
Definition feFopen.cc:24
si_opt_1
VAR unsigned si_opt_1
Definition options.c:5
OPT_REDTAIL
#define OPT_REDTAIL
Definition options.h:92
OPT_REDSB
#define OPT_REDSB
Definition options.h:77
Sy_bit
#define Sy_bit(x)
Definition options.h:31
MivWeightOrderdp
intvec * MivWeightOrderdp(intvec *ivstart)
Definition walk.cc:1457
Xtau
VAR intvec * Xtau
Definition walk.cc:4508
VMrRefine
static ring VMrRefine(intvec *va, intvec *vb)
Definition walk.cc:2732
rec_r_fractal_call
static ideal rec_r_fractal_call(ideal G, int nlev, intvec *ivtarget, int weight_rad, int reduction, int printout)
Definition walk.cc:7454
Xivlp
VAR intvec * Xivlp
Definition walk.cc:4511
MivWeightOrderlp
intvec * MivWeightOrderlp(intvec *ivstart)
Definition walk.cc:1437
XivNull
VAR intvec * XivNull
Definition walk.cc:6928
Xcall
VAR int Xcall
Definition walk.cc:6946
DefRingParlp
static void DefRingParlp(void)
Definition walk.cc:2989
VMatrRefine
static ring VMatrRefine(intvec *va, intvec *vb)
Definition walk.cc:2842
Xivinput
VAR intvec * Xivinput
Definition walk.cc:4510
Xsigma
VAR intvec * Xsigma
Definition walk.cc:4507
MivMatrixOrderlp
intvec * MivMatrixOrderlp(int nV)
Definition walk.cc:1402
ngleich
VAR int ngleich
Definition walk.cc:4506
Mfpertvector
intvec * Mfpertvector(ideal G, intvec *ivtarget)
Definition walk.cc:1513
VMatrDefault
static ring VMatrDefault(intvec *va)
Definition walk.cc:2791
VMrDefaultlp
static void VMrDefaultlp(void)
Definition walk.cc:2899
nnflow
VAR int nnflow
Definition walk.cc:6945
Xngleich
VAR int Xngleich
Definition walk.cc:6947

## Mfwalk()

ideal Mfwalk | ( | ideal | G,
|  | intvec * | ivstart,
|  | intvec * | ivtarget,
|  | int | reduction,
|  | int | printout )

Definition at line 8032 of file walk.cc.

{
BITSET save1 = si_opt_1; // save current options
if(reduction == 0)
{
si_opt_1 &= (~Sy_bit(OPT_REDSB)); // no reduced Groebner basis
//si_opt_1 &= (~Sy_bit(OPT_REDTAIL)); // not tail reductions
}
Set_Error(FALSE);
Overflow_Error = FALSE;
//Print("// pSetm_Error = (%d)", ErrorCheck());
//Print("\n// ring ro = %s;", rString(currRing));
nnflow = 0;
Xngleich = 0;
Xcall = 0;
#ifdef TIME_TEST
xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0; xtextra=0;
xftinput = clock();
#endif
ring oldRing = currRing;
int i, nV = currRing->N;
XivNull = new intvec(nV);
Xivinput = ivtarget;
ngleich = 0;
#ifdef TIME_TEST
to=clock();
#endif
ideal I = MstdCC(G);
G = NULL;
#ifdef TIME_TEST
xftostd=clock()-to;
#endif
Xsigma = ivstart;
Xnlev=nV;
#ifdef FIRST_STEP_FRACTAL
ideal Gw = MwalkInitialForm(I, ivstart);
for(i=IDELEMS(Gw)-1; i>=0; i--)
{
if((Gw->m[i]!=NULL) // len >=0
&& (Gw->m[i]->next!=NULL) // len >=1
&& (Gw->m[i]->next->next!=NULL)) // len >=2
{
intvec* iv_dp = MivUnit(nV); // define (1,1,...,1)
intvec* Mdp;
if(ivstart->length() == nV)
{
if(MivSame(ivstart, iv_dp) != 1)
Mdp = MivWeightOrderdp(ivstart);
else
Mdp = MivMatrixOrderdp(nV);
}
else
{
Mdp = ivstart;
}
Xsigma = Mfpertvector(I, Mdp);
Overflow_Error = FALSE;
delete Mdp;
delete iv_dp;
break;
}
}
idDelete(&Gw);
#endif
ideal I1;
intvec* Mlp;
Xivlp = Mivlp(nV);
if(ivtarget->length() == nV)
{
if(MivComp(ivtarget, Xivlp) != 1)
{
if (rParameter(currRing) != NULL)
DefRingPar(ivtarget);
else
rChangeCurrRing(VMrDefault(ivtarget));
I1 = idrMoveR(I, oldRing,currRing);
Mlp = MivWeightOrderlp(ivtarget);
Xtau = Mfpertvector(I1, Mlp);
}
else
{
if (rParameter(currRing) != NULL)
DefRingParlp();
else
VMrDefaultlp();
I1 = idrMoveR(I, oldRing,currRing);
Mlp = MivMatrixOrderlp(nV);
Xtau = Mfpertvector(I1, Mlp);
}
}
else
{
rChangeCurrRing(VMatrDefault(ivtarget));
I1 = idrMoveR(I,oldRing,currRing);
Mlp = ivtarget;
Xtau = Mfpertvector(I1, Mlp);
}
delete Mlp;
Overflow_Error = FALSE;
//ivString(Xsigma, "Xsigma");
//ivString(Xtau, "Xtau");
id_Delete(&I, oldRing);
ring tRing = currRing;
if(ivtarget->length() == nV)
{
/*
if (rParameter(currRing) != NULL)
DefRingPar(ivstart);
else
rChangeCurrRing(VMrDefault(ivstart));
*/
rChangeCurrRing(VMrRefine(ivtarget,ivstart));
}
else
{
//rChangeCurrRing(VMatrDefault(ivstart));
rChangeCurrRing(VMatrRefine(ivtarget,ivstart));
}
I = idrMoveR(I1,tRing,currRing);
#ifdef TIME_TEST
to=clock();
#endif
ideal J = MstdCC(I);
idDelete(&I);
#ifdef TIME_TEST
xftostd=xftostd+clock()-to;
#endif
ideal resF;
ring helpRing = currRing;
J = rec_fractal_call(J,1,ivtarget,reduction,printout);
//idString(J,"//** Mfwalk: J");
rChangeCurrRing(oldRing);
//Print("\n//Mfwalk: (2)\n");
resF = idrMoveR(J, helpRing,currRing);
//Print("\n//Mfwalk: (3)\n");
idSkipZeroes(resF);
//Print("\n//Mfwalk: (4)\n");
si_opt_1 = save1; //set original options, e. g. option(RedSB)
delete Xivlp;
//delete Xsigma;
delete Xtau;
delete XivNull;
//Print("\n//Mfwalk: (5)\n");
#ifdef TIME_TEST
TimeStringFractal(xftinput, xftostd, xtif, xtstd, xtextra,
xtlift, xtred, xtnw);
//Print("\n// pSetm_Error = (%d)", ErrorCheck());
Print("\n// Overflow_Error? (%d)\n", Overflow_Error);
Print("\n// the numbers of Overflow_Error (%d)", nnflow);
#endif
//Print("\n//Mfwalk: (6)\n");
//idString(resF,"//** Mfwalk: resF");
return(idCopy(resF));
}
idCopy
ideal idCopy(ideal A)
Definition ideals.h:60
idSkipZeroes
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
Definition simpleideals.cc:201
rec_fractal_call
static ideal rec_fractal_call(ideal G, int nlev, intvec *ivtarget, int reduction, int printout)
Definition walk.cc:6952

## MidLift()

ideal MidLift | ( | ideal | Gomega,
|  | ideal | M )

## Mivdp()

intvec * Mivdp | ( | int | nR | ) |

Definition at line 1008 of file walk.cc.

{
int i;
intvec* ivm = new intvec(nR);
for(i=nR-1; i>=0; i--)
{
(*ivm)[i] = 1;
}
return ivm;
}

## Mivlp()

intvec * Mivlp | ( | int | nR | ) |

Definition at line 1023 of file walk.cc.

{
intvec* ivm = new intvec(nR);
(*ivm)[0] = 1;
return ivm;
}

## MivMatrixOrder()

intvec * MivMatrixOrder | ( | intvec * | iv | ) |

Definition at line 964 of file walk.cc.

{
int i, nR = iv->length();
intvec* ivm = new intvec(nR*nR);
for(i=0; i<nR; i++)
{
(*ivm)[i] = (*iv)[i];
}
for(i=1; i<nR; i++)
{
(*ivm)[i*nR+i-1] = 1;
}
return ivm;
}

## MivMatrixOrderdp()

intvec * MivMatrixOrderdp | ( | int | iv | ) |

Definition at line 1418 of file walk.cc.

{
int i;
intvec* ivM = new intvec(nV*nV);
for(i=0; i<nV; i++)
{
(*ivM)[i] = 1;
}
for(i=1; i<nV; i++)
{
(*ivM)[(i+1)*nV - i] = -1;
}
return(ivM);
}

## MivMatrixOrderlp()

intvec * MivMatrixOrderlp | ( | int | nV | ) |

Definition at line 1402 of file walk.cc.

{
int i;
intvec* ivM = new intvec(nV*nV);
for(i=0; i<nV; i++)
{
(*ivM)[i*nV + i] = 1;
}
return(ivM);
}

## Mivperttarget()

intvec * Mivperttarget | ( | ideal | G,
|  | int | ndeg )

## MivSame()

int MivSame | ( | intvec * | u,
|  | intvec * | v )

Definition at line 894 of file walk.cc.

{
assume(u->length() == v->length());
int i, niv = u->length();
for (i=0; i<niv; i++)
{
if ((*u)[i] != (*v)[i])
{
return 0;
}
}
return 1;
}

## MivUnit()

intvec * MivUnit | ( | int | nV | ) |

Definition at line 1497 of file walk.cc.

{
int i;
intvec* ivM = new intvec(nV);
for(i=nV-1; i>=0; i--)
{
(*ivM)[i] = 1;
}
return(ivM);
}

## MivWeightOrderdp()

intvec * MivWeightOrderdp | ( | intvec * | ivstart | ) |

Definition at line 1457 of file walk.cc.

{
int i;
int nV = ivstart->length();
intvec* ivM = new intvec(nV*nV);
for(i=0; i<nV; i++)
{
(*ivM)[i] = (*ivstart)[i];
}
for(i=0; i<nV; i++)
{
(*ivM)[nV+i] = 1;
}
for(i=2; i<nV; i++)
{
(*ivM)[(i+1)*nV - i] = -1;
}
return(ivM);
}

## MivWeightOrderlp()

intvec * MivWeightOrderlp | ( | intvec * | ivstart | ) |

Definition at line 1437 of file walk.cc.

{
int i;
int nV = ivstart->length();
intvec* ivM = new intvec(nV*nV);
for(i=0; i<nV; i++)
{
(*ivM)[i] = (*ivstart)[i];
}
for(i=1; i<nV; i++)
{
(*ivM)[i*nV + i-1] = 1;
}
return(ivM);
}

## MkInterRedNextWeight()

intvec * MkInterRedNextWeight | ( | intvec * | iva,
|  | intvec * | ivb,
|  | ideal | G )

Definition at line 2571 of file walk.cc.

{
intvec* tmp = new intvec(iva->length());
intvec* result;
if(G == NULL)
{
return tmp;
}
if(MivComp(iva, ivb) == 1)
{
return tmp;
}
result = MwalkNextWeightCC(iva, ivb, G);
if(MivComp(result, iva) == 1)
{
delete result;
return tmp;
}
delete tmp;
return result;
}
MwalkNextWeightCC
static intvec * MwalkNextWeightCC(intvec *curr_weight, intvec *target_weight, ideal G)
Definition walk.cc:2229

## MLiftLmalG()

ideal MLiftLmalG | ( | ideal | L,
|  | ideal | G )

## MLiftLmalGMin()

ideal MLiftLmalGMin | ( | ideal | L,
|  | ideal | G )

## MLiftLmalGNew()

ideal MLiftLmalGNew | ( | ideal | Gomega,
|  | ideal | M,
|  | ideal | G )

## MPertNextWeight()

intvec * MPertNextWeight | ( | intvec * | iva,
|  | ideal | G,
|  | int | deg )

## MPertVectors()

intvec * MPertVectors | ( | ideal | G,
|  | intvec * | ivtarget,
|  | int | pdeg )

Definition at line 1089 of file walk.cc.

{
// ivtarget is a matrix order of a degree reverse lex. order
int nV = currRing->N;
//assume(pdeg <= nV && pdeg >= 0);
int i, j, nG = IDELEMS(G);
intvec* v_null = new intvec(nV);
// Check that the perturbed degree is valid
if(pdeg > nV || pdeg <= 0)
{
WerrorS("//** The perturbed degree is wrong!!");
return v_null;
}
delete v_null;
if(pdeg == 1)
{
return ivtarget;
}
mpz_t *pert_vector = (mpz_t*)omAlloc(nV*sizeof(mpz_t));
mpz_t *pert_vector1 = (mpz_t*)omAlloc(nV*sizeof(mpz_t));
for(i=0; i<nV; i++)
{
mpz_init_set_si(pert_vector[i], (*ivtarget)[i]);
mpz_init_set_si(pert_vector1[i], (*ivtarget)[i]);
}
// Calculate max1 = Max(A2)+Max(A3)+...+Max(Apdeg),
// where the Ai are the i-te rows of the matrix target_ord.
int ntemp, maxAi, maxA=0;
for(i=1; i<pdeg; i++)
{
maxAi = (*ivtarget)[i*nV];
if(maxAi<0)
{
maxAi = -maxAi;
}
for(j=i*nV+1; j<(i+1)*nV; j++)
{
ntemp = (*ivtarget)[j];
if(ntemp < 0)
{
ntemp = -ntemp;
}
if(ntemp > maxAi)
{
maxAi = ntemp;
}
}
maxA += maxAi;
}
// Calculate inveps = 1/eps, where 1/eps > totaldeg(p)*max1 for all p in G.
intvec* ivUnit = Mivdp(nV);
mpz_t tot_deg; mpz_init(tot_deg);
mpz_t maxdeg; mpz_init(maxdeg);
mpz_t inveps; mpz_init(inveps);
for(i=nG-1; i>=0; i--)
{
mpz_set_ui(maxdeg, MwalkWeightDegree(G->m[i], ivUnit));
if (mpz_cmp(maxdeg, tot_deg) > 0 )
{
mpz_set(tot_deg, maxdeg);
}
}
delete ivUnit;
mpz_mul_ui(inveps, tot_deg, maxA);
mpz_add_ui(inveps, inveps, 1);
// takes "small" inveps
#ifdef INVEPS_SMALL_IN_MPERTVECTOR
if(mpz_cmp_ui(inveps, pdeg)>0 && pdeg > 3)
{
// Print("\n// choose the\"small\" inverse epsilon := %d / %d = ", mpz_get_si(inveps), pdeg);
mpz_fdiv_q_ui(inveps, inveps, pdeg);
// mpz_out_str(stdout, 10, inveps);
}
#else
// PrintS("\n// the \"big\" inverse epsilon: ");
mpz_out_str(stdout, 10, inveps);
#endif
// pert(A1) = inveps^(pdeg-1)*A1 + inveps^(pdeg-2)*A2+...+A_pdeg,
// pert_vector := A1
for( i=1; i < pdeg; i++ )
{
for(j=0; j<nV; j++)
{
mpz_mul(pert_vector[j], pert_vector[j], inveps);
if((*ivtarget)[i*nV+j]<0)
{
mpz_sub_ui(pert_vector[j], pert_vector[j],-(*ivtarget)[i*nV+j]);
}
else
{
mpz_add_ui(pert_vector[j], pert_vector[j],(*ivtarget)[i*nV+j]);
}
}
}
// 2147483647 is max. integer representation in SINGULAR
mpz_t sing_int;
mpz_init_set_ui(sing_int, 2147483647);
mpz_t check_int;
mpz_init_set_ui(check_int, 100000);
mpz_t ztemp;
mpz_init(ztemp);
mpz_set(ztemp, pert_vector[0]);
for(i=1; i<nV; i++)
{
mpz_gcd(ztemp, ztemp, pert_vector[i]);
if(mpz_cmp_si(ztemp, 1) == 0)
{
break;
}
}
if(mpz_cmp_si(ztemp, 1) != 0)
{
for(i=0; i<nV; i++)
{
mpz_divexact(pert_vector[i], pert_vector[i], ztemp);
}
}
for(i=0; i<nV; i++)
{
if(mpz_cmp(pert_vector[i], check_int)>=0)
{
for(j=0; j<nV; j++)
{
mpz_fdiv_q_ui(pert_vector1[j], pert_vector[j], 100);
}
}
}
intvec* result = new intvec(nV);
int ntrue=0;
for(i=0; i<nV; i++)
{
(*result)[i] = mpz_get_si(pert_vector1[i]);
if(mpz_cmp(pert_vector1[i], sing_int)>=0)
{
ntrue++;
}
}
if(ntrue > 0 || test_w_in_ConeCC(G,result)==0)
{
ntrue=0;
for(i=0; i<nV; i++)
{
(*result)[i] = mpz_get_si(pert_vector[i]);
if(mpz_cmp(pert_vector[i], sing_int)>=0)
{
ntrue++;
if(Overflow_Error == FALSE)
{
Overflow_Error = TRUE;
PrintS("\n// ** OVERFLOW in \"MPertvectors\": ");
mpz_out_str( stdout, 10, pert_vector[i]);
PrintS(" is greater than 2147483647 (max. integer representation)");
Print("\n// So vector[%d] := %d is wrong!!", i+1, (*result)[i]);
}
}
}
if(Overflow_Error == TRUE)
{
ivString(result, "pert_vector");
Print("\n// %d element(s) of it is overflow!!", ntrue);
}
}
mpz_clear(ztemp);
mpz_clear(sing_int);
mpz_clear(check_int);
omFree(pert_vector);
omFree(pert_vector1);
mpz_clear(tot_deg);
mpz_clear(maxdeg);
mpz_clear(inveps);
rComplete(currRing);
for(j=0; j<IDELEMS(G); j++)
{
poly p=G->m[j];
while(p!=NULL)
{
p_Setm(p,currRing); pIter(p);
}
}
return result;
}
test_w_in_ConeCC
static int test_w_in_ConeCC(ideal G, intvec *iv)
Definition walk.cc:786

## MPertVectorslp()

intvec * MPertVectorslp | ( | ideal | G,
|  | intvec * | ivtarget,
|  | int | pdeg )

Definition at line 1300 of file walk.cc.

{
// ivtarget is a matrix order of the lex. order
int nV = currRing->N;
//assume(pdeg <= nV && pdeg >= 0);
int i, j, nG = IDELEMS(G);
intvec* pert_vector = new intvec(nV);
//Checking that the perturbated degree is valid
if(pdeg > nV || pdeg <= 0)
{
WerrorS("//** The perturbed degree is wrong!!");
return pert_vector;
}
for(i=0; i<nV; i++)
{
(*pert_vector)[i]=(*ivtarget)[i];
}
if(pdeg == 1)
{
return pert_vector;
}
// Calculate max1 = Max(A2)+Max(A3)+...+Max(Apdeg),
// where the Ai are the i-te rows of the matrix target_ord.
int ntemp, maxAi, maxA=0;
for(i=1; i<pdeg; i++)
{
maxAi = (*ivtarget)[i*nV];
for(j=i*nV+1; j<(i+1)*nV; j++)
{
ntemp = (*ivtarget)[j];
if(ntemp > maxAi)
{
maxAi = ntemp;
}
}
maxA += maxAi;
}
// Calculate inveps := 1/eps, where 1/eps > deg(p)*max1 for all p in G.
int inveps, tot_deg = 0, maxdeg;
intvec* ivUnit = Mivdp(nV);//19.02
for(i=nG-1; i>=0; i--)
{
// maxdeg = pTotaldegree(G->m[i], currRing); //it's wrong for ex1,2,rose
maxdeg = MwalkWeightDegree(G->m[i], ivUnit);
if (maxdeg > tot_deg )
{
tot_deg = maxdeg;
}
}
delete ivUnit;
inveps = (tot_deg * maxA) + 1;
#ifdef INVEPS_SMALL_IN_FRACTAL
// Print("\n// choose the\"small\" inverse epsilon := %d / %d = ", inveps, pdeg);
if(inveps > pdeg && pdeg > 3)
{
inveps = inveps / pdeg;
}
// Print(" %d", inveps);
#else
PrintS("\n// the \"big\" inverse epsilon %d", inveps);
#endif
// Pert(A1) = inveps^(pdeg-1)*A1 + inveps^(pdeg-2)*A2+...+A_pdeg
for ( i=1; i < pdeg; i++ )
{
for(j=0; j<nV; j++)
{
(*pert_vector)[j] = inveps*((*pert_vector)[j]) + (*ivtarget)[i*nV+j];
}
}
int temp = (*pert_vector)[0];
for(i=1; i<nV; i++)
{
temp = gcd(temp, (*pert_vector)[i]);
if(temp == 1)
{
break;
}
}
if(temp != 1)
{
for(i=0; i<nV; i++)
{
(*pert_vector)[i] = (*pert_vector)[i] / temp;
}
}
intvec* result = pert_vector;
delete pert_vector;
return result;
}
gcd
static long gcd(const long a, const long b)
Definition walk.cc:533

## Mprwalk()

ideal Mprwalk | ( | ideal | Go,
|  | intvec * | orig_M,
|  | intvec * | target_M,
|  | int | weight_rad,
|  | int | op_deg,
|  | int | tp_deg,
|  | int | nP,
|  | int | reduction,
|  | int | printout )

Definition at line 6389 of file walk.cc.

{
BITSET save1 = si_opt_1; // save current options
if(reduction == 0)
{
si_opt_1 &= (~Sy_bit(OPT_REDSB)); // no reduced Groebner basis
si_opt_1 &= (~Sy_bit(OPT_REDTAIL)); // not tail reductions
}
Set_Error(FALSE);
Overflow_Error = FALSE;
//Print("// pSetm_Error = (%d)", ErrorCheck());
#ifdef TIME_TEST
clock_t tinput, tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
xtextra=0;
xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0;
tinput = clock();
clock_t tim;
#endif
nstep = 0;
int i, ntwC=1, ntestw=1, nV = currRing->N; //polylength
//check that weight radius is valid
if(weight_rad < 0)
{
WerrorS("Invalid radius.\n");
return NULL;
}
//check that perturbation degree is valid
if(op_deg < 1 || tp_deg < 1 || op_deg > nV || tp_deg > nV)
{
WerrorS("Invalid perturbation degree.\n");
return NULL;
}
BOOLEAN endwalks = FALSE;
ideal Gomega, M, F, FF, G, Gomega1, Gomega2, M1,F1,Eresult,ssG;
ring newRing, oldRing, TargetRing;
intvec* iv_M;
intvec* iv_M_dp;
intvec* iv_M_lp;
intvec* exivlp = Mivlp(nV);
intvec* curr_weight = new intvec(nV);
intvec* target_weight = new intvec(nV);
for(i=0; i<nV; i++)
{
(*curr_weight)[i] = (*orig_M)[i];
(*target_weight)[i] = (*target_M)[i];
}
intvec* orig_target = target_weight;
intvec* pert_target_vector = target_weight;
intvec* ivNull = new intvec(nV);
intvec* iv_dp = MivUnit(nV);// define (1,1,...,1)
#ifndef BUCHBERGER_ALG
intvec* hilb_func;
#endif
intvec* next_weight;
// to avoid (1,0,...,0) as the target vector
intvec* last_omega = new intvec(nV);
for(i=nV-1; i>0; i--)
(*last_omega)[i] = 1;
(*last_omega)[0] = 10000;
ring XXRing = currRing;
// perturbs the original vector
if(orig_M->length() == nV)
{
if(MivComp(curr_weight, iv_dp) == 1) //rOrdStr(currRing) := "dp"
{
#ifdef TIME_TEST
to = clock();
#endif
G = MstdCC(Go);
#ifdef TIME_TEST
tostd = clock()-to;
#endif
if(op_deg != 1)
{
iv_M_dp = MivMatrixOrderdp(nV);
curr_weight = MPertVectors(G, iv_M_dp, op_deg);
}
}
else
{
//define ring order := (a(curr_weight),lp);
if (rParameter(currRing) != NULL)
DefRingPar(curr_weight);
else
rChangeCurrRing(VMrDefault(curr_weight));
G = idrMoveR(Go, XXRing,currRing);
#ifdef TIME_TEST
to = clock();
#endif
G = MstdCC(G);
#ifdef TIME_TEST
tostd = clock()-to;
#endif
if(op_deg != 1)
{
iv_M_dp = MivMatrixOrder(curr_weight);
curr_weight = MPertVectors(G, iv_M_dp, op_deg);
}
}
}
else
{
rChangeCurrRing(VMatrDefault(orig_M));
G = idrMoveR(Go, XXRing,currRing);
#ifdef TIME_TEST
to = clock();
#endif
G = MstdCC(G);
#ifdef TIME_TEST
tostd = clock()-to;
#endif
if(op_deg != 1)
{
curr_weight = MPertVectors(G, orig_M, op_deg);
}
}
delete iv_dp;
if(op_deg != 1) delete iv_M_dp;
ring HelpRing = currRing;
// perturbs the target weight vector
if(target_M->length() == nV)
{
if(tp_deg > 1 && tp_deg <= nV)
{
if (rParameter(currRing) != NULL)
DefRingPar(target_weight);
else
rChangeCurrRing(VMrDefault(target_weight));
TargetRing = currRing;
ssG = idrMoveR(G,HelpRing,currRing);
if(MivSame(target_weight, exivlp) == 1)
{
iv_M_lp = MivMatrixOrderlp(nV);
target_weight = MPertVectors(ssG, iv_M_lp, tp_deg);
}
else
{
iv_M_lp = MivMatrixOrder(target_weight);
target_weight = MPertVectors(ssG, iv_M_lp, tp_deg);
}
delete iv_M_lp;
pert_target_vector = target_weight;
rChangeCurrRing(HelpRing);
G = idrMoveR(ssG, TargetRing,currRing);
}
}
else
{
if(tp_deg > 1 && tp_deg <= nV)
{
rChangeCurrRing(VMatrDefault(target_M));
TargetRing = currRing;
ssG = idrMoveR(G,HelpRing,currRing);
target_weight = MPertVectors(ssG, target_M, tp_deg);
}
}
if(printout > 0)
{
Print("\n//** Mprwalk: Random Perturbation Walk of degree (%d,%d):",op_deg,tp_deg);
ivString(curr_weight, "//** Mprwalk: new current weight");
ivString(target_weight, "//** Mprwalk: new target weight");
}
#ifdef TIME_TEST
to = clock();
#endif
Gomega = MwalkInitialForm(G, curr_weight); // compute an initial form ideal of <G> w.r.t. "curr_vector"
#ifdef TIME_TEST
tif = tif + clock()-to; //time for computing initial form ideal
#endif
while(1)
{
nstep ++;
#ifdef CHECK_IDEAL_MWALK
if(printout > 1)
{
idString(Gomega,"//** Mprwalk: Gomega");
}
#endif
if(reduction == 0 && nstep > 1)
{
FF = middleOfCone(G,Gomega);
if(FF != NULL)
{
idDelete(&G);
G = idCopy(FF);
idDelete(&FF);
goto NEXT_VECTOR;
}
}
#ifdef ENDWALKS
if(endwalks == TRUE)
{
if(printout > 0)
{
Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
//idElements(G, "G");
//headidString(G, "G");
}
}
#endif
#ifndef BUCHBERGER_ALG
if(isNolVector(curr_weight) == 0)
hilb_func = hFirstSeries(Gomega,NULL,NULL,curr_weight,currRing);
else
hilb_func = hFirstSeries(Gomega,NULL,NULL,last_omega,currRing);
#endif // BUCHBERGER_ALG
oldRing = currRing;
if(target_M->length() == nV)
{/*
// define a new ring with ordering "(a(curr_weight),lp)
if (rParameter(currRing) != NULL)
DefRingPar(curr_weight);
else
rChangeCurrRing(VMrDefault(curr_weight));
*/
rChangeCurrRing(VMrRefine(target_M,curr_weight));
}
else
{
rChangeCurrRing(VMatrRefine(target_M,curr_weight));
}
newRing = currRing;
Gomega1 = idrMoveR(Gomega, oldRing,currRing);
#ifdef ENDWALKS
if(endwalks == TRUE)
{
if(printout > 0)
{
Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
//idElements(Gomega1, "Gw");
//headidString(Gomega1, "headGw");
PrintS("\n// compute a rGB of Gw:\n");
}
#ifndef BUCHBERGER_ALG
ivString(hilb_func, "w");
#endif
}
#endif
#ifdef TIME_TEST
tim = clock();
to = clock();
#endif
// compute a reduced Groebner basis of <Gomega> w.r.t. "newRing"
#ifdef BUCHBERGER_ALG
M = MstdhomCC(Gomega1);
#else
M=kStd2(Gomega1,NULL,isHomog,NULL,hilb_func,0,NULL,curr_weight);
delete hilb_func;
#endif
#ifdef CHECK_IDEAL_MWALK
if(printout > 2)
{
idString(M,"//** Mprwalk: M");
}
#endif
#ifdef TIME_TEST
if(endwalks == TRUE)
{
xtstd = xtstd+clock()-to;
#ifdef ENDWALKS
Print("\n// time for the last std(Gw) = %.2f sec\n",
((double) clock())/1000000 -((double)tim) /1000000);
#endif
}
else
tstd=tstd+clock()-to;
#endif
/* change the ring to oldRing */
rChangeCurrRing(oldRing);
M1 = idrMoveR(M, newRing,currRing);
Gomega2 = idrMoveR(Gomega1, newRing,currRing);
#ifdef TIME_TEST
to=clock();
#endif
/* compute a representation of the generators of submod (M)
with respect to those of mod (Gomega).
Gomega is a reduced Groebner basis w.r.t. the current ring */
F = MLifttwoIdeal(Gomega2, M1, G);
#ifdef TIME_TEST
if(endwalks == FALSE)
tlift = tlift+clock()-to;
else
xtlift=clock()-to;
#endif
#ifdef CHECK_IDEAL_MWALK
if(printout > 2)
{
idString(F,"//** Mprwalk: F");
}
#endif
idDelete(&M1);
idDelete(&Gomega2);
idDelete(&G);
// change the ring to newRing
rChangeCurrRing(newRing);
if(reduction == 0)
{
G = idrMoveR(F,oldRing,currRing);
}
else
{
F1 = idrMoveR(F, oldRing,currRing);
if(printout > 2)
{
PrintS("\n //** Mprwalk: reduce the Groebner basis.\n");
}
#ifdef TIME_TEST
to=clock();
#endif
G = kInterRedCC(F1, NULL);
#ifdef TIME_TEST
if(endwalks == FALSE)
tred = tred+clock()-to;
else
xtred=clock()-to;
#endif
idDelete(&F1);
}
if(endwalks == TRUE)
break;
NEXT_VECTOR:
#ifdef TIME_TEST
to = clock();
#endif
next_weight = MkInterRedNextWeight(curr_weight,target_weight, G);
#ifdef TIME_TEST
tnw = tnw + clock() - to;
#endif
#ifdef TIME_TEST
to = clock();
#endif
// compute an initial form ideal of <G> w.r.t. "next_vector"
Gomega = MwalkInitialForm(G, next_weight);
#ifdef TIME_TEST
tif = tif + clock()-to; //time for computing initial form ideal
#endif
//lengthpoly(Gomega) = 1 if there is a polynomial in Gomega with at least 3 monomials and 0 otherwise
if(lengthpoly(Gomega) > 0)
{
if(printout > 1)
{
PrintS("\n Mpwalk: there is a polynomial in Gomega with at least 3 monomials.\n");
}
// low-dimensional facet of the cone
delete next_weight;
if(target_M->length() == nV)
{
iv_M = MivMatrixOrder(curr_weight);
}
else
{
iv_M = MivMatrixOrderRefine(curr_weight,target_M);
}
#ifdef TIME_TEST
to = clock();
#endif
next_weight = MWalkRandomNextWeight(G, iv_M, target_weight, weight_rad, op_deg);
#ifdef TIME_TEST
tnw = tnw + clock() - to;
#endif
idDelete(&Gomega);
#ifdef TIME_TEST
to = clock();
#endif
Gomega = MwalkInitialForm(G, next_weight);
#ifdef TIME_TEST
tif = tif + clock()-to; //time for computing initial form ideal
#endif
delete iv_M;
}
#ifdef PRINT_VECTORS
if(printout > 0)
{
MivString(curr_weight, target_weight, next_weight);
}
#endif
if(Overflow_Error == TRUE)
{
ntwC = 0;
//Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
//idElements(G, "G");
delete next_weight;
goto FINISH_160302;
}
if(MivComp(next_weight, ivNull) == 1){
newRing = currRing;
delete next_weight;
//Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
break;
}
if(MivComp(next_weight, target_weight) == 1)
endwalks = TRUE;
for(i=nV-1; i>=0; i--)
(*curr_weight)[i] = (*next_weight)[i];
delete next_weight;
}// end of while-loop
if(tp_deg != 1)
{
FINISH_160302:
if(target_M->length() == nV)
{
if(MivSame(orig_target, exivlp) == 1)
if (rParameter(currRing) != NULL)
DefRingParlp();
else
VMrDefaultlp();
else
if (rParameter(currRing) != NULL)
DefRingPar(orig_target);
else
rChangeCurrRing(VMrDefault(orig_target));
}
else
{
rChangeCurrRing(VMatrDefault(target_M));
}
TargetRing=currRing;
F1 = idrMoveR(G, newRing,currRing);
// check whether the pertubed target vector stays in the correct cone
if(ntwC != 0)
{
ntestw = test_w_in_ConeCC(F1, pert_target_vector);
}
if(ntestw != 1 || ntwC == 0)
{
if(ntestw != 1 && printout > 2)
{
#ifdef PRINT_VECTORS
ivString(pert_target_vector, "tau");
#endif
PrintS("\n// **Mprwalk: perturbed target vector doesn't stay in cone.");
Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
//idElements(F1, "G");
}
// LastGB is "better" than the kStd2 subroutine
#ifdef TIME_TEST
to=clock();
#endif
ideal eF1;
if(nP == 0 || tp_deg == 1 || MivSame(orig_target, exivlp) != 1 || target_M->length() != nV)
{
if(printout > 2)
{
PrintS("\n// ** Mprwalk: Call \"std\" to compute a Groebner basis.\n");
}
eF1 = MstdCC(F1);
idDelete(&F1);
}
else
{
if(printout > 2)
{
PrintS("\n// **Mprwalk: Call \"LastGB\" to compute a Groebner basis.\n");
}
rChangeCurrRing(newRing);
ideal F2 = idrMoveR(F1, TargetRing,currRing);
eF1 = LastGB(F2, curr_weight, tp_deg-1);
F2=NULL;
}
#ifdef TIME_TEST
xtextra=clock()-to;
#endif
ring exTargetRing = currRing;
rChangeCurrRing(XXRing);
Eresult = idrMoveR(eF1, exTargetRing,currRing);
}
else
{
rChangeCurrRing(XXRing);
Eresult = idrMoveR(F1, TargetRing,currRing);
}
}
else
{
rChangeCurrRing(XXRing);
Eresult = idrMoveR(G, newRing,currRing);
}
si_opt_1 = save1; //set original options, e. g. option(RedSB)
delete ivNull;
if(tp_deg != 1)
delete target_weight;
if(op_deg != 1 )
delete curr_weight;
delete exivlp;
delete last_omega;
#ifdef TIME_TEST
TimeStringFractal(tinput, tostd, tif+xtif, tstd+xtstd,0, tlift+xtlift, tred+xtred,
tnw+xtnw);
//Print("\n// pSetm_Error = (%d)", ErrorCheck());
//Print("\n// It took %d steps and Overflow_Error? (%d)\n", nstep, Overflow_Error);
#endif
if(printout > 0)
{
Print("\n//** Mprwalk: Perturbation Walk took %d steps.\n", nstep);
}
return(Eresult);
}
rString
char * rString(ring r)
Definition ring.cc:678
lengthpoly
static int lengthpoly(ideal G)
Definition walk.cc:3441
middleOfCone
static ideal middleOfCone(ideal G, ideal Gomega)
Definition walk.cc:3080
MWalkRandomNextWeight
static intvec * MWalkRandomNextWeight(ideal G, intvec *orig_M, intvec *target_weight, int weight_rad, int pert_deg)
Definition walk.cc:4517
MivMatrixOrderRefine
intvec * MivMatrixOrderRefine(intvec *iv, intvec *iw)
Definition walk.cc:984
LastGB
static ideal LastGB(ideal G, intvec *curr_weight, int tp_deg)
Definition walk.cc:3146
idString
static void idString(ideal L, const char *st)
Definition walk.cc:425

## Mpwalk()

ideal Mpwalk | ( | ideal | Go,
|  | int | op_deg,
|  | int | tp_deg,
|  | intvec * | curr_weight,
|  | intvec * | target_weight,
|  | int | nP,
|  | int | reduction,
|  | int | printout )

Definition at line 5948 of file walk.cc.

{
BITSET save1 = si_opt_1; // save current options
if(reduction == 0)
{
si_opt_1 &= (~Sy_bit(OPT_REDSB)); // no reduced Groebner basis
si_opt_1 &= (~Sy_bit(OPT_REDTAIL)); // not tail reductions
}
Set_Error(FALSE );
Overflow_Error = FALSE;
//Print("// pSetm_Error = (%d)", ErrorCheck());
#ifdef TIME_TEST
clock_t tinput, tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
xtextra=0;
xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0;
tinput = clock();
clock_t tim;
#endif
nstep = 0;
int i, ntwC=1, ntestw=1, nV = currRing->N;
//check that perturbation degree is valid
if(op_deg < 1 || tp_deg < 1 || op_deg > nV || tp_deg > nV)
{
WerrorS("Invalid perturbation degree.\n");
return NULL;
}
BOOLEAN endwalks = FALSE;
ideal Gomega, M, F, FF, G, Gomega1, Gomega2, M1,F1,Eresult,ssG;
ring newRing, oldRing, TargetRing;
intvec* iv_M_dp;
intvec* iv_M_lp;
intvec* exivlp = Mivlp(nV);
intvec* orig_target = target_weight;
intvec* pert_target_vector = target_weight;
intvec* ivNull = new intvec(nV);
intvec* iv_dp = MivUnit(nV);// define (1,1,...,1)
#ifndef BUCHBERGER_ALG
intvec* hilb_func;
#endif
intvec* next_weight;
// to avoid (1,0,...,0) as the target vector
intvec* last_omega = new intvec(nV);
for(i=nV-1; i>0; i--)
(*last_omega)[i] = 1;
(*last_omega)[0] = 10000;
ring XXRing = currRing;
#ifdef TIME_TEST
to = clock();
#endif
// perturbs the original vector
if(MivComp(curr_weight, iv_dp) == 1) //rOrdStr(currRing) := "dp"
{
G = MstdCC(Go);
#ifdef TIME_TEST
tostd = clock()-to;
#endif
if(op_deg != 1){
iv_M_dp = MivMatrixOrderdp(nV);
//ivString(iv_M_dp, "iv_M_dp");
curr_weight = MPertVectors(G, iv_M_dp, op_deg);
}
}
else
{
//define ring order := (a(curr_weight),lp);
/*
if (rParameter(currRing) != NULL)
DefRingPar(curr_weight);
else
rChangeCurrRing(VMrDefault(curr_weight));
*/
rChangeCurrRing(VMrRefine(target_weight,curr_weight));
G = idrMoveR(Go, XXRing,currRing);
G = MstdCC(G);
#ifdef TIME_TEST
tostd = clock()-to;
#endif
if(op_deg != 1){
iv_M_dp = MivMatrixOrder(curr_weight);
curr_weight = MPertVectors(G, iv_M_dp, op_deg);
}
}
delete iv_dp;
if(op_deg != 1) delete iv_M_dp;
ring HelpRing = currRing;
// perturbs the target weight vector
if(tp_deg > 1 && tp_deg <= nV)
{
/*
if (rParameter(currRing) != NULL)
DefRingPar(target_weight);
else
rChangeCurrRing(VMrDefault(target_weight));
*/
rChangeCurrRing(VMrRefine(target_weight,curr_weight));
TargetRing = currRing;
ssG = idrMoveR(G,HelpRing,currRing);
if(MivSame(target_weight, exivlp) == 1)
{
iv_M_lp = MivMatrixOrderlp(nV);
target_weight = MPertVectors(ssG, iv_M_lp, tp_deg);
}
else
{
iv_M_lp = MivMatrixOrder(target_weight);
target_weight = MPertVectors(ssG, iv_M_lp, tp_deg);
}
delete iv_M_lp;
pert_target_vector = target_weight;
rChangeCurrRing(HelpRing);
G = idrMoveR(ssG, TargetRing,currRing);
}
if(printout > 0)
{
Print("\n//** Mpwalk: Perturbation Walk of degree (%d,%d):",op_deg,tp_deg);
#ifdef PRINT_VECTORS
ivString(curr_weight, "//** Mpwalk: new current weight");
ivString(target_weight, "//** Mpwalk: new target weight");
#endif
}
while(1)
{
nstep ++;
#ifdef TIME_TEST
to = clock();
#endif
// compute an initial form ideal of <G> w.r.t. the weight vector
// "curr_weight"
Gomega = MwalkInitialForm(G, curr_weight);
#ifdef TIME_TEST
tif = tif + clock()-to;
#endif
#ifdef CHECK_IDEAL_MWALK
if(printout > 1)
{
idString(Gomega,"//** Mpwalk: Gomega");
}
#endif
if(reduction == 0 && nstep > 1)
{
FF = middleOfCone(G,Gomega);
if(FF != NULL)
{
idDelete(&G);
G = idCopy(FF);
idDelete(&FF);
goto NEXT_VECTOR;
}
}
#ifdef ENDWALKS
if(endwalks == TRUE)
{
if(printout > 0)
{
Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
}
//idElements(G, "G");
//headidString(G, "G");
}
#endif
#ifndef BUCHBERGER_ALG
if(isNolVector(curr_weight) == 0)
hilb_func = hFirstSeries(Gomega,NULL,NULL,curr_weight,currRing);
else
hilb_func = hFirstSeries(Gomega,NULL,NULL,last_omega,currRing);
#endif // BUCHBERGER_ALG
oldRing = currRing;
// define a new ring with ordering "(a(curr_weight),lp)
/*
if (rParameter(currRing) != NULL)
DefRingPar(curr_weight);
else
rChangeCurrRing(VMrDefault(curr_weight));
*/
rChangeCurrRing(VMrRefine(target_weight,curr_weight));
newRing = currRing;
Gomega1 = idrMoveR(Gomega, oldRing,currRing);
#ifdef ENDWALKS
if(endwalks==TRUE)
{
if(printout > 0)
{
Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
//idElements(Gomega1, "Gw");
//headidString(Gomega1, "headGw");
PrintS("\n// compute a rGB of Gw:\n");
}
#ifndef BUCHBERGER_ALG
ivString(hilb_func, "w");
#endif
}
#endif
#ifdef TIME_TEST
tim = clock();
to = clock();
#endif
// compute a reduced Groebner basis of <Gomega> w.r.t. "newRing"
#ifdef BUCHBERGER_ALG
M = MstdhomCC(Gomega1);
#else
M=kStd2(Gomega1,NULL,isHomog,NULL,hilb_func,0,NULL,curr_weight);
delete hilb_func;
#endif
if(endwalks == TRUE)
{
#ifdef TIME_TEST
xtstd = xtstd+clock()-to;
#endif
#ifdef ENDWALKS
#ifdef TIME_TEST
if(printout > 1)
{
Print("\n// time for the last std(Gw) = %.2f sec\n",
((double) clock())/1000000 -((double)tim) /1000000);
}
#endif
#endif
}
else
{
#ifdef TIME_TEST
tstd=tstd+clock()-to;
#endif
}
#ifdef CHECK_IDEAL_MWALK
if(printout > 2)
{
idString(M,"//** Mpwalk: M");
}
#endif
// change the ring to oldRing
rChangeCurrRing(oldRing);
M1 = idrMoveR(M, newRing,currRing);
Gomega2 = idrMoveR(Gomega1, newRing,currRing);
#ifdef TIME_TEST
to=clock();
#endif
/* compute a representation of the generators of submod (M)
with respect to those of mod (Gomega).
Gomega is a reduced Groebner basis w.r.t. the current ring */
F = MLifttwoIdeal(Gomega2, M1, G);
#ifdef TIME_TEST
if(endwalks == FALSE)
tlift = tlift+clock()-to;
else
xtlift=clock()-to;
#endif
#ifdef CHECK_IDEAL_MWALK
if(printout > 2)
{
idString(F,"//** Mpwalk: F");
}
#endif
idDelete(&M1);
idDelete(&Gomega2);
idDelete(&G);
// change the ring to newRing
rChangeCurrRing(newRing);
if(reduction == 0)
{
G = idrMoveR(F,oldRing,currRing);
}
else
{
F1 = idrMoveR(F, oldRing,currRing);
if(printout > 2)
{
PrintS("\n //** Mpwalk: reduce the Groebner basis.\n");
}
#ifdef TIME_TEST
to=clock();
#endif
G = kInterRedCC(F1, NULL);
#ifdef TIME_TEST
if(endwalks == FALSE)
tred = tred+clock()-to;
else
xtred=clock()-to;
#endif
idDelete(&F1);
}
if(endwalks == TRUE)
break;
NEXT_VECTOR:
#ifdef TIME_TEST
to=clock();
#endif
// compute a next weight vector
next_weight = MkInterRedNextWeight(curr_weight,target_weight, G);
#ifdef TIME_TEST
tnw=tnw+clock()-to;
#endif
#ifdef PRINT_VECTORS
if(printout > 0)
{
MivString(curr_weight, target_weight, next_weight);
}
#endif
if(Overflow_Error == TRUE)
{
ntwC = 0;
//ntestomega = 1;
//Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
//idElements(G, "G");
delete next_weight;
goto FINISH_160302;
}
if(MivComp(next_weight, ivNull) == 1){
newRing = currRing;
delete next_weight;
//Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
break;
}
if(MivComp(next_weight, target_weight) == 1)
endwalks = TRUE;
for(i=nV-1; i>=0; i--)
(*curr_weight)[i] = (*next_weight)[i];
delete next_weight;
}//end of while-loop
if(tp_deg != 1)
{
FINISH_160302:
if(MivSame(orig_target, exivlp) == 1) {
/* if (rParameter(currRing) != NULL)
DefRingParlp();
else
VMrDefaultlp();
else
if (rParameter(currRing) != NULL)
DefRingPar(orig_target);
else*/
rChangeCurrRing(VMrDefault(orig_target));
}
TargetRing=currRing;
F1 = idrMoveR(G, newRing,currRing);
/*
#ifdef CHECK_IDEAL_MWALK
headidString(G, "G");
#endif
*/
// check whether the pertubed target vector stays in the correct cone
if(ntwC != 0){
ntestw = test_w_in_ConeCC(F1, pert_target_vector);
}
if( ntestw != 1 || ntwC == 0)
{
if(ntestw != 1 && printout >2)
{
ivString(pert_target_vector, "tau");
PrintS("\n// ** perturbed target vector doesn't stay in cone!!");
Print("\n// ring r%d = %s;\n", nstep, rString(currRing));
//idElements(F1, "G");
}
// LastGB is "better" than the kStd2 subroutine
#ifdef TIME_TEST
to=clock();
#endif
ideal eF1;
if(nP == 0 || tp_deg == 1 || MivSame(orig_target, exivlp) != 1){
// PrintS("\n// ** calls \"std\" to compute a GB");
eF1 = MstdCC(F1);
idDelete(&F1);
}
else {
// PrintS("\n// ** calls \"LastGB\" to compute a GB");
rChangeCurrRing(newRing);
ideal F2 = idrMoveR(F1, TargetRing,currRing);
eF1 = LastGB(F2, curr_weight, tp_deg-1);
F2=NULL;
}
#ifdef TIME_TEST
xtextra=clock()-to;
#endif
ring exTargetRing = currRing;
rChangeCurrRing(XXRing);
Eresult = idrMoveR(eF1, exTargetRing,currRing);
}
else{
rChangeCurrRing(XXRing);
Eresult = idrMoveR(F1, TargetRing,currRing);
}
}
else {
rChangeCurrRing(XXRing);
Eresult = idrMoveR(G, newRing,currRing);
}
si_opt_1 = save1; //set original options, e. g. option(RedSB)
delete ivNull;
if(tp_deg != 1)
delete target_weight;
if(op_deg != 1 )
delete curr_weight;
delete exivlp;
delete last_omega;
#ifdef TIME_TEST
TimeStringFractal(tinput, tostd, tif+xtif, tstd+xtstd,0, tlift+xtlift, tred+xtred,
tnw+xtnw);
//Print("\n// pSetm_Error = (%d)", ErrorCheck());
//Print("\n// It took %d steps and Overflow_Error? (%d)\n", nstep, Overflow_Error);
#endif
if(printout > 0)
{
Print("\n//** Mpwalk: Perturbation Walk took %d steps.\n", nstep);
}
return(Eresult);
}

## Mrwalk()

ideal Mrwalk | ( | ideal | Go,
|  | intvec * | orig_M,
|  | intvec * | target_M,
|  | int | weight_rad,
|  | int | pert_deg,
|  | int | reduction,
|  | int | printout )

Definition at line 5604 of file walk.cc.

{
BITSET save1 = si_opt_1; // save current options
if(reduction == 0)
{
si_opt_1 &= (~Sy_bit(OPT_REDSB)); // no reduced Groebner basis
si_opt_1 &= (~Sy_bit(OPT_REDTAIL)); // not tail reductions
}
Set_Error(FALSE);
Overflow_Error = FALSE;
#ifdef TIME_TEST
clock_t tinput, tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0;
tinput = clock();
clock_t tim;
#endif
nstep=0;
int i,nwalk;//polylength;
int nV = currRing->N;
//check that weight radius is valid
if(weight_rad < 0)
{
WerrorS("Invalid radius.\n");
return NULL;
}
//check that perturbation degree is valid
if(pert_deg > nV || pert_deg < 1)
{
WerrorS("Invalid perturbation degree.\n");
return NULL;
}
ideal Gomega, M, F,FF, Gomega1, Gomega2, M1;
ring newRing;
ring targetRing;
ring baseRing = currRing;
ring XXRing = currRing;
intvec* iv_M;
intvec* ivNull = new intvec(nV);
intvec* curr_weight = new intvec(nV);
intvec* target_weight = new intvec(nV);
intvec* next_weight= new intvec(nV);
for(i=0; i<nV; i++)
{
(*curr_weight)[i] = (*orig_M)[i];
(*target_weight)[i] = (*target_M)[i];
}
#ifndef BUCHBERGER_ALG
intvec* hilb_func;
// to avoid (1,0,...,0) as the target vector
intvec* last_omega = new intvec(nV);
for(i=nV-1; i>0; i--)
{
(*last_omega)[i] = 1;
}
(*last_omega)[0] = 10000;
#endif
rComplete(currRing);
if(target_M->length() == nV)
{
targetRing = VMrDefault(target_weight); // define the target ring
}
else
{
targetRing = VMatrDefault(target_M);
}
if(orig_M->length() == nV)
{
//newRing = VMrDefault(curr_weight); // define a new ring with ordering "(a(curr_weight),lp)
newRing=VMrRefine(target_weight, curr_weight);
}
else
{
newRing = VMatrRefine(target_M,curr_weight);//newRing = VMatrDefault(orig_M);
}
rChangeCurrRing(newRing);
#ifdef TIME_TEST
to = clock();
#endif
ideal G = MstdCC(idrMoveR(Go,baseRing,currRing));
#ifdef TIME_TEST
tostd = clock()-to;
#endif
baseRing = currRing;
nwalk = 0;
#ifdef TIME_TEST
to = clock();
#endif
Gomega = MwalkInitialForm(G, curr_weight); // compute an initial form ideal of <G> w.r.t. "curr_vector"
#ifdef TIME_TEST
tif = tif + clock()-to; //time for computing initial form ideal
#endif
while(1)
{
nwalk ++;
nstep ++;
#ifdef CHECK_IDEAL_MWALK
if(printout > 1)
{
idString(Gomega,"//** Mrwalk: Gomega");
}
#endif
if(reduction == 0)
{
FF = middleOfCone(G,Gomega);
if(FF != NULL)
{
idDelete(&G);
G = idCopy(FF);
idDelete(&FF);
goto NEXT_VECTOR;
}
}
#ifndef BUCHBERGER_ALG
if(isNolVector(curr_weight) == 0)
{
hilb_func = hFirstSeries(Gomega,NULL,NULL,curr_weight,currRing);
}
else
{
hilb_func = hFirstSeries(Gomega,NULL,NULL,last_omega,currRing);
}
#endif
if(nwalk == 1)
{
if(orig_M->length() == nV)
{
/*newRing = VMrDefault(curr_weight); // define a new ring with ordering "(a(curr_weight),lp)*/
newRing=VMrRefine(target_weight, curr_weight);
}
else
{
newRing = VMatrRefine(target_M,curr_weight);//newRing = VMatrDefault(orig_M);
}
}
else
{
if(target_M->length() == nV)
{
/*newRing = VMrDefault(curr_weight); // define a new ring with ordering "(a(curr_weight),lp)*/
newRing=VMrRefine(target_weight, curr_weight);
}
else
{
newRing = VMatrRefine(target_M,curr_weight);
}
}
rChangeCurrRing(newRing);
Gomega1 = idrMoveR(Gomega, baseRing,currRing);
idDelete(&Gomega);
// compute a reduced Groebner basis of <Gomega> w.r.t. "newRing"
#ifdef TIME_TEST
to = clock();
#endif
#ifndef BUCHBERGER_ALG
M=kStd2(Gomega1,NULL,isHomog,NULL,hilb_func,0,NULL,curr_weight);
delete hilb_func;
#else
M = kStd2(Gomega1,NULL,testHomog,NULL,(bigintmat*)NULL,0,0,NULL);
#endif
#ifdef TIME_TEST
tstd = tstd + clock() - to;
#endif
idSkipZeroes(M);
#ifdef CHECK_IDEAL_MWALK
if(printout > 2)
{
idString(M, "//** Mrwalk: M");
}
#endif
//change the ring to baseRing
rChangeCurrRing(baseRing);
M1 = idrMoveR(M, newRing,currRing);
idDelete(&M);
Gomega2 = idrMoveR(Gomega1, newRing,currRing);
idDelete(&Gomega1);
#ifdef TIME_TEST
to = clock();
#endif
// compute a representation of the generators of submod (M) with respect to those of mod (Gomega),
// where Gomega is a reduced Groebner basis w.r.t. the current ring
F = MLifttwoIdeal(Gomega2, M1, G);
#ifdef TIME_TEST
tlift = tlift + clock() - to;
#endif
#ifdef CHECK_IDEAL_MWALK
if(printout > 2)
{
idString(F,"//** Mrwalk: F");
}
#endif
idDelete(&Gomega2);
idDelete(&M1);
rChangeCurrRing(newRing); // change the ring to newRing
G = idrMoveR(F,baseRing,currRing);
idDelete(&F);
baseRing = currRing;
#ifdef TIME_TEST
to = clock();
tstd = tstd + clock() - to;
#endif
idSkipZeroes(G);
#ifdef CHECK_IDEAL_MWALK
if(printout > 2)
{
idString(G,"//** Mrwalk: G");
}
#endif
rChangeCurrRing(targetRing);
G = idrMoveR(G,newRing,currRing);
// test whether target cone is reached
if(reduction !=0 && test_w_in_ConeCC(G,curr_weight) == 1)
{
baseRing = currRing;
break;
}
rChangeCurrRing(newRing);
G = idrMoveR(G,targetRing,currRing);
baseRing = currRing;
NEXT_VECTOR:
#ifdef TIME_TEST
to = clock();
#endif
next_weight = MwalkNextWeightCC(curr_weight,target_weight,G);
#ifdef TIME_TEST
tnw = tnw + clock() - to;
#endif
#ifdef TIME_TEST
to = clock();
#endif
Gomega = MwalkInitialForm(G, next_weight); // compute an initial form ideal of <G> w.r.t. "curr_vector"
#ifdef TIME_TEST
tif = tif + clock()-to; //time for computing initial form ideal
#endif
//lengthpoly(Gomega) = 1 if there is a polynomial in Gomega with at least 3 monomials and 0 otherwise
//polylength = lengthpoly(Gomega);
if(lengthpoly(Gomega) > 0)
{
//there is a polynomial in Gomega with at least 3 monomials,
//low-dimensional facet of the cone
delete next_weight;
if(target_M->length() == nV)
{
//iv_M = MivMatrixOrder(curr_weight);
iv_M = MivMatrixOrderRefine(curr_weight,target_M);
}
else
{
iv_M = MivMatrixOrderRefine(curr_weight,target_M);
}
#ifdef TIME_TEST
to = clock();
#endif
next_weight = MWalkRandomNextWeight(G, iv_M, target_weight, weight_rad, pert_deg);
#ifdef TIME_TEST
tnw = tnw + clock() - to;
#endif
idDelete(&Gomega);
#ifdef TIME_TEST
to = clock();
#endif
Gomega = MwalkInitialForm(G, next_weight);
#ifdef TIME_TEST
tif = tif + clock()-to; //time for computing initial form ideal
#endif
delete iv_M;
}
// test whether target weight vector is reached
if(MivComp(next_weight, ivNull) == 1 || MivComp(target_weight,curr_weight) == 1)
{
baseRing = currRing;
delete next_weight;
break;
}
if(reduction ==0)
{
if(MivComp(curr_weight,next_weight)==1)
{
break;
}
}
#ifdef PRINT_VECTORS
if(printout > 0)
{
MivString(curr_weight, target_weight, next_weight);
}
#endif
for(i=nV-1; i>=0; i--)
{
(*curr_weight)[i] = (*next_weight)[i];
}
delete next_weight;
}
baseRing = currRing;
rChangeCurrRing(XXRing);
ideal result = idrMoveR(G,baseRing,currRing);
idDelete(&G);
delete ivNull;
#ifndef BUCHBERGER_ALG
delete last_omega;
#endif
if(printout > 0)
{
Print("\n//** Mrwalk: Groebner Walk took %d steps.\n", nstep);
}
#ifdef TIME_TEST
TimeString(tinput, tostd, tif, tstd, tlift, tred, tnw, nstep);
//Print("\n// pSetm_Error = (%d)", ErrorCheck());
//Print("\n// Overflow_Error? (%d)\n", Overflow_Error);
#endif
si_opt_1 = save1; //set original options
return(result);
}
bigintmat
Matrices of numbers.
Definition bigintmat.h:51
testHomog
@ testHomog
Definition structs.h:34

## MSimpleIV()

intvec * MSimpleIV | ( | intvec * | iv | ) |

## Mwalk()

ideal Mwalk | ( | ideal | Go,
|  | intvec * | orig_M,
|  | intvec * | target_M,
|  | ring | baseRing,
|  | int | reduction,
|  | int | printout )

Definition at line 5303 of file walk.cc.

{
// save current options
BITSET save1 = si_opt_1;
if(reduction == 0)
{
si_opt_1 &= (~Sy_bit(OPT_REDSB)); // no reduced Groebner basis
si_opt_1 &= (~Sy_bit(OPT_REDTAIL)); // not tail reductions
}
Set_Error(FALSE);
Overflow_Error = FALSE;
//BOOLEAN endwalks = FALSE;
#ifdef TIME_TEST
clock_t tinput, tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0;
xtif=0; xtstd=0; xtlift=0; xtred=0; xtnw=0;
tinput = clock();
clock_t tim;
#endif
nstep=0;
int i,nwalk;
int nV = baseRing->N;
ideal Gomega, M, F, FF, Gomega1, Gomega2, M1;
ring newRing;
ring XXRing = baseRing;
ring targetRing;
intvec* ivNull = new intvec(nV);
intvec* curr_weight = new intvec(nV);
intvec* target_weight = new intvec(nV);
intvec* exivlp = Mivlp(nV);
/*
intvec* tmp_weight = new intvec(nV);
for(i=0; i<nV; i++)
{
(*tmp_weight)[i] = (*orig_M)[i];
}
*/
for(i=0; i<nV; i++)
{
(*curr_weight)[i] = (*orig_M)[i];
(*target_weight)[i] = (*target_M)[i];
}
#ifndef BUCHBERGER_ALG
intvec* hilb_func;
// to avoid (1,0,...,0) as the target vector
intvec* last_omega = new intvec(nV);
for(i=nV-1; i>0; i--)
{
(*last_omega)[i] = 1;
}
(*last_omega)[0] = 10000;
#endif
rComplete(currRing);
#ifdef CHECK_IDEAL_MWALK
if(printout > 2)
{
idString(Go,"//** Mwalk: Go");
}
#endif
if(target_M->length() == nV)
{
// define the target ring
targetRing = VMrDefault(target_weight);
}
else
{
targetRing = VMatrDefault(target_M);
}
if(orig_M->length() == nV)
{
// define a new ring with ordering "(a(curr_weight),lp)
//newRing = VMrDefault(curr_weight);
newRing=VMrRefine(target_weight, curr_weight);
}
else
{
newRing = VMatrRefine(target_M,curr_weight); //newRing = VMatrDefault(orig_M);
}
rChangeCurrRing(newRing);
if(printout > 2)
{
Print("\n//** Mrwalk: Current ring r = %s;\n", rString(currRing));
}
#ifdef TIME_TEST
to = clock();
#endif
ideal G = MstdCC(idrMoveR(Go,baseRing,currRing));
#ifdef TIME_TEST
tostd = clock()-to;
#endif
baseRing = currRing;
nwalk = 0;
while(1)
{
nwalk ++;
nstep ++;
//compute an initial form ideal of <G> w.r.t. "curr_vector"
#ifdef TIME_TEST
to = clock();
#endif
Gomega = MwalkInitialForm(G, curr_weight);
#ifdef TIME_TEST
tif = tif + clock()-to;
#endif
#ifdef CHECK_IDEAL_MWALK
if(printout > 1)
{
idString(Gomega,"//** Mwalk: Gomega");
}
#endif
if(reduction == 0)
{
FF = middleOfCone(G,Gomega);
if(FF != NULL)
{
PrintS("middle of Cone");
idDelete(&G);
G = idCopy(FF);
idDelete(&FF);
goto NEXT_VECTOR;
}
}
#ifndef BUCHBERGER_ALG
if(isNolVector(curr_weight) == 0)
{
hilb_func = hFirstSeries(Gomega,NULL,NULL,curr_weight,currRing);
}
else
{
hilb_func = hFirstSeries(Gomega,NULL,NULL,last_omega,currRing);
}
#endif
if(nwalk == 1)
{
if(orig_M->length() == nV)
{
// define a new ring with ordering "(a(curr_weight),lp)
//newRing = VMrDefault(curr_weight);
newRing=VMrRefine(target_weight, curr_weight);
}
else
{
newRing = VMatrRefine(target_M,curr_weight);//newRing = VMatrDefault(orig_M);
}
}
else
{
if(target_M->length() == nV)
{
//define a new ring with ordering "(a(curr_weight),lp)"
//newRing = VMrDefault(curr_weight);
newRing=VMrRefine(target_weight, curr_weight);
}
else
{
//define a new ring with matrix ordering
newRing = VMatrRefine(target_M,curr_weight);
}
}
rChangeCurrRing(newRing);
if(printout > 2)
{
Print("\n// Current ring r = %s;\n", rString(currRing));
}
Gomega1 = idrMoveR(Gomega, baseRing,currRing);
idDelete(&Gomega);
// compute a reduced Groebner basis of <Gomega> w.r.t. "newRing"
#ifdef TIME_TEST
to = clock();
#endif
#ifndef BUCHBERGER_ALG
M=kStd2(Gomega1,NULL,isHomog,NULL,hilb_func,0,NULL,curr_weight);
delete hilb_func;
#else
M = kStd2(Gomega1,NULL,testHomog,NULL,(bigintmat*)NULL,0,0,NULL);
#endif
#ifdef TIME_TEST
tstd = tstd + clock() - to;
#endif
idSkipZeroes(M);
#ifdef CHECK_IDEAL_MWALK
if(printout > 2)
{
idString(M, "//** Mwalk: M");
}
#endif
//change the ring to baseRing
rChangeCurrRing(baseRing);
M1 = idrMoveR(M, newRing,currRing);
idDelete(&M);
Gomega2 = idrMoveR(Gomega1, newRing,currRing);
idDelete(&Gomega1);
#ifdef TIME_TEST
to = clock();
#endif
// compute a representation of the generators of submod (M) with respect to those of mod (Gomega),
// where Gomega is a reduced Groebner basis w.r.t. the current ring
F = MLifttwoIdeal(Gomega2, M1, G);
#ifdef TIME_TEST
tlift = tlift + clock() - to;
#endif
#ifdef CHECK_IDEAL_MWALK
if(printout > 2)
{
idString(F, "//** Mwalk: F");
}
#endif
idDelete(&Gomega2);
idDelete(&M1);
rChangeCurrRing(newRing); // change the ring to newRing
G = idrMoveR(F,baseRing,currRing);
idDelete(&F);
idSkipZeroes(G);
#ifdef CHECK_IDEAL_MWALK
if(printout > 2)
{
idString(G, "//** Mwalk: G");
}
#endif
rChangeCurrRing(targetRing);
G = idrMoveR(G,newRing,currRing);
// test whether target cone is reached
if(reduction !=0 && test_w_in_ConeCC(G,curr_weight) == 1)
{
baseRing = currRing;
break;
//endwalks = TRUE;
}
rChangeCurrRing(newRing);
G = idrMoveR(G,targetRing,currRing);
baseRing = currRing;
NEXT_VECTOR:
#ifdef TIME_TEST
to = clock();
#endif
intvec* next_weight = MwalkNextWeightCC(curr_weight,target_weight,G);
#ifdef TIME_TEST
tnw = tnw + clock() - to;
#endif
#ifdef PRINT_VECTORS
if(printout > 0)
{
MivString(curr_weight, target_weight, next_weight);
}
#endif
if(reduction ==0)
{
if(MivComp(curr_weight,next_weight)==1)
{
break;
}
}
if(MivComp(target_weight,curr_weight) == 1)
{
break;
}
for(i=nV-1; i>=0; i--)
{
//(*tmp_weight)[i] = (*curr_weight)[i];
(*curr_weight)[i] = (*next_weight)[i];
}
delete next_weight;
}
rChangeCurrRing(XXRing);
ideal result = idrMoveR(G,baseRing,currRing);
idDelete(&Go);
idDelete(&G);
//delete tmp_weight;
delete ivNull;
delete exivlp;
#ifndef BUCHBERGER_ALG
delete last_omega;
#endif
#ifdef TIME_TEST
TimeString(tinput, tostd, tif, tstd, tlift, tred, tnw, nstep);
//Print("\n// pSetm_Error = (%d)", ErrorCheck());
//Print("\n// Overflow_Error? (%d)\n", Overflow_Error);
#endif
if(printout > 0)
{
Print("\n//** Mwalk: Groebner Walk took %d steps.\n", nstep);
}
si_opt_1 = save1; //set original options
return(result);
}

## MwalkInitialForm()

ideal MwalkInitialForm | ( | ideal | G,
|  | intvec * | curr_weight )

Definition at line 762 of file walk.cc.

{
BOOLEAN nError = Overflow_Error;
Overflow_Error = FALSE;
int i, nG = IDELEMS(G);
ideal Gomega = idInit(nG, 1);
for(i=nG-1; i>=0; i--)
{
Gomega->m[i] = MpolyInitialForm(G->m[i], ivw);
}
if(Overflow_Error == FALSE)
{
Overflow_Error = nError;
}
return Gomega;
}
idInit
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition simpleideals.cc:35
MpolyInitialForm
static poly MpolyInitialForm(poly g, intvec *curr_weight)
Definition walk.cc:723

## MwalkNextWeight()

intvec * MwalkNextWeight | ( | intvec * | curr_weight,
|  | intvec * | target_weight,
|  | ideal | G )

## TranMImprovwalk()

ideal TranMImprovwalk | ( | ideal | Go,
|  | intvec * | curr_weight,
|  | intvec * | target_weight,
|  | int | nP )

Definition at line 8397 of file walk.cc.

{
#ifdef TIME_TEST
clock_t mtim = clock();
#endif
Set_Error(FALSE );
Overflow_Error = FALSE;
//Print("// pSetm_Error = (%d)", ErrorCheck());
//Print("\n// ring ro = %s;", rString(currRing));
#ifdef TIME_TEST
clock_t tostd, tif=0, tstd=0, tlift=0, tred=0, tnw=0, textra=0;
clock_t tinput = clock();
#endif
int nsteppert=0, i, nV = currRing->N, nwalk=0, npert_tmp=0;
int *npert=(int*)omAlloc(2*nV*sizeof(int));
ideal Gomega, M,F, G1, Gomega1, Gomega2, M1, F1;
//ring endRing;
ring newRing, oldRing, lpRing;
intvec* next_weight;
intvec* ivNull = new intvec(nV); //define (0,...,0)
intvec* iv_dp = MivUnit(nV);// define (1,1,...,1)
intvec* iv_lp = Mivlp(nV); //define (1,0,...,0)
ideal H0;
//ideal H1;
ideal H2, Glp;
int nGB, endwalks = 0, nwalkpert=0;
intvec* Mlp = MivMatrixOrderlp(nV);
intvec* vector_tmp = new intvec(nV);
#ifndef BUCHBERGER_ALG
intvec* hilb_func;
#endif
// to avoid (1,0,...,0) as the target vector
intvec* last_omega = new intvec(nV);
for(i=nV-1; i>0; i--)
(*last_omega)[i] = 1;
(*last_omega)[0] = 10000;
// intvec* extra_curr_weight = new intvec(nV);
intvec* target_weight = new intvec(nV);
for(i=nV-1; i>=0; i--)
(*target_weight)[i] = (*target_tmp)[i];
ring XXRing = currRing;
newRing = currRing;
#ifdef TIME_TEST
to=clock();
#endif
// compute a red. GB w.r.t. the help ring
if(MivComp(curr_weight, iv_dp) == 1) //rOrdStr(currRing) = "dp"
G = MstdCC(G);
else
{
//rOrdStr(currRing) = (a(.c_w..),lp,C)
if (rParameter(currRing) != NULL)
DefRingPar(curr_weight);
else
rChangeCurrRing(VMrDefault(curr_weight));
G = idrMoveR(G, XXRing,currRing);
G = MstdCC(G);
}
#ifdef TIME_TEST
tostd=clock()-to;
#endif
#ifdef REPRESENTATION_OF_SIGMA
ideal Gw = MwalkInitialForm(G, curr_weight);
if(islengthpoly2(Gw)==1)
{
intvec* MDp;
if(MivComp(curr_weight, iv_dp) == 1)
MDp = MatrixOrderdp(nV); //MivWeightOrderlp(iv_dp);
else
MDp = MivWeightOrderlp(curr_weight);
curr_weight = RepresentationMatrix_Dp(G, MDp);
delete MDp;
ring exring = currRing;
if (rParameter(currRing) != NULL)
DefRingPar(curr_weight);
else
rChangeCurrRing(VMrDefault(curr_weight));
#ifdef TIME_TEST
to=clock();
#endif
Gw = idrMoveR(G, exring,currRing);
G = MstdCC(Gw);
Gw = NULL;
#ifdef TIME_TEST
tostd=tostd+clock()-to;
#endif
//ivString(curr_weight,"rep. sigma");
goto COMPUTE_NEW_VECTOR;
}
idDelete(&Gw);
delete iv_dp;
#endif
while(1)
{
#ifdef TIME_TEST
to=clock();
#endif
/* compute an initial form ideal of <G> w.r.t. "curr_vector" */
Gomega = MwalkInitialForm(G, curr_weight);
#ifdef TIME_TEST
tif=tif+clock()-to;
#endif
#ifndef BUCHBERGER_ALG
if(isNolVector(curr_weight) == 0)
hilb_func = hFirstSeries(Gomega,NULL,NULL,curr_weight,currRing);
else
hilb_func = hFirstSeries(Gomega,NULL,NULL,last_omega,currRing);
#endif // BUCHBERGER_ALG
oldRing = currRing;
/* define a new ring that its ordering is "(a(curr_weight),lp) */
if (rParameter(currRing) != NULL)
DefRingPar(curr_weight);
else
rChangeCurrRing(VMrDefault(curr_weight));
newRing = currRing;
Gomega1 = idrMoveR(Gomega, oldRing,currRing);
#ifdef TIME_TEST
to=clock();
#endif
/* compute a reduced Groebner basis of <Gomega> w.r.t. "newRing" */
#ifdef BUCHBERGER_ALG
M = MstdhomCC(Gomega1);
#else
M=kStd2(Gomega1,NULL,isHomog,NULL,hilb_func,0,NULL,curr_weight);
delete hilb_func;
#endif // BUCHBERGER_ALG
#ifdef TIME_TEST
tstd=tstd+clock()-to;
#endif
/* change the ring to oldRing */
rChangeCurrRing(oldRing);
M1 = idrMoveR(M, newRing,currRing);
Gomega2 = idrMoveR(Gomega1, newRing,currRing);
#ifdef TIME_TEST
to=clock();
#endif
/* compute a representation of the generators of submod (M)
with respect to those of mod (Gomega).
Gomega is a reduced Groebner basis w.r.t. the current ring */
F = MLifttwoIdeal(Gomega2, M1, G);
#ifdef TIME_TEST
tlift=tlift+clock()-to;
#endif
idDelete(&M1);
idDelete(&Gomega2);
idDelete(&G);
/* change the ring to newRing */
rChangeCurrRing(newRing);
F1 = idrMoveR(F, oldRing,currRing);
#ifdef TIME_TEST
to=clock();
#endif
/* reduce the Groebner basis <G> w.r.t. new ring */
G = kInterRedCC(F1, NULL);
#ifdef TIME_TEST
tred=tred+clock()-to;
#endif
idDelete(&F1);
COMPUTE_NEW_VECTOR:
newRing = currRing;
nwalk++;
nwalkpert++;
#ifdef TIME_TEST
to=clock();
#endif
// compute a next weight vector
next_weight = MwalkNextWeightCC(curr_weight,target_weight, G);
#ifdef TIME_TEST
tnw=tnw+clock()-to;
#endif
#ifdef PRINT_VECTORS
MivString(curr_weight, target_weight, next_weight);
#endif
/* check whether the computed intermediate weight vector is in
the correct cone; sometimes it is very big e.g. s7, cyc7.
If it is NOT in the correct cone, then compute directly
a reduced Groebner basis with respect to the lexicographic ordering
for the known Groebner basis that it is computed in the last step.
*/
//if(test_w_in_ConeCC(G, next_weight) != 1)
if(Overflow_Error == TRUE)
{
OMEGA_OVERFLOW_TRAN_NEW:
//Print("\n// takes %d steps!", nwalk-1);
//Print("\n//ring lastRing = %s;", rString(currRing));
#ifdef TEST_OVERFLOW
goto BE_FINISH;
#endif
/*
#ifdef CHECK_IDEAL_MWALK
idElements(G, "G");
//headidString(G, "G");
#endif
*/
if(MivSame(target_tmp, iv_lp) == 1)
if (rParameter(currRing) != NULL)
DefRingParlp();
else
VMrDefaultlp();
else
if (rParameter(currRing) != NULL)
DefRingPar(target_tmp);
else
rChangeCurrRing(VMrDefault(target_tmp));
lpRing = currRing;
G1 = idrMoveR(G, newRing,currRing);
#ifdef TIME_TEST
to=clock();
#endif
/*apply kStd2 or LastGB to compute a lex. red. Groebner basis of <G>*/
if(nP == 0 || MivSame(target_tmp, iv_lp) == 0){
//Print("\n\n// calls \"std in ring r_%d = %s;", nwalk, rString(currRing));
G = MstdCC(G1);//no result for qnt1
}
else {
rChangeCurrRing(newRing);
G1 = idrMoveR(G1, lpRing,currRing);
//Print("\n\n// calls \"LastGB\" (%d) to compute a GB", nV-1);
G = LastGB(G1, curr_weight, nV-1); //no result for kats7
rChangeCurrRing(lpRing);
G = idrMoveR(G, newRing,currRing);
}
#ifdef TIME_TEST
textra=clock()-to;
#endif
npert[endwalks]=nwalk-npert_tmp;
npert_tmp = nwalk;
endwalks ++;
break;
}
/* check whether the computed Groebner basis is really a Groebner basis.
If not, we perturb the target vector with the maximal "perturbation"
degree.*/
if(MivComp(next_weight, target_weight) == 1 ||
MivComp(next_weight, curr_weight) == 1 )
{
//Print("\n//ring r_%d = %s;", nwalk, rString(currRing));
//compute the number of perturbations and its step
npert[endwalks]=nwalk-npert_tmp;
npert_tmp = nwalk;
endwalks ++;
/*it is very important if the walk only uses one step, e.g. Fate, liu*/
if(endwalks == 1 && MivComp(next_weight, curr_weight) == 1){
rChangeCurrRing(XXRing);
G = idrMoveR(G, newRing,currRing);
goto FINISH;
}
H0 = id_Head(G,currRing);
if(MivSame(target_tmp, iv_lp) == 1)
if (rParameter(currRing) != NULL)
DefRingParlp();
else
VMrDefaultlp();
else
if (rParameter(currRing) != NULL)
DefRingPar(target_tmp);
else
rChangeCurrRing(VMrDefault(target_tmp));
lpRing = currRing;
Glp = idrMoveR(G, newRing,currRing);
H2 = idrMoveR(H0, newRing,currRing);
/* Apply Lemma 2.2 in Collart et. al (1997) to check whether
cone(k-1) is equal to cone(k) */
nGB = 1;
for(i=IDELEMS(Glp)-1; i>=0; i--)
{
poly t;
if((t=pSub(pHead(Glp->m[i]), pCopy(H2->m[i]))) != NULL)
{
pDelete(&t);
idDelete(&H2);//5.5.02
nGB = 0; //i.e. Glp is no reduced Groebner basis
break;
}
pDelete(&t);
}
idDelete(&H2);//5.5.02
if(nGB == 1)
{
G = Glp;
Glp = NULL;
break;
}
/* perturb the target weight vector, if the vector target_tmp
stays in many cones */
poly p;
BOOLEAN plength3 = FALSE;
for(i=IDELEMS(Glp)-1; i>=0; i--)
{
p = MpolyInitialForm(Glp->m[i], target_tmp);
if(p->next != NULL &&
p->next->next != NULL &&
p->next->next->next != NULL)
{
Overflow_Error = FALSE;
for(i=0; i<nV; i++)
(*vector_tmp)[i] = (*target_weight)[i];
delete target_weight;
target_weight = MPertVectors(Glp, Mlp, nV);
if(MivComp(vector_tmp, target_weight)==1)
{
//PrintS("\n// The old and new representaion vector are the same!!");
G = Glp;
newRing = currRing;
goto OMEGA_OVERFLOW_TRAN_NEW;
}
if(Overflow_Error == TRUE)
{
rChangeCurrRing(newRing);
G = idrMoveR(Glp, lpRing,currRing);
goto OMEGA_OVERFLOW_TRAN_NEW;
}
plength3 = TRUE;
pDelete(&p);
break;
}
pDelete(&p);
}
if(plength3 == FALSE)
{
rChangeCurrRing(newRing);
G = idrMoveR(Glp, lpRing,currRing);
goto TRAN_LIFTING;
}
nwalkpert = 1;
nsteppert ++;
/*
Print("\n// Subroutine needs (%d) steps.", nwalk);
idElements(Glp, "last G in walk:");
PrintS("\n// ****************************************");
Print("\n// Perturb the original target vector (%d): ", nsteppert);
ivString(target_weight, "new target");
PrintS("\n// ****************************************\n");
*/
rChangeCurrRing(newRing);
G = idrMoveR(Glp, lpRing,currRing);
delete next_weight;
//Print("\n// ring rNEW = %s;", rString(currRing));
goto COMPUTE_NEW_VECTOR;
}
TRAN_LIFTING:
for(i=nV-1; i>=0; i--)
(*curr_weight)[i] = (*next_weight)[i];
delete next_weight;
}//while
#ifdef TEST_OVERFLOW
BE_FINISH:
#endif
rChangeCurrRing(XXRing);
G = idrMoveR(G, lpRing,currRing);
FINISH:
delete ivNull;
delete next_weight;
delete iv_lp;
omFree(npert);
/*
#ifdef TIME_TEST
Print("\n// Computation took %d steps and %.2f sec",
nwalk, ((double) (clock()-mtim)/1000000));
TimeStringFractal(tinput, tostd, tif, tstd, textra, tlift, tred, tnw);
// Print("\n// pSetm_Error = (%d)", ErrorCheck());
Print("\n// Overflow_Error? (%d)\n", Overflow_Error);
#endif
*/
return(G);
}
pDelete
#define pDelete(p_ptr)
Definition polys.h:187
pHead
#define pHead(p)
returns newly allocated copy of Lm(p), coef is copied, next=NULL, p might be NULL
Definition polys.h:68
pSub
#define pSub(a, b)
Definition polys.h:288
pCopy
#define pCopy(p)
return a copy of the poly
Definition polys.h:186
id_Head
ideal id_Head(ideal h, const ring r)
returns the ideals of initial terms
Definition simpleideals.cc:1483
islengthpoly2
static int islengthpoly2(ideal G)
Definition walk.cc:3478

## TranMPertVectorslp()

intvec * TranMPertVectorslp | ( | ideal | G | ) |