Periodic linked-cell neighbour lists for molecular simulations.
pairs_within is the cutoff list: one row per atom-image, the caller's shift S, and a squared distance strictly below the cutoff squared.
knearest is the k-nearest list. nanoflann builds Euclidean KD-trees without a minimum-image convention.
The walk is the linked-cell method of Allen and Tildesley (Computer Simulation of Liquids). k-nearest shells stop when the k-th neighbour reaches the unvisited plane.
The optional gpulite path runs that k-nearest walk on a CUDA device and still stops on the looser reach * cell_min bound (linkcell::gpu::Workspace).
src/kokkos/ is the certified walk on a Kokkos execution space.
Pair lists stay on the host.
The host pair-list library is a Library of Data Exchange (LODE) library for the linked-cell walk.
The Rust crate is the implementation.
The C application binary interface (lc_*) is the hourglass waist, the same shape as readcon-core.
C++ is a Resource Acquisition Is Initialization (RAII) header over that interface.
Released versions live in CHANGELOG.md (Keep a Changelog).
Unreleased notes are files under changelog.d/.
The cut is towncrier build --version X.Y.Z.
Rust:
cargo add linkcell
C and C++ consumers include linkcell.h or linkcell.hpp and link the installed library.
Meson, CMake, and pkg-config install both shared and static CPU libraries.
The device API is a separate static library with linkcell_gpu.h / linkcell_gpu.hpp.
The Python library install takes the same search through DLPack (dlpk).
Any __dlpack__() object (numpy, torch, jax, cupy) is a valid xyz / cell, on any device.
A CUDA xyz stays on device; a CUDA cell is inverted on device.
torch.from_dlpack consumes (indices, dist2).
Wheels: one CPython 3.12 limited-ABI (abi3) artifact per platform (GIL, 3.12+), and one abi3t artifact (CPython 3.15+ GIL and free-threaded).
pip install linkcell
import numpy as np
import linkcell
xyz = np.array([[0.2, 0.0, 0.0], [9.4, 0.0, 0.0]], dtype=np.float64)
cell = np.array([10.0, 10.0, 10.0], dtype=np.float64)
nn, d2 = linkcell.knearest(xyz, cell, 1)
nn = np.from_dlpack(nn)meson setup build
meson compile -C build
meson install -C build
As a wrap, Meson exposes linkcell_dep:
[wrap-git]
url = https://github.com/d-SEAMS/linkcell.git
revision = v0.4.2
depth = 1
[provide]
linkcell = linkcell_dep
linkcell-gpu = linkcell_gpu_dep
linkcell_dep = dependency('linkcell', fallback: ['linkcell', 'linkcell_dep'])
linkcell_gpu_dep = dependency(
'linkcell-gpu',
fallback: ['linkcell', 'linkcell_gpu_dep'],
)with_gpulite controls the device target and defaults to auto.
cmake -B build -DCMAKE_INSTALL_PREFIX=$PREFIX
cmake --build build
cmake --install build
find_package(linkcell 0.4 REQUIRED)
target_link_libraries(c_app PRIVATE linkcell::linkcell)
target_link_libraries(cpp_app PRIVATE linkcell::cpp)
target_link_libraries(device_app PRIVATE linkcell::gpu)LINKCELL_WITH_GPULITE=ON builds linkcell::gpu and is the default.
linkcell::cpp carries the C++17 requirement; linkcell::linkcell stays valid in a C-only project.
The same target names work in the build tree and from an installed prefix.
pkg-config --cflags --libs linkcell
pkg-config --cflags --libs linkcell-gpu
Both Meson and CMake write linkcell.pc and, when the device target is built, linkcell-gpu.pc.
Use pkg-config --static when selecting the CPU static archive and its private system libraries.
use linkcell::{knearest, Cell};
let sim = Cell::ortho(10.0, 10.0, 10.0)?;
let sheared = Cell::from_vectors(
[10.0, 0.0, 0.0],
[5.0, 8.66, 0.0],
[0.0, 0.0, 10.0],
[0.0, 0.0, 0.0],
)?;
let xyz = [[0.0, 0.0, 0.0], [1.0, 0.0, 0.0]];
let rows = knearest(&xyz, &sim, 1, None, None)?;
assert_eq!(rows[0].indices, vec![1]);mask[i] == false removes a point as both a source and a candidate.
cell_hint is the target cell edge; None uses 3.0 in the box units.
#include "linkcell.h"
double xyz[] = {0.0, 0.0, 0.0, 1.0, 0.0, 0.0};
lc_cell box = lc_cell_ortho(10.0, 10.0, 10.0);
int out[2];
if (lc_knearest(xyz, 2, &box, 1, NULL, 0.0, out) != 0) {
return 1;
}n and k are size_t.
out has length n * k.
Unused slots are -1.
Neighbours of source i are out[i*k + 0 ..], nearest first.
#include "linkcell.hpp"
const linkcell::Cell box = linkcell::Cell::ortho(10.0, 10.0, 10.0);
const double xyz[] = {0.0, 0.0, 0.0, 1.0, 0.0, 0.0};
const linkcell::Neighbours nn = linkcell::knearest(xyz, 2, box, 1);nn owns the packed n * k buffer.
Unused slots are -1.
nn.neighbour(i, j) is the j-th neighbour of i.
Failure throws linkcell::Error.
The optional device walk reads occupancy from the environment: LINKCELL_TPP (threads per particle) and LINKCELL_BLOCK (CUDA block size).
Unset, the library picks a pair that maximises particles per block under the device thread and 48 KiB shared-memory limits.
d-SEAMS writes the same keys from SEAMS_CONFIG / seams --tpp.
The documentation is published at d-seams.github.io/linkcell, with the Rust API under /api and an llms.txt map. The sources are under docs/.
| Quadrant | Page |
|---|---|
| Tutorial | Two points |
| How-to | Embed from C, Embed from C++, Embed from Python, pkg-config |
| Reference | C ABI, Algorithm, Cell partition |
| Explanation | Minimum image convention (MIC) and cells, SIMD paths and dispatch |
Rust API: docs.rs/linkcell. Map: docs/index.md.
- The cell is a general parallelepiped: three lattice vectors plus an origin.
Orthorhombic boxes are
Cell::ortho/lc_cell_ortho. Binning is in fractional space, so a sheared dump is not treated as orthogonal. - An open axis is not padded into a periodic box.
pairs_open/lc_pairs_openbins the occupied Cartesian cells and returns the half list (i < j, shift zero). With every axis open the partner stencil depends on the cutoff and the bin edge alone, so frames in other bins reuse it; with a periodic axis it is rebuilt when the bounding bins change.lc_stencil_buildscounts the builds.pairs_within_pbcis the same list with a periodicity mask; a fully periodic mask ispairs_within. - Points fold into the primary cell once.
Each source then grows a rectangular box of neighbour cells, one direction at a time.
Pair distances are a Cartesian subtract plus that cell's lattice translation (
dist2_shiftedandlattice_shift), the vesin / LAMMPS ghost construction. Orthorhombic boxes use three independent wraps and skip the two Hinv matvecs. The batched form of that wrap is minimage's Highway kernel,dist2_ortho_diffs, re-exported here and used by the orthorhombic brute-force check. A cutoff row keeps the stencil image, sopairs_withinskips that round on an already shifted difference. A restricted triclinic box is tilt-reduced and uses a triangular shift. - One lattice shift per unique cell is wrong unless every wrap of that cell is visited. The walk visits integer cell offsets, so each wrap of a bin is a separate visit.
knearesttakes a neighbour count and a cell-size hint. The hint only sets the bin width.kneareststores each bin as a contiguous slice. An orthorhombic cell is binned as stored, a restricted triclinic cell is tilt-reduced, and a general orientation is Minkowski-reduced. The box grows until the k-th neighbour is no farther than the nearest unvisited face.- A cutoff pair list is
pairs_within/lc_pairs_within/linkcell.pairs_within: atom-image rows with the caller's shiftS.knearestis the k-nearest list.pairs_within_columns,lc_pairs_within_rows, and the Python call write theijScolumns orlc_pairrows straight from the search, and a C count query keeps its search for the fill that follows on the same thread.
cell_grid is the fractional mesh pairs_within uses, with a point count on each bin.
cell_graph adds the periodic adjacency.
An edge weight is the number of cutoff pairs with one end in each bin.
partition returns one domain id per cell.
halo_width turns a cutoff and a shell count into three bin radii, and halo lists the ghost bins of one domain.
The balance bound defaults to 1 + parts * w_max / total for every system.
w_max is the heaviest cell weight and total is the sum of the cell weights.
lc_partition selects that ratio when balance <= 0.
A weighted median assigns the straddling cell to one side.
The part may exceed the ideal share by at most that cell.
That is the tightest bound a cell-aligned cut can promise, and it is the ratio the d-SEAMS domain driver derives per frame.
Our method computes the default from the five-system panel in examples/partition_panel.rs.
We report the native cut with the smallest sum of edge cuts among the cuts that stay inside that bound.
A tie breaks toward the smaller sum of median wall times.
Morton, Hilbert, recursive coordinate bisection (RCB), and a Fiduccia-Mattheyses pass are always built.
Serial Scotch is --features scotch.
Parallel Scotch is --features ptscotch.
Neither library is vendored, and both features are off by default.
The device path runs weights, curve keys, and the prefix split through gpulite.
Copies both ways are inside that time.
use linkcell::{halo, halo_width, partition, PartRequest, Cell};
let sim = Cell::ortho(10.0, 10.0, 10.0)?;
let xyz = [[0.0, 0.0, 0.0], [1.0, 0.0, 0.0]];
let domain = partition(&xyz, &sim, 3.0, None, None, PartRequest::new(2))?;
let width = halo_width(3.0, 1, [10.0, 10.0, 10.0])?;
let _ghosts = halo(
&linkcell::cell_grid(&xyz, &sim, 3.0, None, None)?,
&domain,
0,
width,
)?;lc_cell_grid, lc_cell_graph, lc_partition, lc_halo_width, and lc_halo are the C entry points.
linkcell::partition in include/linkcell.hpp is the Resource Acquisition Is Initialization wrap.
Python is cell_grid, cell_graph, partition, halo_width, and halo, all DLPack.
Massachusetts Institute of Technology (MIT)