Loading...
Searching...
No Matches
gfan.h
Go to the documentation of this file.
/*
gfan.h Interface to gfan.cc
Author: monerjan
*/
#ifndef GFAN_H
#define GFAN_H
#include "kernel/mod2.h"
#if HAVE_GFANLIB
#include "misc/int64vec.h"
#include "gfanlib/config.h"
#ifdef HAVE_CDDLIB_SETOPER_H
#include <cddlib/setoper.h>
#include <cddlib/cdd.h>
#include <cddlib/cddmp.h>
#else
#ifdef HAVE_CDD_SETOPER_H
#include <cdd/setoper.h>
#include <cdd/cdd.h>
#include <cdd/cddmp.h>
#else
#include <setoper.h>
#include <cdd.h>
#include <cddmp.h>
#endif
#endif
#include "bbfan.h"
#include "bbcone.h"
EXTERN_VAR int gfanHeuristic;
#ifndef USE_ZFAN
#define USE_ZFAN
#endif
#ifndef USE_ZFAN
lists grfan(ideal inputIdeal, int heuristic, bool singleCone);
#else
#include "gfanlib/gfanlib.h"
gfan::ZFan *grfan(ideal inputIdeal, int h, bool singleCone);
#endif
// lists grcone_by_intvec(ideal inputIdeal);
class facet
{
private:
/** \brief Inner normal of the facet, describing it uniquely up to isomorphism */
int64vec *fNormal;
/** \brief An interior point of the facet*/
int64vec *interiorPoint;
/** \brief Universal Cone Number
* The number of the cone the facet belongs to, Set in getConeNormals()
*/
int UCN;
/** \brief The codim of the facet
*/
short codim;
/** \brief The Groebner basis on the other side of a shared facet
*
* In order not to have to compute the flipped GB twice we store the basis we already get
* when identifying search facets. Thus in the next step of the reverse search we can
* just copy the old cone and update the facet and the gcBasis.
* facet::flibGB is set via facet::setFlipGB() and printed via facet::printFlipGB
*/
ideal flipGB; //The Groebner Basis on the other side, computed via gcone::flip
public:
/** \brief Boolean value to indicate whether a facet is flippable or not
* This is also used to mark facets that nominally are flippable but which do
* not intersect with the positive orthant. This check is done in gcone::getCodim2Normals
*/
bool isFlippable; //**flippable facet? */
//bool isIncoming; //Is the facet incoming or outgoing in the reverse search? No longer in use
facet *next; //Pointer to next facet
facet *prev; //Pointer to predecessor. Needed for the SearchList in noRevS
facet *codim2Ptr; //Pointer to (codim-2)-facet. Bit of recursion here ;-)
int numCodim2Facets; //#of (codim-2)-facets of this facet. Set in getCodim2Normals()
unsigned numRays; //Number of spanning rays of the facet
ring flipRing; //the ring on the other side of the facet
// int64vec **fRays;
/** The default constructor. */
facet();
/** Constructor for lower dimensional faces*/
facet(const int &n);
/** The copy constructor */
facet(const facet& f);
/** A shallow copy of facets*/
facet* shallowCopy(const facet& f);
void shallowDelete();
/** The default destructor */
~facet();
/** Comparison operator*/
// inline bool operator==(const facet *f,const facet *g);
/** \brief Comparison of facets*/
// inline bool areEqual(facet *f, facet *g);//Now static
/** Stores the facet normal \param int64vec*/
inline void setFacetNormal(int64vec *iv);
/** Returns the facet normal */
inline int64vec *getFacetNormal() const;
/** Return a reference to the facet normal*/
inline const int64vec *getRef2FacetNormal() const;
/** Method to print the facet normal*/
inline void printNormal() const;
/** Store the flipped GB*/
inline void setFlipGB(ideal I);
/** Return the flipped GB*/
inline ideal getFlipGB();
/** Print the flipped GB*/
inline void printFlipGB();
/** Set the UCN */
inline void setUCN(int n);
/** \brief Get the UCN
* Returns the UCN iff this != NULL, else -1
*/
inline int getUCN();
/** Store an interior point of the facet */
inline void setInteriorPoint(int64vec *iv);
inline int64vec *getInteriorPoint();
inline const int64vec *getRef2InteriorPoint();
/** \brief Debugging function
* prints the facet normal an all (codim-2)-facets that belong to it
*/
volatile void fDebugPrint();
friend class gcone;
};
/**
*\brief Implements the cone structure
*
* A cone is represented by a linked list of facet normals
* @see facet
*/
class gcone
{
private:
ideal inputIdeal; //the original
ring baseRing; //the basering of the cone
int64vec *ivIntPt; //an interior point of the cone
int UCN; //unique number of the cone
int pred; //UCN of the cone this one is derived from
STATIC_VAR int counter;
public:
/** \brief Pointer to the first facet */
facet *facetPtr; //Will hold the adress of the first facet; set by gcone::getConeNormals
#ifdef gfanp
STATIC_VAR float time_getConeNormals;
STATIC_VAR float time_getCodim2Normals;
STATIC_VAR float t_getExtremalRays;
STATIC_VAR float t_ddPolyh;
STATIC_VAR float time_flip;
STATIC_VAR float time_flip2;
STATIC_VAR float t_areEqual;
STATIC_VAR float t_ffG;
STATIC_VAR float t_markings;
STATIC_VAR float t_dd;
STATIC_VAR float t_kStd;
STATIC_VAR float time_enqueue;
STATIC_VAR float time_computeInv;
STATIC_VAR float t_ddMC;
STATIC_VAR float t_mI;
STATIC_VAR float t_iP;
STATIC_VAR float t_isParallel;
STATIC_VAR unsigned parallelButNotEqual;
STATIC_VAR unsigned numberOfFacetChecks;
#endif
/** Matrix to contain the homogeneity/lineality space */
STATIC_VAR dd_MatrixPtr dd_LinealitySpace;
STATIC_VAR int lengthOfSearchList;
/** Maximum size of the searchlist*/
STATIC_VAR int maxSize;
/** is the ideal homogeneous? */
STATIC_VAR bool hasHomInput;
/** # of variables in the ring */
STATIC_VAR int numVars; //#of variables in the ring
/** The hilbert function - for the homogeneous case*/
STATIC_VAR int64vec *hilbertFunction;
/** The zero vector. Needed in case of fNormal mismatch*/
STATIC_VAR int64vec *ivZeroVector;
/** # of facets of the cone
* This value is set by gcone::getConeNormals
*/
int numFacets; //#of facets of the cone
/**
* At least as a workaround we store the irredundant facets of a matrix here.
* This is needed to compute an interior points of a cone. Note that there
* will be non-flippable facets in it!
*/
dd_MatrixPtr ddFacets; //Matrix to store irredundant facets of the cone
/** Array of intvecs representing the rays of the cone*/
int64vec **gcRays;
unsigned numRays; //#rays of the cone
/** Contains the Groebner basis of the cone. Is set by gcone::getGB(ideal I)*/
ideal gcBasis; //GB of the cone, set by gcone::getGB();
gcone *next; //Pointer to next cone
gcone *prev;
gcone();
gcone(ring r, ideal I);
gcone(const gcone& gc, const facet &f);
~gcone();
inline int getCounter();
inline ring getBaseRing();
inline ring getRef2BaseRing();
inline void setBaseRing(ring r);
inline void setIntPoint(int64vec *iv);
inline int64vec *getIntPoint(bool shallow=FALSE);
inline void showIntPoint();
inline void setNumFacets();
inline int getNumFacets();
inline int getUCN();
inline int getPredUCN();
volatile void showFacets(short codim=1);
// volatile void showSLA(facet &f);
// void idDebugPrint(const ideal &I);
// void invPrint(const ideal &I);
// bool isMonomial(const ideal &I);
// int64vec *ivNeg(const int64vec *iv);
// inline int dotProduct(int64vec &iva, int64vec &ivb);
// inline int dotProduct(const int64vec &iva, const int64vec &ivb);
// inline bool isParallel(const int64vec &a, const int64vec &b);
void noRevS(gcone &gcRoot, bool usingIntPoint=FALSE);
// inline int intgcd(const int &a, const int &b);
void writeConeToFile(const gcone &gc, bool usingIntPoints=FALSE);
void readConeFromFile(int gcNum, gcone *gc);
int64vec f2M(gcone *gc, facet *f, int n=1);
// inline void sortRays(gcone *gc);
//The real stuff
void getConeNormals(const ideal &I, bool compIntPoint=FALSE);
void getCodim2Normals(const gcone &gc);
void getExtremalRays(const gcone &gc);
void orderRays();
void flip(ideal gb, facet *f);
void flip2(const ideal &gb, facet *f);
void computeInv(const ideal &gb, ideal &inv, const int64vec &f);
//poly restOfDiv(poly const &f, ideal const &I); removed with r12286
inline ideal ffG(const ideal &H, const ideal &G);
inline void getGB(ideal const &inputIdeal);
void interiorPoint( dd_MatrixPtr &M, int64vec &iv);//used from flip and optionally from getConeNormals
// void interiorPoint2(); //removed Feb 8th, 2010, new method Feb 19th, 2010, again removed Mar 16th, 2010
void preprocessInequalities(dd_MatrixPtr &M);
ring rCopyAndAddWeight(const ring &r, int64vec *ivw);
ring rCopyAndAddWeight2(const ring &, const int64vec *, const int64vec *);
// ring rCopyAndChangeWeight(const ring &r, int64vec *ivw); //NOTE remove
// void reverseSearch(gcone *gcAct); //NOTE both removed from r12286
// bool isSearchFacet(gcone &gcTmp, facet *testfacet); //NOTE remove
void makeInt(const dd_MatrixPtr &M, const int line, int64vec &n);
// void normalize();//NOTE REMOVE
facet * enqueueNewFacets(facet *f);
facet * enqueue2(facet *f);
// dd_MatrixPtr facets2Matrix(const gcone &gc);//NOTE remove
/** Compute the lineality space Ax=0 and return it as dd_MatrixPtr dd_LinealitySpace*/
dd_MatrixPtr computeLinealitySpace();
inline bool iv64isStrictlyPositive(const int64vec *);
/** Exchange 2 ordertype_a by just 1 */
void replaceDouble_ringorder_a_ByASingleOne();
// static void gcone::idPrint(ideal &I);
// friend class facet;
};
lists lprepareResult(gcone *gc, const int n);
/* static int64 int64gcd(const int64 &a, const int64 &b); */
/* static int intgcd(const int &a, const int &b); */
/* static int dotProduct(const int64vec &iva, const int64vec &ivb); */
/* static bool isParallel(const int64vec &a, const int64vec &b); */
/* static int64vec *ivNeg(/\*const*\/ int64vec *iv); */
/* static void idDebugPrint(const ideal &I); */
/* static volatile void showSLA(facet &f); */
/* static bool isMonomial(const ideal &I); */
/* static bool ivAreEqual(const int64vec &a, const int64vec &b); */
/* static bool areEqual2(facet *f, facet *g); */
/* static bool areEqual( facet *f, facet *g); */
// bool iv64isStrictlyPositive(int64vec *);
#endif
#endif
FALSE
#define FALSE
Definition auxiliary.h:97
bbcone.h
bbfan.h
f
FILE * f
Definition checklibs.c:9
facet
Definition gfan.h:47
facet::getFlipGB
ideal getFlipGB()
Return the flipped GB.
facet::facet
facet()
The default constructor.
facet::codim2Ptr
facet * codim2Ptr
Definition gfan.h:82
facet::shallowCopy
facet * shallowCopy(const facet &f)
A shallow copy of facets.
facet::facet
facet(const int &n)
Constructor for lower dimensional faces.
facet::fDebugPrint
volatile void fDebugPrint()
Debugging function prints the facet normal an all (codim-2)-facets that belong to it.
facet::isFlippable
bool isFlippable
Boolean value to indicate whether a facet is flippable or not This is also used to mark facets that n...
Definition gfan.h:78
facet::UCN
int UCN
Universal Cone Number The number of the cone the facet belongs to, Set in getConeNormals().
Definition gfan.h:58
facet::setFlipGB
void setFlipGB(ideal I)
Store the flipped GB.
facet::facet
facet(const facet &f)
The copy constructor.
facet::printFlipGB
void printFlipGB()
Print the flipped GB.
facet::codim
short codim
The codim of the facet.
Definition gfan.h:62
facet::setFacetNormal
void setFacetNormal(int64vec *iv)
Comparison operator.
facet::setInteriorPoint
void setInteriorPoint(int64vec *iv)
Store an interior point of the facet.
facet::getRef2InteriorPoint
const int64vec * getRef2InteriorPoint()
facet::flipRing
ring flipRing
Definition gfan.h:85
facet::printNormal
void printNormal() const
Method to print the facet normal.
facet::numRays
unsigned numRays
Definition gfan.h:84
facet::gcone
friend class gcone
Definition gfan.h:131
facet::setUCN
void setUCN(int n)
Set the UCN.
facet::~facet
~facet()
The default destructor.
facet::getUCN
int getUCN()
Get the UCN Returns the UCN iff this != NULL, else -1.
facet::getFacetNormal
int64vec * getFacetNormal() const
Returns the facet normal.
facet::next
facet * next
Definition gfan.h:80
facet::fNormal
int64vec * fNormal
Inner normal of the facet, describing it uniquely up to isomorphism.
Definition gfan.h:50
facet::flipGB
ideal flipGB
The Groebner basis on the other side of a shared facet.
Definition gfan.h:71
facet::getInteriorPoint
int64vec * getInteriorPoint()
facet::prev
facet * prev
Definition gfan.h:81
facet::interiorPoint
int64vec * interiorPoint
An interior point of the facet.
Definition gfan.h:53
facet::getRef2FacetNormal
const int64vec * getRef2FacetNormal() const
Return a reference to the facet normal.
facet::numCodim2Facets
int numCodim2Facets
Definition gfan.h:83
facet::shallowDelete
void shallowDelete()
gcone
Implements the cone structure.
Definition gfan.h:143
gcone::dd_LinealitySpace
STATIC_VAR dd_MatrixPtr dd_LinealitySpace
Matrix to contain the homogeneity/lineality space.
Definition gfan.h:177
gcone::inputIdeal
ideal inputIdeal
Definition gfan.h:145
gcone::interiorPoint
void interiorPoint(dd_MatrixPtr &M, int64vec &iv)
gcone::getIntPoint
int64vec * getIntPoint(bool shallow=FALSE)
gcone::next
gcone * next
Definition gfan.h:207
gcone::getUCN
int getUCN()
gcone::orderRays
void orderRays()
gcone::noRevS
void noRevS(gcone &gcRoot, bool usingIntPoint=FALSE)
gcone::gcBasis
ideal gcBasis
Contains the Groebner basis of the cone.
Definition gfan.h:206
gcone::getGB
void getGB(ideal const &inputIdeal)
gcone::getBaseRing
ring getBaseRing()
gcone::getExtremalRays
void getExtremalRays(const gcone &gc)
gcone::getRef2BaseRing
ring getRef2BaseRing()
gcone::rCopyAndAddWeight
ring rCopyAndAddWeight(const ring &r, int64vec *ivw)
gcone::lengthOfSearchList
STATIC_VAR int lengthOfSearchList
Definition gfan.h:178
gcone::getConeNormals
void getConeNormals(const ideal &I, bool compIntPoint=FALSE)
gcone::maxSize
STATIC_VAR int maxSize
Maximum size of the searchlist.
Definition gfan.h:180
gcone::pred
int pred
Definition gfan.h:149
gcone::setBaseRing
void setBaseRing(ring r)
gcone::numVars
STATIC_VAR int numVars
Definition gfan.h:184
gcone::~gcone
~gcone()
gcone::baseRing
ring baseRing
Definition gfan.h:146
gcone::getPredUCN
int getPredUCN()
gcone::facetPtr
facet * facetPtr
Pointer to the first facet.
Definition gfan.h:154
gcone::computeLinealitySpace
dd_MatrixPtr computeLinealitySpace()
Compute the lineality space Ax=0 and return it as dd_MatrixPtr dd_LinealitySpace.
gcone::ivIntPt
int64vec * ivIntPt
Definition gfan.h:147
gcone::computeInv
void computeInv(const ideal &gb, ideal &inv, const int64vec &f)
gcone::numFacets
int numFacets
Definition gfan.h:193
gcone::prev
gcone * prev
Definition gfan.h:208
gcone::getCounter
int getCounter()
gcone::flip2
void flip2(const ideal &gb, facet *f)
gcone::gcone
gcone(const gcone &gc, const facet &f)
gcone::ddFacets
dd_MatrixPtr ddFacets
At least as a workaround we store the irredundant facets of a matrix here.
Definition gfan.h:200
gcone::ivZeroVector
STATIC_VAR int64vec * ivZeroVector
The zero vector.
Definition gfan.h:188
gcone::replaceDouble_ringorder_a_ByASingleOne
void replaceDouble_ringorder_a_ByASingleOne()
Exchange 2 ordertype_a by just 1.
gcone::hilbertFunction
STATIC_VAR int64vec * hilbertFunction
The hilbert function - for the homogeneous case.
Definition gfan.h:186
gcone::numRays
unsigned numRays
Definition gfan.h:204
gcone::gcone
gcone()
gcone::UCN
int UCN
Definition gfan.h:148
gcone::counter
STATIC_VAR int counter
Definition gfan.h:150
gcone::enqueue2
facet * enqueue2(facet *f)
gcone::gcone
gcone(ring r, ideal I)
gcone::writeConeToFile
void writeConeToFile(const gcone &gc, bool usingIntPoints=FALSE)
gcone::getNumFacets
int getNumFacets()
gcone::ffG
ideal ffG(const ideal &H, const ideal &G)
gcone::enqueueNewFacets
facet * enqueueNewFacets(facet *f)
gcone::setNumFacets
void setNumFacets()
gcone::setIntPoint
void setIntPoint(int64vec *iv)
gcone::gcRays
int64vec ** gcRays
Array of intvecs representing the rays of the cone.
Definition gfan.h:203
gcone::showFacets
volatile void showFacets(short codim=1)
gcone::iv64isStrictlyPositive
bool iv64isStrictlyPositive(const int64vec *)
gcone::rCopyAndAddWeight2
ring rCopyAndAddWeight2(const ring &, const int64vec *, const int64vec *)
gcone::f2M
int64vec f2M(gcone *gc, facet *f, int n=1)
gcone::flip
void flip(ideal gb, facet *f)
gcone::preprocessInequalities
void preprocessInequalities(dd_MatrixPtr &M)
gcone::readConeFromFile
void readConeFromFile(int gcNum, gcone *gc)
gcone::getCodim2Normals
void getCodim2Normals(const gcone &gc)
gcone::hasHomInput
STATIC_VAR bool hasHomInput
is the ideal homogeneous?
Definition gfan.h:182
gcone::makeInt
void makeInt(const dd_MatrixPtr &M, const int line, int64vec &n)
gcone::showIntPoint
void showIntPoint()
int64vec
Definition int64vec.h:24
H
CanonicalForm H
Definition facAbsFact.cc:60
lprepareResult
lists lprepareResult(gcone *gc, const int n)
grfan
gfan::ZFan * grfan(ideal inputIdeal, int h, bool singleCone)
gfanHeuristic
EXTERN_VAR int gfanHeuristic
Definition gfan.h:33
STATIC_VAR
#define STATIC_VAR
Definition globaldefs.h:7
EXTERN_VAR
#define EXTERN_VAR
Definition globaldefs.h:6
int64vec.h
G
STATIC_VAR TreeM * G
Definition janet.cc:31
h
STATIC_VAR Poly * h
Definition janet.cc:971
mod2.h
lists
slists * lists
Definition mpr_numeric.h:146
M
#define M
Definition sirandom.c:25