The new version 1.2.0 now supports checkpointing for enumerations of triangulations, circuits, and cocircuits.
Versions starting at 1.1.0 use vastly improved enumeration methods for
Moreover, lock-free multithreading is used on demand for enumeration and/or symmetry processing.
For really large problem instances (co-dimension above 13), the exploration-by- ipping of the regular component of the ip-graph in TOPCOM's points2(n)triangs takes a lot of memory. The exploration of the (in general smaller) subregular component of the ip graph can be done with less memory consumption by using MPTOPCOM by Jordan, Joswig, and Kastner (https://polymake.org/doku.php/mptopcom). The enumeration of all triangulations, however, can be done with similar memory consumption much faster now than before by the TOPCOM client points2(n)alltriangs. This client, for the time being, is the fastest method in TOPCOM to enumerate all triangulations of point con gurations.
TOPCOM is a collection of clients to compute Triangulations Of Point Con gurations and Oriented Matroids, resp.
The algorithms use only combinatorial data of the point con guration as is given by its oriented matroid. Some basic commands for computing and manipulating oriented matroids can also be accessed by the user.
All programs read the input from stdin and write the result to stdout so that you can pipe the results to the next command. Up to four units of data input are read: a point con guration; the symmetries of the con guration; the symmetries required for triangulations; a seed triangulation, where, e.g., the ip-graph exploration starts.
A point con guration 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 con guration. A square could be speci ed as follows.
[[0,0,1],[0,1,1],[1,0,1],[1,1,1]]
The symmetries of a con guration with elements are given by a list of permutations, where a permutation is given as a list of the images of 0, . Each permutation must represent a combinatorial symmetry of the con guration. That is: it must map signed cocircuits to signed cocircuits. The symmetry generators of the square read as follows (observe that the count starts at 0):
[[3,2,1,0],[2,3,0,1],[0,2,1,3]]
The required symmetries for the resulting triangulations are given in the same way. They are only observed if the command-line option --triangsymmetries is used. To generate only triangulations of the square symmetric w.r.t. the diagonal of the rst quadrant, add the following line:
[[3,1,2,0]]
A seed triangulation can be given by a set of sets of numbers, where elements of a set are enclosed in curly brackets and separated by commas. For example, for the square:
{{0,1,2},{1,2,3}}
A given seed is only observed if the command-line option --triangseed is used.
(This is new compared to versions of TOPCOM earlier than 1.2.0.) If you want to
prescribe a seed but no (required) symmetries, specify [] for the (required)
symmetries.
Before, inbetween, and after the data units comments may be added: Whenever the hash symbol is detected, the rest of the line is ignored. Note that inside the data units comments are not allowed.
The following commands are provided:
(New.) Displays the points and their symmetry generators in a more readable form.
(New.) Displays some parameters of the point con guration (number, rank, order of symmetry group, order of required symmetries, number of simplices in a given seed triangulation).
(New.) Displays some parameters of the chirotope (number, rank, order of symmetry group, order of required symmetries, number of simplices in a given seed triangulation).
(New.) Checks properties depending on the command line options for a list of seed triangulations.
Computes the chirotope of a point con guration.
Computes the dual of a chirotope.
Computes the circuits of a chirotope.
Dto. for point con gurations (using a faster method).
Computes the cocircuits of a chirotope.
Dto. for point con gurations (using a faster method).
Computes the facets of a set of cocircuits.
Computes a Gale transform of a point con guration.
Computes the circuits of a point con guration.
Computes the cocircuits of a point con guration.
Computes the facets of a point con guration.
Computes the vertices of a point con guration.
Computes the number of ips of a point con gurations and the seed triangulation.
Computes all ips of a point con gurations and the seed triangulation.
Computes the placing triangulation of a chirotope given by the numbering of the elements.
Dto. for point con gurations.
Computes a full (i.e., using all points) triangulation by placing and pushing (obsolete; use --full instead).
Dto. for point con gurations.
Computes all triangulations of a chirotope that are connected by bistellar ips to the seed, which is a regular triangulation if no seed is given in the input le.
Dto. for point con gurations.
Computes the number of all triangulations of a chirotope that are connected by bistellar ips to the seed, which is a regular triangulation if no seed is given in the input le.
Dto. for point con gurations.
Computes all full triangulations (i.e., using all points) of a chirotope that are connected by bistellar ips to a full seed triangulation (obsolete; use --full instead).
Dto. for point con gurations.
Computes the number of all full triangulations (i.e., using all points) of a chirotope that are connected by bistellar ips to a full seed triangulation (obsolete; use --full instead).
Dto. for point con gurations.
Computes all triangulations of a chirotope.
Dto. for point con gurations.
Computes the number of all triangulations of a chirotope.
Dto. for point con gurations.
Computes all full triangulations (i.e., using all points) of a chirotope (obsolete; use --full instead).
Dto. for point con gurations.
Computes the number of all full triangulations (i.e., using all points) of a chirotope (obsolete; use --full instead).
Dto. for point con gurations.
Computes a triangulation of a chirotope with a minimum number of simplices.
Dto. for point con gurations.
Computes the points and symmetry generators of the permutation polytope of the symmetric group of degree , also known as the Birkho polytope.
Computes the points and symmetry generators of the permutation polytope of the alternating group of degree , also known as the even Birkho polytope.
Computes the points and symmetry generators of the permutation polytope of the dihedral group of degree .
Computes B_S n with an additional center point.
Computes B_A n with an additional center point.
Computes B_D n with an additional center point.
Computes the points and symmetry generators of a -cube.
Computes the points and symmetry generators of the cyclic -polytope with vertices.
Computes the points and symmetry generators of the -dimensional cross-polytope.
Computes the points and symmetry generators of the -times dilated -simplex with all interior lattice points.
Computes the points and symmetry generators of copies of the -simplex.
Computes the two-dimensional lattice points with non-negative coordinates at most and their symmetry generators.
Computes the points and symmetry generators of the -th hypersimplex in dimension . A third parameter makes it the -hypersimplex with coordinate sums equal to or .
Computes the point con guration, the symmetry, and the Santos triangulation (without ips).
The following command line options are supported. Note that not all options are sensible for all clients.
read input from [ lename] instead of stdin.
Ignore the symmetries in the input.
(New.) Observe the prescribed symmetries in the input for triangulations in the result.
(New.) Observe the prescribed seed in the input for ip-graph exploration or in the input for property checking. In the latter case, more than one seed may be given.
Check seed triangulation for correctness.
(New.) Check given symmetries for correctness by testing invariance on cocircuits.
Print a usage message.
Debug.
Verbose.
In enumerations, report intermediate results after (at least) [n] discovered nodes.
Output a height vector for every regular triangulation (only in connection with --[find]regular).
(New.) Output the GKZ-vector for every triangulation..
Output all ips in terms of IDs of adjacent triangulations. (Can be used to generate the ip graph.)
When checking for ip-graph connectivity, output ip-paths to regular triangulations in terms of sequences of ips.
Write asymptote graphics commands into le (in rank-3 triangulations, points are drawn as well). The graphics contains a view of the point con guration (only in rank 3), the enumeration tree with a classi cation of enumeration nodes into solutions, non-canonical nodes, deadends, and early detected deadends, as well a statistics le showing a histogram of enumeration node types. The output le has to be processed by the computer graphics compiler asy (https://asymptote.sourceforge.io) using the asy-library Combinatorial_Geometry.asy and the LaTeX-macroes in triangbook_macroes.sty inside share/asy/.
Check triangulations for ip de ciency during ip-graph exploration.
(New form.) Check for regularity and stop if a regular one is found during ip-graph exploration.
Only count symmetry classes, not the total number.
Count/output only triangulations with exactly simplices.
Count/oputput only triangulations with at most simplices.
(New.) Output unimodular triangulations only; while this does not reduce the e ort of ip graph exploration, since unimodular triangulations are in general not connected by themselves, it does reduce the e ort of extension graph exploration like in points2nalltriangs.
Count/oputput only triangulations with simplices containing point (currently only supported by points2(n)alltriangs). Note that in this case only symmetries stabilizing that point are considered.
Output ag triangulations only; while this does not reduce the e ort of ip graph exploration, since ag triangulations are in general not connected by themselves, it does reduce the e ort of extension graph exploration like in points2nalltriangs.
Output non-regular triangulations only; note that this does neither reduce the e ort of ip-graph exploration, since non-regular triangulations are in general not connected by themselves, nor the e ort of extension graph exploration, since non-regularity depends on the combination of simplices in a triangulation.
Output non-subregular triangulations only, i.e., those that cannot be gkz-increasingly ipped to a regular triangulation.
Output non-superregular triangulations only, i.e., those that cannot be gkz-decreasingly ipped to a regular triangulation.
(New.) Output non-regular triangulations only if they are not connected to the ip-graph component of the regular triangulations. (Each such triangulation constitutes a signi cant mathematical result.)
(New.) Output non-regular triangulations only if they are possibly not connected to the ip-graph component of the regular triangulations. This is checked by lex-GKZ-monotone ipping w.r.t. a random permutation.
Search for regular triangulations only (checked liftings are w.r.t. the last homogeneous coordinate, e.g., last coordinates all ones is ne); note that this may reduce the e ort of ip-graph exploration, since regular triangulations are connected by themselves. In particular, if the optional given seed is non-regular, the exploration will stop immediately with no triangulations counted, since non-regular triangulations are not followed.
Search for regular partial triangulations only; note that this may reduce the e ort of extension-graph exploration, since no non-regular partial triangulation can be completed to a regular triangulation.
Search for full triangulations (i.e., using all points) only.
Never ip-in a point that is unused in the seed triangulation.
Try to greedily minimize the number of points used while ipping; keep a global upper bound on the current minimal number of points and do not accept triangulations with more points.
Never change the cardinality of triangulations by ipping.
(New form.) Assume that the symmetries are a ne, in particular, that they conserve regularity.
(New.) Assume that the symmetries are isometric, in particular, that they preserve volume.
(New; currently the default.) Ignore the prescribed symmetries for triangulations in the result (option supported for backwards-compatibility).
Save memory by using caching techniques.
(New.) Use an iterative version of the depth- rst-search enumeration algorithms (avoids potential call-stack over ows on small machines).
(New.) Use a recursive version of the depth- rst-search enumeration algorithms (default).
(New.) Use GKZ vectors as a nger print in symmetry handling (only for points with isometric symmetries).
(New.) Use naive full traversal of all symmetries for symmetry handling.
(New.) Use critical-element tables for symmetry handling (default for triangulations).
(New.) Use Jordan-Joswig-Kastner switch tables for symmetry handling (default for (co-)circuits).
(New.) Use tables of classi ed symmetries for symmetry handling. Obsolete, since slower than the other options.
(New.) Use [n] symtables for preprocessing symmetries. Obsolete, since slower than the other options.
(New.) Preprocess the chirotope (default for points2[n]alltriangs).
(New.) Heuristically transform points.
(New.) Preprocess a representation of the symmetry group on simplex indices (only relevant for triangulation enumeration).
(New.) Sort simplices in preprocessed index table randomly (only for points with isometric symmetries).
(New.) Sort simplices in preprocessed index table by volume (only for points with isometric symmetries).
(New.) Use volumes to check extendability of partial triangulations (only for points with isometric symmetries).
(New.) Put more e ort in the check of extendability of a partial triangulation.
(New.) Skip the check of extendability of a partial triangulation.
(New.) Check extendability prior to symmetry.
Set the chirotope cache to elements.
Set the cache for local operations.
Use QSopt_ex for regularity checks (not thread-safe).
Use soplex for regularity checks (requires separate installation of soplex).
Use multiple threads for enumeration.
(Currently the default.) Control the interrupt of workers by size of the current workbu er.
Control the interrupt of workers by node budgets.
Use multiple threads only locally for symmetry checks.
Use [n] threads (if possible).
Let each thread process at least [n] nodes (to avoid multi-threading overhead).
Let each thread process at most [n] nodes (to avoid thread starving).
Scale the default node budget by [n] percent (n integer)
(Currently unused.) Try to keep the work bu er above [n] nodes (to balance overhead and thread starving).
(Currently unused.) Try to keep the work bu er below [n] node (to balance overhead and thread starving).
These options currently work for the clients points2(n)triangs, chiro2(n)triangs, points2(n)alltriangs, chiro2(n)alltriangs, and points2(n)(co)circuits.
Write intermediate results into a le; a symbolic link with the basename will be placed pointing to the most recent actual dump le.
Dump into di erent rotating les indicated by numerical post xes.
Write intermediate results into les with basename dumpfilename (default: TOPCOM.dump); a symbolic link with the basename will be placed pointing to the most recent actual dump le.
Dump the results at each th object (what object means, depends on the kind of enumeration)
Read intermediate results from a le.
Read intermediate results from le dumpfilename (default: TOPCOM.dump).
In the subdirectory examples you nd some example inputs for TOPCOM routines.
If you want to see the input in a prettier way, then you can type the following:
points2prettyprint < cube_3.dat
It prints the matrix of point coordinates and the symmetry generators in tabular form.
Or:
points2chiro < lattice_3_3.dat
outputs the sign string of the chirotope of the sub-lattice of integer points with .
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 ips.
points2ntriangs --regular --affinesymmetries < moae.dat
counts all regular triangulations of the mother of all examples , two nested triangles in the plane.
points2nalltriangs < lattice_3_3.dat
yields the number of all triangulations via a new algorithm symmetric lex-subset reverse-search on partial triangulations. It is mostly faster than ip-graph exploration and much faster than in older versions of TOPCOM; moreover, it does not take a lot of memory.
The example r12.chiro is the chirotope of the oriented matroid with disconnected realization space, constructed by Jürgen Richter-Gebert. If you want to compute, e.g., a placing triangulation of then type
chiro2placingtriang < r12.chiro
The facets of a -cube can be computed by
cube 4 | points2facets
but be aware of the fact that this is not an e cient way of computing facets of a point con guration. It is, however, numerically stable because rational arithmetics is used.
Most notably, you can check the Santos triangulation by
santos_triang | points2nflips -v --memopt --checktriang
Recall that the options mean:
verbose;
save memory;
check seed triangulation.
A new result as of version 1.0.10 is that TOPCOM can now enumerate all triangulations of larger point con gurations like the -cube in reasonable time. The speed depends on the computational environment and the options:
cube 4 | points2nalltriangs -v --parallelenumeration
uses verbose output and multi-threaded symmetry processing with load-balancing based on work bu er control, i.e., the workers stop and push the open nodes into the job list whenever the master's job list contains fewer elements than there are workers.
Since not every point con guration can be represented in rational coordinates, it is useful to enumerate triangulations from the chirotope data. This way you can compute, e.g., all triangulations of the regular icosahedron:
chiro2nalltriangs -i icosahedron.chiro -v
Note the newly supported alternative syntax -i [filename] for the speci cation of the input le.
Enumerating all triangulations can be restricted to regular, unimodular, ag, and symmetric triangulations. For example, assume the input moae.dat for the mother of all examples contains a permutation (rotation by 120 degrees) generating the symmetries required for the triangulations as follows (note the use of comments):
# content of moae.dat: # the points: [[4,0,0],[0,4,0],[0,0,4],[2,1,1],[1,2,1],[1,1,2]] # the symmetries: [[1,0,2,4,3,5],[0,2,1,3,5,4]] # the required symmetries generated by 120-degree rotations: [[1,2,0,4,5,3]] # no seed.
Then (with \ just indicating a split line):
points2alltriangs -i moae.dat --triangsymmetries \ --regular --heights --gkzvecs
enumerates all regular triangulations that have C3-rotational symmetry and outputs their regularity-heights and GKZ vectors. The result:
[triangID:0,workerID:0,runID:0,inorbitID:0,triang:{{0,1,2}}, \
has_required_syms:true,is_regular:true,is_flag:true, \
heights:[0,0,0,1,1,1],gkzvec:[64,64,64,0,0,0]]
Consequently, only the triangulation with one big simplex consisting of the vertices of the con guration is counted.
Moreover:
points2alltriangs -i moae.dat --flag -v
shows that there are only three ag (sometimes known as quadratic ' or clique ) triangulations.
The enumeration of circuits and cocircuits up to symmetry is now a non-trivial part of TOPCOM. For example:
cube 4 | points2ncircuits -v --parallelenumeration
enumerates the symmetry classes of all the circuits of the 4-cube.
Moreover, the clients to explore the ip graph for points can now use the GKZ vector as a ngerprint to detect known triangulation classes in case all symmetries are isometric. This is faster, but needs some more memory for storing all the known GKZ vectors. Moreover, a basic multi-threaded symmetry check can be used. You can activate all of this by:
cube 4 | points2ntriangs --parallelsymmetries \ --usegkz --isometricsymmetries
As an example for the graphics output the 2-by-3 lattice in dimension two is presented. Graphics output is supported by the enumeration of all triangulations, circuits and cocircuits. The les Combinatorial_Geometry.asy and triangbook_macroes.sty (to be found under share/asy in the TOPCOM home directory) must be present in the working directory where TOPCOM_graphics.asy is compiled via asy. For example, if 3D2.dat contains the input data for the 3-times dilated 2-simplex with 120-degree rotations as required symmetries, then
points2nalltriangs -i 3D2.dat -v --parallelenumeration --asy \ --triangsymmetries --flag --unimodular
followed by
asy TOPCOM_graphics.asy
yields besides the numerical result three graphics les in pdf-format.
The point con guration can be found in TOPCOM_points.pdf (see Figure 1).
The enumeration tree can be found in TOPCOM_tree_graph.pdf (see Figure 2).
Here, a clover icon means a triangulation in a new symmetry class, a recycling icon means a node in an old symmetry class, a stop-sign icon means a deadend with no possible admissible lex-larger extension, a bulb icon means an early detected deadend with an uncoverable interior facet, a lightning-sign icon means that no further extension option can prevent an uncoverable interior facet, and, nally, a red-tra c-light icon means a node with unavoidable non-facial cliques in the edge graph. Statistics can be found in TOPCOM_statistics.pdf (see Figure 3).
