# source:git/gfanlib/gfanlib_zcone.h@5ff68b

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