Skip to main content

unitri

Paper: Further Bounding the Kreuzer-Skarke Landscape (arXiv:2602.16909)

Exactly counts the fine (unimodular) triangulations of a lattice polygon. For a convex polygon, hand it the polygon's lattice points and get the exact count; for more general regions it also takes an explicit upper/lower boundary description. It counts without enumerating, so it reaches regions with astronomically many triangulations that enumeration tools cannot.

Based on the original program by Stepan Orevkov (http://picard.ups-tlse.fr/~orevkov), reworked and generalized by Nate MacFadden (with Claude Opus 4.8); an earlier minor cleanup was by Michael Stepniczka and Nate MacFadden.

If there are any bugs/issues in this code, assume they are due to Nate MacFadden's rework and not Stepan Orevkov's original code.

Install

pip install -e .          # builds the Cython extension; needs a C toolchain + libgmp

libgmp is optional: it powers the fast single-run exact counter (count_triangulations, na_query). It comes from apt install libgmp-dev (Debian/Ubuntu), brew install gmp (macOS), or conda install -c conda-forge gmp, and the build finds it automatically (pkg-config, falling back to Homebrew/conda via the bundled _gmp.py). Without GMP, pip install simply skips that extension and you count via count_triangulations_parallel (mod-prime + CRT, needs only a C compiler) -- see below.

Counting a polygon's unimodular triangulations

Give count_triangulations the polygon's lattice points and it returns the exact number of fine (unimodular) triangulations:

import unitri

unitri.count_triangulations([(0,0), (4,0), (3,2), (1,2)])          # 140    (a trapezoid)
unitri.count_triangulations([(0,0), (4,0), (3,3), (1,3), (0,1)])   # 10843  (a pentagon)

There is also a command-line front end. It reads a point set from a file or stdin in almost any bracket/comma/whitespace format -- a pasted numpy array, [x, y] lists, or x y per line:

echo "[[0,0],[4,0],[3,3],[1,3],[0,1]]" | python -m unitri     # -> 10843
python -m unitri points.txt

The count is exact (arbitrary precision). The point-set path is for convex regions; for non-convex regions -- valleys, concave tops -- describe them directly with boundary profiles, below.

For large counts, or when you don't have GMP, count the same thing in parallel across cores via the mod-prime + CRT path (needs only a C compiler, no libgmp):

unitri.count_triangulations_parallel([(0,0), (4,0), (3,2), (1,2)])   # 140, in parallel

It runs the mod-prime counter for successive primes across cores and CRT-combines them into the exact integer -- the GMP-free way to get exact counts, and often faster than the single GMP run for very large ones.

The counting core (C CLI and boundary profiles)

Under the point-set convenience is a single-header C counter, na_query.h (stb-style), driven by an m x n bounding box and upper/lower boundary profiles. This is the lower-level, more general interface -- it handles any region between a lower and an upper boundary, including non-convex ones -- and it needs no Python. na-query.c is a thin CLI that pulls in the implementation; width m and height n are runtime arguments, so one binary handles every size:

gcc -O2 -o na-query unitri/na-query.c                 # default: counts modulo a prime
gcc -O2 -DGMP -o na-query unitri/na-query.c -lgmp     # big-integer: the whole count

If GMP isn't on the compiler's default path (Homebrew, or a conda env), splice in the bundled locator's flags: gcc -O2 $(python3 _gmp.py) -DGMP -o na-query unitri/na-query.c -lgmp. Or just use the Makefile: make na-query-mod (mod-prime), make na-query (GMP), or make both.

Run ./na-query <m> <n> [prime_index] and pipe the region to stdin, one profile per line:

  • Line 1 -- upper boundary (the query): m+1 heights h_0 h_1 ... h_m, each an integer in [0, n], or . for an absent vertex (the boundary passes between lattice points there). The endpoints h_0 and h_m must be present.
  • Line 2 -- lower boundary / floor (optional): same format; a blank line or Ctrl-D leaves the floor flat at 0. The upper profile must lie on or above it.
echo "4 4 4 4 4" | ./na-query 4 4                  # query_value 736983568  (full 4x4 square)
printf '4 4 4 4 4\n0 1 0 1 0\n' | ./na-query 4 4    # query_value 14032211   (over a non-flat floor)
echo "0 . 3 . 0" | ./na-query 4 4                  # query_value 35          (an absent vertex)

The result prints as query_value <count> -- the whole integer under -DGMP, or a residue mod the chosen prime in the default build (combine several primes with unitri/crt_combine.py to recover the exact count). With no input at all, na-query <m> <n> prints the flat-rectangle f(m,k) table for k = 1..n.

The same profile interface is available in-process from Python as unitri.na_query(m, n, upper, lower=None) -- what count_triangulations calls under the hood; upper/lower are the m+1 boundary heights, omit lower for a flat floor at 0:

unitri.na_query(4, 4, [4, 4, 4, 4, 4])              # 736983568  (the 4x4 square)
unitri.na_query(3, 12, [12, 8, 4, 0])               # 668517487  (a base-3 triangle)
unitri.na_query(4, 4, [4,4,4,4,4], [0,1,0,1,0])     # 14032211   (over a non-flat floor)

Run the tests with pip install -e .[test] (adds pytest, plus cytools for the TOPCOM cross-checks) then pytest tests/.

Performance

na_query counts triangulations with a dynamic-programming recurrence -- it never enumerates them -- so its cost depends only on the bounding box (m, n), not on the (often astronomically large) number of triangulations. TOPCOM, by contrast, enumerates one triangulation at a time, so its cost scales with the count and cannot reach large regions at all.

Exact (GMP) build vs TOPCOM (via CYTools) on an Intel Core Ultra 7 270K Plus, Ubuntu 26.04, gcc 15.2. Both columns are warmed up once, then reported as the per-call mean ± stdev: na_query in process through the compiled extension (not a subprocess), with auto-scaled repetitions over 7 batches; TOPCOM one run per batch, its repeats stopping once their cumulative time exceeds a 60 s budget. The vertices column gives each region's convex-hull corners; pass them to count_triangulations (or count_triangulations_parallel) to reproduce.

region vertices triangulations na_query TOPCOM
3x2 rectangle (0,0),(0,2),(3,0),(3,2) 852 0.020 ± 0.000 ms 0.04 ± 0.01 s
polygon (0,2),(1,3),(2,0),(3,0),(3,3),(4,1),(4,2) 10,653 0.190 ± 0.001 ms 0.56 ± 0.00 s
polygon (0,3),(1,1),(1,4),(2,0),(3,0),(3,4),(4,1),(4,3) 840,021 0.517 ± 0.001 ms 55.0 ± 0.3 s
4x4 square (0,0),(0,4),(4,0),(4,4) 736,983,568 0.330 ± 0.004 ms infeasible
4x10 square (0,0),(0,10),(4,0),(4,10) ~5.8e23 13.10 ± 0.04 ms infeasible
triangle, height 84 (0,0),(0,84),(3,0) ~7.6e65 1.26 ± 0.003 s infeasible

Counts agree exactly with TOPCOM wherever TOPCOM can finish. Reproduce with pip install -e . && python benchmarks/benchmark.py.

Organization

unitri/
├── unitri/
│   ├── profiles.py     # point set -> (m,n,upper,lower); count_triangulations (the main entry)
│   ├── na_query.pyx    # Cython binding: in-process na_query(m, n, upper, lower)
│   ├── na_query.h      # the counter: stb-style single header, mod-prime (default) or GMP (-DGMP)
│   ├── na-query.c      # thin CLI wrapper around na_query.h
│   ├── crt_combine.py  # combine the default build's per-prime residues into the exact count
│   ├── crt_parallel.py # GMP-free exact counts: parallel mod-prime runs + CRT
│   ├── __main__.py     # CLI: python -m unitri (count a lattice point set)
│   └── __init__.py
├── tests/
│   ├── test_topcom_convex.py    # convex polygons vs TOPCOM: curated + randomized (the main use-case)
│   ├── test_counts.py           # exact counts vs literature / TOPCOM; f(m,k) table mode
│   ├── test_mod_prime.py        # default mod-prime backend + crt_combine (CRT reconstruction)
│   ├── test_symmetry.py         # hard x<->m-x reflection cases
│   ├── test_unimodular.py       # unimodular invariance
│   ├── test_readme_examples.py  # the examples in this README, asserted
│   ├── check_topcom.py          # standalone TOPCOM cross-check (fixed convex regions)
│   ├── conftest.py              # shared fixtures (builds the GMP/mod-prime binaries)
│   ├── _cli.py                  # shared "run the na-query CLI" helper
│   ├── _topcom.py               # shared TOPCOM enumeration helper
│   └── transforms.py            # GL(2,Z) invariance helpers
├── benchmarks/
│   ├── benchmark.py             # na_query vs TOPCOM timing (the Performance table)
│   └── profile.sh               # wall-time + peak-memory profiler for any command
├── Makefile                     # build the na-query CLI (make both / na-query / na-query-mod)
├── pyproject.toml
├── setup.py
├── environment.yml              # conda env with the GMP backend (recommended)
├── environment-nogmp.yml        # conda env without GMP (mod-prime + CRT path)
├── _gmp.py                      # locate GMP (pkg-config -> Homebrew/conda); shared by setup.py + tests
├── MANIFEST.in
├── CITATION.cff
├── NOTICE                       # provenance: Orevkov's original code, shared with permission
└── LICENSE                      # GPLv3

Provenance

The core counting algorithm and original code are by Stepan Orevkov, included and distributed with his permission; see NOTICE and the attribution notes in unitri/na_query.h and CITATION.cff. The modifications, generalizations, and packaging are licensed under GPLv3 (see LICENSE).

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

unitri-0.2.0.tar.gz (127.4 kB view details)

Uploaded Source

Built Distributions

If you're not sure about the file name format, learn more about wheel file names.

unitri-0.2.0-cp313-cp313-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (541.9 kB view details)

Uploaded CPython 3.13manylinux: glibc 2.17+ x86-64

unitri-0.2.0-cp313-cp313-macosx_14_0_arm64.whl (365.3 kB view details)

Uploaded CPython 3.13macOS 14.0+ ARM64

unitri-0.2.0-cp312-cp312-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (544.5 kB view details)

Uploaded CPython 3.12manylinux: glibc 2.17+ x86-64

unitri-0.2.0-cp312-cp312-macosx_14_0_arm64.whl (365.1 kB view details)

Uploaded CPython 3.12macOS 14.0+ ARM64

unitri-0.2.0-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (537.3 kB view details)

Uploaded CPython 3.11manylinux: glibc 2.17+ x86-64

unitri-0.2.0-cp311-cp311-macosx_14_0_arm64.whl (365.1 kB view details)

Uploaded CPython 3.11macOS 14.0+ ARM64

unitri-0.2.0-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (527.4 kB view details)

Uploaded CPython 3.10manylinux: glibc 2.17+ x86-64

unitri-0.2.0-cp310-cp310-macosx_14_0_arm64.whl (365.6 kB view details)

Uploaded CPython 3.10macOS 14.0+ ARM64

unitri-0.2.0-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (527.1 kB view details)

Uploaded CPython 3.9manylinux: glibc 2.17+ x86-64

unitri-0.2.0-cp39-cp39-macosx_14_0_arm64.whl (365.8 kB view details)

Uploaded CPython 3.9macOS 14.0+ ARM64

File details

Details for the file unitri-0.2.0.tar.gz.

File metadata

  • Download URL: unitri-0.2.0.tar.gz
  • Upload date:
  • Size: 127.4 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? Yes
  • Uploaded via: twine/7.0.0 CPython/3.13.14

File hashes

Hashes for unitri-0.2.0.tar.gz
Algorithm Hash digest
SHA256 831f2797c5dbcf622fd0eedc895fba95ab9ef49b02a948368c4ed33b1748b4e9
MD5 74c034b5c8b4a5610dc308c38dbefc58
BLAKE2b-256 1f19dd25adf085ec07d6ea66584c09c518f531af70fb6b9ca7368bed0f508284

See more details on using hashes here.

Provenance

The following attestation bundles were made for unitri-0.2.0.tar.gz:

Publisher: deploy.yml on natemacfadden/unitri

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file unitri-0.2.0-cp313-cp313-manylinux_2_17_x86_64.manylinux2014_x86_64.whl.

File metadata

File hashes

Hashes for unitri-0.2.0-cp313-cp313-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm Hash digest
SHA256 b458a96dd7d5ca334b1b1e26f265c4e04ae968ac025b730fbc9382da21ee05da
MD5 837637db10ff2b2724983b1c58fe168e
BLAKE2b-256 a90019171735fae31bc098176fbba37d4a32ca34f803e7b1ba4ddc868dfe3cce

See more details on using hashes here.

Provenance

The following attestation bundles were made for unitri-0.2.0-cp313-cp313-manylinux_2_17_x86_64.manylinux2014_x86_64.whl:

Publisher: deploy.yml on natemacfadden/unitri

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file unitri-0.2.0-cp313-cp313-macosx_14_0_arm64.whl.

File metadata

File hashes

Hashes for unitri-0.2.0-cp313-cp313-macosx_14_0_arm64.whl
Algorithm Hash digest
SHA256 0d1cf01fb0abcce7a03cbc31b488220e59a7f3e01728d21b65a10209b326bd20
MD5 f8dc8a734f5b856142442586f666e90c
BLAKE2b-256 8255c1c6cfd648db0863210be43ac791f653f2e137206eb2b07a9e5127cad380

See more details on using hashes here.

Provenance

The following attestation bundles were made for unitri-0.2.0-cp313-cp313-macosx_14_0_arm64.whl:

Publisher: deploy.yml on natemacfadden/unitri

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file unitri-0.2.0-cp312-cp312-manylinux_2_17_x86_64.manylinux2014_x86_64.whl.

File metadata

File hashes

Hashes for unitri-0.2.0-cp312-cp312-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm Hash digest
SHA256 7451ae922c9619500a54714dbae9cd0f79e478ca3b607f06845fcc3eec9e0ec2
MD5 ff11dac22712d663046161b2642207e3
BLAKE2b-256 214e46a871a207ce1a116ca9c8a6e1aaa0c0b4a181174c9352660ea7effe951f

See more details on using hashes here.

Provenance

The following attestation bundles were made for unitri-0.2.0-cp312-cp312-manylinux_2_17_x86_64.manylinux2014_x86_64.whl:

Publisher: deploy.yml on natemacfadden/unitri

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file unitri-0.2.0-cp312-cp312-macosx_14_0_arm64.whl.

File metadata

File hashes

Hashes for unitri-0.2.0-cp312-cp312-macosx_14_0_arm64.whl
Algorithm Hash digest
SHA256 89ec153cce0ca755591af7b08cb3fb07c30ed6cbea5c6283cf12f23c1a6519e8
MD5 e2301d9469e10e664197f813dd54fe13
BLAKE2b-256 785bf7746340b0eb246b0d5decb77bb7181fa466ec24fa2c2d014e10ebacf842

See more details on using hashes here.

Provenance

The following attestation bundles were made for unitri-0.2.0-cp312-cp312-macosx_14_0_arm64.whl:

Publisher: deploy.yml on natemacfadden/unitri

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file unitri-0.2.0-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl.

File metadata

File hashes

Hashes for unitri-0.2.0-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm Hash digest
SHA256 67f1237fbb540d41c15fc1273efddba38c2bd5480774ed47f526e6d9eac1ee41
MD5 05ab69abf85cd4024c46e78528ef5e27
BLAKE2b-256 35ad40ac67fa3120757d2f6cbda6e7b72e965bf9bcd59b37f5d6725a2c1a898c

See more details on using hashes here.

Provenance

The following attestation bundles were made for unitri-0.2.0-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl:

Publisher: deploy.yml on natemacfadden/unitri

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file unitri-0.2.0-cp311-cp311-macosx_14_0_arm64.whl.

File metadata

File hashes

Hashes for unitri-0.2.0-cp311-cp311-macosx_14_0_arm64.whl
Algorithm Hash digest
SHA256 225a3b7b339da85f0084e4e5174541b4de8c78119b563868bc76425633ad110f
MD5 184a0e6c3141e6615d004626b56c4142
BLAKE2b-256 4ce7520cb04f4c02759660ec6e7a1d65fa500e577686dd92b50fd77d78dab87c

See more details on using hashes here.

Provenance

The following attestation bundles were made for unitri-0.2.0-cp311-cp311-macosx_14_0_arm64.whl:

Publisher: deploy.yml on natemacfadden/unitri

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file unitri-0.2.0-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl.

File metadata

File hashes

Hashes for unitri-0.2.0-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm Hash digest
SHA256 5f84abcd9fd2fe9a27428ed7fbf56465c89c6735727acf5f90a1e80a97394e73
MD5 ac999dea93e59ba2868e41a6d9ae52d6
BLAKE2b-256 475d271102d38865d91ff257c397f484940bee01d6d295d2156f808623bc0580

See more details on using hashes here.

Provenance

The following attestation bundles were made for unitri-0.2.0-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl:

Publisher: deploy.yml on natemacfadden/unitri

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file unitri-0.2.0-cp310-cp310-macosx_14_0_arm64.whl.

File metadata

File hashes

Hashes for unitri-0.2.0-cp310-cp310-macosx_14_0_arm64.whl
Algorithm Hash digest
SHA256 876e0590bdfd455cb2fc21ca49b3c066df96cfbc5af964bd8010f54d6427ac6c
MD5 a3ba357f3510fed287f6f8379ba1853c
BLAKE2b-256 f4d0aa2c332bc0a40322e2b948f6d38795cd85f2e19f2a6f5e78bf4e277ff3c1

See more details on using hashes here.

Provenance

The following attestation bundles were made for unitri-0.2.0-cp310-cp310-macosx_14_0_arm64.whl:

Publisher: deploy.yml on natemacfadden/unitri

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file unitri-0.2.0-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl.

File metadata

File hashes

Hashes for unitri-0.2.0-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm Hash digest
SHA256 89d8883671748e40d6916fcbb0bad646eb0aa8f3eb7f7d0c94b4fdb1a85fde0e
MD5 a3c781c820721a2adff714ba84245610
BLAKE2b-256 2727e9c6194e9aa03bcd1d4d33ae7741b114bd42fc24c10b836424925655f35e

See more details on using hashes here.

Provenance

The following attestation bundles were made for unitri-0.2.0-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl:

Publisher: deploy.yml on natemacfadden/unitri

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file unitri-0.2.0-cp39-cp39-macosx_14_0_arm64.whl.

File metadata

File hashes

Hashes for unitri-0.2.0-cp39-cp39-macosx_14_0_arm64.whl
Algorithm Hash digest
SHA256 fee9549e061e195ccadae66858baefaad6b00a4d7650f70a150a60e0cb209e45
MD5 b9a76cd5c3e1038c41ce01726624add3
BLAKE2b-256 0ff77a2d08955c4f0d0225f91eb0e95d4f54e3d172e946f262792d952b6f5b79

See more details on using hashes here.

Provenance

The following attestation bundles were made for unitri-0.2.0-cp39-cp39-macosx_14_0_arm64.whl:

Publisher: deploy.yml on natemacfadden/unitri

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

Release history Release notifications | RSS feed

This release

0.2.0 This release

11 files

Anthropic, PBC Visionary sponsor Bloomberg Visionary sponsor Hudson River Trading Visionary sponsor Meta Visionary sponsor NVIDIA Visionary sponsor Microsoft Sustainability sponsor Depot Continuous Integration AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Sentry Error logging StatusPage Status page