2-D Fast Multipole Method: three demos
Interactive, in-browser ports of three Java Fast Multipole Method demos written by Yang Wang for the UMIACS course CMSC 878R / AMSC 698R, Fast Multipole Methods (Nail Gumerov and Ramani Duraiswami), 2003-2005. Each solves the 2-D Coulombic (log-kernel) potential problem φ(y) = ∑i ui log(y − xi) for a set of charged source points, evaluated at a set of target points, in O(N) instead of O(N²) work. No dependencies, no build step, no CDN.
Regular MLFMM
A single uniform-depth quadtree, every leaf holding at most a fixed number of points. Greengard & Rokhlin, "A fast algorithm for particle simulations," J. Comput. Phys. 73(2):325-348 (1987).
Adaptive: Cheng-Greengard-Rokhlin
Per-branch subdivision with four classical interaction lists (List 1-4) and placeholder "dummy" boxes filling out a uniform-depth array. Cheng, Greengard & Rokhlin, "A fast adaptive multipole algorithm in three dimensions," J. Comput. Phys. 155:468-498 (1999).
Adaptive: Gumerov-Duraiswami
A pruned D-tree of variable-depth target boxes plus a companion C-forest supplying multipole expansions. Gumerov & Duraiswami, Fast Multipole Methods for the Helmholtz Equation in Three Dimensions, pp. 265-283, Elsevier Science, Oxford, 2005, Ch. 6.
What "adaptive" buys you
On a strongly clustered 2000-point set (8 tight clusters), the regular tree must
subdivide uniformly to depth 7 everywhere to keep the densest cluster's leaves under
threshold, materializing 5,461 boxes. The Cheng-Greengard-Rokhlin tree needs only 413
active (non-placeholder) boxes for the same accuracy; the Gumerov-Duraiswami tree's
pruned D-tree needs only 289 active nodes -- see fantalgo-fmm/fmmjs/NOTES.md
for the full measurement and the command that reproduces it.
Source provenance
All three Java demos are named directly on Yang Wang's own 2005 page, still live one
level up at ../index.htm: "Regular Multilevel
FMM" (fmmdemo.zip), "Adaptive Multilevel FMM" (fmmdemo-adaptive.zip,
the Gumerov-Duraiswami tree) and "Another Adaptive Multilevel FMM"
(fmmdemo-adaptive2.zip, the Cheng-Greengard-Rokhlin tree).
- Regular tree and Cheng-Greengard-Rokhlin adaptive tree: source
found in two independent places agreeing byte-for-byte -- the archive copy at
FMMcourse/adaptive/fmmdemo-adaptive2(2005-08-02) andFMMcourse/2008/adaptive.zip-- and confirmed as the same code insidefmm/files/fmmdemo-adaptive2.zipon this page. - Gumerov-Duraiswami adaptive tree: not present anywhere under
FMMcourse/(only its compiled classes were archived there,fmm_adaptive_GD/*.class, 2005-08-10). It was first recovered 26 Sep 2026 by decompiling those classes with CFR and cross-checked against Gumerov & Duraiswami's book chapter (Ch. 6 SS6, "Adaptive MLFMM") and, separately, against a fixed-seed run of the original compiled classes on Nexus (roundoff agreement, ~1e-14). Its real, hand-written source then turned up infmm/files/fmmdemo-adaptive.zipright here on the homepage -- confirming the decompiled reconstruction field-for-field and line-for-line (down to the exact recursion condition inbuildDTreeHelper), so the shipped port is a direct transcription of that source, not the decompiled approximation. - Every numeric expansion and translation operator (S, R, S|S, S|R, R|R) is ported
unchanged from
Potential.java, shared by all three trees.
Validation
All three trees are checked in a Node test suite (node --test) against
direct O(N·M) summation for N = 100, 1,000 and 10,000 on both uniform and
clustered point sets; error is checked to fall as the truncation order p increases;
the three trees are checked to agree with each other and with direct summation to
truncation error on the same inputs; and the two adaptive trees are cross-checked
against the original Java classes as above. See fantalgo-fmm/fmmjs/NOTES.md
for the full table.