1// The solvers shipped with the site. Each solver is a MATLAB function
2// file (solver.m) implementing the interface documented in
3// docs/problems/laplace-dirichlet-2d.md. A submitted solver adds a
4// directory here plus a manifest entry.
5//
6// Two manifest entries may share one solver.m: the "-mat" entries are the
7// same file as their numbl twin, run in real MATLAB instead, which makes
8// the pair of curves a measurement of the runtime rather than of the
9// method. Such an entry sets sourceDir to the twin's directory.
11export interface SolverManifest {
12 /** Short stable identifier used in results and URLs. */
13 id: string;
14 name: string;
15 /** One-paragraph description of the method for the problem page. */
16 description: string;
17 /** Semantic version of the solver code; bump on any change that could
18 * alter results. */
19 version: string;
20 backend: "cpu" | "gpu";
21 /** What executes the solver: "numbl" solvers run in the browser and in
22 * the CLI; "matlab" solvers run only in real MATLAB via the CLI. */
23 runtime: "numbl" | "matlab";
24 /** The resolution values a standard work-precision sweep runs. */
25 sweepN: number[];
26 /** Resolutions for instances that need a different range from sweepN,
27 * keyed by instance id. A harder geometry can need several times the
28 * resolution, and putting those values in every sweep would only make
29 * the easy instances slow. */
30 sweepNByInstance?: Record<string, number[]>;
31 /** Directory under src/solvers/ holding this solver's solver.m, when it
32 * is not the solver's own id: set by entries that share a file with
33 * another entry. Both entries must then carry the same version. */
34 sourceDir?: string;
35}
37/** Directory under src/solvers/ holding a solver's solver.m. */
38export function solverSourceDir(s: SolverManifest): string {
39 return s.sourceDir ?? s.id;
40}
42/** The resolutions a sweep of this solver runs on this instance. */
43export function sweepNFor(s: SolverManifest, instanceId: string): number[] {
44 return s.sweepNByInstance?.[instanceId] ?? s.sweepN;
45}
47export const SOLVERS: SolverManifest[] = [
48 {
49 id: "mfs",
50 name: "Method of fundamental solutions",
51 description:
52 "Represents the solution as n logarithmic point charges on a curve " +
53 "a fixed distance 0.3 outside the boundary, with strengths found by " +
54 "collocation at n boundary points. Converges geometrically when the " +
55 "data continues harmonically past the charge curve, reaching machine " +
56 "precision on the easier instances with far less work than the " +
57 "integral-equation methods. When the data's singularities sit inside " +
58 "that curve, as on star-hard, convergence is lost: more charges keep " +
59 "helping only until the system's ill-conditioning takes over, and the " +
60 "error settles near 1e-6 however far the sweep is pushed. On " +
61 "flower-15 the method fails outright, and for a reason worth stating: " +
62 "a fixed offset of 0.3 from a boundary whose curvature radius is " +
63 "0.014 is not a curve at all. The offset self-intersects and leaves " +
64 "some 45 percent of the charges inside the domain, where they " +
65 "destroy the harmonicity of the representation. A better MFS would " +
66 "choose the offset from the local geometry rather than fixing it in " +
67 "advance; this one does not, and the instance shows what that costs. " +
68 "On square-corners it is instead the strongest method by a wide " +
69 "margin, reaching 2e-13. Two things go its way there: the domain is " +
70 "convex, so the offset charge curve is simple again, and the charges " +
71 "stay 0.3 away from every evaluation point, so the near-corner " +
72 "targets that defeat the integral-equation methods cost it nothing. " +
73 "Its error at the target 0.005 inside a corner is the same 1e-13 as " +
74 "in the bulk. On star-nearfield, whose targets come within 0.005 of " +
75 "the boundary, it likewise pays nothing for them: charges 0.3 " +
76 "outside the domain make the representation smooth all the way in, " +
77 "so the error there is the conditioning-limited few times 1e-6 it " +
78 "already reaches on star-hard (1.7e-6 in real MATLAB, 3.9e-6 in " +
79 "numbl, the two differing because the error is set by rounding in a " +
80 "badly conditioned solve). That makes it the cheapest route to 1e-6 " +
81 "of the three solvers on that instance, and the one with nothing " +
82 "left beyond it.",
83 version: "1.0.0",
84 backend: "cpu",
85 runtime: "numbl",
86 sweepN: [8, 12, 16, 24, 32, 48, 64, 96, 128, 192, 256, 384, 512, 768],
87 },
88 {
89 id: "nystrom-dlp",
90 name: "Nystrom double-layer BIE",
91 description:
92 "Second-kind boundary integral equation for the double-layer " +
93 "density, discretized with the periodic trapezoid rule at n " +
94 "boundary nodes. Converges geometrically for any smooth data, at a " +
95 "rate set by how far the data continues analytically, so the hard " +
96 "instance costs more nodes rather than a lost method assumption. On " +
97 "flower-15 that price is about four times the nodes: a few hundred " +
98 "to resolve fifteen lobes at all, and more still because the plain " +
99 "quadrature is inaccurate for the evaluation points nearest the " +
100 "boundary until the node spacing falls well below their distance to " +
101 "it (0.0295 at the closest). Past that the geometric convergence " +
102 "returns, and it is fast: on that instance the error falls from " +
103 "5e-4 at n = 768 to 2e-7 at n = 1536. square-corners exposes the " +
104 "method's real weakness instead, which is evaluation rather than " +
105 "solution. At n = 768 the bulk error there is 7e-9, already " +
106 "converged, while the error at the target 0.005 inside a corner is " +
107 "4.6e-2: uncorrected quadrature for a target a fraction of a node " +
108 "spacing from the boundary loses everything, and the reported error " +
109 "follows exp(-2 pi delta / h) across the four target distances. " +
110 "Reaching 1e-8 at those targets takes about 4000 nodes, where the " +
111 "bulk alone would need 500. star-nearfield makes the same point " +
112 "without the geometry, being the domain and data of star-hard with " +
113 "32 targets 0.005 to 0.05 inside the boundary, and there the " +
114 "exp(-2 pi delta / h) law is legible straight down the ladder: at " +
115 "1024 nodes one and the same density is accurate to 7.5e-14 in the " +
116 "bulk, 6e-14 at the target 0.05 in, 6.6e-6 at 0.02, 2.7e-3 at 0.01 " +
117 "and 6.3e-2 at 0.005. The browser sweep, stopping at 1536 nodes, " +
118 "reaches 1.2e-2; the MATLAB twin needs 4096 nodes and 0.86 s for " +
119 "6.7e-6. We emphasize that this is a property of the uncorrected " +
120 "quadrature rule and not of Nystrom methods: a near-field " +
121 "correction, whether by kernel splitting or by a locally corrected " +
122 "or expansion-based rule, removes it, and chunkie-dlp, which is the " +
123 "same integral equation with one, reaches 1.8e-11 there.",
124 version: "1.0.0",
125 backend: "cpu",
126 runtime: "numbl",
127 sweepN: [16, 24, 32, 48, 64, 96, 128, 192, 256, 384, 512, 768],
128 // flower-15 needs roughly four times the nodes: the boundary itself
129 // costs about 200 to resolve, and the evaluation points sit close
130 // enough to it that the plain quadrature stays inaccurate until the
131 // node spacing is well under that distance.
132 sweepNByInstance: {
133 "flower-15": [32, 48, 64, 96, 128, 192, 256, 384, 512, 768, 1024, 1536],
134 // The corner targets need a node spacing well below 0.005, which is
135 // thousands of nodes. This list stops at 1536 because a numbl solve
136 // at 2048 takes about five seconds, and a browser sweep has to stay
137 // usable; nystrom-dlp-mat carries the tail.
138 "square-corners": [64, 96, 128, 192, 256, 384, 512, 768, 1024, 1536],
139 // Same story as square-corners, for the same reason: the closest
140 // near-boundary target is 0.005 inside, and the coarse end of the
141 // standard list is off the chart (relMax above 1 at n = 16).
142 "star-nearfield": [64, 96, 128, 192, 256, 384, 512, 768, 1024, 1536],
143 },
144 },
145 {
146 id: "chunkie-dlp",
147 name: "chunkie double-layer BIE",
148 description:
149 "The same second-kind double-layer formulation as nystrom-dlp, " +
150 "discretized by chunkie, a production MATLAB boundary-integral " +
151 "toolbox: n uniform 16th-order Gauss-Legendre panels, high-order " +
152 "singular quadrature in the assembly, a direct dense solve, and " +
153 "near-corrected evaluation of the potential. Runs in real MATLAB " +
154 "only: the command line invokes matlab -batch and installs chunkie " +
155 "with the mip package manager on first use, so its results appear " +
156 "here but cannot be rerun in the browser. chunkie's default " +
157 "quadrature tolerances cap the attainable accuracy near 1e-11. Its " +
158 "corrected quadrature buys a great deal of accuracy per node: on " +
159 "flower-15 it is some 250 times more accurate than nystrom-dlp at " +
160 "the same number of boundary points. Note, however, that this does " +
161 "not make it the faster route to a given accuracy here. Each solve " +
162 "costs roughly eight times as much per point (adaptive singular " +
163 "quadrature in the assembly, near-corrections in the evaluation), " +
164 "and against that the trapezoid rule's geometric convergence wins: " +
165 "on flower-15 in the same MATLAB, nystrom-dlp-mat reaches 1e-9 in " +
166 "0.2 s where chunkie needs 0.3 s, and goes on to 1e-14, which " +
167 "chunkie's tolerances do not permit. The generality chunkie pays " +
168 "for (corners, adaptive panels, fast algorithms) is barely " +
169 "exercised by the star instances. The fast algorithms in particular " +
170 "never get their chance. The solver runs with chunkie's defaults, " +
171 "so the fmm2d library that mip installs alongside it accelerates " +
172 "the evaluation, but with some 300 evaluation points there is " +
173 "little there to accelerate: it is worth 1.2 times at the top of " +
174 "the flower-15 sweep and nothing below. The two routes that would " +
175 "replace the dense assembly and factorization, a chunkerflam fast " +
176 "direct solve or GMRES on an FMM matvec, both break even only past " +
177 "about 4000 boundary points, which on this problem is beyond where " +
178 "the error has already stopped improving. square-corners exercises " +
179 "part of it, and is one of the two instances where chunkie leads " +
180 "the other integral-equation solver: its corrected evaluation " +
181 "handles the " +
182 "targets inside the corners, so what limits it is resolving a " +
183 "corner of radius 0.014 with uniform panels rather than the " +
184 "proximity of the targets. It reaches 2e-8 in 0.6 s where " +
185 "nystrom-dlp-mat needs 0.85 s for 7e-9 and 0.23 s to manage only " +
186 "1e-4. Note that both are beaten there by mfs, whose singularities " +
187 "lie outside the domain and which therefore has no near-field problem " +
188 "at all. The other instance, and the clearest case for the toolbox, " +
189 "is star-nearfield. Its domain and data are star-hard's, so the " +
190 "equation is identical and only the targets move, to within 0.005 " +
191 "of the boundary; what is measured is the corrected near-field " +
192 "evaluation by itself. chunkie loses nothing there: 1.8e-11 at 64 " +
193 "panels in 0.11 s, against 2.3e-11 at 48 panels in 0.05 s on " +
194 "star-hard, so the near targets cost it a third more panels and " +
195 "about twice the time, and no accuracy. nystrom-dlp-mat, the same " +
196 "integral equation with an uncorrected evaluation, gives 1.5e-10 on " +
197 "star-hard in 0.017 s and 1.5e-1 here at those same 768 nodes, and " +
198 "needs 4096 nodes and 0.86 s to bring the closest target to 6.7e-6: " +
199 "eight times chunkie's time for five orders less accuracy. mfs-mat, " +
200 "which as on square-corners has no near field to correct, is " +
201 "stopped instead by its own conditioning at 1.7e-6, and is the " +
202 "cheapest route to that accuracy (0.017 s against chunkie's " +
203 "0.065 s for 2.4e-6). Past 1e-6, though, chunkie is the only one of " +
204 "the three that goes anywhere at all.",
205 version: "3.0.0",
206 backend: "cpu",
207 runtime: "matlab",
208 sweepN: [2, 3, 4, 6, 8, 12, 16, 24, 32, 48],
209 // Two panels cannot see a 15-lobe boundary at all, and the sweep has
210 // to run out to 192 panels before the quadrature tolerance caps it.
211 sweepNByInstance: {
212 "flower-15": [8, 12, 16, 24, 32, 48, 64, 96, 128, 192],
213 // Uniform panels have to get down to the corner radius of 0.014.
214 "square-corners": [8, 12, 16, 24, 32, 48, 64, 96, 128, 192, 256],
215 // Two panels past the standard list: on star-hard the quadrature
216 // tolerance caps the error by n = 48, and the near-boundary targets
217 // of star-nearfield take a little more resolution to reach the same
218 // cap.
219 "star-nearfield": [2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96],
220 },
221 },
222 {
223 id: "mfs-mat",
224 name: "Method of fundamental solutions (MATLAB)",
225 description:
226 "The mfs solver file, unchanged, executed by real MATLAB instead of " +
227 "numbl. The method, the resolution sweep, and the source file are the " +
228 "same, so the pair of curves measures the runtime rather than the " +
229 "discretization. Where the method converges, the two agree to the " +
230 "digits reported; in the conditioning-limited regime of star-hard " +
231 "and star-nearfield they do not, since there the error is set by " +
232 "rounding in a badly " +
233 "conditioned solve and the two linear-algebra libraries round " +
234 "differently. Runs from the command line only, which invokes " +
235 "matlab -batch.",
236 version: "1.0.0",
237 backend: "cpu",
238 runtime: "matlab",
239 sweepN: [8, 12, 16, 24, 32, 48, 64, 96, 128, 192, 256, 384, 512, 768],
240 sourceDir: "mfs",
241 },
242 {
243 id: "nystrom-dlp-mat",
244 name: "Nystrom double-layer BIE (MATLAB)",
245 description:
246 "The nystrom-dlp solver file, unchanged, executed by real MATLAB " +
247 "instead of numbl, with the same resolution sweep except on " +
248 "square-corners and star-nearfield, where being some fifteen times " +
249 "faster lets it follow the near-field targets out to 4096 nodes, " +
250 "past where a browser sweep would stay usable. Unlike " +
251 "chunkie-dlp, which is a different discretization of the same " +
252 "integral equation, nothing here changes the numerics: the systems " +
253 "are well conditioned on every instance and the reported errors " +
254 "reproduce those of nystrom-dlp, so what remains between the two " +
255 "curves is the cost of the runtime. Runs from the command line only, " +
256 "which invokes matlab -batch.",
257 version: "1.0.0",
258 backend: "cpu",
259 runtime: "matlab",
260 sweepN: [16, 24, 32, 48, 64, 96, 128, 192, 256, 384, 512, 768],
261 sweepNByInstance: {
262 "flower-15": [32, 48, 64, 96, 128, 192, 256, 384, 512, 768, 1024, 1536],
263 // Real MATLAB is fast enough to follow the corner targets all the
264 // way down, which the numbl twin's list stops short of.
265 "square-corners": [
266 64, 96, 128, 192, 256, 384, 512, 768, 1024, 1536, 2048, 3072, 4096,
267 ],
268 "star-nearfield": [
269 64, 96, 128, 192, 256, 384, 512, 768, 1024, 1536, 2048, 3072, 4096,
270 ],
271 },
272 sourceDir: "nystrom-dlp",
273 },
274];
276export function getSolver(id: string): SolverManifest {
277 const s = SOLVERS.find((x) => x.id === id);
278 if (!s) throw new Error(`Unknown solver: ${id}`);
279 return s;
280}