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.