Let $P \subseteq \mathbb{R}^d$ be an $\mathcal{H}$-polytope. The *vertex enumeration problem* asks for the set of vertices $V$ of $P$. Theoretically, the vertex enumeration problem for $P$ can be performed in $\mathcal{O}(|V|^{\lfloor d/2 \rfloor})$, cf. [[1]](http://www.mathematik.tu-darmstadt.de/~pfetsch/Publications/polycomplex.pdf).
Practically, one would use the *double description method*, cf. [[2]](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.45.8343&rep=rep1&type=pdf), and cf. [cddlib](http://www.inf.ethz.ch/personal/fukudak/cdd_home/) for an implementation of the former.


In my application, I have to solve a rather large number of such vertex enumeration problems in let's say dimension $10$. Unfortunately, *ccdlib* is too slow and causes numerical problems (the GMP version is even slower). 


Moreover, for my application it suffices to find a superset of $V$. Hence, I thought there might be a way to decompose $P$ into "simpler" polytopes such that the vertex enumeration for each such polytope could be performed much faster. 


Is anybody aware of such method?



Computionally efficient vertex enumeration for (convex) polytopes
cddlib is rather old; a much more efficient implementation of the double description method is in PPL (Parma Polyhedra Library). One frontend to PPL can be found in Sagemath: <http://www.sagemath.org/doc/reference/geometry/sage/geometry/polyhedron/constructor.html>
PPL will perform computations exactly.


Apart from the double description there is the reverse search, a method consisting of "walking" over the vertices, implemented in lrs: [http://cgm.cs.mcgill.ca/~avis/C/lrs.html](http://cgm.cs.mcgill.ca/%7Eavis/C/lrs.html)
and it might work better for your problems.


More info on double description and reverse search methods can be found in Komei Fukuda's [Polyhedral FAQ](https://cddlib.github.io/polyhedral_faq/)


