source: git/kernel/gfan.h @ 835d83

spielwiese
Last change on this file since 835d83 was 2e06300, checked in by Martin Monerjan, 14 years ago
Various attempts on preprocessing gcone::preprocessInequalities is the one to proceed with interiorPoint2 as a crude attempt on computing the said Possibility to remove strictly positive rows in getConeNormals - no speedup worth mentioning Several minor tweaks - note that getCodim2Normals actually seems to compute the extremal rays. However that does not do any harm since comparison works that way as well. Might only come cheaper to get cddlib to return the actual normals. But who knows with cddlib... Timestamps with gettimeofday for crude profiling dd_FindRelativeInterior -> dd_LPSolve Ring construction in readConeFromFile git-svn-id: file:///usr/local/Singular/svn/trunk@12395 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 7.4 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
16#define p800
17#ifdef p800
18#include "../../cddlib/include/setoper.h"
19#include "../../cddlib/include/cdd.h"
20#include "../../cddlib/include/cddmp.h"
21#endif
22extern int gfanHeuristic;
23#define gfanp
24// #ifdef gfanp
25// extern       static float time_getConeNormals;
26// extern       static float time_getCodim2Normals;
27// extern       static float time_flip;
28// extern       static float time_enqueue;
29// extern       static float time_computeInv;
30// #endif
31//ideal getGB(ideal inputIdeal);
32// ideal gfan(ideal inputIdeal, int heuristic);
33lists gfan(ideal inputIdeal, int heuristic);
34
35//int dotProduct(intvec a, intvec b);
36//bool isParallel(intvec a, intvec b);
37
38class facet
39{
40        private:
41                /** \brief Inner normal of the facet, describing it uniquely up to isomorphism */
42                intvec *fNormal;
43               
44                /** \brief An interior point of the facet*/
45                intvec *interiorPoint;
46               
47                /** \brief Universal Cone Number
48                 * The number of the cone the facet belongs to, Set in getConeNormals()
49                 */
50                int UCN;
51               
52                /** \brief The codim of the facet
53                 */
54                int codim;
55               
56                /** \brief The Groebner basis on the other side of a shared facet
57                 *
58                 * In order not to have to compute the flipped GB twice we store the basis we already get
59                 * when identifying search facets. Thus in the next step of the reverse search we can
60                 * just copy the old cone and update the facet and the gcBasis.
61                 * facet::flibGB is set via facet::setFlipGB() and printed via facet::printFlipGB
62                 */
63                ideal flipGB;           //The Groebner Basis on the other side, computed via gcone::flip
64               
65        public: 
66                /** \brief Boolean value to indicate whether a facet is flippable or not
67                * This is also used to mark facets that nominally are flippable but which do
68                * not intersect with the positive orthant. This check is done in gcone::getCodim2Normals
69                 */     
70                bool isFlippable;       //**flippable facet? */
71                bool isIncoming;        //Is the facet incoming or outgoing in the reverse search?
72                facet *next;            //Pointer to next facet
73                facet *prev;            //Pointer to predecessor. Needed for the SearchList in noRevS
74                facet *codim2Ptr;       //Pointer to (codim-2)-facet. Bit of recursion here ;-)
75                int numCodim2Facets;    //#of (codim-2)-facets of this facet. Set in getCodim2Normals()
76                ring flipRing;          //the ring on the other side of the facet
77                                       
78                /** The default constructor. */
79                facet();
80                /** Constructor for lower dimensional faces*/
81                facet(int const &n);
82                /**  The copy constructor */
83                facet(const facet& f);
84               
85                /** The default destructor */
86                ~facet();
87                               
88                /** \brief Comparison of facets*/
89                inline bool areEqual(facet *f, facet *g);
90                /** Stores the facet normal \param intvec*/
91                inline void setFacetNormal(intvec *iv);
92                /** Hopefully returns the facet normal */
93                inline intvec *getFacetNormal();
94                /** Method to print the facet normal*/
95                inline void printNormal();
96                /** Store the flipped GB*/
97                inline void setFlipGB(ideal I);
98                /** Return the flipped GB*/
99                inline ideal getFlipGB();
100                /** Print the flipped GB*/
101                inline void printFlipGB();
102                /** Set the UCN */
103                inline void setUCN(int n);
104                /** \brief Get the UCN
105                 * Returns the UCN iff this != NULL, else -1
106                 */
107                inline int getUCN();
108                /** Store an interior point of the facet */
109                inline void setInteriorPoint(intvec *iv);
110                inline intvec *getInteriorPoint();
111                /** \brief Debugging function
112                 * prints the facet normal an all (codim-2)-facets that belong to it
113                 */
114                inline void fDebugPrint();
115                friend class gcone;             
116};
117
118/**
119 *\brief Implements the cone structure
120 *
121 * A cone is represented by a linked list of facet normals
122 * @see facet
123 */
124
125class gcone
126{
127        private:               
128//              ring rootRing;          //good to know this -> generic walk
129                ideal inputIdeal;       //the original
130                ring baseRing;          //the basering of the cone                             
131                intvec *ivIntPt;        //an interior point of the cone
132                int UCN;                //unique number of the cone
133                int pred;               //UCN of the cone this one is derived from
134                static int counter;
135               
136        public: 
137                /** \brief Pointer to the first facet */
138                facet *facetPtr;        //Will hold the adress of the first facet; set by gcone::getConeNormals
139#ifdef gfanp
140                static float time_getConeNormals;
141                static float time_getCodim2Normals;
142                static float time_flip;
143                static float t_ffG;
144                static float t_markings;
145                static float t_dd;
146                static float t_kStd;
147                static float time_enqueue;             
148                static float time_computeInv;
149                static float t_ddMC;
150                static float t_mI;
151                static float t_iP;
152#endif
153
154                /** # of variables in the ring */
155                int numVars;            //#of variables in the ring
156               
157                /** # of facets of the cone
158                 * This value is set by gcone::getConeNormals
159                 */
160                int numFacets;          //#of facets of the cone
161               
162                /**
163                 * At least as a workaround we store the irredundant facets of a matrix here.
164                 * Otherwise, since we throw away non-flippable facets, facets2Matrix will not
165                 * yield all the necessary information
166                 */
167                dd_MatrixPtr ddFacets;  //Matrix to store irredundant facets of the cone
168               
169                /** Contains the Groebner basis of the cone. Is set by gcone::getGB(ideal I)*/
170                ideal gcBasis;          //GB of the cone, set by gcone::getGB();
171                gcone *next;            //Pointer to next cone
172                gcone *prev;
173               
174                gcone();
175                gcone(ring r, ideal I);
176                gcone(const gcone& gc, const facet &f);
177                ~gcone();
178                inline int getCounter();
179                inline ring getBaseRing();
180                inline void setIntPoint(intvec *iv);
181                inline intvec *getIntPoint();
182                inline void showIntPoint();
183                inline void setNumFacets();
184                inline int getNumFacets();
185                inline int getUCN();
186                inline int getPredUCN();               
187                inline void showFacets(short codim=1);
188                inline volatile void showSLA(facet &f);
189                inline void idDebugPrint(const ideal &I);
190                inline void invPrint(const ideal &I);
191                inline bool isMonomial(const ideal &I);
192                inline intvec *ivNeg(const intvec *iv);
193                inline int dotProduct(const intvec &iva, const intvec &ivb);
194                inline bool isParallel(const intvec &a, const intvec &b);
195                inline bool areEqual(const intvec &a, const intvec &b);
196                inline bool areEqual(facet *f, facet *g);
197                inline int intgcd(int a, int b);
198                inline void writeConeToFile(const gcone &gc, bool usingIntPoints=FALSE);
199                inline void readConeFromFile(int gcNum, gcone *gc);
200                inline intvec f2M(gcone *gc, facet *f, int n=1);
201               
202                //The real stuff
203                inline void getConeNormals(const ideal &I, bool compIntPoint=FALSE);
204                inline void getCodim2Normals(const gcone &gc);
205                inline void flip(ideal gb, facet *f);
206                inline void computeInv(ideal &gb, ideal &inv, intvec &f);
207//              poly restOfDiv(poly const &f, ideal const &I); removed with r12286
208                inline ideal ffG(const ideal &H, const ideal &G);
209                inline void getGB(ideal const &inputIdeal);             
210                inline void interiorPoint( dd_MatrixPtr &M, intvec &iv);
211                inline void interiorPoint2(const dd_MatrixPtr &M, intvec &iv);
212                inline void preprocessInequalities(dd_MatrixPtr &M);
213                ring rCopyAndAddWeight(const ring &r, const intvec *ivw);
214                ring rCopyAndChangeWeight(const ring &r, intvec *ivw);         
215//              void reverseSearch(gcone *gcAct); //NOTE both removed from r12286
216//              bool isSearchFacet(gcone &gcTmp, facet *testfacet);
217                void noRevS(gcone &gcRoot, bool usingIntPoint=FALSE);
218                inline void makeInt(const dd_MatrixPtr &M, const int line, intvec &n);
219                inline void normalize();
220                facet * enqueueNewFacets(facet *f);
221                dd_MatrixPtr facets2Matrix(const gcone &gc);           
222//              static void gcone::idPrint(ideal &I);           
223                friend class facet;     
224};
225lists lprepareResult(gcone *gc, int n);
226#endif
227#endif
Note: See TracBrowser for help on using the repository browser.