latticepts

Nate MacFadden, Liam McAllister Group, Cornell

Fast lattice point enumeration for convex polyhedra. A C/Cython implementation of Kannan's algorithm, significantly outperforming Normaliz and OR-Tools CP-SAT in speed for certain problems. To demonstrate the performance, latticepts materializes ~108M lattice points in the strict interior of an example 7D cone ('Manwe') in ~13s single-threaded, or ~6.3s on 12 threads on an Intel Core Ultra 7 270K (30 GB RAM, Ubuntu 26.04); reproduce this with benchmark_enum_lattice_points.py (build with LATTICEPTS_OPENMP=1 for the multithreaded figure). We can also just count points, which is quicker.

Used by CYTools and Macaulay2 (see here).

Description

More explicitly, latticepts enumerates lattice points

$$ \{x\in\mathbb{Z}^{\text{dim}}: Hx\geq\text{rhs}\} $$

for $H\in\mathbb{Z}^{N_\text{hyps}\times\text{dim}}$ and $\text{rhs}\in\mathbb{Z}^{N_\text{hyps}}$. Here each row of $H$ is an inward-facing facet normal and the corresponding entry of $\text{rhs}$ is its offset. Cones correspond to $\text{rhs}=0$; 'stretched cones' (e.g., for finding strict interior points) correspond to $\text{rhs} > 0$; polyhedra to general $\text{rhs}$.

latticepts materializes the lattice points (lists them). The exposed count_only mode is there primarily to size that allocation -- it runs the search and reports how many output points there are (the matrix size to allocate) without itself allocating the (multi-GB) output array. Getting a count is incidental; for counting alone, LattE is likely faster. For generating the points, the closer competing approach is to compute/use a Hilbert basis.

Limitations

Maximum dimension: 256. For convex cones, latticepts excels at low-dimensions. It can become sluggish in comparison to alternatives at higher-dimensions (well before 256)
Windows is not supported: the C kernel uses C99 variable-length arrays, which MSVC does not support

Installation

pip install latticepts

This installs a prebuilt wheel from PyPI -- no C compiler needed (CPython 3.9-3.13 on Linux and macOS; Windows is unsupported, see Limitations).

Building from source

Build from a clone for a development install, or to enable the machine-specific (LATTICEPTS_NATIVE) or parallel (LATTICEPTS_OPENMP) builds below:

pip install -e .

Requires a C compiler.

For a faster, machine-specific build, set LATTICEPTS_NATIVE=1:

LATTICEPTS_NATIVE=1 pip install -e .

Enumeration runs in parallel over the independent top-level search branches -- both counting and materializing. Opt in with LATTICEPTS_OPENMP=1 (needs an OpenMP-capable compiler -- standard on most Linux machines, not on most Macs):

LATTICEPTS_OPENMP=1 pip install -e .

then set the thread count at runtime via the OMP_NUM_THREADS environment variable:

OMP_NUM_THREADS=8 python your_script.py

The two build flags are independent and compose; for the fastest build, set both:

LATTICEPTS_NATIVE=1 LATTICEPTS_OPENMP=1 pip install -e .

Counting parallelizes well -- ~7x on 12 threads when there are many top-level branches (latticepts splits the search across the top coordinate's values, so that count caps the speedup); materializing gains less (~2x: its two-pass count-then-fill is more memory-bound), and the thread-startup overhead can make the serial path (parallel=False) faster for small outputs. No extra memory either way: counting holds only each thread's small O(N_hyps * dim) search state, and materializing fills disjoint slices of the single output buffer (no per-thread copies). See the benchmarks for thread-scaling plots.

Algorithm Notes

This repo contains a Cython wrapper of a C implementation of Kannan's algorithm. See this webpage for some other relevant work (not by me). The specific implementation in this repo is for lattice point enumeration in square boxes $|x_i|\leq B$ for $B\geq 1$. I.e.,

$$ \{x\in\mathbb{Z}^{\text{dim}}: Hx\geq\text{rhs} \text{ and } |x|_\infty \leq B\}. $$

It is a short, single-file implementation: one self-contained, dependency-free C header (box_enum.h, ~290 lines of code, depending only on standard C libraries... no extra install) - I encourage you to read it. The single-file format was inspired by the stb-style. If Python is easier to follow, reference/kannan_reference.py is a pedagogical numba.njit port of the same algorithm. The Python port is efficient but has less options than box_enum (scalar rhs only, so cones and stretched cones but not general polyhedra) and is not used at runtime or as a correctness oracle (box_enum is authoritative).

A helper method to box_enum is provided in case the user wants $N$ points but doesn't care about box size. One such task here is for enumerating some lattice points in convex cones. In this case, boxes of increasing sizes $B$ are studied until $\geq N$ lattice points are found.

Benchmarks

The three comparison benchmarks below are single-threaded -- each tool is given one thread, so none is helped or hurt by its own parallelism -- measured on a 24-core Intel Core Ultra 7 270K (30 GB RAM, Ubuntu 26.04) with the default pip install build (GCC -O3). Each plotted point is the median of several warmed-up runs; error bars are usually smaller than the marker. To recreate (Python >= 3.12): pip install -e ".[benchmark]", then run the benchmarks/ scripts. latticepts's own multicore scaling is shown separately below.

Convex cones: runtime vs requested number of interior lattice points in a cone (i.e., not on the boundary). The cone studied is the 7D 'Manwe' from https://arxiv.org/abs/2406.13751:

Runtime vs N on the Manwe example: latticepts outperforms PyNormaliz and OR-Tools CP-SAT

Polytopes: runtime to enumerate all contained lattice points for various 4D reflexive polytopes. Size of the polytope is measured by h11 with one polytope per h11 value, h11 = 6..491:

Runtime vs h11 for 4D reflexive polytopes

More polytopes: runtime vs dimension of length-2 hypercubes $[0,2]^{dim}$ for dim = 2..14:

Runtime vs dimension for the length-2 hypercube

Thread scaling: latticepts also parallelizes (build with LATTICEPTS_OPENMP=1; the comparison plots above use the single-threaded serial path). It splits the search across the top coordinate's values, so the number of top-level branches caps the speedup. On a bounded cube $|x_i|\leq 10$ in 6D (~86M points, 21 top-level branches), the parallelization achieves ~7x speedup for counting the points and ~2x speedup for materializing them, both on 12 threads. Parallelization was often counterproductive (slower) for Normaliz and CP-SAT.

latticepts thread scaling on a bounded cube: counting ~7x on 12 threads, materializing ~2x

Usage

There are two primary interfaces. For unbounded polyhedra (e.g., cones), the focus is on efficiently generating a finite collection of lattice points. This can be done via enum_lattice_points which enumerates all lattice points with components bounded by $|x_i|\leq B$ in the polyhedron. The algorithm increases the size of $B$ until a user-requested number of points is found. See the following example of how to use this to get lattice points in the strict (since $rhs=1$) interior of a convex cone:

import numpy as np
from latticepts import enum_lattice_points

# Find at least 1000 lattice points in {x : H @ x >= rhs}
H   = np.array([[1, 2], [3, -1]], dtype=np.int32)
rhs = 1
pts = enum_lattice_points(H=H, rhs=rhs, min_N_pts=1000)
# pts.shape -> (1062, 2), dtype int32; overshoots min_N_pts because the
# search grows B in steps (stops at B=31) and returns all points at that B

# Optionally restrict to primitive vectors (GCD = 1)
pts = enum_lattice_points(H=H, rhs=rhs, min_N_pts=1000, primitive=True)
# pts.shape -> (1026, 2): still >= min_N_pts, but primitive vectors are
# sparser, so the search steps to a larger box (B=39) to reach the minimum

box_enum allows direct control over the box size $B$ instead of the number of lattice points. I.e., to enumerate all lattice points in $\{x: Hx \geq \text{rhs},\ |x|_\infty \leq B\}$:

from latticepts import box_enum

pts, status, N_nodes = box_enum(B=5, H=H, rhs=rhs, max_N_out=10_000)
# pts.shape -> (31, 2), status == 0 (success), N_nodes == 39
# status: 0 = success, -1 = dim>256, -2 = hit max_N_out, -3 = hit max_N_nodes, -4 = too many constraints
# (statuses are also explained in the docstring)

box_enum is well suited to lattice point enumeration in polytopes (assuming an H-representation is known). For example, if one knows a bounding box of the polytope (if you have a V-representation, this is trivial: $B = \max|v_i|$ over all vertices), then the lattice point enumeration can be done as follows. Here's an example of the $h^{1,1}=491$ 4D reflexive polytope:

import numpy as np
from latticepts import box_enum

H   = np.array([[ 1,   0,   0,   0],
                [-15,  8,   6,   1],
                [-15,  8,   6,  -1],
                [ -1,  1,  -1,   0],
                [  0, -1,   0,   0]], dtype=np.int32)
rhs = np.array([-1, -1, -1, -1, -1], dtype=np.int32)
# has bounding box B = max(|vertices|) = 42 (basis-dependent)
B   = 42

# one can then get the lattice points via:
pts, status, N_nodes = box_enum(B=B, H=H, rhs=rhs, max_N_out=10_000)
# pts.shape -> (680, 4), status == 0, N_nodes == 1289

Citation

If you use latticepts in your research, please cite it:

@software{latticepts,
  author  = {MacFadden, Nate},
  title   = {latticepts},
  doi     = {10.5281/zenodo.19405318},
  url     = {https://github.com/natemacfadden/latticepts},
  orcid   = {0000-0002-8481-3724},
}

Organization

latticepts/
├── latticepts/
│   ├── box_enum.h                       # STB-style library for the Kannan enumeration (serial)
│   ├── box_enum_omp.h                   # optional OpenMP parallel layer (count + materialize) over box_enum.h
|   ├── box_enum.pyx                     # Cython wrapper
|   └── latticepts.py                    # the enum_lattice_points wrapper for box_enum
├── tests/
│   ├── conftest.py                      # shared test helpers (pytest)
│   ├── test_box_enum.py                 # tests of box_enum
│   ├── test_manwe.py                    # tests relating to 'Manwe' (arXiv:2406.13751)
│   ├── test_enum_lattice_points.py      # tests of enum_lattice_points
|   └── c/                               # simple C-kernel tests (no Python interface)
├── benchmarks/                          # perf benchmarks; double as usage examples + make the README figures
│   ├── benchmark_box_enum.py            # runtime vs B for the Manwe geometry (h11=491, 7D)
│   ├── benchmark_enum_lattice_points.py # runtime vs requested N for the Manwe cone (h11=491, 7D)
│   ├── benchmark_polytopes.py           # runtime vs h11 for 4D reflexive polytopes; runtime vs dimension for hypercubes
│   └── benchmark_narrowness.py          # runtime vs narrowness for a 4D convex cone
├── reference/
│   └── kannan_reference.py              # readable pure-Python (numba.njit) port of the algorithm; not used at runtime
├── docs/                                # README figures (benchmark_*.png)
├── pyproject.toml
└── setup.py

License

Download files

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

Source Distribution

latticepts-0.4.0.tar.gz (213.3 kB view details)

Uploaded Sep 9, 2026 Source

Built Distributions

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

The dropdown lists show the available interpreters, ABIs, and platforms. Enable javascript to be able to filter the list of wheel files.

latticepts-0.4.0-cp313-cp313-musllinux_1_2_x86_64.whl (835.4 kB view details)

Uploaded Sep 9, 2026 CPython 3.13musllinux: musl 1.2+ x86-64

latticepts-0.4.0-cp313-cp313-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (800.5 kB view details)

Uploaded Sep 9, 2026 CPython 3.13manylinux: glibc 2.17+ x86-64

latticepts-0.4.0-cp313-cp313-macosx_11_0_arm64.whl (296.2 kB view details)

Uploaded Sep 9, 2026 CPython 3.13macOS 11.0+ ARM64

latticepts-0.4.0-cp313-cp313-macosx_10_13_x86_64.whl (295.0 kB view details)

Uploaded Sep 9, 2026 CPython 3.13macOS 10.13+ x86-64

latticepts-0.4.0-cp312-cp312-musllinux_1_2_x86_64.whl (835.1 kB view details)

Uploaded Sep 9, 2026 CPython 3.12musllinux: musl 1.2+ x86-64

latticepts-0.4.0-cp312-cp312-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (810.7 kB view details)

Uploaded Sep 9, 2026 CPython 3.12manylinux: glibc 2.17+ x86-64

latticepts-0.4.0-cp312-cp312-macosx_11_0_arm64.whl (296.4 kB view details)

Uploaded Sep 9, 2026 CPython 3.12macOS 11.0+ ARM64

latticepts-0.4.0-cp312-cp312-macosx_10_13_x86_64.whl (295.1 kB view details)

Uploaded Sep 9, 2026 CPython 3.12macOS 10.13+ x86-64

latticepts-0.4.0-cp311-cp311-musllinux_1_2_x86_64.whl (845.8 kB view details)

Uploaded Sep 9, 2026 CPython 3.11musllinux: musl 1.2+ x86-64

latticepts-0.4.0-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (814.3 kB view details)

Uploaded Sep 9, 2026 CPython 3.11manylinux: glibc 2.17+ x86-64

latticepts-0.4.0-cp311-cp311-macosx_11_0_arm64.whl (295.8 kB view details)

Uploaded Sep 9, 2026 CPython 3.11macOS 11.0+ ARM64

latticepts-0.4.0-cp311-cp311-macosx_10_9_x86_64.whl (294.1 kB view details)

Uploaded Sep 9, 2026 CPython 3.11macOS 10.9+ x86-64

latticepts-0.4.0-cp310-cp310-musllinux_1_2_x86_64.whl (815.6 kB view details)

Uploaded Sep 9, 2026 CPython 3.10musllinux: musl 1.2+ x86-64

latticepts-0.4.0-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (787.3 kB view details)

Uploaded Sep 9, 2026 CPython 3.10manylinux: glibc 2.17+ x86-64

latticepts-0.4.0-cp310-cp310-macosx_11_0_arm64.whl (297.1 kB view details)

Uploaded Sep 9, 2026 CPython 3.10macOS 11.0+ ARM64

latticepts-0.4.0-cp310-cp310-macosx_10_9_x86_64.whl (295.5 kB view details)

Uploaded Sep 9, 2026 CPython 3.10macOS 10.9+ x86-64

latticepts-0.4.0-cp39-cp39-musllinux_1_2_x86_64.whl (813.9 kB view details)

Uploaded Sep 9, 2026 CPython 3.9musllinux: musl 1.2+ x86-64

latticepts-0.4.0-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (784.4 kB view details)

Uploaded Sep 9, 2026 CPython 3.9manylinux: glibc 2.17+ x86-64

latticepts-0.4.0-cp39-cp39-macosx_11_0_arm64.whl (297.4 kB view details)

Uploaded Sep 9, 2026 CPython 3.9macOS 11.0+ ARM64

latticepts-0.4.0-cp39-cp39-macosx_10_9_x86_64.whl (295.9 kB view details)

Uploaded Sep 9, 2026 CPython 3.9macOS 10.9+ x86-64

File details

Details for the file latticepts-0.4.0.tar.gz.

File metadata

Download URL: latticepts-0.4.0.tar.gz
Upload date: Sep 9, 2026
Size: 213.3 kB
Tags: Source
Uploaded using Trusted Publishing? Yes
Uploaded via: twine/7.0.0 CPython/3.13.14

File hashes

Hashes for latticepts-0.4.0.tar.gz
Algorithm	Hash digest
SHA256	`b52cc9ed7b1ae86f3108855761a2b6c3b64fa050b96ebe4646991c863108eda5`
MD5	`b14f844450fc4de708568389b3aac18a`
BLAKE2b-256	`21646438d2be64a3fb115384a07913782f2d766907e034406ebe2969e7130530`

Algorithm	Hash digest
SHA256	`697c68508232b7d1e0bad731de1d1f3d62668f7e1693bfcbe41646d955e89131`
MD5	`74fe6df4c5f1c2a5ff22cfa1310dc5c4`
BLAKE2b-256	`762a278061eb7354d5c1726c0c424d830198d697069b668d419f565d807addb3`

Algorithm	Hash digest
SHA256	`027d37838a0efa71adfcacdae3539c26e7b92aeb1edae14990437af155c545c1`
MD5	`4b815b1612d52dba14db96f65dd8197a`
BLAKE2b-256	`627afacf2521b348fdd5e552731ed79a338eecb53eef07f8921216c025ec8870`

Algorithm	Hash digest
SHA256	`5c8687ab0335c5ee72b1d6aa7d2cf94dbe34443c089a90286d16981c5042e1da`
MD5	`9ab2b1eea5bc814495cd65d62a929025`
BLAKE2b-256	`fb8f040e13b4b9350208a284c11946835c987fe91c56d42ed267e96d2b77424c`

Algorithm	Hash digest
SHA256	`7cf54cd06d9ada072105b3c30ef519e8dab5d2c41ad53dee30f14c089aebd62b`
MD5	`03703eeb5f023615ea4b21088c35b916`
BLAKE2b-256	`ebb6d7b5b2d6db1c12a89434521ee310c91d334cd153998f75b5c930dbf047f6`

Algorithm	Hash digest
SHA256	`06288e96f09590e406616713849bc2bafbb066ead4daa7bf8c4bb209c48a0d8b`
MD5	`c6fcbf98b5a6ff2cc3b64c87e3df0cf0`
BLAKE2b-256	`659cc051c1a45a7ad05e7acf9c62b5f3748b7a24ed9b7f9e20ea2d2020ca4daa`

Algorithm	Hash digest
SHA256	`01b8cd31655d9fd9e15a030def79f784f96c99f4fbb3c871539a7be5a1008f85`
MD5	`633c773bb2dcf9b4a0577c44d0fc251b`
BLAKE2b-256	`7d6c0ce73fc7dbc936f5dcbaf3db7e241a24729964019528bf3583fb5c788eba`

Algorithm	Hash digest
SHA256	`2fde527dc8fb3887e049e9021e1f780f7fdac90df5f6140bbc32ed6d942141e5`
MD5	`0ad77be8f48419679e6373fd7e803118`
BLAKE2b-256	`f1e820f0be6c18023ee8c4581dbaf943e9698ae8ade770bbe714764eaf03e390`

Algorithm	Hash digest
SHA256	`ed42283df25dca090d3111ea4fa20a8932441de712c4ca87a206e972f005cb7a`
MD5	`f4762996cf0bb54d2525828ab34468c7`
BLAKE2b-256	`94614092a7a10b2a0e973f123c1f084d3f6f787fdb8ed6cf21b1c3cb3284c504`

Algorithm	Hash digest
SHA256	`b5a0daf964124a1aff4e724dc63b053766f3107acd015c2aa97bbe4f7570ac87`
MD5	`5f42bd0f67dd21edd67b770bcd372752`
BLAKE2b-256	`932d4ce408b253e392442811d648dc3cc58f3b5992182769d2b61fef2c779c73`

Algorithm	Hash digest
SHA256	`14d201b1b4d8b1fb2386104a4ef2d3720be6c91d3e53fb2f35a914f9a1fefeb9`
MD5	`e648ef2d594caa4f612bd77c6088af60`
BLAKE2b-256	`f0f9fe72b84afa032e7cbf5cf0ec6c873f0b9375db48fd322a5a8b70789e50e9`

Algorithm	Hash digest
SHA256	`a72603471298c3d838f60662ed29a33e256077eeade18a9d59fe6f85d0d4799c`
MD5	`81a0590e1da246400984e6f9b02262e5`
BLAKE2b-256	`3197ba2f02de14f0ddc64c2522609b9d6548692c037faaad3f5a2012e24c9a9d`

Algorithm	Hash digest
SHA256	`d9aec45c55c9e158d8f10e9cda1384398f6d69df4796847ad3eed59c12c9860f`
MD5	`8b71f139f8590c8536bd69203affef7b`
BLAKE2b-256	`3334229153f2a30cd384cc405ae502a943b4762ece85432aca758c1678233e1f`

Algorithm	Hash digest
SHA256	`aad76cfc7227696096b6ed590320a659cc2ae730558f59c184a22c68c331d4ba`
MD5	`e9a7ebf99c0fe7c603a5835cf7f7f4ef`
BLAKE2b-256	`f8bab994761d2bbdfdc71ba4540bed35b57dc2dd6bd8ceed44600cf50374160c`

Algorithm	Hash digest
SHA256	`2d2763b9491bb3c4fa82f0b6d2ad7e5136821a6406c80131b8d4ed50f349e715`
MD5	`102d3dbf866d61349f4b38f408fce4df`
BLAKE2b-256	`488f18d86d234fe39325d2ae2fbd8bfc12205aebf4041a1ab4d1dcdad1c2ab78`

Algorithm	Hash digest
SHA256	`295d22574e884e2de82bcd3fc51bacb9c9323ae79b992ac80b99ccb3eca49e26`
MD5	`61e5c6de3b5630f10e7ca2cd822f3c0c`
BLAKE2b-256	`0cf763b5bd5c60e11ce25ac41b6329a1a70a31ad17caa44a663b8c90ac7ee57b`

Algorithm	Hash digest
SHA256	`12caac57b49fccb80fa46a687d0959d3daed85e9962558c25d613d4905e11f00`
MD5	`3b021d00c1a5d2e236b7469a6e13677f`
BLAKE2b-256	`4e6982def22869d13fe5c07679b9a263665cc7c62706b8204163e30091a6d15c`

Algorithm	Hash digest
SHA256	`bbafa3a9c52591ba5dfc8ce9d282578774564f3f464e38dd6c682344ef49e05e`
MD5	`be4f0aa750503bf09c948b328cb51dc2`
BLAKE2b-256	`9ed2ea8cafda95cba09f2fc398de0441bb36691d8592324bebd79f017d800d04`

Algorithm	Hash digest
SHA256	`6037bd0c103c64a8b59be132903017ab49e1574cfafab4af173ff645070e5b9b`
MD5	`af603820b46ab7d5e4b3682adb39fdaa`
BLAKE2b-256	`8a135e29ae0a7ef611b52deb01ff4b4ff3506035c6d6b2e1557cdbf9f801b281`

Algorithm	Hash digest
SHA256	`8e116ad82672b87f8207a5b05b1e706540c494fef90650833a70c8fd0f8e226f`
MD5	`54be9ac168849fefa552126e429b3bc6`
BLAKE2b-256	`f99a93881ca12292f952055764a9c38c5da6cf1adf36e27f15830c884b6c59de`

Algorithm	Hash digest
SHA256	`f6a1c5189bad6c24ec9c9f93fc4ccbbf47c840dd5f970f16ca9a04e7c8a592c6`
MD5	`6f1b3f9074bac7f974cfce8aabfed17b`
BLAKE2b-256	`fc74a8d283d64f0b33196d550586e403db0545852662f8e2f2a86fba07bc6f34`

latticepts 0.4.0

latticepts

Description

Limitations

Installation

Building from source

Algorithm Notes

Benchmarks

Usage

Citation

Organization

License

Project links

Key dates

1 maintainer

Credits

GitHub Statistics

License expression

Requires

Provides Extra

Tags

Classifiers

Download files

Source Distribution

Built Distributions

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes