tropicalStrategy Class Reference

#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 ()
	destructor More...
tropicalStrategy &	operator= (const tropicalStrategy &currentStrategy)
	assignment operator More...
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	getExpectedAmbientDimension () const
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...

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 36 of file tropicalStrategy.h.

Constructor & Destructor Documentation

tropicalStrategy() [1/3]

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 138 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_Z(r));
  if (!completelyHomogeneous)
  {
    weightAdjustingAlgorithm1 = valued_adjustWeightForHomogeneity;
    weightAdjustingAlgorithm2 = valued_adjustWeightUnderHomogeneity;
  }
  if (!completeSpace)
    onlyLowerHalfSpace = true;
}

tropicalStrategy() [2/3]

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 277 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,FALSE); // do not copy q-ideal
  nKillChar(shortcutRing->cf);
  shortcutRing->cf = nInitChar(n_Zp,(void*)(long)IsPrime(n_Int(uniformizingParameter,startingRing->cf)));
  rComplete(shortcutRing);
  rTest(shortcutRing);
}

tropicalStrategy() [3/3]

tropicalStrategy::tropicalStrategy

(

const tropicalStrategy &

currentStrategy

)

copy constructor

Definition at line 316 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::~tropicalStrategy

(

)

destructor

Definition at line 346 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

adjustWeightForHomogeneity()

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 248 of file tropicalStrategy.h.

  {
    return this->weightAdjustingAlgorithm1(w);
  }

adjustWeightUnderHomogeneity()

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 258 of file tropicalStrategy.h.

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

checkForUniformizingBinomial()

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 814 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<IDELEMS(I); i++)
  {
    if (p_EqualPolys(I->m[i],pt,r))
    {
      p_Delete(&pt,r);
      return true;
    }
  }
  p_Delete(&pt,r);
  return false;
}

checkForUniformizingParameter()

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 867 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<IDELEMS(inI); i++)
  {
    if (p_EqualPolys(inI->m[i],p,r))
    {
      p_Delete(&p,r);
      return true;
    }
  }
  p_Delete(&p,r);
  return false;
}

checkInitialIdealForMonomial()

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 496 of file tropicalStrategy.cc.

{
  // quick check whether I already contains an ideal
  int k = IDELEMS(I);
  for (int i=0; i<k; i++)
  {
    poly g = I->m[i];
    if (g!=NULL
    && 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;
  }
 
  gfan::ZCone C0 = homogeneitySpace(inIShortcut,rShortcut);
  gfan::ZCone pos = gfan::ZCone::positiveOrthant(C0.ambientDimension());
  gfan::ZCone C0pos = intersection(C0,pos);
  C0pos.canonicalize();
  gfan::ZVector wpos = C0pos.getRelativeInteriorPoint();
  assume(checkForNonPositiveEntries(wpos));
 
  // check initial ideal for monomial and
  // if it exsists, return a copy of the monomial in the input ring
  poly p = searchForMonomialViaStepwiseSaturation(inIShortcut,rShortcut,wpos);
  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);
}

computeFlip()

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 762 of file tropicalStrategy.cc.

{
  assume(isValuationTrivial() || interiorPoint[0].sign()<0);
  assume(checkForUniformizingBinomial(Ir,r));
  assume(checkWeightVector(Ir,r,interiorPoint));
 
  // 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 = IDELEMS(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 = IDELEMS(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);
 
  reduce(Js,s);
  assume(areIdealsEqual(Js,s,Ir,r));
  assume(isValuationTrivial() || isOrderingLocalInT(s));
  assume(checkWeightVector(Js,s,interiorPoint));
 
  // 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);
}

computeLift()

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

Definition at line 688 of file tropicalStrategy.cc.

{
  int k = IDELEMS(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;
}

computeStdOfInitialIdeal()

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

given generators of the initial ideal, computes its standard basis

Definition at line 656 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 = IDELEMS(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 = IDELEMS(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;
}

computeWitness()

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 574 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(IDELEMS(inI)==IDELEMS(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 = IDELEMS(inJ);
    int l = IDELEMS(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;
  }
}

copyAndChangeCoefficientRing()

ring tropicalStrategy::copyAndChangeCoefficientRing ( const ring  r ) const

private

Definition at line 564 of file tropicalStrategy.cc.

{
  ring rShortcut = rCopy0(r,FALSE); // do not copy q-ideal
  nKillChar(rShortcut->cf);
  rShortcut->cf = nCopyCoeff(shortcutRing->cf);
  rComplete(rShortcut);
  rTest(rShortcut);
  return rShortcut;
}

copyAndChangeOrderingLS()

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

private

Definition at line 734 of file tropicalStrategy.cc.

{
  // copy shortcutRing and change to desired ordering
  bool ok;
  ring s = rCopy0(r,FALSE,FALSE);
  int n = rVar(s);
  s->order = (rRingOrder_t*) omAlloc0(5*sizeof(rRingOrder_t));
  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;
}

copyAndChangeOrderingWP()

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

private

Definition at line 704 of file tropicalStrategy.cc.

{
  // copy shortcutRing and change to desired ordering
  bool ok;
  ring s = rCopy0(r,FALSE,FALSE);
  int n = rVar(s);
  gfan::ZVector wAdjusted = adjustWeightForHomogeneity(w);
  gfan::ZVector vAdjusted = adjustWeightUnderHomogeneity(v,wAdjusted);
  s->order = (rRingOrder_t*) omAlloc0(5*sizeof(rRingOrder_t));
  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;
}

findPositionOfUniformizingBinomial()

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

private

Definition at line 842 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<IDELEMS(I); i++)
  {
    if (p_EqualPolys(I->m[i],pt,r))
    {
      p_Delete(&pt,r);
      return i;
    }
  }
  p_Delete(&pt,r);
  return -1;
}

getExpectedAmbientDimension()

int tropicalStrategy::getExpectedAmbientDimension ( ) const

inline

Definition at line 191 of file tropicalStrategy.h.

  {
    return rVar(startingRing);
  }

getExpectedDimension()

int tropicalStrategy::getExpectedDimension ( ) const

inline

returns the expected Dimension of the polyhedral output

Definition at line 199 of file tropicalStrategy.h.

  {
    return expectedDimension;
  }

getHomogeneitySpace()

gfan::ZCone tropicalStrategy::getHomogeneitySpace ( ) const

inline

returns the homogeneity space of the preimage ideal

Definition at line 222 of file tropicalStrategy.h.

  {
    return linealitySpace;
  }

getOriginalIdeal()

ideal tropicalStrategy::getOriginalIdeal ( ) const

inline

returns the input ideal over the field with valuation

Definition at line 167 of file tropicalStrategy.h.

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

getOriginalRing()

ring tropicalStrategy::getOriginalRing ( ) const

inline

returns the polynomial ring over the field with valuation

Definition at line 158 of file tropicalStrategy.h.

  {
    rTest(originalRing);
    return originalRing;
  }

getShortcutRing()

ring tropicalStrategy::getShortcutRing ( ) const

inline

Definition at line 213 of file tropicalStrategy.h.

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

getShortcutRingPrependingWeight()

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 448 of file tropicalStrategy.cc.

{
  ring rShortcut = rCopy0(r,FALSE); // do not copy q-ideal
 
  // save old ordering
  rRingOrder_t* 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 = (rRingOrder_t*) omAlloc0((h+2)*sizeof(rRingOrder_t));
  rShortcut->block0 = (int*) omAlloc0((h+2)*sizeof(int));
  rShortcut->block1 = (int*) omAlloc0((h+2)*sizeof(int));
  rShortcut->wvhdl = (int**) omAlloc0((h+2)*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;
}

getStartingIdeal()

ideal tropicalStrategy::getStartingIdeal ( ) const

inline

returns the input ideal

Definition at line 185 of file tropicalStrategy.h.

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

getStartingRing()

ring tropicalStrategy::getStartingRing ( ) const

inline

returns the polynomial ring over the valuation ring

Definition at line 176 of file tropicalStrategy.h.

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

getUniformizingParameter()

number tropicalStrategy::getUniformizingParameter ( ) const

inline

returns the uniformizing parameter in the valuation ring

Definition at line 207 of file tropicalStrategy.h.

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

homogeneitySpaceContains()

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

inline

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

Definition at line 230 of file tropicalStrategy.h.

  {
    return linealitySpace.contains(v);
  }

isValuationNonTrivial()

bool tropicalStrategy::isValuationNonTrivial ( ) const

inline

Definition at line 149 of file tropicalStrategy.h.

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

isValuationTrivial()

bool tropicalStrategy::isValuationTrivial ( ) const

inline

Definition at line 144 of file tropicalStrategy.h.

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

negateWeight()

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

inline

Definition at line 263 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;
  }

operator=()

tropicalStrategy & tropicalStrategy::operator=

(

const tropicalStrategy &

currentStrategy

)

assignment operator

Definition at line 363 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;
}

pReduce()

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

Definition at line 432 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;
}

putUniformizingBinomialInFront()

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

private

Definition at line 387 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 = IDELEMS(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;
}

reduce()

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 416 of file tropicalStrategy.cc.

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

restrictToLowerHalfSpace()

bool tropicalStrategy::restrictToLowerHalfSpace ( ) const

inline

returns true, if valuation non-trivial, false otherwise

Definition at line 238 of file tropicalStrategy.h.

  {
    return onlyLowerHalfSpace;
  }

Field Documentation

expectedDimension

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 53 of file tropicalStrategy.h.

extraReductionAlgorithm

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 98 of file tropicalStrategy.h.

linealitySpace

gfan::ZCone tropicalStrategy::linealitySpace

private

the homogeneity space of the Grobner fan

Definition at line 57 of file tropicalStrategy.h.

onlyLowerHalfSpace

bool tropicalStrategy::onlyLowerHalfSpace

private

true if valuation non-trivial, false otherwise

Definition at line 78 of file tropicalStrategy.h.

originalIdeal

ideal tropicalStrategy::originalIdeal

private

input ideal, assumed to be a homogeneous prime ideal

Definition at line 46 of file tropicalStrategy.h.

originalRing

ring tropicalStrategy::originalRing

private

polynomial ring over a field with valuation

Definition at line 42 of file tropicalStrategy.h.

shortcutRing

ring tropicalStrategy::shortcutRing

private

polynomial ring over the residue field

Definition at line 73 of file tropicalStrategy.h.

startingIdeal

ideal tropicalStrategy::startingIdeal

private

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

Definition at line 65 of file tropicalStrategy.h.

startingRing

ring tropicalStrategy::startingRing

private

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

Definition at line 61 of file tropicalStrategy.h.

uniformizingParameter

number tropicalStrategy::uniformizingParameter

private

uniformizing parameter in the valuation ring

Definition at line 69 of file tropicalStrategy.h.

weightAdjustingAlgorithm1

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 86 of file tropicalStrategy.h.

weightAdjustingAlgorithm2

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 93 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