Note, this software was originally written by **Ambros Marzetta**
when he was a Ph.D. student at ETHZ Zurich.
Since Ambros is no longer involved in this area of research, I have
taken over maintaining this code.
David Bremner

## Compiling pd

Download the package gzipped tarfile of source code. It contains a makefile. You may want to use another compiler by changing the line CC = gcc

Or you may want to use other compiler options by changing the line CFLAGS = -O -DNDEBUG -DOMIT_TIMES

If you remove -DOMIT_TIMES, the program measures the execution time for the different phases of the algorithm. Then, simply type make

and you get an executable named pd.

## Running pd

pd reads the input data from stdin. Start the program by typing % pd < pdtest/cross2.ine

## Input format

pd accepts files in .ine-format like lrs, prs and cdd. The input must consist of rational numbers (no floating point numbers). There are some restrictions on the input data: V-representation: The polyhedron must be bounded (no rays) and full-dimensional. H-representation: The origin must be in the interior of the polyhedron (in the interior, not on the border!), and the polyhedron must have at least one vertex. There may be a digits command before the begin line: digits n: Use n decimal digits for the numerator and denominator of all rational numbers. Default is 180. There may be options after the end of the input matrix:

incidence: After every facet found, print a list of its incident vertices.

#incidence: After every facet found, print the number of incident vertices. notranslation: For V-representations: The origin is in the interior of the polytope. For H-representations: The input polyhedron is bounded. In both cases, the option instructs the program not to translate the input. This can make the computation much faster. volume: Compute the volume of the polytope. This option is only valid for H-representations and if the polyhedron is bounded.

#### Example 1: Vertex enumeration of a cube

##### Input

```
Cube of dimension 3 (the center is at the origin)
H-representation
digits 20
begin
6 4 integer
1 1 0 0
1 0 1 0
1 0 0 1
1 -1 0 0
1 0 -1 0
1 0 0 -1
end
notranslation
```

##### The output should contain (along with other comment lines beginning with a "*")

```
dec digits: 20
*Input File: Cube
V-representation
begin
***** 4 rational
1 -1 1 1
1 -1 -1 1
1 -1 1 -1
1 1 1 1
1 1 -1 -1
1 -1 -1 -1
1 1 1 -1
1 1 -1 1
end
*Number of vertices+rays: 8
```

#### Example 2: Facet enumeration of a pyramid

##### Input

```
Pyramid (the last vertex is the top of the pyramid)
V-representation
begin
5 4 integer
1 10 10 0
1 10 12 0
1 12 10 0
1 12 12 0
1 11 11 5
end
incidence
```

##### The output should contain (along with other comment lines beginning with a "*")

```
*Input File: Pyramid
H-representation
begin
***** 4 rational
60 -5 0 -1: 5 4 3|3
60 0 -5 -1: 5 4 2|3
-50 5 0 -1: 5 2 1|3
0 0 0 1: 4 3 2 1|4
-50 0 5 -1: 5 3 1|3
end
*Number of facets: 5
```

The numbers between the ":" and the "|" give the vertices incident to the facet, and the number after the "|" gives the number of incident vertices.

## Error messages

When pd is run, the following error messages may be generated: Syntax error in the input file. Internal error. Please send me a bug report. Not enough memory. Change (decrease) the digits line in your input file. Overflow. Change (increase) the digits line in your input file. Digits is too large. Increase MAX_DIGITS in prs_mp.h and recompile the program. Unbounded / origin not in the interior. Remove the "notranslation" or the "volume" option from the input file, and check the restrictions on the input data. Not full-dimensional.

## Release notes

pd prints its revision number in the first or second line of the output. Currently, this is revision 1.8.

## Bug reports

Send bug reports to bremner@unb.ca.