Metadata-Version: 2.4
Name: linkcell
Version: 0.4.2
Classifier: Programming Language :: Rust
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.12
Classifier: Programming Language :: Python :: 3.13
Classifier: Programming Language :: Python :: 3.14
Classifier: Programming Language :: Python :: 3.15
Requires-Dist: pytest>=8.0 ; extra == 'test'
Requires-Dist: numpy>=1.26 ; extra == 'test'
Provides-Extra: test
License-File: LICENSE
Summary: Periodic linked-cell cutoff pairs and k-nearest neighbour search
Author-email: Rohit Goswami <rgoswami@ieee.org>
License: MIT
Requires-Python: >=3.12
Description-Content-Type: text/markdown; charset=UTF-8; variant=GFM
Project-URL: Documentation, https://d-seams.github.io/linkcell/
Project-URL: Homepage, https://d-seams.github.io/linkcell/
Project-URL: Repository, https://github.com/d-SEAMS/linkcell

# linkcell

<p align="center">
  <img src="assets/branding/linkcell-logo-light.svg" width="360" alt="linkcell">
</p>

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](https://github.com/lode-org/readcon-core).
C++ is a Resource Acquisition Is Initialization (RAII) header over that interface.

Released versions live in [CHANGELOG.md](CHANGELOG.md) (Keep a Changelog).
Unreleased notes are files under `changelog.d/`.
The cut is `towncrier build --version X.Y.Z`.

## Install

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
```

```python
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

```
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
```

```meson
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

```
cmake -B build -DCMAKE_INSTALL_PREFIX=$PREFIX
cmake --build build
cmake --install build
```

```cmake
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

```
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.

## Rust

```rust
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.

## C

```c
#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.

## C++

```cpp
#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`.

## Docs

The documentation is published at [d-seams.github.io/linkcell](https://d-seams.github.io/linkcell/), with the Rust API under [/api](https://d-seams.github.io/linkcell/api/linkcell/) and an [llms.txt](https://d-seams.github.io/linkcell/llms.txt) map. The sources are under `docs/`.

| Quadrant | Page |
| --- | --- |
| Tutorial | [Two points](docs/tutorials/two-points.md) |
| How-to | [Embed from C](docs/how-to/embed-c.md), [Embed from C++](docs/how-to/embed-cpp.md), [Embed from Python](docs/how-to/embed-python.md), [pkg-config](docs/how-to/pkg-config.md) |
| Reference | [C ABI](docs/reference/c-api.md), [Algorithm](docs/reference/algorithm.md), [Cell partition](docs/reference/partition.md) |
| Explanation | [Minimum image convention (MIC) and cells](docs/explanation/mic-and-cells.md), [SIMD paths and dispatch](docs/explanation/simd-paths.md) |

Rust API: [docs.rs/linkcell](https://docs.rs/linkcell).
Map: [docs/index.md](docs/index.md).

## Design

- 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_open` bins 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_builds` counts the builds.
  `pairs_within_pbc` is the same list with a periodicity mask; a fully periodic mask is `pairs_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_shifted` and `lattice_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, so `pairs_within` skips 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.
- `knearest` takes a neighbour count and a cell-size hint.
  The hint only sets the bin width.
  `knearest` stores 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 shift `S`.
  `knearest` is the k-nearest list.
  `pairs_within_columns`, `lc_pairs_within_rows`, and the Python call write the `ijS` columns or `lc_pair` rows straight from the search, and a C count query keeps its search for the fill that follows on the same thread.

## Domain partition

`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.

```rust
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.

## License

Massachusetts Institute of Technology (MIT)

