source: git/kernel/gfan.h @ 85583b

spielwiese
Last change on this file since 85583b was 85583b, checked in by Martin Monerjan, 14 years ago
Back to intvec intvec* facet::getRef2FacetNormal() speeds up gcone::areEqual by about 65% check for hasHomInput in getExtremalRays & bugfix bool gcone::iv64isStrictlyPositive git-svn-id: file:///usr/local/Singular/svn/trunk@12551 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 8.3 KB
Line 
1/*
2gfan.h Interface to gfan.cc
3
4$Author: monerjan $
5$Date: 2009/11/03 06:57:32 $
6$Header: /usr/local/Singular/cvsroot/kernel/gfan.h,v 1.13 2009/11/03 06:57:32 monerjan Exp $
7$Id$
8*/
9#ifdef HAVE_GFAN
10
11#ifndef GFAN_H
12#define GFAN_H
13
14#include "intvec.h"
15#include "intvec.h"
16
17#define p800
18#ifdef p800
19#include "../../cddlib/include/setoper.h"
20#include "../../cddlib/include/cdd.h"
21#include "../../cddlib/include/cddmp.h"
22#endif
23extern int gfanHeuristic;
24// extern dd_MatrixPtr ddLinealitySpace;
25#define gfanp
26// #ifdef gfanp
27// extern       static float time_getConeNormals;
28// extern       static float time_getCodim2Normals;
29// extern       static float time_flip;
30// extern       static float time_enqueue;
31// extern       static float time_computeInv;
32// #endif
33//ideal getGB(ideal inputIdeal);
34// ideal gfan(ideal inputIdeal, int heuristic);
35lists gfan(ideal inputIdeal, int heuristic);
36
37//int dotProduct(intvec a, intvec b);
38//bool isParallel(intvec a, intvec b);
39
40class facet
41{
42        private:
43                /** \brief Inner normal of the facet, describing it uniquely up to isomorphism */
44                intvec *fNormal;
45               
46                /** \brief An interior point of the facet*/
47                intvec *interiorPoint;
48               
49                /** \brief Universal Cone Number
50                 * The number of the cone the facet belongs to, Set in getConeNormals()
51                 */
52                int UCN;
53               
54                /** \brief The codim of the facet
55                 */
56                int codim;
57               
58                /** \brief The Groebner basis on the other side of a shared facet
59                 *
60                 * In order not to have to compute the flipped GB twice we store the basis we already get
61                 * when identifying search facets. Thus in the next step of the reverse search we can
62                 * just copy the old cone and update the facet and the gcBasis.
63                 * facet::flibGB is set via facet::setFlipGB() and printed via facet::printFlipGB
64                 */
65                ideal flipGB;           //The Groebner Basis on the other side, computed via gcone::flip
66               
67        public: 
68                /** \brief Boolean value to indicate whether a facet is flippable or not
69                * This is also used to mark facets that nominally are flippable but which do
70                * not intersect with the positive orthant. This check is done in gcone::getCodim2Normals
71                 */     
72                bool isFlippable;       //**flippable facet? */
73                bool isIncoming;        //Is the facet incoming or outgoing in the reverse search?
74                facet *next;            //Pointer to next facet
75                facet *prev;            //Pointer to predecessor. Needed for the SearchList in noRevS
76                facet *codim2Ptr;       //Pointer to (codim-2)-facet. Bit of recursion here ;-)
77                int numCodim2Facets;    //#of (codim-2)-facets of this facet. Set in getCodim2Normals()
78                ring flipRing;          //the ring on the other side of the facet
79                unsigned numRays;       //Number of spanning rays of the cone                   
80                /** The default constructor. */
81                facet();
82                /** Constructor for lower dimensional faces*/
83                facet(int const &n);
84                /**  The copy constructor */
85                facet(const facet& f);
86               
87                /** The default destructor */
88                ~facet();
89                               
90                /** \brief Comparison of facets*/
91                inline bool areEqual(facet *f, facet *g);
92                /** Stores the facet normal \param intvec*/
93                inline void setFacetNormal(intvec *iv);
94                /** Hopefully returns the facet normal */
95                inline intvec *getFacetNormal();
96                /** Return a reference to the facet normal*/
97                inline intvec *getRef2FacetNormal();
98                /** Method to print the facet normal*/
99                inline void printNormal();
100                /** Store the flipped GB*/
101                inline void setFlipGB(ideal I);
102                /** Return the flipped GB*/
103                inline ideal getFlipGB();
104                /** Print the flipped GB*/
105                inline void printFlipGB();
106                /** Set the UCN */
107                inline void setUCN(int n);
108                /** \brief Get the UCN
109                 * Returns the UCN iff this != NULL, else -1
110                 */
111                inline int getUCN();
112                /** Store an interior point of the facet */
113                inline void setInteriorPoint(intvec *iv);
114                inline intvec *getInteriorPoint();
115                /** \brief Debugging function
116                 * prints the facet normal an all (codim-2)-facets that belong to it
117                 */
118                inline void fDebugPrint();
119                friend class gcone;             
120};
121
122/**
123 *\brief Implements the cone structure
124 *
125 * A cone is represented by a linked list of facet normals
126 * @see facet
127 */
128
129class gcone
130{
131        private:               
132//              ring rootRing;          //good to know this -> generic walk
133                ideal inputIdeal;       //the original
134                ring baseRing;          //the basering of the cone                             
135                intvec *ivIntPt;        //an interior point of the cone
136                int UCN;                //unique number of the cone
137                int pred;               //UCN of the cone this one is derived from
138                static int counter;
139               
140        public: 
141                /** \brief Pointer to the first facet */
142                facet *facetPtr;        //Will hold the adress of the first facet; set by gcone::getConeNormals
143#ifdef gfanp
144                static float time_getConeNormals;
145                static float time_getCodim2Normals;
146                static float t_getExtremalRays;
147                static float time_flip;
148                static float t_areEqual;
149                static float t_ffG;
150                static float t_markings;
151                static float t_dd;
152                static float t_kStd;
153                static float time_enqueue;             
154                static float time_computeInv;
155                static float t_ddMC;
156                static float t_mI;
157                static float t_iP;
158                static unsigned parallelButNotEqual;
159                static unsigned numberOfFacetChecks;
160#endif
161                /** Matrix to contain the homogeneity/lineality space */
162                static dd_MatrixPtr dd_LinealitySpace;
163                static int lengthOfSearchList;
164                /** Maximum size of the searchlist*/
165                static int maxSize;
166                /** is the ideal homogeneous? */
167                static bool hasHomInput;
168                /** # of variables in the ring */
169                int numVars;            //#of variables in the ring
170               
171                /** # of facets of the cone
172                 * This value is set by gcone::getConeNormals
173                 */
174                int numFacets;          //#of facets of the cone
175               
176                /**
177                 * At least as a workaround we store the irredundant facets of a matrix here.
178                 * This is needed to compute an interior points of a cone. Note that there
179                 * will be non-flippable facets in it!           
180                 */
181                dd_MatrixPtr ddFacets;  //Matrix to store irredundant facets of the cone
182               
183                /** Contains the Groebner basis of the cone. Is set by gcone::getGB(ideal I)*/
184                ideal gcBasis;          //GB of the cone, set by gcone::getGB();
185                gcone *next;            //Pointer to next cone
186                gcone *prev;
187               
188                gcone();
189                gcone(ring r, ideal I);
190                gcone(const gcone& gc, const facet &f);
191                ~gcone();
192                inline int getCounter();
193                inline ring getBaseRing();
194                inline void setIntPoint(intvec *iv);
195                inline intvec *getIntPoint();
196                inline void showIntPoint();
197                inline void setNumFacets();
198                inline int getNumFacets();
199                inline int getUCN();
200                inline int getPredUCN();               
201                volatile void showFacets(short codim=1);
202                inline volatile void showSLA(facet &f);
203                inline void idDebugPrint(const ideal &I);
204                inline void invPrint(const ideal &I);
205                inline bool isMonomial(const ideal &I);
206                inline intvec *ivNeg(intvec *iv);
207                inline int dotProduct(intvec &iva, intvec &ivb);
208                inline bool isParallel(intvec &a, intvec &b);
209                inline bool areEqual(intvec &a, intvec &b);
210                inline bool areEqual( facet *f,  facet *g);
211                inline int intgcd(int a, int b);
212                inline void writeConeToFile(const gcone &gc, bool usingIntPoints=FALSE);
213                inline void readConeFromFile(int gcNum, gcone *gc);
214                inline intvec f2M(gcone *gc, facet *f, int n=1);
215                inline void sortRays(gcone *gc);
216                //The real stuff
217                inline void getConeNormals(const ideal &I, bool compIntPoint=FALSE);
218                inline void getCodim2Normals(const gcone &gc);
219                inline void getExtremalRays(const gcone &gc);
220                inline void flip(ideal gb, facet *f);
221                inline void computeInv(ideal &gb, ideal &inv, intvec &f);
222//              poly restOfDiv(poly const &f, ideal const &I); removed with r12286
223                inline ideal ffG(const ideal &H, const ideal &G);
224                inline void getGB(ideal const &inputIdeal);             
225                inline void interiorPoint( dd_MatrixPtr &M, intvec &iv);
226//              inline void interiorPoint2(const dd_MatrixPtr &M, intvec &iv);//removed Feb 8th, 2010
227                inline void preprocessInequalities(dd_MatrixPtr &M);
228                ring rCopyAndAddWeight(const ring &r, intvec *ivw);
229                ring rCopyAndChangeWeight(const ring &r, intvec *ivw);         
230//              void reverseSearch(gcone *gcAct); //NOTE both removed from r12286
231//              bool isSearchFacet(gcone &gcTmp, facet *testfacet);
232                void noRevS(gcone &gcRoot, bool usingIntPoint=FALSE);
233                inline void makeInt(const dd_MatrixPtr &M, const int line, intvec &n);
234                inline void normalize();
235                facet * enqueueNewFacets(facet *f);
236                facet * enqueue2(facet *f);
237                dd_MatrixPtr facets2Matrix(const gcone &gc);
238                /** Compute the lineality space Ax=0 and return it as dd_MatrixPtr dd_LinealitySpace*/
239                inline dd_MatrixPtr computeLinealitySpace();
240                inline bool iv64isStrictlyPositive(intvec *);
241//              static void gcone::idPrint(ideal &I);           
242                friend class facet;     
243};
244lists lprepareResult(gcone *gc, int n);
245// bool iv64isStrictlyPositive(intvec *);
246#endif
247#endif
Note: See TracBrowser for help on using the repository browser.