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:

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:

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

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.

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

GPLv3. Copyright (c) 2026 Nate MacFadden.