retriangulate


	retriangulate

Name

retriangulate — Exhaustively retriangulate a given manifold

Synopsis

retriangulate [-h, --height=height] [-t, --threads=threads] [-4, --dim4] {isosig}

retriangulate {--help}

Description

Given a 3-manifold or 4-manifold triangulation, this utility uses Pachner moves to exhaustively search for other triangulations of the same manifold that are the same size or smaller.

Specifically, suppose the input triangulation contains n tetrahedra (for a 3-manifold) or pentachora (for a 4-manifold). Then this utility will exhaustively retriangulate the manifold using repeated Pachner moves, without ever exceeding n + height tetrahedra/pentachora in total. Moreover, all such retriangulations are guaranteed to be found, each once and only once.

For 3-manifold triangulations, this utility will only attempt 2-3 and 2-3 Pachner moves, never 1-4 or 4-1 moves. For 4-manifold triangulations, all types of Pachner moves are used (1-5, 2-4, 3-3, 4-2, and 5-1).

The program will output each triangulation that it finds of the same size n (including the original input triangulation). If it ever finds a smaller triangulation (thereby proving the original to be non-minimal), it will output that smaller triangulation and then stop immediately. Otherwise it will continue outputting triangulations of size n until no more can be found. Although the program also finds larger triangulations as part of its exhaustive search using Pachner moves, these larger triangulations (of which there are typically many) will not be output at all.

All triangulations, both input and output, are described using isomorphism signatures. These are short text strings that identify a triangulation uniquely up to combinatorial isomorphism (i.e., up to relabellings of the tetrahedra/pentachora and their vertices). The input triangulation will be interpreted as the isomorphism signature of a 3-manifold unless you pass the option --dim4 (in which case it will be treated as a 4-manifold instead).

From Regina's graphical user interface, you can view the isomorphism signature of a triangulation by switching to the Composition tab in the triangulation viewer. From Python you can fetch the isomorphism signature of the triangulation x by calling x.isoSig(). For a full and precise specification of isomorphism signatures for 3-manifolds, see Simplification paths in the Pachner graphs of closed orientable 3-manifold triangulations, Burton, 2011, arXiv:1110.6080.

Options

-h, --height=height

Specifies the number of additional tetrahedra (for a 3-manifold) or pentachora (for a 4-manifold) that we allow during intermediate stages of retriangulation. That is, if the input triangulation has n tetrahedra (or pentachora), then this utility will exhaustively search through all triangulations that it can reach via Pachner moves that do not exceed n + height tetrahedra (or pentachora) in total.

Note that these larger intermediate triangulations will not be written to output; however, a larger height may allow the program to access additional smaller triangulations that were otherwise inaccessible.

The given height must be positive, and for 4-manifolds it must also be even. If not specified, this option defaults to 1 for 3-manifolds (if --dim4 is not passed), or 2 for 4-manifolds (if --dim4 is passed).

Warning

In general, the running time can grow superexponentially with height. It is strongly suggested that you begin with --height=1 (or 2 for 4-manifolds) and increase it one step at a time until the performance becomes unacceptable.

-t, --threads=threads

Specifies the degree to which this utility uses parallel processing. Specifically, this program will use threads simultaneous threads of execution as it works its way through the different retriangulations of the input manifold.

This program is typically able to use parallelism effectively, and so running with k threads should approximately divide the running time by k.

If not specified, this option defaults to 1 (i.e., single-threaded processing, with no parallelism).

-4, --dim4

Indicates that the given isomorphism signature describes a 4-manifold triangulation. If this argument is not given, then by default the argument is assumed to describe a 3-manifold triangulation.

Examples

The 3-manifold triangulation is non-minimal, but it requires a bit of work to see this:

    example$ retriangulate -h2 hLLAAkbdceefggdonxdjxn
    hLLAAkbdceefggdonxdjxn
    hLALPkbcbefgfghxwnxark
    Found 2 triangulation(s).
    example$ retriangulate -h3 hLLAAkbdceefggdonxdjxn
    hLLAAkbdceefggdonxdjxn
    hLALPkbcbefgfghxwnxark
    hLLMMkbcdfefgglcghtchj
    gLLPQcdcefffqsjpunw
    Triangulation is non-minimal!
    Smaller triangulation: gLLPQcdcefffqsjpunw
    example$

Although the program stopped as soon as it found a smaller triangulation, this can be simplified even further:

    example$ retriangulate gLLPQcdcefffqsjpunw
    gLLPQcdcefffqsjpunw
    fLAMcbbcdeedhwhxn
    Triangulation is non-minimal!
    Smaller triangulation: fLAMcbbcdeedhwhxn
    example$

A little more probing shows this to be the cusped hyperbolic manifold m112:

    example$ censuslookup fLAMcbbcdeedhwhxn
    fLAMcbbcdeedhwhxn: 1 hit
        m112 : #2 -- Cusped hyperbolic census (orientable)
    
    example$

MacOS Users

If you downloaded a drag-and-drop app bundle, this utility is shipped inside it. If you dragged Regina to the main Applications folder, you can run it as /Applications/Regina.app/Contents/MacOS/retriangulate.

Windows Users

The command-line utilities are installed beneath the Program Files directory; on some machines this directory is called Program Files (x86). You can start this utility by running c:\Program Files\Regina\Regina 6.0.1\bin\retriangulate.exe.

Author

This utility was written by Benjamin Burton <bab@maths.uq.edu.au>. Many people have been involved in the development of Regina; see the acknowledgements page for a full list of credits.

Prev	Contents	Next
regfiletype	Up	sigcensus