#include <tropicalStrategy.h>

Public Member Functions
	tropicalStrategy (const ideal I, const ring r, const bool completelyHomogeneous=true, const bool completeSpace=true)
	Constructor for the trivial valuation case. More...

	tropicalStrategy (const ideal J, const number p, const ring s)
	Constructor for the non-trivial valuation case p is the uniformizing parameter of the valuation. More...

	tropicalStrategy (const tropicalStrategy &currentStrategy)
	copy constructor More...

	tropicalStrategy ()

	~tropicalStrategy ()
	destructor More...

tropicalStrategy &	operator= (const tropicalStrategy &currentStrategy)
	assignment operator More...

bool	isConstantCoefficientCase () const

bool	isValuationTrivial () const

bool	isValuationNonTrivial () const

ring	getOriginalRing () const
	returns the polynomial ring over the field with valuation More...

ideal	getOriginalIdeal () const
	returns the input ideal over the field with valuation More...

ring	getStartingRing () const
	returns the polynomial ring over the valuation ring More...

ideal	getStartingIdeal () const
	returns the input ideal More...

int	getExpectedDimension () const
	returns the expected Dimension of the polyhedral output More...

number	getUniformizingParameter () const
	returns the uniformizing parameter in the valuation ring More...

ring	getShortcutRing () const

gfan::ZCone	getHomogeneitySpace () const
	returns the homogeneity space of the preimage ideal More...

bool	homogeneitySpaceContains (const gfan::ZVector &v) const
	returns true, if v is contained in the homogeneity space; false otherwise More...

bool	restrictToLowerHalfSpace () const
	returns true, if valuation non-trivial, false otherwise More...

gfan::ZVector	adjustWeightForHomogeneity (gfan::ZVector w) const
	Given weight w, returns a strictly positive weight u such that an ideal satisfying the valuation-sepcific homogeneity conditions is weighted homogeneous with respect to w if and only if it is homogeneous with respect to u. More...

gfan::ZVector	adjustWeightUnderHomogeneity (gfan::ZVector v, gfan::ZVector w) const
	Given strictly positive weight w and weight v, returns a strictly positive weight u such that on an ideal that is weighted homogeneous with respect to w the weights u and v coincide. More...

gfan::ZVector	negateWeight (const gfan::ZVector &w) const

ring	getShortcutRingPrependingWeight (const ring r, const gfan::ZVector &w) const
	If valuation trivial, returns a copy of r with a positive weight prepended, such that any ideal homogeneous with respect to w is homogeneous with respect to that weight. More...

bool	reduce (ideal I, const ring r) const
	reduces the generators of an ideal I so that the inequalities and equations of the Groebner cone can be read off. More...

void	pReduce (ideal I, const ring r) const

std::pair< poly, int >	checkInitialIdealForMonomial (const ideal I, const ring r, const gfan::ZVector &w=0) const
	If given w, assuming w is in the Groebner cone of the ordering on r and I is a standard basis with respect to that ordering, checks whether the initial ideal of I with respect to w contains a monomial. More...

ideal	computeStdOfInitialIdeal (const ideal inI, const ring r) const
	given generators of the initial ideal, computes its standard basis More...

ideal	computeWitness (const ideal inJ, const ideal inI, const ideal I, const ring r) const
	suppose w a weight in maximal groebner cone of > suppose I (initially) reduced standard basis w.r.t. More...

ideal	computeLift (const ideal inJs, const ring s, const ideal inIr, const ideal Ir, const ring r) const

std::pair< ideal, ring >	computeFlip (const ideal Ir, const ring r, const gfan::ZVector &interiorPoint, const gfan::ZVector &facetNormal) const
	given an interior point of a groebner cone computes the groebner cone adjacent to it More...

Static Public Member Functions
static tropicalStrategy	debugStrategy (const ideal startIdeal, number unifParameter, ring startRing)

Private Member Functions
ring	copyAndChangeCoefficientRing (const ring r) const

ring	copyAndChangeOrderingWP (const ring r, const gfan::ZVector &w, const gfan::ZVector &v) const

ring	copyAndChangeOrderingLS (const ring r, const gfan::ZVector &w, const gfan::ZVector &v) const

bool	checkForUniformizingBinomial (const ideal I, const ring r) const
	if valuation non-trivial, checks whether the generating system contains p-t otherwise returns true More...

bool	checkForUniformizingParameter (const ideal inI, const ring r) const
	if valuation non-trivial, checks whether the genearting system contains p otherwise returns true More...

int	findPositionOfUniformizingBinomial (const ideal I, const ring r) const

void	putUniformizingBinomialInFront (ideal I, const ring r, const number q) const

Private Attributes
ring	originalRing
	polynomial ring over a field with valuation More...

ideal	originalIdeal
	input ideal, assumed to be a homogeneous prime ideal More...

int	expectedDimension
	the expected Dimension of the polyhedral output, i.e. More...

gfan::ZCone	linealitySpace
	the homogeneity space of the Grobner fan More...

ring	startingRing
	polynomial ring over the valuation ring extended by one extra variable t More...

ideal	startingIdeal
	preimage of the input ideal under the map that sends t to the uniformizing parameter More...

number	uniformizingParameter
	uniformizing parameter in the valuation ring More...

ring	shortcutRing
	polynomial ring over the residue field More...

bool	onlyLowerHalfSpace
	true if valuation non-trivial, false otherwise More...

gfan::ZVector(*	weightAdjustingAlgorithm1 )(const gfan::ZVector &w)
	A function such that: Given weight w, returns a strictly positive weight u such that an ideal satisfying the valuation-sepcific homogeneity conditions is weighted homogeneous with respect to w if and only if it is homogeneous with respect to u. More...

gfan::ZVector(*	weightAdjustingAlgorithm2 )(const gfan::ZVector &v, const gfan::ZVector &w)
	A function such that: Given strictly positive weight w and weight v, returns a strictly positive weight u such that on an ideal that is weighted homogeneous with respect to w the weights u and v coincide. More...

bool(*	extraReductionAlgorithm )(ideal I, ring r, number p)
	A function that reduces the generators of an ideal I so that the inequalities and equations of the Groebner cone can be read off. More...

Detailed Description

Definition at line 37 of file tropicalStrategy.h.

Constructor & Destructor Documentation

tropicalStrategy::tropicalStrategy	(	const ideal	I,
		const ring	r,
		const bool	completelyHomogeneous = `true`,
		const bool	completeSpace = `true`
	)

Constructor for the trivial valuation case.

Initializes all relevant structures and information for the trivial valuation case, i.e.

computing a tropical variety without any valuation.

Definition at line 120 of file tropicalStrategy.cc.

                                                             :
   originalRing(rCopy(r)),
   originalIdeal(id_Copy(I,r)),
   expectedDimension(dim(originalIdeal,originalRing)),
   linealitySpace(homogeneitySpace(originalIdeal,originalRing)),
   startingRing(rCopy(originalRing)),
   startingIdeal(id_Copy(originalIdeal,originalRing)),
   uniformizingParameter(NULL),
   shortcutRing(NULL),
   onlyLowerHalfSpace(false),
   weightAdjustingAlgorithm1(nonvalued_adjustWeightForHomogeneity),
   weightAdjustingAlgorithm2(nonvalued_adjustWeightUnderHomogeneity),
   extraReductionAlgorithm(noExtraReduction)
 {
   assume(rField_is_Q(r) || rField_is_Zp(r) || rField_is_Ring_Z(r));
   if (!completelyHomogeneous)
   {
     weightAdjustingAlgorithm1 = valued_adjustWeightForHomogeneity;
     weightAdjustingAlgorithm2 = valued_adjustWeightUnderHomogeneity;
   }
   if (!completeSpace)
     onlyLowerHalfSpace = true;
 }

tropicalStrategy::tropicalStrategy	(	const ideal	J,
		const number	p,
		const ring	s
	)

Constructor for the non-trivial valuation case p is the uniformizing parameter of the valuation.

Definition at line 246 of file tropicalStrategy.cc.

                                                            :
   originalRing(rCopy(s)),
   originalIdeal(id_Copy(J,s)),
   expectedDimension(dim(originalIdeal,originalRing)+1),
   linealitySpace(gfan::ZCone()), // to come, see below
   startingRing(NULL),            // to come, see below
   startingIdeal(NULL),           // to come, see below
   uniformizingParameter(NULL),   // to come, see below
   shortcutRing(NULL),            // to come, see below
   onlyLowerHalfSpace(true),
   weightAdjustingAlgorithm1(valued_adjustWeightForHomogeneity),
   weightAdjustingAlgorithm2(valued_adjustWeightUnderHomogeneity),
   extraReductionAlgorithm(ppreduceInitially)
 {
   /* assume that the ground field of the originalRing is Q */
   assume(rField_is_Q(s));
 
   /* replace Q with Z for the startingRing
    * and add an extra variable for tracking the uniformizing parameter */
   startingRing = constructStartingRing(originalRing);
 
   /* map the uniformizing parameter into the new coefficient domain */
   nMapFunc nMap = n_SetMap(originalRing->cf,startingRing->cf);
   uniformizingParameter = nMap(q,originalRing->cf,startingRing->cf);
 
   /* map the input ideal into the new polynomial ring */
   startingIdeal = constructStartingIdeal(J,s,uniformizingParameter,startingRing);
   reduce(startingIdeal,startingRing);
 
   linealitySpace = homogeneitySpace(startingIdeal,startingRing);
 
   /* construct the shorcut ring */
   shortcutRing = rCopy0(startingRing);
   nKillChar(shortcutRing->cf);
   shortcutRing->cf = nInitChar(n_Zp,(void*)(long)IsPrime(n_Int(uniformizingParameter,startingRing->cf)));
   rComplete(shortcutRing);
   rTest(shortcutRing);
 }

tropicalStrategy::tropicalStrategy ( const tropicalStrategy & currentStrategy )

copy constructor

Definition at line 285 of file tropicalStrategy.cc.

                                                                          :
   originalRing(rCopy(currentStrategy.getOriginalRing())),
   originalIdeal(id_Copy(currentStrategy.getOriginalIdeal(),currentStrategy.getOriginalRing())),
   expectedDimension(currentStrategy.getExpectedDimension()),
   linealitySpace(currentStrategy.getHomogeneitySpace()),
   startingRing(rCopy(currentStrategy.getStartingRing())),
   startingIdeal(id_Copy(currentStrategy.getStartingIdeal(),currentStrategy.getStartingRing())),
   uniformizingParameter(NULL),
   shortcutRing(NULL),
   onlyLowerHalfSpace(currentStrategy.restrictToLowerHalfSpace()),
   weightAdjustingAlgorithm1(currentStrategy.weightAdjustingAlgorithm1),
   weightAdjustingAlgorithm2(currentStrategy.weightAdjustingAlgorithm2),
   extraReductionAlgorithm(currentStrategy.extraReductionAlgorithm)
 {
   if (originalRing) rTest(originalRing);
   if (originalIdeal) id_Test(originalIdeal,originalRing);
   if (startingRing) rTest(startingRing);
   if (startingIdeal) id_Test(startingIdeal,startingRing);
   if (currentStrategy.getUniformizingParameter())
   {
     uniformizingParameter = n_Copy(currentStrategy.getUniformizingParameter(),startingRing->cf);
     n_Test(uniformizingParameter,startingRing->cf);
   }
   if (currentStrategy.getShortcutRing())
   {
     shortcutRing = rCopy(currentStrategy.getShortcutRing());
     rTest(shortcutRing);
   }
 }

tropicalStrategy::tropicalStrategy ( )

Definition at line 870 of file tropicalStrategy.cc.

                                   :
   originalRing(NULL),
   originalIdeal(NULL),
   expectedDimension(NULL),
   linealitySpace(gfan::ZCone()),
   startingRing(NULL),
   startingIdeal(NULL),
   uniformizingParameter(NULL),
   shortcutRing(NULL),
   onlyLowerHalfSpace(false)
 {
   weightAdjustingAlgorithm1=NULL;
   weightAdjustingAlgorithm2=NULL;
   extraReductionAlgorithm=NULL;
 }

tropicalStrategy::~tropicalStrategy ( )

destructor

Definition at line 315 of file tropicalStrategy.cc.

 {
   if (originalRing) rTest(originalRing);
   if (originalIdeal) id_Test(originalIdeal,originalRing);
   if (startingRing) rTest(startingRing);
   if (startingIdeal) id_Test(startingIdeal,startingRing);
   if (uniformizingParameter) n_Test(uniformizingParameter,startingRing->cf);
   if (shortcutRing) rTest(shortcutRing);
 
   id_Delete(&originalIdeal,originalRing);
   rDelete(originalRing);
   if (startingIdeal) id_Delete(&startingIdeal,startingRing);
   if (uniformizingParameter) n_Delete(&uniformizingParameter,startingRing->cf);
   if (startingRing) rDelete(startingRing);
   if (shortcutRing) rDelete(shortcutRing);
 }

Member Function Documentation

gfan::ZVector tropicalStrategy::adjustWeightForHomogeneity ( gfan::ZVector w ) const

inline

Given weight w, returns a strictly positive weight u such that an ideal satisfying the valuation-sepcific homogeneity conditions is weighted homogeneous with respect to w if and only if it is homogeneous with respect to u.

Definition at line 254 of file tropicalStrategy.h.

   {
     return this->weightAdjustingAlgorithm1(w);
   }

gfan::ZVector tropicalStrategy::adjustWeightUnderHomogeneity	(	gfan::ZVector	v,
		gfan::ZVector	w
	)		const

inline

Given strictly positive weight w and weight v, returns a strictly positive weight u such that on an ideal that is weighted homogeneous with respect to w the weights u and v coincide.

Definition at line 264 of file tropicalStrategy.h.

   {
     return this->weightAdjustingAlgorithm2(v,w);
   }

bool tropicalStrategy::checkForUniformizingBinomial	(	const ideal	I,
		const ring	r
	)		const

private

if valuation non-trivial, checks whether the generating system contains p-t otherwise returns true

Definition at line 790 of file tropicalStrategy.cc.

 {
   // if the valuation is trivial,
   // then there is no special condition the first generator has to fullfill
   if (isValuationTrivial())
     return true;
 
   // if the valuation is non-trivial then checks if the first generator is p-t
   nMapFunc identity = n_SetMap(startingRing->cf,r->cf);
   poly p = p_One(r);
   p_SetCoeff(p,identity(uniformizingParameter,startingRing->cf,r->cf),r);
   poly t = p_One(r);
   p_SetExp(t,1,1,r);
   p_Setm(t,r);
   poly pt = p_Add_q(p,p_Neg(t,r),r);
 
   for (int i=0; i<idSize(I); i++)
   {
     if (p_EqualPolys(I->m[i],pt,r))
     {
       p_Delete(&pt,r);
       return true;
     }
   }
   p_Delete(&pt,r);
   return false;
 }

bool tropicalStrategy::checkForUniformizingParameter	(	const ideal	inI,
		const ring	r
	)		const

private

if valuation non-trivial, checks whether the genearting system contains p otherwise returns true

Definition at line 843 of file tropicalStrategy.cc.

 {
   // if the valuation is trivial,
   // then there is no special condition the first generator has to fullfill
   if (isValuationTrivial())
     return true;
 
   // if the valuation is non-trivial then checks if the first generator is p
   if (inI->m[0]==NULL)
     return false;
   nMapFunc identity = n_SetMap(startingRing->cf,r->cf);
   poly p = p_One(r);
   p_SetCoeff(p,identity(uniformizingParameter,startingRing->cf,r->cf),r);
 
   for (int i=0; i<idSize(inI); i++)
   {
     if (p_EqualPolys(inI->m[i],p,r))
     {
       p_Delete(&p,r);
       return true;
     }
   }
   p_Delete(&p,r);
   return false;
 }

std::pair< poly, int > tropicalStrategy::checkInitialIdealForMonomial	(	const ideal	I,
		const ring	r,
		const gfan::ZVector &	w = `0`
	)		const

If given w, assuming w is in the Groebner cone of the ordering on r and I is a standard basis with respect to that ordering, checks whether the initial ideal of I with respect to w contains a monomial.

If no w is given, assuming that I is already an initial form of some ideal, checks whether I contains a monomial. In both cases returns a monomial, if it contains one, returns NULL otherwise.

Definition at line 463 of file tropicalStrategy.cc.

 {
   // quick check whether I already contains an ideal
   int k = idSize(I);
   for (int i=0; i<k; i++)
   {
     poly g = I->m[i];
     if (pNext(g)==NULL && (isValuationTrivial() || n_IsOne(p_GetCoeff(g,r),r->cf)))
       return std::pair<poly,int>(g,i);
   }
 
   ring rShortcut;
   ideal inIShortcut;
   if (w.size()>0)
   {
     // if needed, prepend extra weight for homogeneity
     // switch to residue field if valuation is non trivial
     rShortcut = getShortcutRingPrependingWeight(r,w);
 
     // compute the initial ideal and map it into the constructed ring
     // if switched to residue field, remove possibly 0 elements
     ideal inI = initial(I,r,w);
     inIShortcut = idInit(k);
     nMapFunc intoShortcut = n_SetMap(r->cf,rShortcut->cf);
     for (int i=0; i<k; i++)
       inIShortcut->m[i] = p_PermPoly(inI->m[i],NULL,r,rShortcut,intoShortcut,NULL,0);
     if (isValuationNonTrivial())
       idSkipZeroes(inIShortcut);
     id_Delete(&inI,r);
   }
   else
   {
     rShortcut = r;
     inIShortcut = I;
   }
 
   // check initial ideal for monomial and
   // if it exsists, return a copy of the monomial in the input ring
   poly p = checkForMonomialViaSuddenSaturation(inIShortcut,rShortcut);
   poly monomial = NULL;
   if (p!=NULL)
   {
     monomial=p_One(r);
     for (int i=1; i<=rVar(r); i++)
       p_SetExp(monomial,i,p_GetExp(p,i,rShortcut),r);
     p_Setm(monomial,r);
     p_Delete(&p,rShortcut);
   }
 
 
   if (w.size()>0)
   {
     // if needed, cleanup
     id_Delete(&inIShortcut,rShortcut);
     rDelete(rShortcut);
   }
   return std::pair<poly,int>(monomial,-1);
 }

std::pair< ideal, ring > tropicalStrategy::computeFlip	(	const ideal	Ir,
		const ring	r,
		const gfan::ZVector &	interiorPoint,
		const gfan::ZVector &	facetNormal
	)		const

given an interior point of a groebner cone computes the groebner cone adjacent to it

Definition at line 743 of file tropicalStrategy.cc.

 {
   assume(isValuationTrivial() || interiorPoint[0].sign()<0);
   assume(checkForUniformizingBinomial(Ir,r));
 
   // get a generating system of the initial ideal
   // and compute a standard basis with respect to adjacent ordering
   ideal inIr = initial(Ir,r,interiorPoint);
   ring sAdjusted = copyAndChangeOrderingWP(r,interiorPoint,facetNormal);
   nMapFunc identity = n_SetMap(r->cf,sAdjusted->cf);
   int k = idSize(Ir);
   ideal inIsAdjusted = idInit(k);
   for (int i=0; i<k; i++)
     inIsAdjusted->m[i] = p_PermPoly(inIr->m[i],NULL,r,sAdjusted,identity,NULL,0);
   ideal inJsAdjusted = computeStdOfInitialIdeal(inIsAdjusted,sAdjusted);
 
   // find witnesses of the new standard basis elements of the initial ideal
   // with the help of the old standard basis of the ideal
   k = idSize(inJsAdjusted);
   ideal inJr = idInit(k);
   identity = n_SetMap(sAdjusted->cf,r->cf);
   for (int i=0; i<k; i++)
     inJr->m[i] = p_PermPoly(inJsAdjusted->m[i],NULL,sAdjusted,r,identity,NULL,0);
 
   ideal Jr = computeWitness(inJr,inIr,Ir,r);
   ring s = copyAndChangeOrderingLS(r,interiorPoint,facetNormal);
   identity = n_SetMap(r->cf,s->cf);
   ideal Js = idInit(k);
   for (int i=0; i<k; i++)
     Js->m[i] = p_PermPoly(Jr->m[i],NULL,r,s,identity,NULL,0);
 
   // this->reduce(Jr,r);
   // cleanup
   id_Delete(&inIsAdjusted,sAdjusted);
   id_Delete(&inJsAdjusted,sAdjusted);
   rDelete(sAdjusted);
   id_Delete(&inIr,r);
   id_Delete(&Jr,r);
   id_Delete(&inJr,r);
 
   assume(isValuationTrivial() || isOrderingLocalInT(s));
   return std::make_pair(Js,s);
 }

ideal tropicalStrategy::computeLift	(	const ideal	inJs,
		const ring	s,
		const ideal	inIr,
		const ideal	Ir,
		const ring	r
	)		const

Definition at line 646 of file tropicalStrategy.cc.

 {
   int k = idSize(inJs);
   ideal inJr = idInit(k);
   nMapFunc identitysr = n_SetMap(s->cf,r->cf);
   for (int i=0; i<k; i++)
     inJr->m[i] = p_PermPoly(inJs->m[i],NULL,s,r,identitysr,NULL,0);
 
   ideal Jr = computeWitness(inJr,inIr,Ir,r);
   nMapFunc identityrs = n_SetMap(r->cf,s->cf);
   ideal Js = idInit(k);
   for (int i=0; i<k; i++)
     Js->m[i] = p_PermPoly(Jr->m[i],NULL,r,s,identityrs,NULL,0);
   return Js;
 }

ideal tropicalStrategy::computeStdOfInitialIdeal	(	const ideal	inI,
		const ring	r
	)		const

given generators of the initial ideal, computes its standard basis

Definition at line 614 of file tropicalStrategy.cc.

 {
   // if valuation trivial, then compute std as usual
   if (isValuationTrivial())
     return gfanlib_kStd_wrapper(inI,r);
 
   // if valuation non-trivial, then uniformizing parameter is in ideal
   // so switch to residue field first and compute standard basis over the residue field
   ring rShortcut = copyAndChangeCoefficientRing(r);
   nMapFunc takingResidues = n_SetMap(r->cf,rShortcut->cf);
   int k = idSize(inI);
   ideal inIShortcut = idInit(k);
   for (int i=0; i<k; i++)
     inIShortcut->m[i] = p_PermPoly(inI->m[i],NULL,r,rShortcut,takingResidues,NULL,0);
   ideal inJShortcut = gfanlib_kStd_wrapper(inIShortcut,rShortcut);
 
   // and lift the result back to the ring with valuation
   nMapFunc takingRepresentatives = n_SetMap(rShortcut->cf,r->cf);
   k = idSize(inJShortcut);
   ideal inJ = idInit(k+1);
   inJ->m[0] = p_One(r);
   nMapFunc identity = n_SetMap(startingRing->cf,r->cf);
   p_SetCoeff(inJ->m[0],identity(uniformizingParameter,startingRing->cf,r->cf),r);
   for (int i=0; i<k; i++)
     inJ->m[i+1] = p_PermPoly(inJShortcut->m[i],NULL,rShortcut,r,takingRepresentatives,NULL,0);
 
   id_Delete(&inJShortcut,rShortcut);
   id_Delete(&inIShortcut,rShortcut);
   rDelete(rShortcut);
   return inJ;
 }

ideal tropicalStrategy::computeWitness	(	const ideal	inJ,
		const ideal	inI,
		const ideal	I,
		const ring	r
	)		const

suppose w a weight in maximal groebner cone of > suppose I (initially) reduced standard basis w.r.t.

and inI initial forms of its elements w.r.t. w

suppose inJ elements of initial ideal that are homogeneous w.r.t w returns J elements of ideal whose initial form w.r.t. w are inI in particular, if w lies also inthe maximal groebner cone of another ordering >' and inJ is a standard basis of the initial ideal w.r.t. >' then the returned J will be a standard baiss of the ideal w.r.t. >'

change ground ring into finite field and map the data into it

Compute a division with remainder over the finite field and map the result back to r

Compute the normal forms

Definition at line 532 of file tropicalStrategy.cc.

 {
   // if the valuation is trivial and the ring and ideal have not been extended,
   // then it is sufficient to return the difference between the elements of inJ
   // and their normal forms with respect to I and r
   if (isValuationTrivial())
     return witness(inJ,I,r);
   // if the valuation is non-trivial and the ring and ideal have been extended,
   // then we can make a shortcut through the residue field
   else
   {
     assume(idSize(inI)==idSize(I));
     int uni = findPositionOfUniformizingBinomial(I,r);
     assume(uni>=0);
     /**
      * change ground ring into finite field
      * and map the data into it
      */
     ring rShortcut = copyAndChangeCoefficientRing(r);
 
     int k = idSize(inJ);
     int l = idSize(I);
     ideal inJShortcut = idInit(k);
     ideal inIShortcut = idInit(l);
     nMapFunc takingResidues = n_SetMap(r->cf,rShortcut->cf);
     for (int i=0; i<k; i++)
       inJShortcut->m[i] = p_PermPoly(inJ->m[i],NULL,r,rShortcut,takingResidues,NULL,0);
     for (int j=0; j<l; j++)
       inIShortcut->m[j] = p_PermPoly(inI->m[j],NULL,r,rShortcut,takingResidues,NULL,0);
     id_Test(inJShortcut,rShortcut);
     id_Test(inIShortcut,rShortcut);
 
     /**
      * Compute a division with remainder over the finite field
      * and map the result back to r
      */
     matrix QShortcut = divisionDiscardingRemainder(inJShortcut,inIShortcut,rShortcut);
     matrix Q = mpNew(l,k);
     nMapFunc takingRepresentatives = n_SetMap(rShortcut->cf,r->cf);
     for (int ij=k*l-1; ij>=0; ij--)
       Q->m[ij] = p_PermPoly(QShortcut->m[ij],NULL,rShortcut,r,takingRepresentatives,NULL,0);
 
     nMapFunc identity = n_SetMap(startingRing->cf,r->cf);
     number p = identity(uniformizingParameter,startingRing->cf,r->cf);
 
     /**
      * Compute the normal forms
      */
     ideal J = idInit(k);
     for (int j=0; j<k; j++)
     {
       poly q0 = p_Copy(inJ->m[j],r);
       for (int i=0; i<l; i++)
       {
         poly qij = p_Copy(MATELEM(Q,i+1,j+1),r);
         poly inIi = p_Copy(inI->m[i],r);
         q0 = p_Add_q(q0,p_Neg(p_Mult_q(qij,inIi,r),r),r);
       }
       q0 = p_Div_nn(q0,p,r);
       poly q0g0 = p_Mult_q(q0,p_Copy(I->m[uni],r),r);
       // q0 = NULL;
       poly qigi = NULL;
       for (int i=0; i<l; i++)
       {
         poly qij = p_Copy(MATELEM(Q,i+1,j+1),r);
         // poly inIi = p_Copy(I->m[i],r);
         poly Ii = p_Copy(I->m[i],r);
         qigi = p_Add_q(qigi,p_Mult_q(qij,Ii,r),r);
       }
       J->m[j] = p_Add_q(q0g0,qigi,r);
     }
 
     id_Delete(&inIShortcut,rShortcut);
     id_Delete(&inJShortcut,rShortcut);
     mp_Delete(&QShortcut,rShortcut);
     rDelete(rShortcut);
     mp_Delete(&Q,r);
     n_Delete(&p,r->cf);
     return J;
   }
 }

ring tropicalStrategy::copyAndChangeCoefficientRing ( const ring r ) const

private

Definition at line 522 of file tropicalStrategy.cc.

 {
   ring rShortcut = rCopy0(r);
   nKillChar(rShortcut->cf);
   rShortcut->cf = nCopyCoeff(shortcutRing->cf);
   rComplete(rShortcut);
   rTest(rShortcut);
   return rShortcut;
 }

ring tropicalStrategy::copyAndChangeOrderingLS	(	const ring	r,
		const gfan::ZVector &	w,
		const gfan::ZVector &	v
	)		const

private

Definition at line 714 of file tropicalStrategy.cc.

 {
   // copy shortcutRing and change to desired ordering
   bool ok;
   ring s = rCopy0(r);
   int n = rVar(s);
   deleteOrdering(s);
   s->order = (int*) omAlloc0(5*sizeof(int));
   s->block0 = (int*) omAlloc0(5*sizeof(int));
   s->block1 = (int*) omAlloc0(5*sizeof(int));
   s->wvhdl = (int**) omAlloc0(5*sizeof(int**));
   s->order[0] = ringorder_a;
   s->block0[0] = 1;
   s->block1[0] = n;
   s->wvhdl[0] = ZVectorToIntStar(w,ok);
   s->order[1] = ringorder_a;
   s->block0[1] = 1;
   s->block1[1] = n;
   s->wvhdl[1] = ZVectorToIntStar(v,ok);
   s->order[2] = ringorder_lp;
   s->block0[2] = 1;
   s->block1[2] = n;
   s->order[3] = ringorder_C;
   rComplete(s);
   rTest(s);
 
   return s;
 }

ring tropicalStrategy::copyAndChangeOrderingWP	(	const ring	r,
		const gfan::ZVector &	w,
		const gfan::ZVector &	v
	)		const

private

Definition at line 683 of file tropicalStrategy.cc.

 {
   // copy shortcutRing and change to desired ordering
   bool ok;
   ring s = rCopy0(r);
   int n = rVar(s);
   deleteOrdering(s);
   gfan::ZVector wAdjusted = adjustWeightForHomogeneity(w);
   gfan::ZVector vAdjusted = adjustWeightUnderHomogeneity(v,wAdjusted);
   s->order = (int*) omAlloc0(5*sizeof(int));
   s->block0 = (int*) omAlloc0(5*sizeof(int));
   s->block1 = (int*) omAlloc0(5*sizeof(int));
   s->wvhdl = (int**) omAlloc0(5*sizeof(int**));
   s->order[0] = ringorder_a;
   s->block0[0] = 1;
   s->block1[0] = n;
   s->wvhdl[0] = ZVectorToIntStar(wAdjusted,ok);
   s->order[1] = ringorder_a;
   s->block0[1] = 1;
   s->block1[1] = n;
   s->wvhdl[1] = ZVectorToIntStar(vAdjusted,ok);
   s->order[2] = ringorder_lp;
   s->block0[2] = 1;
   s->block1[2] = n;
   s->order[3] = ringorder_C;
   rComplete(s);
   rTest(s);
 
   return s;
 }

tropicalStrategy tropicalStrategy::debugStrategy	(	const ideal	startIdeal,
		number	unifParameter,
		ring	startRing
	)

static

Definition at line 886 of file tropicalStrategy.cc.

 {
   tropicalStrategy debug;
   debug.originalRing = rCopy(startRing);
   debug.originalIdeal = id_Copy(startIdeal,startRing);
   debug.startingRing = rCopy(startRing);
   debug.startingIdeal = id_Copy(startIdeal,startRing);
   debug.uniformizingParameter = n_Copy(unifParameter,startRing->cf);
 
   debug.shortcutRing = rCopy0(startRing);
   nKillChar(debug.shortcutRing->cf);
   debug.shortcutRing->cf = nInitChar(n_Zp,(void*)(long)IsPrime(n_Int(unifParameter,startRing->cf)));
   rComplete(debug.shortcutRing);
   rTest(debug.shortcutRing);
 
   debug.onlyLowerHalfSpace = true;
   debug.weightAdjustingAlgorithm1 = valued_adjustWeightForHomogeneity;
   debug.weightAdjustingAlgorithm2 = valued_adjustWeightUnderHomogeneity;
   debug.extraReductionAlgorithm = ppreduceInitially;
 
   return debug;
 }

int tropicalStrategy::findPositionOfUniformizingBinomial	(	const ideal	I,
		const ring	r
	)		const

private

Definition at line 818 of file tropicalStrategy.cc.

 {
   assume(isValuationNonTrivial());
 
   // if the valuation is non-trivial then checks if the first generator is p-t
   nMapFunc identity = n_SetMap(startingRing->cf,r->cf);
   poly p = p_One(r);
   p_SetCoeff(p,identity(uniformizingParameter,startingRing->cf,r->cf),r);
   poly t = p_One(r);
   p_SetExp(t,1,1,r);
   p_Setm(t,r);
   poly pt = p_Add_q(p,p_Neg(t,r),r);
 
   for (int i=0; i<idSize(I); i++)
   {
     if (p_EqualPolys(I->m[i],pt,r))
     {
       p_Delete(&pt,r);
       return i;
     }
   }
   p_Delete(&pt,r);
   return -1;
 }

int tropicalStrategy::getExpectedDimension ( ) const

inline

returns the expected Dimension of the polyhedral output

Definition at line 205 of file tropicalStrategy.h.

   {
     return expectedDimension;
   }

gfan::ZCone tropicalStrategy::getHomogeneitySpace ( ) const

inline

returns the homogeneity space of the preimage ideal

Definition at line 228 of file tropicalStrategy.h.

   {
     return linealitySpace;
   }

ideal tropicalStrategy::getOriginalIdeal ( ) const

inline

returns the input ideal over the field with valuation

Definition at line 178 of file tropicalStrategy.h.

   {
     if (originalIdeal) id_Test(originalIdeal,originalRing);
     return originalIdeal;
   }

ring tropicalStrategy::getOriginalRing ( ) const

inline

returns the polynomial ring over the field with valuation

Definition at line 169 of file tropicalStrategy.h.

   {
     rTest(originalRing);
     return originalRing;
   }

ring tropicalStrategy::getShortcutRing ( ) const

inline

Definition at line 219 of file tropicalStrategy.h.

   {
     if (shortcutRing) rTest(shortcutRing);
     return shortcutRing;
   }

ring tropicalStrategy::getShortcutRingPrependingWeight	(	const ring	r,
		const gfan::ZVector &	w
	)		const

If valuation trivial, returns a copy of r with a positive weight prepended, such that any ideal homogeneous with respect to w is homogeneous with respect to that weight.

If valuation non-trivial, changes the coefficient ring to the residue field.

Definition at line 415 of file tropicalStrategy.cc.

 {
   ring rShortcut = rCopy0(r);
 
   // save old ordering
   int* order = rShortcut->order;
   int* block0 = rShortcut->block0;
   int* block1 = rShortcut->block1;
   int** wvhdl = rShortcut->wvhdl;
 
   // adjust weight and create new ordering
   gfan::ZVector w = adjustWeightForHomogeneity(v);
   int h = rBlocks(r); int n = rVar(r);
   rShortcut->order = (int*) omAlloc0((h+1)*sizeof(int));
   rShortcut->block0 = (int*) omAlloc0((h+1)*sizeof(int));
   rShortcut->block1 = (int*) omAlloc0((h+1)*sizeof(int));
   rShortcut->wvhdl = (int**) omAlloc0((h+1)*sizeof(int*));
   rShortcut->order[0] = ringorder_a;
   rShortcut->block0[0] = 1;
   rShortcut->block1[0] = n;
   bool overflow;
   rShortcut->wvhdl[0] = ZVectorToIntStar(w,overflow);
   for (int i=1; i<=h; i++)
   {
     rShortcut->order[i] = order[i-1];
     rShortcut->block0[i] = block0[i-1];
     rShortcut->block1[i] = block1[i-1];
     rShortcut->wvhdl[i] = wvhdl[i-1];
   }
 
   // if valuation non-trivial, change coefficient ring to residue field
   if (isValuationNonTrivial())
   {
     nKillChar(rShortcut->cf);
     rShortcut->cf = nCopyCoeff(shortcutRing->cf);
   }
   rComplete(rShortcut);
   rTest(rShortcut);
 
   // delete old ordering
   omFree(order);
   omFree(block0);
   omFree(block1);
   omFree(wvhdl);
 
   return rShortcut;
 }

ideal tropicalStrategy::getStartingIdeal ( ) const

inline

returns the input ideal

Definition at line 196 of file tropicalStrategy.h.

   {
     if (startingIdeal) id_Test(startingIdeal,startingRing);
     return startingIdeal;
   }

ring tropicalStrategy::getStartingRing ( ) const

inline

returns the polynomial ring over the valuation ring

Definition at line 187 of file tropicalStrategy.h.

   {
     if (startingRing) rTest(startingRing);
     return startingRing;
   }

number tropicalStrategy::getUniformizingParameter ( ) const

inline

returns the uniformizing parameter in the valuation ring

Definition at line 213 of file tropicalStrategy.h.

   {
     if (uniformizingParameter) n_Test(uniformizingParameter,startingRing->cf);
     return uniformizingParameter;
   }

bool tropicalStrategy::homogeneitySpaceContains ( const gfan::ZVector & v ) const

inline

returns true, if v is contained in the homogeneity space; false otherwise

Definition at line 236 of file tropicalStrategy.h.

   {
     return linealitySpace.contains(v);
   }

bool tropicalStrategy::isConstantCoefficientCase ( ) const

inline

Definition at line 150 of file tropicalStrategy.h.

   {
     bool b = (uniformizingParameter==NULL);
     return b;
   }

bool tropicalStrategy::isValuationNonTrivial ( ) const

inline

Definition at line 160 of file tropicalStrategy.h.

   {
     bool b = (uniformizingParameter!=NULL);
     return b;
   }

bool tropicalStrategy::isValuationTrivial ( ) const

inline

Definition at line 155 of file tropicalStrategy.h.

   {
     bool b = (uniformizingParameter==NULL);
     return b;
   }

gfan::ZVector tropicalStrategy::negateWeight ( const gfan::ZVector & w ) const

inline

Definition at line 269 of file tropicalStrategy.h.

   {
     gfan::ZVector wNeg(w.size());
 
     if (this->isValuationNonTrivial())
     {
       wNeg[0]=w[0];
       for (unsigned i=1; i<w.size(); i++)
         wNeg[i]=w[i];
     }
     else
       wNeg = -w;
 
     return wNeg;
   }

tropicalStrategy & tropicalStrategy::operator= ( const tropicalStrategy & currentStrategy )

assignment operator

Definition at line 332 of file tropicalStrategy.cc.

 {
   originalRing = rCopy(currentStrategy.getOriginalRing());
   originalIdeal = id_Copy(currentStrategy.getOriginalIdeal(),currentStrategy.getOriginalRing());
   expectedDimension = currentStrategy.getExpectedDimension();
   startingRing = rCopy(currentStrategy.getStartingRing());
   startingIdeal = id_Copy(currentStrategy.getStartingIdeal(),currentStrategy.getStartingRing());
   uniformizingParameter = n_Copy(currentStrategy.getUniformizingParameter(),startingRing->cf);
   shortcutRing = rCopy(currentStrategy.getShortcutRing());
   onlyLowerHalfSpace = currentStrategy.restrictToLowerHalfSpace();
   weightAdjustingAlgorithm1 = currentStrategy.weightAdjustingAlgorithm1;
   weightAdjustingAlgorithm2 = currentStrategy.weightAdjustingAlgorithm2;
   extraReductionAlgorithm = currentStrategy.extraReductionAlgorithm;
 
   if (originalRing) rTest(originalRing);
   if (originalIdeal) id_Test(originalIdeal,originalRing);
   if (startingRing) rTest(startingRing);
   if (startingIdeal) id_Test(startingIdeal,startingRing);
   if (uniformizingParameter) n_Test(uniformizingParameter,startingRing->cf);
   if (shortcutRing) rTest(shortcutRing);
 
   return *this;
 }

void tropicalStrategy::pReduce	(	ideal	I,
		const ring	r
	)		const

Definition at line 399 of file tropicalStrategy.cc.

 {
   rTest(r);
   id_Test(I,r);
 
   if (isValuationTrivial())
     return;
 
   nMapFunc identity = n_SetMap(startingRing->cf,r->cf);
   number p = identity(uniformizingParameter,startingRing->cf,r->cf);
   ::pReduce(I,p,r);
   n_Delete(&p,r->cf);
 
   return;
 }

void tropicalStrategy::putUniformizingBinomialInFront	(	ideal	I,
		const ring	r,
		const number	q
	)		const

private

Definition at line 356 of file tropicalStrategy.cc.

 {
   poly p = p_One(r);
   p_SetCoeff(p,q,r);
   poly t = p_One(r);
   p_SetExp(t,1,1,r);
   p_Setm(t,r);
   poly pt = p_Add_q(p,p_Neg(t,r),r);
 
   int k = idSize(I);
   int l;
   for (l=0; l<k; l++)
   {
     if (p_EqualPolys(I->m[l],pt,r))
       break;
   }
   p_Delete(&pt,r);
 
   if (l>1)
   {
     pt = I->m[l];
     for (int i=l; i>0; i--)
       I->m[l] = I->m[l-1];
     I->m[0] = pt;
     pt = NULL;
   }
   return;
 }

bool tropicalStrategy::reduce	(	ideal	I,
		const ring	r
	)		const

reduces the generators of an ideal I so that the inequalities and equations of the Groebner cone can be read off.

Definition at line 385 of file tropicalStrategy.cc.

 {
   rTest(r);
   id_Test(I,r);
 
   nMapFunc identity = n_SetMap(startingRing->cf,r->cf);
   number p = identity(uniformizingParameter,startingRing->cf,r->cf);
   bool b = extraReductionAlgorithm(I,r,p);
   // putUniformizingBinomialInFront(I,r,p);
   n_Delete(&p,r->cf);
 
   return b;
 }

bool tropicalStrategy::restrictToLowerHalfSpace ( ) const

inline

returns true, if valuation non-trivial, false otherwise

Definition at line 244 of file tropicalStrategy.h.

   {
     return onlyLowerHalfSpace;
   }

Field Documentation

int tropicalStrategy::expectedDimension

private

the expected Dimension of the polyhedral output, i.e.

the dimension of the ideal if valuation trivial or the dimension of the ideal plus one if valuation non-trivial (as the output is supposed to be intersected with a hyperplane)

Definition at line 54 of file tropicalStrategy.h.

bool(* tropicalStrategy::extraReductionAlgorithm) (ideal I, ring r, number p)

private

A function that reduces the generators of an ideal I so that the inequalities and equations of the Groebner cone can be read off.

Definition at line 99 of file tropicalStrategy.h.

gfan::ZCone tropicalStrategy::linealitySpace

private

the homogeneity space of the Grobner fan

Definition at line 58 of file tropicalStrategy.h.

bool tropicalStrategy::onlyLowerHalfSpace

private

true if valuation non-trivial, false otherwise

Definition at line 79 of file tropicalStrategy.h.

ideal tropicalStrategy::originalIdeal

private

input ideal, assumed to be a homogeneous prime ideal

Definition at line 47 of file tropicalStrategy.h.

ring tropicalStrategy::originalRing

private

polynomial ring over a field with valuation

Definition at line 43 of file tropicalStrategy.h.

ring tropicalStrategy::shortcutRing

private

polynomial ring over the residue field

Definition at line 74 of file tropicalStrategy.h.

ideal tropicalStrategy::startingIdeal

private

preimage of the input ideal under the map that sends t to the uniformizing parameter

Definition at line 66 of file tropicalStrategy.h.

ring tropicalStrategy::startingRing

private

polynomial ring over the valuation ring extended by one extra variable t

Definition at line 62 of file tropicalStrategy.h.

number tropicalStrategy::uniformizingParameter

private

uniformizing parameter in the valuation ring

Definition at line 70 of file tropicalStrategy.h.

gfan::ZVector(* tropicalStrategy::weightAdjustingAlgorithm1) (const gfan::ZVector &w)

private

A function such that: Given weight w, returns a strictly positive weight u such that an ideal satisfying the valuation-sepcific homogeneity conditions is weighted homogeneous with respect to w if and only if it is homogeneous with respect to u.

Definition at line 87 of file tropicalStrategy.h.

gfan::ZVector(* tropicalStrategy::weightAdjustingAlgorithm2) (const gfan::ZVector &v, const gfan::ZVector &w)

private

A function such that: Given strictly positive weight w and weight v, returns a strictly positive weight u such that on an ideal that is weighted homogeneous with respect to w the weights u and v coincide.

Definition at line 94 of file tropicalStrategy.h.

The documentation for this class was generated from the following files:

Singular/dyn_modules/gfanlib/tropicalStrategy.h
Singular/dyn_modules/gfanlib/tropicalStrategy.cc

Public Member Functions

Static Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Field Documentation