tropicalTraversal.h File Reference

#include "groebnerCone.h"

Go to the source code of this file.

Functions
groebnerCones	tropicalTraversalMinimizingFlips (const groebnerCone startingCone)
groebnerCones	tropicalTraversal (const groebnerCone startingCone)
groebnerCones	groebnerTraversal (const groebnerCone startingCone)

Function Documentation

groebnerTraversal()

groebnerCones groebnerTraversal

(

const groebnerCone

startingCone

)

Pick a maximal Groebner cone from the working list and compute interior points on its facets as well as outer facet normals

Definition at line 141 of file tropicalTraversal.cc.

{
  const tropicalStrategy* currentStrategy = startingCone.getTropicalStrategy();
 
  groebnerCones groebnerFan;
  groebnerCones workingList;
  workingList.insert(startingCone);
  std::set<gfan::ZVector> finishedInteriorPoints;
  bool onlyLowerHalfSpace = !currentStrategy->isValuationTrivial();
 
  while(!workingList.empty())
  {
    /**
     * Pick a maximal Groebner cone from the working list
     * and compute interior points on its facets as well as outer facet normals
     */
    groebnerCone sigma=*(workingList.begin());
    workingList.erase(workingList.begin());
 
    std::pair<gfan::ZMatrix,gfan::ZMatrix> interiorPointsAndOuterFacetNormals = interiorPointsAndNormalsOfFacets(sigma.getPolyhedralCone(), finishedInteriorPoints, onlyLowerHalfSpace);
    gfan::ZMatrix interiorPoints = interiorPointsAndOuterFacetNormals.first;
    gfan::ZMatrix outerFacetNormals = interiorPointsAndOuterFacetNormals.second;
    std::vector<bool> needToFlip = checkNecessaryGroebnerFlips(groebnerFan,workingList, interiorPoints);
 
    for (int i=0; i<interiorPoints.getHeight(); i++)
    {
      gfan::ZVector interiorPoint = interiorPoints[i];
 
      if (needToFlip[i]==true)
      {
        groebnerCone neighbour = sigma.flipCone(interiorPoint,outerFacetNormals[i]);
        workingList.insert(neighbour);
      }
      finishedInteriorPoints.insert(interiorPoints[i]);
    }
 
    sigma.deletePolynomialData();
    groebnerFan.insert(sigma);
    if (printlevel > 0)
      Print("cones finished: %lu   cones in working list: %lu\n",
      (unsigned long)groebnerFan.size(), (unsigned long)workingList.size());
  }
  return groebnerFan;
}

tropicalTraversal()

groebnerCones tropicalTraversal

(

const groebnerCone

startingCone

)

tropicalTraversalMinimizingFlips()

groebnerCones tropicalTraversalMinimizingFlips

(

const groebnerCone

startingCone

)

Pick an element the working list and compute interior points on its facets

For each interior point, compute the rays of the tropical star in that point

Definition at line 52 of file tropicalTraversal.cc.

{
  groebnerCones tropicalVariety;
  if (startingCone.isTrivial())
  {
    return tropicalVariety;
  }
 
  groebnerCones workingList;
  workingList.insert(startingCone);
  const tropicalStrategy* currentStrategy=startingCone.getTropicalStrategy();
  std::set<gfan::ZVector> finishedInteriorPoints;
  while(!workingList.empty())
  {
    /**
     * Pick an element the working list and compute interior points on its facets
     */
    groebnerCone sigma=*(workingList.begin());
    gfan::ZMatrix interiorPoints = interiorPointsOfFacets(sigma.getPolyhedralCone(),finishedInteriorPoints);
 
    for (int i=0; i<interiorPoints.getHeight(); i++)
    {
      /**
       * For each interior point, compute the rays of the tropical star in that point
       */
      gfan::ZVector interiorPoint = interiorPoints[i];
      if (!(currentStrategy->restrictToLowerHalfSpace() && interiorPoint[0].sign()==0))
      {
        ideal inI = initial(sigma.getPolynomialIdeal(),sigma.getPolynomialRing(),interiorPoint);
        ideal inISTD = gfanlib_satStd_wrapper(inI,sigma.getPolynomialRing());
        id_Delete(&inI,sigma.getPolynomialRing());
        gfan::ZMatrix normalVectors = raysOfTropicalStar(inISTD,
                                                         sigma.getPolynomialRing(),
                                                         interiorPoint,
                                                         sigma.getTropicalStrategy());
        id_Delete(&inISTD,sigma.getPolynomialRing());
 
        std::vector<bool> needToFlip = checkNecessaryTropicalFlips(tropicalVariety,workingList,interiorPoint,normalVectors);
        for (int j=0; j<normalVectors.getHeight(); j++)
        {
          if (needToFlip[j])
          {
            groebnerCone neighbour = sigma.flipCone(interiorPoint,normalVectors[j]);
            workingList.insert(neighbour);
          }
        }
      }
      finishedInteriorPoints.insert(interiorPoint);
    }
 
    sigma.deletePolynomialData();
    workingList.erase(sigma);
    tropicalVariety.insert(sigma);
    if (printlevel > 0)
      Print("cones finished: %lu   cones in working list: %lu\n",
      (unsigned long)tropicalVariety.size(), (unsigned long)workingList.size());
  }
  return tropicalVariety;
}