10#include "evolver_erk.h"
24void evolver_erk_run(EvolverDerivs derivs,
29 const EvolverOptions& options) {
30 const double tolerance = options.rtol;
31 const int* used_in_output = options.used_in_output;
32 const double* x_sampling = options.x_sampling;
33 const int x_size = options.x_sampling_size;
34 const EvolverOutput
output = options.output.value();
35 const auto& print_variables = options.print_variables;
41 const ErkControllerConfig cfg = options.erk.value_or(ErkControllerConfig{});
51 class_test(x_sampling ==
nullptr,
"%s requires a non-null x_sampling array", Tab::kName);
52 class_test(tolerance <= 0., "%s requires tolerance > 0 (got %e)
", Tab::kName, tolerance);
54 /* Counters are local to this call, so they need no synchronisation -- the
55 relaxed atomics they replace cost a handful of operations per STEP, which
56 was enough that the profiling binary had an environment variable to switch
57 them off before timing. Null means "not collecting
". */
58 EvolverStats counters;
59 ErkHistograms* const histograms = options.histograms;
61 const int neq = y_size;
62 const double rtol = tolerance;
63 const double abstol = options.abstol;
64 const double threshold = abstol / rtol;
65 const double pow_grow = 1.0 / Tab::kOrder;
66 constexpr int s = Tab::kStages;
67 constexpr int deg = Tab::kDenseDeg;
69 /* The derivative at the right end of an accepted step. FSAL pairs already have
70 it as the last stage; otherwise it costs one extra evaluation, which also
71 supplies the next step's k0. */
72 constexpr int idx_end = Tab::kFsal ? (s - 1) : s;
73 constexpr int k_rows = Tab::kFsal ? s : (s + 1);
75 std::vector<double> ynew(neq);
76 std::vector<double> ytemp(neq);
77 std::vector<double> err(neq);
78 std::vector<double> yinterp(neq);
79 std::vector<double> dyinterp(neq);
80 std::vector<double> ki(static_cast<size_t>(k_rows) * neq);
83 double thpow[deg + 1];
85 /* History for the quintic Hermite interpolant: the value and the derivative at
86 the END of the step before this one. Allocated only when that interpolant is
87 selected -- it is two more vectors of the state size per workspace. */
88 const bool want_hermite = (cfg.interpolant == ErkInterpolant::hermite3);
89 std::vector<double> y_prev;
90 std::vector<double> f_prev;
92 bool have_prev = false;
100 /* initialise k0 = f(t, y) */
101 derivs(t, y, ki.data());
102 ++counters.derivs_evaluations;
104 const double hmax = fabs(x_end - x_ini) / 10.0;
107 absh = std::min(hmax, fabs(x_sampling[1] - x_sampling[0]));
116 /* initial step from derivative scale */
118 for (int k = 0; k < neq; k++) {
119 double maxtmp = std::max(fabs(y[k]), threshold);
120 rh = std::max(rh, fabs(ki[k]) / maxtmp);
122 rh /= cfg.safety * pow(rtol, pow_grow);
123 if (absh * rh > 1.0) {
127 const int tdir = (x_end > x_ini) ? 1 : -1;
128 double hnew = absh * tdir;
129 bool nofailed = true;
131 /* PI memory: the previous ACCEPTED step's error ratio. Hairer's DOPRI5 seeds
132 this at 1e-4 so the first steps are not throttled by an absent history. */
133 double ratio_old = 1e-4;
134 const double alpha_pi = pow_grow - 0.75 * cfg.pi_beta;
137 if ((t - x_end) * tdir < 0.0) {
138 for (idx = 0; (idx < x_size) && ((x_sampling[idx] - t) * tdir < 0.0); idx++) {
143 const bool step_to_output = (cfg.output_stepping == ErkOutputStepping::exact);
145 while ((t - x_end) * tdir < 0.0) {
147 const double hmin = 100.0 * DBL_MIN * fabs(t);
148 class_test(fabs(h) < hmin,
149 "%s: step size %e fell below minimum %e at x=%e
",
154 if (fabs(h) > 0.9 * fabs(x_end - t)) {
158 /* In `exact` output stepping the step is truncated so it ends on the next
159 sampling point. `clamped` records that the length was imposed rather than
160 chosen: the controller must then NOT read its own proposal back from this
161 step, because a truncated step has a smaller error for reasons that say
162 nothing about how large the next step may be. */
163 bool clamped = false;
164 double t_clamped = 0.0;
165 if (step_to_output && idx < x_size) {
166 const double dt_out = (x_sampling[idx] - t) * tdir;
167 /* `<=` and not `<`: when the step already ends on the point, t + h still
168 only lands within a rounding of it, which is enough to miss the equality
169 test at emission and push an exactly-known state through the interpolant. */
170 if (dt_out > 0.0 && dt_out <= fabs(h)) {
173 t_clamped = x_sampling[idx];
177 /* stage 0 (FSAL: ki[0..neq) already holds k0) */
178 for (int k = 0; k < neq; k++) {
179 ynew[k] = y[k] + h * Tab::b[0] * ki[k];
180 err[k] = h * Tab::e[0] * ki[k];
182 for (int i = 1; i < s; i++) {
183 for (int k = 0; k < neq; k++) {
186 for (int j = 0; j < i; j++) {
187 const double aij = Tab::A[i * s + j];
188 for (int k = 0; k < neq; k++) {
189 ytemp[k] += h * aij * ki[j * neq + k];
192 derivs(t + Tab::c[i] * h, ytemp.data(), ki.data() + i * neq);
193 ++counters.derivs_evaluations;
194 for (int k = 0; k < neq; k++) {
195 ynew[k] += h * Tab::b[i] * ki[i * neq + k];
196 err[k] += h * Tab::e[i] * ki[i * neq + k];
200 /* The non-finite flag is accumulated INSIDE the error reduction, not tested on
201 errmax afterwards, because the reduction cannot carry a NaN out:
202 `errtemp > errmax` is FALSE for NaN, so a NaN component leaves errmax at 0 and
203 the step is ACCEPTED -- h then grows and the run completes, silently, with a
204 poisoned state. Inf behaves differently (inf > x is true), which is why the
205 observed decaying-NCDM failure hung on rejection instead of returning garbage.
206 Both modes have to be caught, so the test is per component. */
209 for (int k = 0; k < neq; k++) {
210 double errtemp = fabs(err[k] / std::max(threshold, fabs(ynew[k])));
211 nonfinite |= static_cast<int>(IsNonFinite(ynew[k]) || IsNonFinite(err[k]));
212 errmax = std::max(errmax, errtemp);
214 /* `errmax` stays the quantity reported in diagnostics; `errnorm` is what the
215 controller acts on. They coincide unless the RMS norm is selected, which
216 is a second reduction rather than a modification of the first so that the
217 max-norm path keeps its exact historical arithmetic. */
218 double errnorm = errmax;
219 if (cfg.norm == ErkErrorNorm::rms_norm) {
221 for (int k = 0; k < neq; k++) {
222 const double e_k = err[k] / std::max(threshold, fabs(ynew[k]));
225 errnorm = sqrt(acc / neq);
228 /* A non-finite state must ABORT, not be handed back to the step controller. The
229 O(neq) search for the offending index runs only on the failure path.
231 On the Inf path the run does not stop, it GRINDS: errmax > rtol is taken, the
232 step is rejected, h shrinks, and the only exit is class_test(fabs(h) < hmin)
233 with hmin = 100*DBL_MIN*|x|. h converges ONTO that value without going below
234 it, so the guard never fires. Measured on the decaying-NCDM sector at Gamma=1e8
235 (dr_N_q=30, k=0.5): NaN at x=523.76, then h pinned at 1.1654e-303 with 99.4% of
236 steps rejected, repeating identically -- two multi-hour runs burned on what
237 should have been an immediate error.
239 IsNonFinite is a bit test rather than std::isnan because classpp is built with
240 -ffast-math, under which std::isnan may be folded to false (see nonfinite.h). */
241 if (nonfinite != 0) {
243 for (int k = 0; k < neq; k++) {
244 if (IsNonFinite(ynew[k]) || IsNonFinite(err[k])) {
250 "%s: non-finite state at x=%e (h=%e, errmax=%e): y[%d]=%e, err[%d]=%e. The
"
251 "integration cannot recover -- rejecting and shrinking h only converges onto the
"
252 "step-size floor. Something upstream produced NaN/Inf.
",
263 if (errnorm > rtol) {
264 erk_detail::Record(&counters.steps_rejected, histograms, false, t, errnorm / rtol);
265 if (cfg.kind == ErkControllerKind::legacy) {
266 /* Standard ode45 control: first failure shrinks by the error-proportional
267 factor and marks nofailed; consecutive failures halve. (This corrects a
268 transcription bug in the PhD2024-EBH branch where nofailed was never
269 set, making the halving path dead code.) */
272 hnew = tdir * std::max(hmin,
273 fabs(h) * std::max(cfg.fac_min,
274 cfg.safety * pow(rtol / errnorm, pow_grow)));
277 hnew = tdir * std::max(hmin, 0.5 * fabs(h));
281 double fac = cfg.safety * pow(rtol / errnorm, pow_grow);
282 fac = std::max(cfg.fac_min, std::min(fac, 1.0));
284 fac = std::min(fac, 0.5); /* repeated failures: force a real cut */
287 hnew = tdir * std::max(hmin, fabs(h) * fac);
293 erk_detail::Record(&counters.steps_accepted, histograms, true, t, errnorm / rtol);
296 for (int k = 0; k < neq; k++) {
299 derivs(t + h, ytemp.data(), ki.data() + idx_end * neq);
300 ++counters.derivs_evaluations;
303 if (print_variables.has_value()) {
304 (*print_variables)(t + h, ynew.data(), ki.data() + idx_end * neq);
308 /* keep the controller's own proposal; this step's length was imposed */
309 hnew = tdir * std::max(hmin, fabs(hnew));
311 else if (cfg.kind == ErkControllerKind::legacy) {
314 fabs(h) * std::max(cfg.fac_min, cfg.safety * pow(rtol / errnorm, pow_grow)));
317 const double ratio = errnorm / rtol;
319 if (cfg.kind == ErkControllerKind::pi && ratio > 0.0) {
320 fac = cfg.safety * pow(ratio, -alpha_pi) * pow(ratio_old, cfg.pi_beta);
323 fac = cfg.safety * pow(rtol / errnorm, pow_grow);
325 fac = std::max(cfg.fac_min, std::min(fac, cfg.fac_max));
326 /* Never grow immediately after a rejection: the step that just failed is
327 evidence that the local scale shrank. Measured on LCDM + Mnu this is
328 worth little on its own -- with the growth cap it moves the rejection
329 rate only from 13.3% to 12.1% -- so it is the PI memory term above, not
330 this, that takes rejections down to ~6%. */
332 fac = std::min(fac, 1.0);
334 hnew = tdir * std::max(hmin, fabs(h) * fac);
335 ratio_old = std::max(ratio, 1e-4);
338 /* A truncated step ends ON the sampling point by construction. Recomputing
339 t + h instead would land within a rounding of it, which is enough to miss
340 the equality test below and send an exactly-known state through the
342 const double tnew = clamped ? t_clamped : (t + h);
344 /* emit output at all sampling points within (t, tnew] */
345 for (; (idx < x_size) && ((tnew - x_sampling[idx]) * tdir >= 0.0); idx++) {
346 if (tnew == x_sampling[idx]) {
347 ++counters.exact_points;
348 output(tnew, ynew.data(), ki.data() + idx_end * neq, idx);
351 ++counters.dense_points;
352 const double ti = x_sampling[idx];
353 const double th = (ti - t) / h;
354 /* theta^m, m = 0..deg. Squaring for m = 2 and m = 4 is not an
355 optimisation: it is the association the hand-written Dormand-Prince
356 interpolant used, and keeping it makes this driver reproduce the
357 previous rkdp45 output bit for bit. */
364 thpow[3] = thpow[2] * th;
367 thpow[4] = thpow[2] * thpow[2];
369 for (int m = 5; m <= deg; m++) {
370 thpow[m] = thpow[m - 1] * th;
372 for (int i = 0; i < s; i++) {
375 for (int m = 0; m < deg; m++) {
376 const double r = Tab::R[i * deg + m];
377 vy += r * thpow[m + 1];
378 vd += r * (m + 1) * thpow[m];
383 for (int k = 0; k < neq; k++) {
384 if (used_in_output[k]) {
387 for (int i = 0; i < s; i++) {
388 yinterp[k] += h * bi_vec_y[i] * ki[i * neq + k];
389 dyinterp[k] += bi_vec_dy[i] * ki[i * neq + k];
394 if (want_hermite && have_prev) {
395 /* Quintic Hermite through (t_prev, t, tnew), value and derivative at
396 each. The six basis functions depend only on the node positions and
397 on ti, so they are built once and then applied to every component --
398 the same cost per component as the tableau extension it replaces.
400 h_i(x) = [1 - 2 (x - x_i) L_i'(x_i)] L_i(x)^2
401 hbar_i(x) = (x - x_i) L_i(x)^2
402 with L_i the Lagrange basis of the three nodes. */
403 const double x0 = t_prev;
405 const double x2 = tnew;
406 const double d01 = x0 - x1;
407 const double d02 = x0 - x2;
408 const double d12 = x1 - x2;
409 /* Coincident nodes would make this singular; they cannot occur (each
410 node is a strictly later accepted step end) but a zero-length step
411 would, so fall back rather than divide by it. */
412 if (d01 != 0.0 && d02 != 0.0 && d12 != 0.0) {
413 const double u0 = ti - x0;
414 const double u1 = ti - x1;
415 const double u2 = ti - x2;
416 const double L0 = (u1 * u2) / (d01 * d02);
417 const double L1 = (u0 * u2) / (-d01 * d12);
418 const double L2 = (u0 * u1) / (d02 * d12);
419 /* L_i'(x_i) = sum_{j != i} 1/(x_i - x_j) */
420 const double Lp0 = 1.0 / d01 + 1.0 / d02;
421 const double Lp1 = -1.0 / d01 + 1.0 / d12;
422 const double Lp2 = -1.0 / d02 - 1.0 / d12;
423 /* derivative of L_i at ti, for the interpolant's own derivative */
424 const double dL0 = (u1 + u2) / (d01 * d02);
425 const double dL1 = (u0 + u2) / (-d01 * d12);
426 const double dL2 = (u0 + u1) / (d02 * d12);
428 const double L0s = L0 * L0;
429 const double L1s = L1 * L1;
430 const double L2s = L2 * L2;
431 const double w0 = (1.0 - 2.0 * u0 * Lp0) * L0s;
432 const double w1 = (1.0 - 2.0 * u1 * Lp1) * L1s;
433 const double w2 = (1.0 - 2.0 * u2 * Lp2) * L2s;
434 const double v0 = u0 * L0s;
435 const double v1 = u1 * L1s;
436 const double v2 = u2 * L2s;
437 const double dw0 = -2.0 * Lp0 * L0s + (1.0 - 2.0 * u0 * Lp0) * 2.0 * L0 * dL0;
438 const double dw1 = -2.0 * Lp1 * L1s + (1.0 - 2.0 * u1 * Lp1) * 2.0 * L1 * dL1;
439 const double dw2 = -2.0 * Lp2 * L2s + (1.0 - 2.0 * u2 * Lp2) * 2.0 * L2 * dL2;
440 const double dv0 = L0s + u0 * 2.0 * L0 * dL0;
441 const double dv1 = L1s + u1 * 2.0 * L1 * dL1;
442 const double dv2 = L2s + u2 * 2.0 * L2 * dL2;
444 const double* f1 = ki.data(); /* f at t (FSAL k0) */
445 const double* f2 = ki.data() + idx_end * neq; /* f at tnew */
446 for (int k = 0; k < neq; k++) {
447 if (used_in_output[k]) {
448 yinterp[k] = w0 * y_prev[k] + w1 * y[k] + w2 * ynew[k] + v0 * f_prev[k] +
449 v1 * f1[k] + v2 * f2[k];
450 dyinterp[k] = dw0 * y_prev[k] + dw1 * y[k] + dw2 * ynew[k] + dv0 * f_prev[k] +
451 dv1 * f1[k] + dv2 * f2[k];
456 output(ti, yinterp.data(), dyinterp.data(), idx);
461 /* This step's LEFT end becomes the history for the next step. It must be
462 copied before y and ki are overwritten below -- and only for the
463 components the interpolant can ever be asked about, since this copy runs
464 on every accepted step while the interpolant runs on roughly half of
466 for (int k = 0; k < neq; k++) {
467 if (used_in_output[k]) {
475 for (int k = 0; k < neq; k++) {
477 ki[k] = ki[idx_end * neq + k]; /* FSAL: last stage becomes next k0 */
482 if (options.stats != nullptr) {
483 *options.stats = counters;