1 // This is a -*- C++ -*- header file. 2 3 /* barvinok.h -- Barvinok's decomposition of a cone. 4 5 Copyright 2002, 2003 Ruriko Yoshida 6 Copyright 2006, 2007, 2008 Matthias Koeppe 7 8 This file is part of LattE. 9 10 LattE is free software; you can redistribute it and/or modify it 11 under the terms of the version 2 of the GNU General Public License 12 as published by the Free Software Foundation. 13 14 LattE is distributed in the hope that it will be useful, but 15 WITHOUT ANY WARRANTY; without even the implied warranty of 16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 17 General Public License for more details. 18 19 You should have received a copy of the GNU General Public License 20 along with LattE; if not, write to the Free Software Foundation, 21 Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA. 22 */ 23 24 #ifndef BARVINOK__H 25 #define BARVINOK__H 26 27 #include "cone.h" 28 #include "cone_consumer.h" 29 #include "timing.h" 30 #include "triangulation/RegularTriangulation.h" 31 #include <vector> 32 33 class BarvinokParameters { 34 public: 35 // Whether we use the 36 // - traditional LattE monomial substitution z_i |-> (1 + s)^(lambda_i) 37 // - or the exponential substitution z_i |-> exp(t lambda_i) 38 // - or no substitution, keeping a multivariate generating function 39 enum { PolynomialSubstitution, 40 ExponentialSubstitution, 41 NoSubstitution 42 } substitution; 43 // Whether to use 44 // - traditional dual decomposition 45 // - irrational primal decomposition 46 // - irrational all-primal decomposition 47 // (i.e., both triangulation and Barvinok decomposition in primal space) 48 typedef enum { 49 DualDecomposition, 50 IrrationalPrimalDecomposition, 51 IrrationalAllPrimalDecomposition 52 } DecompositionType; 53 DecompositionType decomposition; 54 // The kind of triangulation to use. 55 typedef enum { 56 RegularTriangulationWithCdd, 57 RegularTriangulationWithCddlib, 58 DeloneTriangulationWithCddlib, 59 SubspaceAvoidingBoundaryTriangulation, 60 SubspaceAvoidingSpecialTriangulation, 61 PlacingTriangulationWithTOPCOM, 62 RegularTriangulationWith4ti2 63 } TriangulationType; 64 TriangulationType triangulation; 65 int triangulation_max_height; 66 int triangulation_bias; 67 bool nonsimplicial_subdivision; 68 listCone *triangulation_special_cone; 69 prescribed_height_data *triangulation_prescribed_height_data; 70 bool debug_triangulation; 71 bool triangulation_assume_fulldim; 72 // How to dualize non-simplicial cones. 73 typedef enum { 74 DualizationWithCdd, 75 DualizationWith4ti2 76 } DualizationType; 77 DualizationType dualization; 78 // The kind of short vectors we use for decomposition 79 typedef enum { 80 LatteLLL, 81 SubspaceAvoidingLLL 82 } ShortVectorType; 83 ShortVectorType shortvector; 84 // The Smith form computation algorithm 85 typedef enum { 86 IlioSmithForm, 87 LidiaSmithForm 88 } SmithFormType; 89 SmithFormType smithform; 90 // The maximum determinant of cones that we do not subdivide 91 // further. Set to 1 to subdivide until we reach unimodular cones 92 // only. Set to 0 (special case) to not subdivide at all. 93 int max_determinant; 94 // A file name that is used for constructing file names for 95 // temporary and semi-temporary files. 96 const char *File_Name; 97 // Ambient dimension. 98 int Number_of_Variables; 99 // Parameters that control the computation. 100 unsigned int Flags; 101 // Data that are used during the computation. 102 int Cone_Index; /* Its index in the list of all master 103 cones; only used for naming 104 triangulation caches. */ 105 // Timers. 106 Timer total_time; 107 Timer read_time; 108 Timer vertices_time; 109 Timer irrationalize_time; 110 Timer dualize_time; 111 Timer triangulate_time; 112 Timer decompose_time; 113 int num_triangulations_with_trivial_heights; 114 int num_triangulations_with_dependent_heights; 115 int num_triangulations; 116 // Constructor & destructor. 117 BarvinokParameters(); 118 virtual ~BarvinokParameters(); 119 virtual void print_statistics(ostream &s); 120 // Call this method to deliver the result. Several legacy codepaths 121 // in LattE want to deliver the result and exit early, in situations 122 // where emptiness is detected. This method at least unifies how 123 // this output is delivered. --mkoeppe 124 virtual void deliver_number_of_lattice_points(const ZZ &number); 125 }; 126 127 class Single_Cone_Parameters : public BarvinokParameters, public ConeConsumer { 128 public: 129 // Statistics collected during the computation. 130 ZZ Total_Uni_Cones; 131 ZZ Total_Simplicial_Cones; 132 ZZ Current_Simplicial_Cones_Total; 133 ZZ Max_Simplicial_Cones_Total; 134 int Current_Depth; 135 int Max_Depth; 136 public: Single_Cone_Parameters()137 Single_Cone_Parameters() : Current_Depth(0), Max_Depth(0) {}; Single_Cone_Parameters(const BarvinokParameters & params)138 Single_Cone_Parameters(const BarvinokParameters ¶ms) : 139 BarvinokParameters(params), Current_Depth(0), Max_Depth(0) {}; ~Single_Cone_Parameters()140 virtual ~Single_Cone_Parameters() {} 141 virtual void print_statistics(ostream &s); 142 }; 143 144 // Send all decomposed cones to a different ConeConsumer. 145 146 class DelegatingSingleConeParameters : public Single_Cone_Parameters { 147 public: DelegatingSingleConeParameters(const BarvinokParameters & params)148 DelegatingSingleConeParameters(const BarvinokParameters ¶ms) : 149 Single_Cone_Parameters(params), consumer(0) {}; 150 void SetConsumer(ConeConsumer *a_consumer); 151 int ConsumeCone(listCone *cone); 152 protected: 153 ConeConsumer *consumer; 154 }; 155 156 /* Do a signed decomposition, modulo lower-dimensional cones, of the 157 SIMPLICIAL cone spanned by the ROW VECTORS of B with apex at 158 VERTEX, until the determinants of all cones are at most 159 PARAMETERS->max_determinant. 160 161 Call PARAMETERS->ConsumeCone() for each of the small cones. 162 */ 163 int 164 barvinok_Single(mat_ZZ B, Single_Cone_Parameters *Parameters, 165 const Vertex *vertex); 166 167 /* Do a signed decomposition, modulo lower-dimensional cones, of the 168 polyhedral CONE, until the determinants of all cones are at most 169 PARAMETERS->max_determinant. (When the cone is not simplicial, we 170 triangulate it first.) 171 172 Call PARAMETERS->ConsumeCone() for each of the small cones. 173 */ 174 int 175 barvinokDecomposition_Single (listCone *cone, 176 Single_Cone_Parameters *Parameters); 177 178 /* Decompose the cone spanned by GENERATOR (which has determinant DET) 179 according to Barvinok's theory into M (the dimension) many CONES 180 and store their determinants in DETS. 181 182 Entries with Det[i] == 0 have Cones[i] == NULL (we don't generate 183 lower-dimensional cones). 184 185 Return true if the decomposition successfully reduced determinants; 186 this is always the case except for SubspaceAvoidingLLL. 187 */ 188 bool 189 barvinokStep(const listCone *Cone, 190 std::vector <listCone *> &Cones, vec_ZZ &Dets, 191 int m, Single_Cone_Parameters *Parameters); 192 193 #endif 194