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