fast-multipole

A Python implementation of the two-dimensional Fast Multipole Method (FMM) for the logarithmic kernel.

The project currently provides a tested O(N²) direct-force baseline and an interactive visualization scaffold. The baseline follows the force convention used by keyframe41/Fast-Multipole-Method. The adaptive quadtree and FMM expansion passes are the next implementation milestone.

Goals

• Implement adaptive two-dimensional FMM in clear, typed Python.
• Use NumPy for deterministic numerical kernels.
• Validate FMM output against the direct-force baseline.
• Visualize sources, forces, quadtree cells, and interaction lists.
• Preserve implementation decisions and evidence with LDGR.

Install

uv sync --extra demo

Use the direct baseline

import numpy as np

from fast_multipole import direct_forces

positions = np.array([[0.0, 0.0], [1.0, 0.0]])
strengths = np.array([2.0, 3.0])
forces = direct_forces(positions, strengths)

Run the demo

The demo uses FastAPI, HTMX, and copied Greeble components.

uv run --extra demo uvicorn demo.app:app --reload

Open http://127.0.0.1:8000. Change the source count or random seed to regenerate the direct-force field.

Development

dev is the project control surface.

dev install python
dev fix
dev ci

dev ci checks formatting, lint, types, tests, and pre-commit hooks. GitHub Actions runs the same command.

Implementation map

The Python port will follow these reference concepts without copying the C++ structure mechanically:

1. Source model and direct-force validation.
2. Adaptive quadtree construction and stable source partitioning.
3. Complex multipole and local expansion primitives.
4. Upward pass with multipole-to-multipole translation.
5. Interaction lists and multipole-to-local translation.
6. Downward pass with local-to-local translation.
7. Near-field evaluation and complete force assembly.
8. Accuracy, complexity, and visualization checks.

See NOTICE for upstream attribution. See the LDGR ledger for durable work history.

License

MIT. See LICENSE.