1 /* 2 * lib_cone.h 3 * 4 * Created on: Sep 28, 2010 5 * Author: anders 6 */ 7 8 #ifndef LIB_CONE_H_ 9 #define LIB_CONE_H_ 10 11 #include "gfanlib_matrix.h" 12 13 namespace gfan{ 14 /** 15 * Returns true if cddlib is needed for the ZCone implementation. 16 */ 17 bool isCddlibRequired(); 18 /** 19 * Only call this function if gfanlib is the only code in your program using cddlib. 20 * Should be paired with a deinitializeCddlibIfRequired() call. 21 * Calling the function repeatedly may cause memory leaks even if deinitializeCddlibIfRequired() is also called. 22 */ 23 void initializeCddlibIfRequired(); 24 /** 25 * This function may do nothing. 26 */ 27 void deinitializeCddlibIfRequired(); 28 29 /** 30 A PolyhedralCone is represented by linear inequalities and equations. The inequalities are non-strict 31 and stored as the rows of a matrix and the equations are stored as rows of a second matrix. 32 33 A cone can be in one of the four states: 34 0) Nothing has been done to remove redundancies. This is the initial state. 35 1) A basis for the true, implied equations space has been computed. This means that 36 the implied equations have been computed. In particular the dimension of the cone is known. 37 2) Redundant inequalities have been computed and have been eliminated. 38 This means that the true set of facets is known - one for each element in halfSpaces. 39 3) The inequalities and equations from 2) have been transformed into a canonical form. Besides having 40 a unique representation for the cone this also allows comparisons between cones with operator<(). 41 42 Since moving for one state to the next is expensive, the user of the PolyhedralCone can specify flags 43 at the construction of the cone informing about which things are known. 44 45 PCP_impliedEquationsKnown means that the given set of equations generate the space of implied equations. 46 PCP_facetsKnown means that each inequalities describe define a (different) facet of the cone. 47 48 Each cone has the additional information: multiplicity and linear forms. 49 The multiplicity is an integer whose default value is one. It can be set by the user. 50 When a cone is projected, it can happen that the multiplicity changes according to a lattice index. 51 The linear forms are stored in a matrix linearForms, whose width equals the dimension of the ambient space. 52 The idea is that a collection of cones in this way can represent a piecewise linear function (a tropical rational function). 53 54 Caching: 55 When new properties are computed by changing state the information is stored in the object by updating equations and inequalities. 56 When some other properties are computed, such as rays the result is cached in the object. Each cached property has a corresponding flag telling if a cached value has been stored. 57 These methods 58 for these properties are considered const. Caching only works for extreme rays at the moment. 59 60 Notice: 61 The lineality space of a cone C is C\cap(-C). 62 A cone is ray if its dimension is 1+the dimension of the its lineality space. 63 64 Should the user of this class know about the states? 65 66 need to think about this... 67 Always putting the cone in state 1 after something has changed helps a lot. 68 Then all operations can be performed except comparing and getting facets with 69 out taking the cone to a special state. 70 71 72 Things to change: 73 - Thomas wants operations where the natural description is the dual to be fast. 74 One way to achieve this is as Frank suggests to have a state -1, in which only 75 the generator description is known. These should be stored in the cache. If it 76 is required to move to state 0, then the inequality description is computed. 77 This sounds like a reasonable solution, but of course, what we are really storing is the dual. 78 79 - Basically all data in the object should be mutable, while almost every method should be const. 80 81 - A method should set the cone in a given state if required. The reason for this is that 82 it will be difficult for the user to figure out which state is required and therefore 83 will tend to call canonicalize when not needed. 84 85 - Cache should be added for more properties. 86 87 Optimization: 88 - When inequalities can be represented in 32 bit some optimizations can be done. 89 90 More things to consider: 91 - Does it make sense to do dimension reduction when lineality space / linear span has been 92 computed? 93 94 95 When calling generated by rays, two flags should be passed. 96 97 */ 98 99 enum PolyhedralConePreassumptions{ 100 PCP_none=0, 101 PCP_impliedEquationsKnown=1, 102 PCP_facetsKnown=2 103 }; 104 105 class ZCone; 106 ZCone intersection(const ZCone &a, const ZCone &b); 107 class ZCone 108 { 109 int preassumptions; 110 mutable int state; 111 int n; 112 Integer multiplicity; 113 ZMatrix linearForms; 114 mutable ZMatrix inequalities; 115 mutable ZMatrix equations; 116 mutable ZMatrix cachedExtremeRays; 117 /** 118 * If this bool is true it means that cachedExtremeRays contains the extreme rays as found by extremeRays(). 119 */ 120 mutable bool haveExtremeRaysBeenCached; 121 void ensureStateAsMinimum(int s)const; 122 123 bool isInStateMinimum(int s)const; 124 int getState()const; 125 public: 126 /** 127 * Constructs a polyhedral cone with specified equations and ineqalities. They are read off as rows 128 * of the matrices. For efficiency it is possible to specifying a PolyhedralConePreassumptions flag 129 * which tells what is known about the description already. 130 */ 131 ZCone(ZMatrix const &inequalities_, ZMatrix const &equations_, int preassumptions_=PCP_none); 132 133 /** 134 * Get the multiplicity of the cone. 135 */ 136 Integer getMultiplicity()const; 137 /** 138 * Set the multiplicity of the cone. 139 */ 140 void setMultiplicity(Integer const &m); 141 /** 142 * Returns the matrix of linear forms stored in the cone object. 143 */ 144 ZMatrix getLinearForms()const; 145 /** 146 * Store a matrix of linear forms in the cone object. 147 */ 148 void setLinearForms(ZMatrix const &linearForms_); 149 150 /** 151 * Get the inequalities in the description of the cone. 152 */ 153 ZMatrix getInequalities()const; 154 /** 155 * Get the equations in the description of the cone. 156 */ 157 ZMatrix getEquations()const; 158 /** 159 * Compute generators of the span of the cone. They are stored as rows of the returned matrix. 160 */ 161 ZMatrix generatorsOfSpan()const; 162 /** 163 * Compute generators of the lineality space of the cone. The returned set of generators is a vector spaces basis. They are stored as rows of the returned matrix. 164 */ 165 ZMatrix generatorsOfLinealitySpace()const; 166 /** 167 * Returns true iff it is known that every inequalities in the description defines a different facets of the cone. 168 */ areFacetsKnown()169 bool areFacetsKnown()const{return (state>=2)||(preassumptions&PCP_facetsKnown);} 170 /** 171 * Returns true iff it is known that the set of equations span the space of implied equations of the description. 172 */ areImpliedEquationsKnown()173 bool areImpliedEquationsKnown()const{return (state>=1)||(preassumptions&PCP_impliedEquationsKnown);} 174 /** 175 * Returns true iff the extreme rays are known. 176 */ areExtremeRaysKnown()177 bool areExtremeRaysKnown()const{return haveExtremeRaysBeenCached;} 178 179 /** 180 * Takes the cone to a canonical form. After taking cones to canonical form, two cones are the same 181 * if and only if their matrices of equations and inequalities are the same. 182 */ 183 void canonicalize(); 184 /** 185 * Computes and returns the facet inequalities of the cone. 186 */ 187 ZMatrix getFacets()const; 188 /** 189 * After this function has been called all inequalities describe different facets of the cone. 190 */ 191 void findFacets(); 192 /** 193 * The set of linear forms vanishing on the cone is a subspace. This routine returns a basis 194 * of this subspace as the rows of a matrix. 195 */ 196 ZMatrix getImpliedEquations()const; 197 /** 198 * After this function has been called a minimal set of implied equations for the cone is known and is 199 * returned when calling getEquations(). The returned equations form a basis of the space of implied 200 * equations. 201 */ 202 void findImpliedEquations(); 203 204 /** 205 * Constructor for polyhedral cone with no inequalities or equations. Tthat is, the full space of some dimension. 206 */ 207 ZCone(int ambientDimension=0); 208 209 /** 210 * Computes are relative interior point of the cone. 211 */ 212 ZVector getRelativeInteriorPoint()const; 213 /** 214 Assuming that this cone C is in state at least 3 (why not 2?), this routine returns a relative interior point v(C) of C with the following properties: 215 1) v is a function, that is v(C) is found deterministically 216 2) for any angle preserving, lattice preserving and lineality space preserving transformation T of R^n we have that v(T(C))=T(v(C)). This makes it easy to check if two cones in the same fan are equal up to symmetry. Here preserving the lineality space L just means T(L)=L. 217 */ 218 ZVector getUniquePoint()const; 219 /** 220 * Takes a list of possible extreme rays and add up those actually contained in the cone. 221 */ 222 ZVector getUniquePointFromExtremeRays(ZMatrix const &extremeRays)const; 223 /** 224 * Returns the dimension of the ambient space. 225 */ 226 int ambientDimension()const; 227 /** 228 * Returns the dimension of the cone. 229 */ 230 int dimension()const; 231 /** 232 * Returns (ambient dimension)-(dimension). 233 */ 234 int codimension()const; 235 /** 236 * Returns the dimension of the lineality space of the cone. 237 */ 238 int dimensionOfLinealitySpace()const; 239 /** 240 * Returns true iff the cone is the origin. 241 */ 242 bool isOrigin()const; 243 /** 244 * Returns true iff the cone is the full space. 245 */ 246 bool isFullSpace()const; 247 248 /** 249 * Returns the intersection of cone a and b as a cone object. 250 */ 251 friend ZCone intersection(const ZCone &a, const ZCone &b); 252 /** 253 * Returns the Cartesian product of the two cones a and b. 254 */ 255 friend ZCone product(const ZCone &a, const ZCone &b); 256 /** 257 * Returns the positive orthant of some dimension as a polyhedral cone. 258 */ 259 static ZCone positiveOrthant(int dimension); 260 /** 261 * Returns the cone which is the sum of row span of linealitySpace and 262 * the non-negative span of the rows of generators. 263 */ 264 static ZCone givenByRays(ZMatrix const &generators, ZMatrix const &linealitySpace); 265 266 /** 267 * To use the comparison operator< the cones must have been canonicalized. 268 */ 269 friend bool operator<(ZCone const &a, ZCone const &b); 270 /** 271 * To use the comparison operator!= the cones must have been canonicalized. 272 */ 273 friend bool operator!=(ZCone const &a, ZCone const &b); 274 275 /** 276 * Returns true iff the cone contains a positive vector. 277 */ 278 bool containsPositiveVector()const; 279 /** 280 * Returns true iff the cone contains the specified vector v. 281 */ 282 bool contains(ZVector const &v)const; 283 /** 284 * Returns true iff the cone contains all rows of the matrix l. 285 */ 286 bool containsRowsOf(ZMatrix const &l)const; 287 /** 288 * Returns true iff c is contained in the cone. 289 */ 290 bool contains(ZCone const &c)const; 291 /** 292 * Returns true iff the PolyhedralCone contains v in its relative interior. False otherwise. The cone must be in state at least 1. 293 */ 294 bool containsRelatively(ZVector const &v)const; 295 /* 296 * Returns true iff the cone is simplicial. That is, iff the dimension of the cone equals the number of facets. 297 */ 298 bool isSimplicial()const; 299 300 //PolyhedralCone permuted(IntegerVector const &v)const; 301 302 /** 303 * Returns the lineality space of the cone as a polyhedral cone. 304 */ 305 ZCone linealitySpace()const; 306 307 /** 308 * Returns the dual cone of the cone. 309 */ 310 ZCone dualCone()const; 311 /** 312 * Return -C, where C is the cone. 313 */ 314 ZCone negated()const; 315 /** 316 * Compute the extreme rays of the cone, and return generators of these as the rows of a matrix. 317 * The returned extreme rays are represented by vectors which are orthogonal to the lineality 318 * space and which are primitive primitive. 319 * This makes them unique and invariant under lattice and angle preserving linear transformations 320 * in the sense that a transformed cone would give the same set of extreme rays except the 321 * extreme rays have been transformed. 322 * If generators for the lineality space are known, they can be supplied. This can 323 * speed up computations a lot. 324 */ 325 ZMatrix extremeRays(ZMatrix const *generatorsOfLinealitySpace=0)const; 326 /** 327 The cone defines two lattices, namely Z^n intersected with the 328 span of the cone and Z^n intersected with the lineality space of 329 the cone. Clearly the second is contained in the 330 first. Furthermore, the second is a saturated lattice of the 331 first. The quotient is torsion-free - hence a lattice. Generators 332 of this lattice as vectors in the span of the cone are computed 333 by this routine. The implied equations must be known when this 334 function is called - if not the routine asserts. 335 */ 336 ZMatrix quotientLatticeBasis()const; 337 /** 338 For a ray (dim=linealitydim +1) 339 the quotent lattice described in quotientLatticeBasis() is 340 isomorphic to Z. In fact the ray intersected with Z^n modulo the 341 lineality space intersected with Z^n is a semigroup generated by 342 just one element. This routine computes that element as an 343 integer vector in the cone. Asserts if the cone is not a ray. 344 Asserts if the implied equations have not been computed. 345 */ 346 ZVector semiGroupGeneratorOfRay()const; 347 348 /** 349 Computes the link of the face containing v in its relative 350 interior. 351 */ 352 ZCone link(ZVector const &w)const; 353 354 /** 355 Tests if f is a face of the cone. 356 */ 357 bool hasFace(ZCone const &f)const; 358 /** 359 Computes the face of the cone containing v in its relative interior. 360 The vector MUST be contained in the cone. 361 */ 362 ZCone faceContaining(ZVector const &v)const; 363 /** 364 * Computes the projection of the cone to the first newn coordinates. 365 * The ambient space of the returned cone has dimension newn. 366 */ 367 // PolyhedralCone projection(int newn)const; 368 friend std::ostream &operator<<(std::ostream &f, ZCone const &c); 369 std::string toString()const; 370 }; 371 372 } 373 374 375 376 377 #endif /* LIB_CONE_H_ */ 378