User Guide
Warning: There are no guarantees for the robustness of the GeoCalcLib! Please report any malfunction.
The GeoCalcLib provides five different wrappers to call the LRS routines:

facetEnumeration()
calculates a half space description for the provides vertex/ray description. 
vertexEnumeration()
calculates a vertex description for the provided half space description. inequalityReduction()
produces an irredundant half space description for a polyhedron in half space description.vertexReduction()
produces an irredundant vertex/ray description of a polyhedron in vertex/ray description.projectPolyhedron()
does not call a LRS routine, but projects a polyhedron in half space description and returns the result in half space description.LRS()
allows passing more data to the LRS engine to perform the vertex and facet enumeration. Allows passing parameters.
On top of the direct interface to the LRS library createLRSfile()
and readLRSfile()
are provided to write and read an LRS input file respectively.
Facet Enumeration
Generate a set of vertices:
\begin{equation} V = \left(\begin{array}{c} v_1^T \\[0em] v_2^T \\[0em] \vdots \end{array}\right) \end{equation}
For example translates to
We can produce a plot of the polytope using
The Hrepresentation of is trivially obtained as
\begin{equation} P = \left\{x\in\mathbb R^2 : \begin{pmatrix} 1 & 1 \\[0em] 1 & 1 \\[0em] 1 & 1 \\[0em] 1 & 1 \end{pmatrix} x \leq \begin{pmatrix} 1 \\[0em] 1 \\[0em] 1 \\[0em] 1 \end{pmatrix} \right\} \end{equation}
This can result is obtained by calling [A,b] = facetEnumeration(V)
. Called with one argument facetEnumeration(V)
assumes that all rows in V
are vertices.
If rays are present, an additional vector type
must be provided
each row in type
is either type(i) = 1
if V(i,:)
is a vertex or type(i) = 0
if V(i,:)
is a ray.
[A,b] = facetEnumeration(V,ones(size(V,1),1))
produces the same result as [A,b]=facetEnumeration(V)
.
Vertex Enumeration
The vertexEnumeration()
function produces a vertex/ray representation for a given polyhedron .
Assume we want to understand the epigraph of the piecewise affine function for . The epigraph is given by
\begin{equation} \text{epi}(\varphi) = \left\{ (x,t) : 0\leq x\leq 5, x+1\leq t, 2x \leq t, 3x4\leq t \right\} \end{equation}
\begin{equation} A = \begin{pmatrix} 1 & 1\\[0em] 2 & 1\\[0em] 3 & 1\\[0em] 1 & 0\\[0em] 1 & 0 \end{pmatrix} , b = \begin{pmatrix}1 \\[0em] 0 \\[0em] 4 \\[0em] 5 \\[0em] 0 \end{pmatrix} \end{equation}
Using this as an input
we obtain the vertices and rays generating the epigraph.
Inequality Reduction
The call [Aout,bout] = inequalityReduction(Ain,bin)
returns an irredundant Hrepresentation of .
Vertex Reduction
The call [Vout,tout] = vertexReduction(Vin,tin)
returns an irredundant Vrepresentation of where the vertices in Vin
are passed by setting tin(i) = 1
if Vin(i,:)
is a vertex and tin(i) = 0
if Vin(i,:)
is a ray.
If , passing tin = ones(size(V,1),1)
can be omitted Vout = vertexReduction(Vin)
assumes all passed points are vertices.
Projection
The projection of polyhedral sets is performed for polyhedra in Hrepresentation , and is always projected on to . The projected set is returned in Hrepresentation.
Internally a vertex enumeration is performed on , the projection operator acts trivially on points by just dropping off the last elements, after that a facet enumeration is appended to produce the Hrepresentation of .
The function call [Aout,bout] = projectPolyhedron(Ain,bin,d)
performs this operation for general polyhedra:
Vertex and facet enumeration with LRS parameters
The functions vertexEnumeration()
and facetEnumeration()
perform a vertex and facet enumeration respectively for data that was preconditioned by the user.
The vertexEnumeration()
call requires the user to prepare a type vector if rays are present etc. and the facetEnumeration()
call only treats inequality constrained sets.
To exploit (almost) the full scope of possibilities the LRS engine offers the LRS()
function is provided.
The argument is a struct
with the required field 'rep'
specifying whether a V or an Hrepresentation is passed.
Each representation has its own arguments:
Assume we want to facet enumerate the first quadrant, i.e. , then we define the structure
If we have we set the additional field
That is, if the s.rep='V'
at least one of s.V
or s.R
has to be passed.
Assume now that we want to vertex enumerate the 3dimensional simplex ,
that is the representation of rep='H'
The interpretation of the output for a vertex enumeration is exactly the same as for vertexEnumeration()
that is, V(i,:)
is a vertex if t(i)=1
and V(i,:)
is a ray if t(i)=0
.
If s.rep='H'
then s.Aineq
and s.bineq
are required, s.Aeq
and s.beq
are optional.
In addition to the computational data parameters may be passed, so far maxcobases
, maxoutput
and maxdepth
are accepted. See LRS options for details.
If we want to restrict the number of search depth in the vertex enumeration of a 12dimensional cube, and further we also want to constrain the number of explored cobases and only need 5 vertices we would call
Warning: Although this function has been thoroughly tested, there might be uncaught exceptions. Matlab will immediately crash if you come across an uncaught exception. These exceptions have no numerical nature, but can occur when passing unaccepted data types (passing cell arrays instead of arrays etc.). Please test your code your function calls before calling this function in an automated environment!
Writing and reading LRS input files
Many LRS users might prefer to call the LRS executable directly in order to be able to see the output as it is obtained, rather than waiting for the entire solution to be returned.
For this purpose createLRSfile('param1',param1,...)
is provided to generate a LRS input file from within the Matlab environment.
The supported parameters are
fname
 specifies the file name of the LRS input file created, if omitted a file calledlrstest.ine
is created in the current directory.rep
'V'
or'H'
implying that the data is passed in a V or Hrepresentation respectively. If
rep='V'
vertices are passed as the parameterV
in a matrixvdat
containing a vertex/ray in each row, optionallyType
can be used to pass a vector of1/0
such thattype(i) = 0
impliesvdat(i,:)
is a ray andtype(i) = 1
impliesvdat(i,:)
is a vertex. IfType
is not specified all rows ofvdat
are assumed to be vertices.  If
rep='H'
the set of inequalities is passed by settingA
toAdat
andb
tobdat
. Ifb
is omitted the set is assumed to be  The optional parameter
tol
may be set to the desired conversion tolerance to a rational format, default1e12
.
To create an LRS input file myfile.ine
to vertex enumerate the unit ball in two dimensions we would use
Users who have produced results using the LRS executable wanting to import it into the Matlab environment would first change the head of the result file into an admissible LRS input file, i.e replace the ***** n rational
line by m n rational
, where m
and n
are the number of rows and columns respectively. Then pass the filename
to readLRSfile('filename')
.
To read in the result of a vertex enumeration in myfile.ext
, i.e. the result is in Vrepresentation, we would call