source: git/kernel/gfan.h @ 6ce030f

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