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#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
46class 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. */
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*/
97 /** The default destructor */
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
142class 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
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};
272lists 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 * 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: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.
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: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 * getInteriorPoint()
facet * prev
Definition: gfan.h:81
int64vec * interiorPoint
An interior point of the facet.
Definition: gfan.h:53
const int64vec * getRef2FacetNormal() const
Return a reference to the facet normal.
int numCodim2Facets
Definition: gfan.h:83
void shallowDelete()
Implements the cone structure.
Definition: gfan.h:143
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)
int64vec * getIntPoint(bool shallow=FALSE)
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
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
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:203
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:182
void makeInt(const dd_MatrixPtr &M, const int line, int64vec &n)
void showIntPoint()
Definition: lists.h:24
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: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