My Project
gfan.h
Go to the documentation of this file.
1 /*
2 gfan.h Interface to gfan.cc
3 
4 Author: monerjan
5 */
6 #ifndef GFAN_H
7 #define GFAN_H
8 
9 #include "kernel/mod2.h"
10 
11 #if HAVE_GFANLIB
12 
13 #include "misc/int64vec.h"
14 
15 #include "gfanlib/config.h"
16 #ifdef HAVE_CDDLIB_SETOPER_H
17 #include <cddlib/setoper.h>
18 #include <cddlib/cdd.h>
19 #include <cddlib/cddmp.h>
20 #else
21 #ifdef HAVE_CDD_SETOPER_H
22 #include <cdd/setoper.h>
23 #include <cdd/cdd.h>
24 #include <cdd/cddmp.h>
25 #else
26 #include <setoper.h>
27 #include <cdd.h>
28 #include <cddmp.h>
29 #endif
30 #endif
31 #include "bbfan.h"
32 #include "bbcone.h"
34 
35 #ifndef USE_ZFAN
36 #define USE_ZFAN
37 #endif
38 #ifndef USE_ZFAN
39  lists grfan(ideal inputIdeal, int heuristic, bool singleCone);
40 #else
41  #include "gfanlib/gfanlib.h"
42  gfan::ZFan *grfan(ideal inputIdeal, int h, bool singleCone);
43 #endif
44 // lists grcone_by_intvec(ideal inputIdeal);
45 
46 class facet
47 {
48  private:
49  /** \brief Inner normal of the facet, describing it uniquely up to isomorphism */
51 
52  /** \brief An interior point of the facet*/
54 
55  /** \brief Universal Cone Number
56  * The number of the cone the facet belongs to, Set in getConeNormals()
57  */
58  int UCN;
59 
60  /** \brief The codim of the facet
61  */
62  short codim;
63 
64  /** \brief The Groebner basis on the other side of a shared facet
65  *
66  * In order not to have to compute the flipped GB twice we store the basis we already get
67  * when identifying search facets. Thus in the next step of the reverse search we can
68  * just copy the old cone and update the facet and the gcBasis.
69  * facet::flibGB is set via facet::setFlipGB() and printed via facet::printFlipGB
70  */
71  ideal flipGB; //The Groebner Basis on the other side, computed via gcone::flip
72 
73  public:
74  /** \brief Boolean value to indicate whether a facet is flippable or not
75  * This is also used to mark facets that nominally are flippable but which do
76  * not intersect with the positive orthant. This check is done in gcone::getCodim2Normals
77  */
78  bool isFlippable; //**flippable facet? */
79  //bool isIncoming; //Is the facet incoming or outgoing in the reverse search? No longer in use
80  facet *next; //Pointer to next facet
81  facet *prev; //Pointer to predecessor. Needed for the SearchList in noRevS
82  facet *codim2Ptr; //Pointer to (codim-2)-facet. Bit of recursion here ;-)
83  int numCodim2Facets; //#of (codim-2)-facets of this facet. Set in getCodim2Normals()
84  unsigned numRays; //Number of spanning rays of the facet
85  ring flipRing; //the ring on the other side of the facet
86 // int64vec **fRays;
87 
88  /** The default constructor. */
89  facet();
90  /** Constructor for lower dimensional faces*/
91  facet(const int &n);
92  /** The copy constructor */
93  facet(const facet& f);
94  /** A shallow copy of facets*/
96  void shallowDelete();
97  /** The default destructor */
98  ~facet();
99  /** Comparison operator*/
100 // inline bool operator==(const facet *f,const facet *g);
101  /** \brief Comparison of facets*/
102 // inline bool areEqual(facet *f, facet *g);//Now static
103  /** Stores the facet normal \param int64vec*/
104  inline void setFacetNormal(int64vec *iv);
105  /** Returns the facet normal */
106  inline int64vec *getFacetNormal() const;
107  /** Return a reference to the facet normal*/
108  inline const int64vec *getRef2FacetNormal() const;
109  /** Method to print the facet normal*/
110  inline void printNormal() const;
111  /** Store the flipped GB*/
112  inline void setFlipGB(ideal I);
113  /** Return the flipped GB*/
114  inline ideal getFlipGB();
115  /** Print the flipped GB*/
116  inline void printFlipGB();
117  /** Set the UCN */
118  inline void setUCN(int n);
119  /** \brief Get the UCN
120  * Returns the UCN iff this != NULL, else -1
121  */
122  inline int getUCN();
123  /** Store an interior point of the facet */
124  inline void setInteriorPoint(int64vec *iv);
127  /** \brief Debugging function
128  * prints the facet normal an all (codim-2)-facets that belong to it
129  */
130  volatile void fDebugPrint();
131  friend class gcone;
132 };
133 
134 
135 /**
136  *\brief Implements the cone structure
137  *
138  * A cone is represented by a linked list of facet normals
139  * @see facet
140  */
141 
142 class gcone
143 {
144  private:
145  ideal inputIdeal; //the original
146  ring baseRing; //the basering of the cone
147  int64vec *ivIntPt; //an interior point of the cone
148  int UCN; //unique number of the cone
149  int pred; //UCN of the cone this one is derived from
151 
152  public:
153  /** \brief Pointer to the first facet */
154  facet *facetPtr; //Will hold the adress of the first facet; set by gcone::getConeNormals
155 #ifdef gfanp
156  STATIC_VAR float time_getConeNormals;
157  STATIC_VAR float time_getCodim2Normals;
158  STATIC_VAR float t_getExtremalRays;
159  STATIC_VAR float t_ddPolyh;
160  STATIC_VAR float time_flip;
161  STATIC_VAR float time_flip2;
162  STATIC_VAR float t_areEqual;
163  STATIC_VAR float t_ffG;
164  STATIC_VAR float t_markings;
165  STATIC_VAR float t_dd;
166  STATIC_VAR float t_kStd;
167  STATIC_VAR float time_enqueue;
168  STATIC_VAR float time_computeInv;
169  STATIC_VAR float t_ddMC;
170  STATIC_VAR float t_mI;
171  STATIC_VAR float t_iP;
172  STATIC_VAR float t_isParallel;
173  STATIC_VAR unsigned parallelButNotEqual;
174  STATIC_VAR unsigned numberOfFacetChecks;
175 #endif
176  /** Matrix to contain the homogeneity/lineality space */
179  /** Maximum size of the searchlist*/
181  /** is the ideal homogeneous? */
183  /** # of variables in the ring */
184  STATIC_VAR int numVars; //#of variables in the ring
185  /** The hilbert function - for the homogeneous case*/
187  /** The zero vector. Needed in case of fNormal mismatch*/
189 
190  /** # of facets of the cone
191  * This value is set by gcone::getConeNormals
192  */
193  int numFacets; //#of facets of the cone
194 
195  /**
196  * At least as a workaround we store the irredundant facets of a matrix here.
197  * This is needed to compute an interior points of a cone. Note that there
198  * will be non-flippable facets in it!
199  */
200  dd_MatrixPtr ddFacets; //Matrix to store irredundant facets of the cone
201 
202  /** Array of intvecs representing the rays of the cone*/
204  unsigned numRays; //#rays of the cone
205  /** Contains the Groebner basis of the cone. Is set by gcone::getGB(ideal I)*/
206  ideal gcBasis; //GB of the cone, set by gcone::getGB();
207  gcone *next; //Pointer to next cone
209 
210  gcone();
211  gcone(ring r, ideal I);
212  gcone(const gcone& gc, const facet &f);
214  inline int getCounter();
215  inline ring getBaseRing();
216  inline ring getRef2BaseRing();
217  inline void setBaseRing(ring r);
218  inline void setIntPoint(int64vec *iv);
219  inline int64vec *getIntPoint(bool shallow=FALSE);
220  inline void showIntPoint();
221  inline void setNumFacets();
222  inline int getNumFacets();
223  inline int getUCN();
224  inline int getPredUCN();
225  volatile void showFacets(short codim=1);
226 // volatile void showSLA(facet &f);
227 // void idDebugPrint(const ideal &I);
228 // void invPrint(const ideal &I);
229 // bool isMonomial(const ideal &I);
230 // int64vec *ivNeg(const int64vec *iv);
231 // inline int dotProduct(int64vec &iva, int64vec &ivb);
232 // inline int dotProduct(const int64vec &iva, const int64vec &ivb);
233 // inline bool isParallel(const int64vec &a, const int64vec &b);
234  void noRevS(gcone &gcRoot, bool usingIntPoint=FALSE);
235 // inline int intgcd(const int &a, const int &b);
236  void writeConeToFile(const gcone &gc, bool usingIntPoints=FALSE);
237  void readConeFromFile(int gcNum, gcone *gc);
238  int64vec f2M(gcone *gc, facet *f, int n=1);
239 // inline void sortRays(gcone *gc);
240  //The real stuff
241  void getConeNormals(const ideal &I, bool compIntPoint=FALSE);
242  void getCodim2Normals(const gcone &gc);
243  void getExtremalRays(const gcone &gc);
244  void orderRays();
245  void flip(ideal gb, facet *f);
246  void flip2(const ideal &gb, facet *f);
247  void computeInv(const ideal &gb, ideal &inv, const int64vec &f);
248  //poly restOfDiv(poly const &f, ideal const &I); removed with r12286
249  inline ideal ffG(const ideal &H, const ideal &G);
250  inline void getGB(ideal const &inputIdeal);
251  void interiorPoint( dd_MatrixPtr &M, int64vec &iv);//used from flip and optionally from getConeNormals
252 // void interiorPoint2(); //removed Feb 8th, 2010, new method Feb 19th, 2010, again removed Mar 16th, 2010
253  void preprocessInequalities(dd_MatrixPtr &M);
254  ring rCopyAndAddWeight(const ring &r, int64vec *ivw);
255  ring rCopyAndAddWeight2(const ring &, const int64vec *, const int64vec *);
256 // ring rCopyAndChangeWeight(const ring &r, int64vec *ivw); //NOTE remove
257 // void reverseSearch(gcone *gcAct); //NOTE both removed from r12286
258 // bool isSearchFacet(gcone &gcTmp, facet *testfacet); //NOTE remove
259  void makeInt(const dd_MatrixPtr &M, const int line, int64vec &n);
260 // void normalize();//NOTE REMOVE
263 // dd_MatrixPtr facets2Matrix(const gcone &gc);//NOTE remove
264  /** Compute the lineality space Ax=0 and return it as dd_MatrixPtr dd_LinealitySpace*/
265  dd_MatrixPtr computeLinealitySpace();
266  inline bool iv64isStrictlyPositive(const int64vec *);
267  /** Exchange 2 ordertype_a by just 1 */
269 // static void gcone::idPrint(ideal &I);
270 // friend class facet;
271 };
272 lists lprepareResult(gcone *gc, const int n);
273 /* static int64 int64gcd(const int64 &a, const int64 &b); */
274 /* static int intgcd(const int &a, const int &b); */
275 /* static int dotProduct(const int64vec &iva, const int64vec &ivb); */
276 /* static bool isParallel(const int64vec &a, const int64vec &b); */
277 /* static int64vec *ivNeg(/\*const*\/ int64vec *iv); */
278 /* static void idDebugPrint(const ideal &I); */
279 /* static volatile void showSLA(facet &f); */
280 /* static bool isMonomial(const ideal &I); */
281 /* static bool ivAreEqual(const int64vec &a, const int64vec &b); */
282 /* static bool areEqual2(facet *f, facet *g); */
283 /* static bool areEqual( facet *f, facet *g); */
284 // bool iv64isStrictlyPositive(int64vec *);
285 #endif
286 #endif
#define FALSE
Definition: auxiliary.h:96
FILE * f
Definition: checklibs.c:9
Definition: gfan.h:47
ideal getFlipGB()
Return the flipped GB.
facet()
The default constructor.
facet * codim2Ptr
Definition: gfan.h:82
facet(const int &n)
Constructor for lower dimensional faces.
volatile void fDebugPrint()
Debugging function prints the facet normal an all (codim-2)-facets that belong to it.
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
int UCN
Universal Cone Number The number of the cone the facet belongs to, Set in getConeNormals()
Definition: gfan.h:58
void setFlipGB(ideal I)
Store the flipped GB.
facet(const facet &f)
The copy constructor.
void printFlipGB()
Print the flipped GB.
short codim
The codim of the facet.
Definition: gfan.h:62
void setFacetNormal(int64vec *iv)
Comparison operator.
void setInteriorPoint(int64vec *iv)
Store an interior point of the facet.
const int64vec * getRef2InteriorPoint()
ring flipRing
Definition: gfan.h:85
void printNormal() const
Method to print the facet normal.
unsigned numRays
Definition: gfan.h:84
void setUCN(int n)
Set the UCN.
~facet()
The default destructor.
const int64vec * getRef2FacetNormal() const
Return a reference to the facet normal.
int64vec * getInteriorPoint()
int getUCN()
Get the UCN Returns the UCN iff this != NULL, else -1.
facet * shallowCopy(const facet &f)
A shallow copy of facets.
facet * next
Definition: gfan.h:80
int64vec * fNormal
Inner normal of the facet, describing it uniquely up to isomorphism.
Definition: gfan.h:50
ideal flipGB
The Groebner basis on the other side of a shared facet.
Definition: gfan.h:71
int64vec * getFacetNormal() const
Returns the facet normal.
facet * prev
Definition: gfan.h:81
int64vec * interiorPoint
An interior point of the facet.
Definition: gfan.h:53
int numCodim2Facets
Definition: gfan.h:83
void shallowDelete()
Implements the cone structure.
Definition: gfan.h:143
int64vec * getIntPoint(bool shallow=FALSE)
STATIC_VAR dd_MatrixPtr dd_LinealitySpace
Matrix to contain the homogeneity/lineality space.
Definition: gfan.h:177
ideal inputIdeal
Definition: gfan.h:145
void interiorPoint(dd_MatrixPtr &M, int64vec &iv)
gcone * next
Definition: gfan.h:207
int getUCN()
void orderRays()
void noRevS(gcone &gcRoot, bool usingIntPoint=FALSE)
ideal gcBasis
Contains the Groebner basis of the cone.
Definition: gfan.h:206
facet * enqueueNewFacets(facet *f)
void getGB(ideal const &inputIdeal)
ring getBaseRing()
void getExtremalRays(const gcone &gc)
ring getRef2BaseRing()
ring rCopyAndAddWeight(const ring &r, int64vec *ivw)
STATIC_VAR int lengthOfSearchList
Definition: gfan.h:178
void getConeNormals(const ideal &I, bool compIntPoint=FALSE)
STATIC_VAR int maxSize
Maximum size of the searchlist.
Definition: gfan.h:180
int pred
Definition: gfan.h:149
void setBaseRing(ring r)
STATIC_VAR int numVars
Definition: gfan.h:184
ring baseRing
Definition: gfan.h:146
int getPredUCN()
facet * facetPtr
Pointer to the first facet.
Definition: gfan.h:154
dd_MatrixPtr computeLinealitySpace()
Compute the lineality space Ax=0 and return it as dd_MatrixPtr dd_LinealitySpace.
int64vec * ivIntPt
Definition: gfan.h:147
void computeInv(const ideal &gb, ideal &inv, const int64vec &f)
int numFacets
Definition: gfan.h:193
gcone * prev
Definition: gfan.h:208
int getCounter()
void flip2(const ideal &gb, facet *f)
gcone(const gcone &gc, const facet &f)
dd_MatrixPtr ddFacets
At least as a workaround we store the irredundant facets of a matrix here.
Definition: gfan.h:200
STATIC_VAR int64vec * ivZeroVector
The zero vector.
Definition: gfan.h:188
void replaceDouble_ringorder_a_ByASingleOne()
Exchange 2 ordertype_a by just 1.
STATIC_VAR int64vec * hilbertFunction
The hilbert function - for the homogeneous case.
Definition: gfan.h:186
unsigned numRays
Definition: gfan.h:204
int UCN
Definition: gfan.h:148
STATIC_VAR int counter
Definition: gfan.h:150
gcone(ring r, ideal I)
void writeConeToFile(const gcone &gc, bool usingIntPoints=FALSE)
int getNumFacets()
ideal ffG(const ideal &H, const ideal &G)
void setNumFacets()
void setIntPoint(int64vec *iv)
int64vec ** gcRays
Array of intvecs representing the rays of the cone.
Definition: gfan.h:203
volatile void showFacets(short codim=1)
bool iv64isStrictlyPositive(const int64vec *)
facet * enqueue2(facet *f)
ring rCopyAndAddWeight2(const ring &, const int64vec *, const int64vec *)
int64vec f2M(gcone *gc, facet *f, int n=1)
void flip(ideal gb, facet *f)
void preprocessInequalities(dd_MatrixPtr &M)
void readConeFromFile(int gcNum, gcone *gc)
void getCodim2Normals(const gcone &gc)
STATIC_VAR bool hasHomInput
is the ideal homogeneous?
Definition: gfan.h:182
void makeInt(const dd_MatrixPtr &M, const int line, int64vec &n)
void showIntPoint()
Definition: lists.h:24
CanonicalForm H
Definition: facAbsFact.cc:60
gfan::ZFan * grfan(ideal inputIdeal, int h, bool singleCone)
lists lprepareResult(gcone *gc, const int n)
EXTERN_VAR int gfanHeuristic
Definition: gfan.h:33
#define STATIC_VAR
Definition: globaldefs.h:7
#define EXTERN_VAR
Definition: globaldefs.h:6
STATIC_VAR TreeM * G
Definition: janet.cc:31
STATIC_VAR Poly * h
Definition: janet.cc:971
#define M
Definition: sirandom.c:25