Welcome to NYCU CSIT Mirror site

TOPCOM User Manual

TOPCOM User Manual

Jörg Rambau
Universtät Bayreuth, Germany

May 7, 2008

1 What is TOPCOM?

TOPCOM is a collection of clients to compute Triangulations Of Point Configurations and Oriented Matroids, resp.

The algorithms use only combinatorial data of the point configuration as is given by its oriented matroid. Some basic commands for computing and manipulating oriented matroids can also be accessed by the user.

2 How do I use TOPCOM?

All programs read the input from stdin and write the result to stdout so that you can pipe the results to the next command.

A point configuration is given by a matrix (enclosed in square brackets) whose columns (enclosed in square brackets) are the homogeneous coordinates (seperated by commas) of the points in the configuration. A square could be specified as follows.

    [[0,0,1],[0,1,1],[1,0,1],[1,1,1]]

You may specify generators of the combinatorial symmetry of a point configuration as permutations of the vertex numbers. The symmetry of the square reads as follows (observe that the count starts at 0!):

    [[3,2,1,0],[2,3,0,1],[0,2,1,3]]

3 Commands

The following commands are provided:

points2chiro
Computes the chirotope of a point configuration.
chiro2dual
Computes the dual of a chirotope.
chiro2circuits
Computes the circuits of a chirotope.
chiro2cocircuits
Computes the circuits of a chirotope.
cocircuits2facets
Computes the facets of a set of cocircuits.
points2facets
Computes the facets of a point configuration.
points2nflips
Computes the number of flips of a point configurations and the seed triangulation.
points2flips
Computes all flips of a point configurations and the seed triangulation.
chiro2placingtriang
Computes the placing triangulation of a chirotope given by the numbering of the elements.
points2placingtriang
dto. for point configurations.
chiro2finetriang
Computes a fine (i.e., using all vertices) triangulation by placing and pushing.
points2finetriang
dto. for point configurations.
chiro2triangs
Computes all triangulations of a chirotope that are connected by bistellar flips to the regular triangulations.
points2triangs
dto. for point configurations.
chiro2ntriangs
Computes the number of all triangulations of a chirotope that are connected by bistellar flips to the regular triangulations.
points2ntriangs
dto. for point configurations.
chiro2finetriangs
Computes all fine triangulations of a chirotope that are connected by bistellar flips to a fine seed triangulation.
points2finetriangs
dto. for point configurations.
chiro2nfinetriangs
Computes the number of all fine triangulations of a chirotope that are connected by bistellar flips to a fine seed triangulation.
points2nfinetriangs
dto. for point configurations.
chiro2alltriangs
Computes all triangulations of a chirotope.
points2alltriangs
dto. for point configurations.
chiro2nalltriangs
Computes the number of all triangulations of a chirotope.
points2nalltriangs
dto. for point configurations.
chiro2allfinetriangs
Computes all fine triangulations of a chirotope.
points2allfinetriangs
dto. for point configurations.
chiro2nallfinetriangs
Computes the number of all fine triangulations of a chirotope.
points2nallfinetriangs
dto. for point configurations.
cube d
Computes the vertices and symmetry generators of a d-cube.
cyclic n d
Computes the vertices and symmetry generators of the cyclic d-polytope with n vertices.
cross d
Computes the vertices of the d-dimensional cross-polytope.
hypersimplex k d
Computes the vertices and symmetry generators of the k-th hypersimplex in dimension d.
santos_triang
Computes the point configuration, the symmetry, and the Santos triangulation (without flips).

4 Command Line Options

The following command line options are supported:

Options controlling the overall behaviour of clients

-d
Debug.
-h
Print a usage message.
-v
Verbose.

Options controlling what is computed

--cardinality [k]
Count only triangulations with exactly k simplices.
--checktriang
Check seed triangulation.
--flipdeficiency
Check triangulations for flip deficiency.
--frequency [k]
Check every k-th triangulation for regularity and stop if one is found.
--heights
Output a height vector for every regular triangulation (implies --regular).
--noinsertion
Never add a point that is unused in the seed triangulation.
--reducepoints
Try to greedily minimize the number of vertices used; keep a global upper bound on the current minimal number of vertices and do not accept triangulations with more vertices.
--regular
Search for regular triangulations only (checked liftings are w.r.t. the last homogeneous coordinate, e.g., last coordinates all ones is fine); note that this may reduce the effort of exploration, since regular triangulations are connected by themselves.
--nonregular
Output non-regular triangulations only; note that this does not reduce the effort of exploration, since non-regular triangulations are in general not connected by themselves.

Options controlling the internals of the clients

--chirocache [n]
Set the chirotope cache to n elements.
--localcache [n]
Set the cache for local operations.
--memopt
Save memory by using caching techniques.
--soplex
Use soplex instead of cdd for regularity checks (unstable).

4.1 Options for warm starts from previous calculations

--dump
Write intermediate results into a file.
--dumpfile [dumpfilename]
Write intermediate results into file dumpfilename (default: TOPCOM.dump).
--dumpfrequency [k]
Dump the results of each kth BFS round
--dumprotations [k]
Dump into k different rotating files.
--read
Read intermediate results from a file.
--readfile [readfilename]
Read intermediate results from file dumpfilename (default: TOPCOM.dump).

5 Examples

In the subdirectory examples you find some example inputs for TOPCOM routines. For example,

  points2chiro < lattice_3_3.dat

outputs the sign string of the chirotope of the sub-lattice of integer points (i,j) with i,j = 0, 1, 2.

  points2chiro < lattice_3_3.dat | chiro2ntriangs

or

  points2ntriangs < lattice_3_3.dat

yields the number of triangulations that are connected to the regular ones by bistellar flips.

  points2ntriangs -r --affine < moae_testfile

counts all regular triangulations of the “mother of all examples”, two nested triangles in the plane.

  points2chiro < lattice_3_3.dat | chiro2nalltriangs

yields the number of all triangulations via a branch & bound algorithm. For large examples this routine may take a lot of time but since it branches in a DFS manner it does not take a lot of memory.

The example r12.chiro is the chirotope of the oriented matroid R12 with disconnected realization space, constructed by Jürgen Richter-Gebert. If you want to compute, e.g., a placing triangulation of R12 then type

  chiro2placingtriang < r12.chiro

The facets of a 4-cube can be computed by

  cube 4 | points2chiro | chiro2dual | \  
  chiro2circuits | cocircuits2facets

but be aware of the fact that this is not an efficient way of computing facets of a point configuration. It is, however, numerically stable because rational arithmetics is used.

Finally, you can check the Santos triangulation by

  santos_triang | points2nflips -v --memopt --checktriang

Recall that the options mean:

-v
verbose;
--memopt
save memory;
--checktriang
check seed triangulation.