Skip to main content

tpt_sci_ode/
solver.rs

1//! From-scratch ODE integration for `tpt-sci-ode`.
2//!
3//! Four methods are provided, all implemented in-house on top of the in-crate
4//! dense linear algebra (no `diffsol`/`nalgebra`/`faer` in the shipped graph):
5//!
6//! * [`Method::Tsit45`] — explicit Runge–Kutta 5(4) (Dormand–Prince),
7//!   non-stiff.
8//! * [`Method::TrBdf2`] — TR-BDF2 (3-stage ESDIRK form), A-/L-stable, stiff.
9//! * [`Method::Esdirk34`] — 4-stage ESDIRK order 3(4), A-/L-stable, stiff.
10//! * [`Method::Bdf`] — variable-order (1–5) backward differentiation, stiff.
11//!
12//! A shared adaptive-step driver (`integrate`) handles step-size control and
13//! dense output via Hermite interpolation.
14
15use crate::error::OdeError;
16use crate::events::{Direction, Event, EventHit, EventSolution, bisect_root};
17use crate::linalg::{DMat, NEWTON_TOL, RhsFn, Tol, eval, jacobian, sdirk_stage};
18use crate::problem::OdeProblem;
19use crate::sparse::JacobianPattern;
20
21/// Integration method selection for [`OdeProblem::solve`].
22#[derive(Debug, Clone, Copy, PartialEq, Eq)]
23pub enum Method {
24    /// Backward Differentiation Formulae — variable-order (1–5), stiff-capable,
25    /// L-stable. The default for general problems.
26    Bdf,
27    /// Explicit Runge–Kutta 5(4) (Dormand–Prince), non-stiff.
28    Tsit45,
29    /// Trapezoidal-rule BDF2 (SDIRK/ESDIRK family) — stiff-capable, A-/L-stable.
30    TrBdf2,
31    /// Explicit-first-stage singly-diagonally-implicit RK of order 3(4) — stiff-
32    /// capable, A-/L-stable.
33    Esdirk34,
34}
35
36impl Method {
37    /// Exponent `q` of the local error in the step-size controller: the local
38    /// error of one step is `O(h^q)`, so the controller scales `h` by
39    /// `(target / err)^(1/q)`.
40    fn error_order(self, bdf_order: usize) -> f64 {
41        match self {
42            Method::Tsit45 => 5.0,                 // 5(4): local error ~ h^5
43            Method::TrBdf2 => 3.0,                 // trapezoid vs TR-BDF2 difference ~ h^3
44            Method::Esdirk34 => 4.0,               // 3(4): local error ~ h^4
45            Method::Bdf => bdf_order as f64 + 1.0, // BDF-k: LTE ~ h^{k+1}
46        }
47    }
48}
49
50/// Result of a single successful step.
51struct StepResult {
52    /// New time.
53    t: f64,
54    /// New state.
55    y: Vec<f64>,
56    /// Per-component local error estimate (at the new state).
57    err: Vec<f64>,
58    /// Derivative at the end of the step.
59    f_new: Vec<f64>,
60}
61
62/// Attempt one step of the given method; returns `Ok` on success with the new
63/// state and a local error estimate, or `Err` if the nonlinear solve could not
64/// converge (caller should shrink `h` and retry). `bdf_state`, if `Some`, is the
65/// BDF order/history; it is updated in place on success.
66#[allow(clippy::too_many_arguments)]
67fn try_step(
68    method: Method,
69    f: &dyn crate::RhsCallable,
70    t: f64,
71    y: &[f64],
72    h: f64,
73    tol: Tol,
74    jac: Option<&JacobianPattern>,
75    bdf_state: Option<&mut NordsieckState>,
76) -> Result<StepResult, OdeError> {
77    match method {
78        Method::Tsit45 => step_dp54(f, t, y, h),
79        Method::TrBdf2 => step_sdirk2(f, t, y, h, tol, jac),
80        Method::Esdirk34 => step_esdirk34(f, t, y, h, tol, jac),
81        Method::Bdf => step_bdf(
82            f,
83            t,
84            y,
85            h,
86            tol,
87            jac,
88            bdf_state.expect("BDF requires a Nordsieck state"),
89        ),
90    }
91}
92
93/// Adaptive-step driver shared by `solve` and `solve_dense`.
94/// Result of one call to [`integrate`].
95struct Integration {
96    /// Recorded states at the `t_eval` points (empty when no `t_eval` was given).
97    outputs: Vec<Vec<f64>>,
98    /// Time where integration stopped.
99    t_end: f64,
100    /// State at `t_end`.
101    y_end: Vec<f64>,
102    /// Event crossings, in time order.
103    hits: Vec<EventHit>,
104}
105
106fn integrate(
107    prob: &OdeProblem,
108    method: Method,
109    t_final: f64,
110    t_eval: Option<&[f64]>,
111    events: &[Event],
112) -> Result<Integration, OdeError> {
113    let f = &*prob.rhs;
114    let rtol = prob.rtol;
115    let atol = prob.atol;
116    let tol = Tol { rtol, atol };
117
118    let mut t = prob.t0;
119    let mut y = prob.y0.clone();
120    let mut f_cur = eval(f, t, &y)?;
121    let dir = if t_final >= t { 1.0 } else { -1.0 };
122    let span = (t_final - t).abs();
123
124    let h_min = 1e-14_f64.max(span * 1e-15);
125    let h_max = span; // never step past the whole interval at once
126    let max_steps = 100_000usize;
127    let safety = 0.9_f64;
128
129    // Initial step: the caller's `h0` if given, otherwise a heuristic fraction of
130    // the interval. Either way it is clamped to the step limits.
131    let h_init = prob.h0.unwrap_or(span * 1e-2).abs().max(1e-6).min(h_max);
132    let mut h = if dir < 0.0 { -h_init } else { h_init };
133
134    let mut bdf_state = if method == Method::Bdf {
135        let mut ns = NordsieckState::new(prob.nstates());
136        // Initialize at order 1 (backward Euler) using the first step h.
137        ns.initialize(&prob.y0, &f_cur, h);
138        Some(ns)
139    } else {
140        None
141    };
142    // Steps taken at the current order, used to gate BDF order changes.
143    let mut bdf_steps_at_order = 0usize;
144
145    // Output bookkeeping.
146    let mut outputs: Vec<Vec<f64>> = Vec::new();
147    let mut eval_idx = 0usize;
148    if let Some(te) = t_eval {
149        // Every point must lie beyond t0 and each must follow the previous one in
150        // the direction of integration. `!(x > 0)` also rejects NaN.
151        let mut prev = t;
152        for &tev in te {
153            let step = dir * (tev - prev);
154            if step.is_nan() || step <= 0.0 {
155                return Err(OdeError::invalid(
156                    "t_eval entries must be finite, strictly increasing, and beyond t0",
157                ));
158            }
159            prev = tev;
160        }
161    }
162
163    let mut hits: Vec<EventHit> = Vec::new();
164    let mut steps = 0usize;
165    loop {
166        let h_to_final = dir * (t_final - t);
167        if h_to_final <= 0.0 {
168            break;
169        }
170        // When a step is clamped onto a target time, remember the target so the
171        // accepted step can be snapped onto it exactly (see below).
172        let mut snap: Option<f64> = None;
173        if h.abs() > h_to_final {
174            h = dir * h_to_final;
175            snap = Some(t_final);
176        }
177        if let Some(te) = t_eval {
178            if eval_idx < te.len() {
179                let h_to_eval = dir * (te[eval_idx] - t);
180                if h.abs() > h_to_eval {
181                    h = dir * h_to_eval;
182                    snap = Some(te[eval_idx]);
183                }
184            }
185        }
186        if h.abs() < h_min {
187            return Err(OdeError::StepTooSmall { t });
188        }
189
190        let q = method.error_order(bdf_state.as_ref().map(|s| s.order).unwrap_or(1));
191        // Snapshot the BDF history so a *rejected* step (which still mutates the
192        // Nordsieck vector inside `step_bdf`) cannot corrupt the integration.
193        // On rejection we restore this snapshot before retrying.
194        let bdf_snapshot = bdf_state.clone();
195        match try_step(
196            method,
197            f,
198            t,
199            &y,
200            h,
201            tol,
202            prob.jac_pattern.as_ref(),
203            bdf_state.as_mut(),
204        ) {
205            Ok(mut res) => {
206                // `t + h` can land an ulp short of the target, which would leave a
207                // sliver of remaining interval and a step below `h_min`. The step
208                // was sized to end exactly on the target, so take that time as-is.
209                if let Some(target) = snap {
210                    res.t = target;
211                }
212                let err_est = weighted_norm(&res.err, &res.y, rtol, atol);
213                // A step is accepted only if it meets the tolerance. When the step
214                // is already at its minimum, rejection leads to `StepTooSmall` below
215                // rather than a silently inaccurate result.
216                let accept = err_est <= 1.0;
217                if !accept {
218                    // Reject: restore the snapshot, shrink h, and retry without
219                    // advancing. This keeps the BDF history consistent across
220                    // retries (the previous behaviour let rejected steps scramble
221                    // the Nordsieck columns, which eventually produced garbage).
222                    if let (Some(ns), Some(saved)) = (bdf_state.as_mut(), &bdf_snapshot) {
223                        *ns = saved.clone();
224                    }
225                    let mut next = h * safety * 0.2_f64.max(err_est.powf(-1.0 / q));
226                    if dir < 0.0 {
227                        next = -next.abs();
228                    }
229                    if next.abs() < h_min {
230                        return Err(OdeError::StepTooSmall { t });
231                    }
232                    h = next;
233                    continue;
234                }
235
236                // Accept: grow step for next time, record outputs, advance.
237                // Limit step size growth to at most 1.5x per step to prevent instability.
238                //
239                // The step-size controller targets a weighted local error of
240                // ~1.0 for the explicit/SDIRK methods. For BDF we deliberately
241                // target a smaller value (~0.4) so there is headroom to raise
242                // the method order when profitable.
243                let target = if method == Method::Bdf { 0.4 } else { 1.0 };
244                let growth_factor = if err_est < 1e-12 {
245                    1.5_f64
246                } else {
247                    (target / err_est).powf(1.0 / q) * safety
248                }
249                .min(5.0)
250                .min(1.5);
251                let mut next = h * growth_factor;
252                if dir < 0.0 {
253                    next = -next.abs();
254                }
255                next = dir * next.abs().min(h_max);
256
257                // Locate event crossings inside this step. A terminal event
258                // ends the integration at its crossing time.
259                if let Some((te, y_te, f_te)) =
260                    detect_events(events, f, t, &y, &f_cur, &res, &mut hits)?
261                {
262                    let stop = StepResult {
263                        t: te,
264                        y: y_te.clone(),
265                        err: Vec::new(),
266                        f_new: f_te,
267                    };
268                    record_outputs(
269                        t,
270                        &y,
271                        &f_cur,
272                        &stop,
273                        t_eval,
274                        &mut eval_idx,
275                        dir,
276                        &mut outputs,
277                    );
278                    return Ok(Integration {
279                        outputs,
280                        t_end: te,
281                        y_end: y_te,
282                        hits,
283                    });
284                }
285
286                record_outputs(
287                    t,
288                    &y,
289                    &f_cur,
290                    &res,
291                    t_eval,
292                    &mut eval_idx,
293                    dir,
294                    &mut outputs,
295                );
296
297                if let Some(ns) = bdf_state.as_mut() {
298                    // Order control. Variable-order BDF: raise the order when
299                    // the step is comfortably accurate for several steps; lower
300                    // it when the local error is eating the whole budget (the
301                    // higher-order method is not earning its keep on this
302                    // problem / step size).
303                    if ns.order < BDF_MAX_ORDER && err_est < 0.6 {
304                        bdf_steps_at_order += 1;
305                        if bdf_steps_at_order >= 3 {
306                            ns.increase_order();
307                            bdf_steps_at_order = 0;
308                        }
309                    } else if ns.order > 1 && err_est > 0.95 {
310                        ns.decrease_order();
311                        bdf_steps_at_order = 0;
312                    } else {
313                        bdf_steps_at_order = 0;
314                    }
315                    // Rescale the Nordsieck vector to the next step size.
316                    if (ns.h - next).abs() > 1e-14 * next.abs() {
317                        ns.rescale(next);
318                    }
319                }
320
321                t = res.t;
322                y = res.y;
323                f_cur = res.f_new;
324                h = next;
325                steps += 1;
326                if steps > max_steps {
327                    return Err(OdeError::MaxSteps { t_final, max_steps });
328                }
329                if dir * (t_final - t) <= 0.0 {
330                    record_final(t, &y, t_eval, &mut eval_idx, t_final, dir, &mut outputs);
331                    break;
332                }
333            }
334            Err(OdeError::Newton { t: _, residual: _ }) | Err(OdeError::StepTooSmall { t: _ }) => {
335                let contracted = h * 0.5;
336                if contracted.abs() < h_min {
337                    return Err(OdeError::StepTooSmall { t });
338                }
339                h = contracted;
340            }
341            Err(e) => return Err(e),
342        }
343    }
344
345    Ok(Integration {
346        outputs,
347        t_end: t,
348        y_end: y,
349        hits,
350    })
351}
352
353/// A terminal stop: crossing time, state there, and derivative there.
354type StopState = (f64, Vec<f64>, Vec<f64>);
355
356/// Check every event for a sign change across the accepted step `t0 → res.t`.
357///
358/// Each crossing is located by bisection on the step's Hermite interpolant and
359/// appended to `hits` in time order. If a terminal event fires, returns the
360/// crossing time, state and derivative so the caller can stop there; later
361/// crossings in the same step are discarded.
362fn detect_events(
363    events: &[Event],
364    f: &RhsFn<'_>,
365    t0: f64,
366    y0: &[f64],
367    f0: &[f64],
368    res: &StepResult,
369    hits: &mut Vec<EventHit>,
370) -> Result<Option<StopState>, OdeError> {
371    if events.is_empty() {
372        return Ok(None);
373    }
374    let interp = |tau: f64| hermite(t0, y0, f0, res.t, &res.y, &res.f_new, tau);
375
376    let mut found: Vec<(f64, usize, Direction)> = Vec::new();
377    for (idx, ev) in events.iter().enumerate() {
378        let g0 = ev.eval(t0, y0);
379        let g1 = ev.eval(res.t, &res.y);
380        if let Some(dir) = ev.crossing(g0, g1) {
381            let te = bisect_root(t0, g0, res.t, |tau| ev.eval(tau, &interp(tau)));
382            found.push((te, idx, dir));
383        }
384    }
385    // Sort by distance travelled from t0, so simultaneous crossings keep time order.
386    found.sort_by(|a, b| (a.0 - t0).abs().total_cmp(&(b.0 - t0).abs()));
387
388    for (te, idx, dir) in found {
389        let y_te = interp(te);
390        hits.push(EventHit {
391            index: idx,
392            t: te,
393            y: y_te.clone(),
394            direction: dir,
395        });
396        if events[idx].is_terminal() {
397            let f_te = eval(f, te, &y_te)?;
398            return Ok(Some((te, y_te, f_te)));
399        }
400    }
401    Ok(None)
402}
403
404#[allow(clippy::too_many_arguments)]
405fn record_outputs(
406    t_old: f64,
407    y_old: &[f64],
408    f_old: &[f64],
409    res: &StepResult,
410    t_eval: Option<&[f64]>,
411    eval_idx: &mut usize,
412    dir: f64,
413    outputs: &mut Vec<Vec<f64>>,
414) {
415    if let Some(te) = t_eval {
416        while *eval_idx < te.len() && dir * (te[*eval_idx] - t_old) <= dir * (res.t - t_old) {
417            let tev = te[*eval_idx];
418            outputs.push(hermite(t_old, y_old, f_old, res.t, &res.y, &res.f_new, tev));
419            *eval_idx += 1;
420        }
421    }
422}
423
424fn record_final(
425    t: f64,
426    y: &[f64],
427    t_eval: Option<&[f64]>,
428    eval_idx: &mut usize,
429    t_final: f64,
430    dir: f64,
431    outputs: &mut Vec<Vec<f64>>,
432) {
433    if let Some(te) = t_eval {
434        while *eval_idx < te.len() && dir * (te[*eval_idx] - t) <= 0.0 {
435            outputs.push(y.to_vec());
436            *eval_idx += 1;
437        }
438        if *eval_idx < te.len() && (te[*eval_idx] - t_final).abs() < 1e-12 {
439            outputs.push(y.to_vec());
440            *eval_idx += 1;
441        }
442    } else {
443        let _ = (t, t_final);
444    }
445}
446
447/// Cubic Hermite interpolation at `tau ∈ [t0, t1]`.
448fn hermite(t0: f64, y0: &[f64], f0: &[f64], t1: f64, y1: &[f64], f1: &[f64], tau: f64) -> Vec<f64> {
449    let h = t1 - t0;
450    let s = (tau - t0) / h;
451    let s2 = s * s;
452    let s3 = s2 * s;
453    let h00 = 2.0 * s3 - 3.0 * s2 + 1.0;
454    let h10 = s3 - 2.0 * s2 + s;
455    let h01 = -2.0 * s3 + 3.0 * s2;
456    let h11 = s3 - s2;
457    let mut out = vec![0.0; y0.len()];
458    for i in 0..y0.len() {
459        out[i] = h00 * y0[i] + h10 * h * f0[i] + h01 * y1[i] + h11 * h * f1[i];
460    }
461    out
462}
463
464fn weighted_norm(err: &[f64], y: &[f64], rtol: f64, atol: f64) -> f64 {
465    let n = err.len();
466    let mut sum = 0.0;
467    for i in 0..n {
468        let w = atol + rtol * y[i].abs();
469        sum += (err[i] / w).powi(2);
470    }
471    (sum / n as f64).sqrt()
472}
473
474// ---------------------------------------------------------------------------
475// Dormand–Prince RK5(4) — explicit, non-stiff.
476// ---------------------------------------------------------------------------
477
478const DP_C: [f64; 7] = [0.0, 1.0 / 5.0, 3.0 / 10.0, 4.0 / 5.0, 8.0 / 9.0, 1.0, 1.0];
479// Lower-triangular A (row-indexed by stage s, columns 0..s).
480const DP_A: [[f64; 6]; 6] = [
481    [1.0 / 5.0, 0.0, 0.0, 0.0, 0.0, 0.0],
482    [3.0 / 40.0, 9.0 / 40.0, 0.0, 0.0, 0.0, 0.0],
483    [44.0 / 45.0, -56.0 / 15.0, 32.0 / 9.0, 0.0, 0.0, 0.0],
484    [
485        19372.0 / 6561.0,
486        -25360.0 / 2187.0,
487        64448.0 / 6561.0,
488        -212.0 / 729.0,
489        0.0,
490        0.0,
491    ],
492    [
493        9017.0 / 3168.0,
494        -355.0 / 33.0,
495        46732.0 / 5247.0,
496        49.0 / 176.0,
497        -5103.0 / 18656.0,
498        0.0,
499    ],
500    [
501        35.0 / 384.0,
502        0.0,
503        500.0 / 1113.0,
504        125.0 / 192.0,
505        -2187.0 / 6784.0,
506        11.0 / 84.0,
507    ],
508];
509const DP_B: [f64; 7] = [
510    35.0 / 384.0,
511    0.0,
512    500.0 / 1113.0,
513    125.0 / 192.0,
514    -2187.0 / 6784.0,
515    11.0 / 84.0,
516    0.0,
517];
518const DP_BHAT: [f64; 7] = [
519    5179.0 / 57600.0,
520    0.0,
521    7571.0 / 16695.0,
522    393.0 / 640.0,
523    -92097.0 / 339200.0,
524    187.0 / 2100.0,
525    1.0 / 40.0,
526];
527
528fn step_dp54(
529    f: &dyn crate::RhsCallable,
530    t: f64,
531    y: &[f64],
532    h: f64,
533) -> Result<StepResult, OdeError> {
534    let n = y.len();
535    let mut k = vec![vec![0.0; n]; 7];
536    k[0] = eval(f, t, y)?;
537    for s in 1..7 {
538        let mut stage = vec![0.0; n];
539        for i in 0..n {
540            let mut acc = y[i];
541            for col in 0..s {
542                let a = DP_A[s - 1][col];
543                if a != 0.0 {
544                    acc += h * a * k[col][i];
545                }
546            }
547            stage[i] = acc;
548        }
549        k[s] = eval(f, t + h * DP_C[s], &stage)?;
550    }
551    let mut y_new = vec![0.0; n];
552    let mut y_hat = vec![0.0; n];
553    for i in 0..n {
554        let mut acc5 = y[i];
555        let mut acc4 = y[i];
556        for s in 0..7 {
557            acc5 += h * DP_B[s] * k[s][i];
558            acc4 += h * DP_BHAT[s] * k[s][i];
559        }
560        y_new[i] = acc5;
561        y_hat[i] = acc4;
562    }
563    let err = y_new
564        .iter()
565        .zip(&y_hat)
566        .map(|(a, b)| a - b)
567        .collect::<Vec<_>>();
568    let f_new = eval(f, t + h, &y_new)?;
569    Ok(StepResult {
570        t: t + h,
571        y: y_new,
572        err,
573        f_new,
574    })
575}
576
577// ---------------------------------------------------------------------------
578// TR-BDF2 — 3-stage ESDIRK form (explicit first row), A-/L-stable, stiff.
579// Bank et al. (1985). γ = 2 - √2 ≈ 0.585786 is the split point; d = γ/2.
580//
581// Stage 1 (trapezoid over [t, t+γh]): y_s = y + d·h·(k0 + k1), k1 = f(t+γh, y_s).
582// Stage 2 (BDF2 over [t, t+h]):       y₊ = y + h·(w0·k0 + w1·k1 + w2·k2),
583//                                     k2 = f(t+h, y₊).
584// Consistency: row sums equal the abscissae (γ and 1) and the weights satisfy
585// Σw = 1 and w·c = 1/2, so the scheme is second order.
586// ---------------------------------------------------------------------------
587
588const TRBDF2_GAMMA: f64 = 0.585_786_437_626_904_9; // 2 - sqrt(2)
589const TRBDF2_D: f64 = TRBDF2_GAMMA / 2.0;
590const TRBDF2_W0: f64 = 0.353_553_390_593_273_73; // 1 / (2(2 - γ)) = 1/(2√2)
591const TRBDF2_W1: f64 = TRBDF2_W0;
592const TRBDF2_W2: f64 = 0.292_893_218_813_452_5; // (1 - γ) / (2 - γ)
593
594fn step_sdirk2(
595    f: &dyn crate::RhsCallable,
596    t: f64,
597    y: &[f64],
598    h: f64,
599    tol: Tol,
600    jac: Option<&JacobianPattern>,
601) -> Result<StepResult, OdeError> {
602    let n = y.len();
603    let g = TRBDF2_GAMMA;
604    let d = TRBDF2_D;
605    let f_start = eval(f, t, y)?;
606
607    // Stage 1: k1 = f(t + γh, y + d·h·k0 + d·h·k1) — an SDIRK solve with the
608    // explicit part of the trapezoid folded into the base state.
609    let base1: Vec<f64> = y
610        .iter()
611        .zip(&f_start)
612        .map(|(yi, k0i)| yi + d * h * k0i)
613        .collect();
614    let k1 = sdirk_stage(f, t + g * h, &base1, d * h, &f_start, tol, jac)?;
615
616    // Stage 2: y₊ = y + h(w0·k0 + w1·k1) + h·w2·k2, k2 = f(t + h, y₊).
617    let base2: Vec<f64> = (0..n)
618        .map(|i| y[i] + h * (TRBDF2_W0 * f_start[i] + TRBDF2_W1 * k1[i]))
619        .collect();
620    let k2 = sdirk_stage(f, t + h, &base2, TRBDF2_W2 * h, &k1, tol, jac)?;
621
622    let y_new: Vec<f64> = (0..n).map(|i| base2[i] + TRBDF2_W2 * h * k2[i]).collect();
623    // k2 = f(t + h, y_new) by construction, so the derivative at the end of the
624    // step is already available without another RHS evaluation.
625    let f_new = k2;
626
627    // Embedded error: the difference between the TR-BDF2 solution and the full-step
628    // trapezoidal solution y + h/2·(f(t, y) + f(t + h, y_new)). Both are second
629    // order, so their difference is O(h³) locally, which matches the controller
630    // exponent in `Method::error_order`.
631    let err: Vec<f64> = (0..n)
632        .map(|i| y_new[i] - (y[i] + 0.5 * h * (f_start[i] + f_new[i])))
633        .collect();
634    Ok(StepResult {
635        t: t + h,
636        y: y_new,
637        err,
638        f_new,
639    })
640}
641
642// ---------------------------------------------------------------------------
643// ESDIRK34 — 4-stage ESDIRK order 3(4), A-/L-stable, stiff
644// (Kennedy & Carpenter 2003, with B weights normalized to sum to 1).
645// ---------------------------------------------------------------------------
646
647const ESDIRK34_GAMMA: f64 = 0.435_866_521_508_459;
648const ESDIRK34_C2: f64 = 0.871_733_043_016_918; // 2·gamma
649const ESDIRK34_C3: f64 = 0.468_238_744_851_844_4;
650const ESDIRK34_A31: f64 = 0.140_737_774_724_706_2;
651const ESDIRK34_A32: f64 = -0.108_365_551_381_320_8;
652// B weights (order 3, stiffly accurate: the last weight is γ, which equals the
653// final stage's diagonal, so y_{n+1} = Y_4). Solved from the order-1..3 conditions
654// Σb = 1, Σb·c = 1/2, Σb·c² = 1/3, Σ_i b_i Σ_j a_ij c_j = 1/6 with the A-row
655// coefficients above; the residual of every condition is ~1e-17.
656const ESDIRK34_B: [f64; 4] = [
657    0.102_399_400_616_089,
658    -0.376_878_452_267_324,
659    0.838_612_530_188_334,
660    ESDIRK34_GAMMA,
661];
662// Embedded weights (order 4): sum to 1.
663const ESDIRK34_BHAT: [f64; 4] = [
664    0.157_024_897_860_324_95,
665    0.117_330_441_370_438_85,
666    0.616_678_030_392_121_4,
667    0.108_966_630_377_114_75,
668];
669
670fn step_esdirk34(
671    f: &dyn crate::RhsCallable,
672    t: f64,
673    y: &[f64],
674    h: f64,
675    tol: Tol,
676    jac: Option<&JacobianPattern>,
677) -> Result<StepResult, OdeError> {
678    let n = y.len();
679    let g = ESDIRK34_GAMMA;
680    let k0 = eval(f, t, y)?; // explicit first stage
681
682    // Stage 1 (c = 2g): Y1 = y + h·(g·k0 + g·k1).
683    let base1: Vec<f64> = y
684        .iter()
685        .zip(&k0)
686        .map(|(yi, k0i)| yi + h * g * k0i)
687        .collect();
688    let k1 = sdirk_stage(f, t + ESDIRK34_C2 * h, &base1, g * h, &k0, tol, jac)?;
689
690    // Stage 2 (c = c3): Y2 = y + h·(a31·k0 + a32·k1 + g·k2).
691    let base2: Vec<f64> = y
692        .iter()
693        .zip(&k0)
694        .zip(&k1)
695        .map(|((yi, k0i), k1i)| yi + h * (ESDIRK34_A31 * k0i + ESDIRK34_A32 * k1i))
696        .collect();
697    let k2 = sdirk_stage(f, t + ESDIRK34_C3 * h, &base2, g * h, &k1, tol, jac)?;
698
699    // Stage 3 (c = 1): Y3 = y + h·(b0·k0 + b1·k1 + b2·k2 + g·k3).
700    let base3: Vec<f64> = y
701        .iter()
702        .zip(&k0)
703        .zip(&k1)
704        .zip(&k2)
705        .map(|(((yi, k0i), k1i), k2i)| {
706            yi + h * (ESDIRK34_B[0] * k0i + ESDIRK34_B[1] * k1i + ESDIRK34_B[2] * k2i)
707        })
708        .collect();
709    let k3 = sdirk_stage(f, t + h, &base3, g * h, &k2, tol, jac)?;
710
711    let ks = [&k0, &k1, &k2, &k3];
712    let mut y_new = y.to_vec();
713    let mut y_hat = y.to_vec();
714    for i in 0..n {
715        let mut s5 = y[i];
716        let mut s4 = y[i];
717        for j in 0..4 {
718            s5 += h * ESDIRK34_B[j] * ks[j][i];
719            s4 += h * ESDIRK34_BHAT[j] * ks[j][i];
720        }
721        y_new[i] = s5;
722        y_hat[i] = s4;
723    }
724    let err = y_new
725        .iter()
726        .zip(&y_hat)
727        .map(|(a, b)| a - b)
728        .collect::<Vec<_>>();
729    let f_new = eval(f, t + h, &y_new)?;
730    Ok(StepResult {
731        t: t + h,
732        y: y_new,
733        err,
734        f_new,
735    })
736}
737
738// ---------------------------------------------------------------------------
739// BDF — variable-order (1–5) backward differentiation, stiff.
740//
741// Implemented in the Nordsieck (Gear) representation. The Nordsieck vector is
742// stored column-major as `z[col][comp]` for `col = 0..=MAX_ORDER`:
743//   z[0] = y,  z[k] = h^k/k! · y^(k)   (the scaled k-th derivative at the
744//   current time, for k ≥ 1).
745//
746// Each step uses the fixed-leading-coefficient (FLC) BDF corrector (the form
747// used by SUNDIALS/CVODE):
748//   y_c - y_p = h·β0·(f(t, y_c) - ẏ_p),   ẏ_p = z[1]/h,
749// where y_p = Σ_k z[k] is the Taylor predictor and β0 = 1/(1 + 1/2 + … + 1/q).
750// After convergence the vector is corrected with the standard Nordsieck
751// coefficients l_j (derived from the corrector polynomial c(t)), and the local
752// truncation error is estimated from the change in the highest column.
753// ---------------------------------------------------------------------------
754
755const BDF_MAX_ORDER: usize = 5;
756
757// β0 = 1/(1 + 1/2 + … + 1/q) for q = 1..5.
758const BDF_BETA0: [f64; 5] = [1.0, 2.0 / 3.0, 6.0 / 11.0, 12.0 / 25.0, 60.0 / 137.0];
759
760// Nordsieck corrector coefficients l_j for orders q = 1..5.
761// l_j = g^{(j)}(0) / (j!·q!)  with  g(u) = ∏_{i=1}^q (u + i).
762const BDF_L: [[f64; 6]; 5] = [
763    [1.0, 1.0, 0.0, 0.0, 0.0, 0.0],
764    [1.0, 1.5, 0.5, 0.0, 0.0, 0.0],
765    [1.0, 11.0 / 6.0, 1.0, 1.0 / 6.0, 0.0, 0.0],
766    [1.0, 25.0 / 12.0, 35.0 / 24.0, 5.0 / 12.0, 1.0 / 24.0, 0.0],
767    [
768        1.0,
769        137.0 / 60.0,
770        15.0 / 8.0,
771        17.0 / 24.0,
772        1.0 / 8.0,
773        1.0 / 120.0,
774    ],
775];
776
777// Delta-to-local-error scaling factors r_q = C_{q+1} / (C_{q+1} + 1/(q+1)!)
778// for orders q = 1..5, used to turn the corrector correction delta into an
779// absolute local-error estimate.
780const BDF_R: [f64; 5] = [0.5, 5.0 / 7.0, 0.9, 251.0 / 257.0, 238.0 / 239.0];
781
782/// Binomial coefficient C(n, k) for small n (n ≤ 10).
783fn binom(n: usize, k: usize) -> f64 {
784    if k > n {
785        return 0.0;
786    }
787    if k == 0 || k == n {
788        return 1.0;
789    }
790    let mut res = 1.0;
791    for i in 0..k {
792        res = res * (n - i) as f64 / (i + 1) as f64;
793    }
794    res
795}
796
797/// Nordsieck vector state for the variable-order (1–5) BDF.
798#[derive(Clone)]
799struct NordsieckState {
800    /// `z[col][comp]`: column-major Nordsieck array, `col = 0..=BDF_MAX_ORDER`.
801    z: Vec<Vec<f64>>,
802    /// Current method order (1–5).
803    order: usize,
804    /// Current step size (the array is scaled to this h).
805    h: f64,
806}
807
808impl NordsieckState {
809    fn new(n: usize) -> Self {
810        let z = vec![vec![0.0; n]; BDF_MAX_ORDER + 1];
811        NordsieckState {
812            z,
813            order: 1,
814            h: 0.0,
815        }
816    }
817
818    fn n(&self) -> usize {
819        self.z[0].len()
820    }
821
822    /// Seed the state at `t0` from the initial `y0`/`f0` and first step `h`.
823    fn initialize(&mut self, y0: &[f64], f0: &[f64], h: f64) {
824        self.order = 1;
825        self.h = h;
826        let n = y0.len();
827        for i in 0..n {
828            self.z[0][i] = y0[i];
829            self.z[1][i] = h * f0[i];
830            for c in 2..=BDF_MAX_ORDER {
831                self.z[c][i] = 0.0;
832            }
833        }
834    }
835
836    /// Rescale the Nordsieck columns for a step-size change `h_new`
837    /// (column `c` scales by `(h_new/h)^c`).
838    fn rescale(&mut self, h_new: f64) {
839        if self.h == 0.0 {
840            self.h = h_new;
841            return;
842        }
843        let ratio = h_new / self.h;
844        if (ratio - 1.0).abs() < 1e-14 {
845            return;
846        }
847        let n = self.n();
848        for c in 0..=BDF_MAX_ORDER {
849            let s = ratio.powi(c as i32);
850            for i in 0..n {
851                self.z[c][i] *= s;
852            }
853        }
854        self.h = h_new;
855    }
856
857    /// Predictor: binomial shift of the stored array to the next point,
858    /// `z_pred[j] = Σ_{m=0}^{order-j} C(j+m, j)·z[j+m]`.
859    #[allow(clippy::needless_range_loop)]
860    fn predict(&self) -> Vec<Vec<f64>> {
861        let n = self.n();
862        let order = self.order;
863        let mut zp = vec![vec![0.0; n]; BDF_MAX_ORDER + 1];
864        for j in 0..=order {
865            for i in 0..n {
866                let mut s = 0.0;
867                for m in 0..=(order - j) {
868                    s += binom(j + m, j) * self.z[j + m][i];
869                }
870                zp[j][i] = s;
871            }
872        }
873        zp
874    }
875
876    fn increase_order(&mut self) {
877        if self.order < BDF_MAX_ORDER {
878            self.order += 1;
879        }
880    }
881
882    fn decrease_order(&mut self) {
883        if self.order > 1 {
884            self.order -= 1;
885        }
886    }
887}
888
889#[allow(clippy::needless_range_loop)]
890fn step_bdf(
891    f: &dyn crate::RhsCallable,
892    t: f64,
893    _y: &[f64],
894    h: f64,
895    tol: Tol,
896    jac: Option<&JacobianPattern>,
897    state: &mut NordsieckState,
898) -> Result<StepResult, OdeError> {
899    let n = state.n();
900
901    // Rescale if the requested step differs from the stored one (e.g. a
902    // rejected step shrank h, or the driver advanced h for the next step).
903    if (state.h - h).abs() > 1e-14 * h.abs() {
904        state.rescale(h);
905    }
906
907    let order = state.order;
908    let beta0 = BDF_BETA0[order - 1];
909    let gamma = h * beta0;
910
911    let z_pred = state.predict();
912    let y_p = &z_pred[0];
913    // Predicted derivative from the Nordsieck array: ẏ_p = z[1]/h.
914    let ydot_p: Vec<f64> = z_pred[1].iter().map(|v| v / h).collect();
915
916    // Highest column at the start of the step, for the LTE estimate.
917    let last_col_prev = state.z[order].clone();
918
919    // Newton corrector for the FLC-BDF equation
920    //   y_c - y_p - γ·(f(t+h, y_c) - ẏ_p) = 0,  γ = h·β0.
921    // Convergence is tested on the weighted norm of the Newton correction, so
922    // the test scales with the tolerances rather than with absolute magnitudes.
923    let mut y_cur = y_p.clone();
924    let mut fk = eval(f, t + h, &y_cur)?;
925    let mut corr = f64::INFINITY;
926    let mut converged = false;
927    for _iter in 0..30 {
928        let residual: Vec<f64> = (0..n)
929            .map(|i| y_cur[i] - y_p[i] - gamma * (fk[i] - ydot_p[i]))
930            .collect();
931        let rnorm = residual.iter().map(|r| r * r).sum::<f64>().sqrt();
932        // Large systems route the Newton linear solve through the sparse
933        // CSR/LU path (`sparse` module): the finite-difference Jacobian is
934        // built directly in compressed storage and never materialised densely.
935        let delta = if n >= crate::sparse::SPARSE_LU_MIN_N {
936            let jmat = match jac {
937                Some(pattern) => crate::sparse::CsrMatrix::jacobian_colored(
938                    |t, y, dydt| f.call(t, y, dydt),
939                    t + h,
940                    &y_cur,
941                    &fk,
942                    pattern,
943                )?,
944                None => crate::sparse::CsrMatrix::jacobian(
945                    |t, y, dydt| f.call(t, y, dydt),
946                    t + h,
947                    &y_cur,
948                    &fk,
949                    None,
950                )?,
951            };
952            let a = jmat.scaled_identity_minus_scaled(gamma);
953            a.sparse_solve(&residual).ok_or(OdeError::Newton {
954                t: t + h,
955                residual: rnorm,
956            })?
957        } else {
958            let jac = jacobian(f, t + h, &y_cur, &fk)?;
959            let mut a = DMat::new(n, n);
960            for i in 0..n {
961                for j in 0..n {
962                    a.set(i, j, if i == j { 1.0 } else { 0.0 } - gamma * jac.get(i, j));
963                }
964            }
965            a.solve(&residual).ok_or(OdeError::Newton {
966                t: t + h,
967                residual: rnorm,
968            })?
969        };
970        for i in 0..n {
971            y_cur[i] -= delta[i];
972        }
973        corr = tol.wrms(&delta, &y_cur);
974        fk = eval(f, t + h, &y_cur)?;
975        if corr < NEWTON_TOL {
976            converged = true;
977            break;
978        }
979    }
980    if !converged {
981        return Err(OdeError::Newton {
982            t: t + h,
983            residual: corr,
984        });
985    }
986    let f_new = fk;
987
988    // Correction relative to the predicted solution.
989    let delta: Vec<f64> = y_cur.iter().zip(y_p).map(|(a, b)| a - b).collect();
990
991    // Nordsieck corrector update:  z_new[j] = z_pred[j] + l_j·δ.
992    let l = &BDF_L[order - 1];
993    for j in 0..=order {
994        for i in 0..n {
995            state.z[j][i] = z_pred[j][i] + l[j] * delta[i];
996        }
997    }
998
999    // Local truncation error from the correction delta. The BDF corrector of
1000    // order q satisfies (predictor error) = (corrector error) + delta, with
1001    // predictor error = h^(q+1)/(q+1)!*y^(q+1) and corrector (local) error
1002    // LTE = C_{q+1}*h^(q+1)*y^(q+1). Hence LTE = r_q*delta, where
1003    //   r_q = C_{q+1} / (C_{q+1} + 1/(q+1)!).
1004    // This estimate is reliable even when the higher Nordsieck columns are
1005    // still being populated after an order change.
1006    let r = BDF_R[order - 1];
1007    let mut err = vec![0.0; n];
1008    for i in 0..n {
1009        err[i] = r * delta[i];
1010    }
1011
1012    // Proactively bootstrap the NEXT Nordsieck column from the within-step
1013    // finite difference of the current highest column (at a single, consistent
1014    // step size), so it is ready when the order is later raised.
1015    if order < BDF_MAX_ORDER {
1016        let denom = (order as f64) + 1.0;
1017        for i in 0..n {
1018            state.z[order + 1][i] = (state.z[order][i] - last_col_prev[i]) / denom;
1019        }
1020    }
1021
1022    Ok(StepResult {
1023        t: t + h,
1024        y: y_cur,
1025        err,
1026        f_new,
1027    })
1028}
1029
1030impl OdeProblem {
1031    /// Integrate the problem from its initial time to `t_final` and return the
1032    /// state vector at `t_final`, using the requested `method`.
1033    ///
1034    /// # Errors
1035    ///
1036    /// Returns [`OdeError`] if the integration fails (non-convergent Newton
1037    /// step, collapsed step size, or step budget exceeded).
1038    pub fn solve(&self, method: Method, t_final: f64) -> Result<Vec<f64>, OdeError> {
1039        Ok(integrate(self, method, t_final, None, &[])?.y_end)
1040    }
1041
1042    /// Integrate to `t_final` while watching the given [`Event`]s.
1043    ///
1044    /// Every sign change of an event function is reported in
1045    /// [`EventSolution::hits`]. Each crossing is bracketed by the accepted step
1046    /// and located by bisection on that step's cubic-Hermite dense output, so its
1047    /// accuracy is that of the interpolant (roughly `O(h⁴)` per step), not
1048    /// round-off. If a terminal event fires, integration stops at its
1049    /// crossing and [`EventSolution::t_end`] is that time; otherwise `t_end` is
1050    /// `t_final`.
1051    ///
1052    /// # Errors
1053    ///
1054    /// Returns [`OdeError`] if the integration fails (see [`OdeProblem::solve`]).
1055    ///
1056    /// # Examples
1057    ///
1058    /// A bouncing ball that hits the floor at `t = √(2h/g)`:
1059    ///
1060    /// ```
1061    /// use tpt_sci_ode::{Method, OdeProblem};
1062    /// use tpt_sci_ode::events::{Direction, Event};
1063    ///
1064    /// // State [height, velocity]; g = 9.81.
1065    /// let prob = OdeProblem::new(
1066    ///     |_t, y, dy| {
1067    ///         dy[0] = y[1];
1068    ///         dy[1] = -9.81;
1069    ///     },
1070    ///     vec![10.0, 0.0],
1071    ///     0.0,
1072    /// )
1073    /// .unwrap();
1074    /// let floor = Event::new(|_t, y| y[0])
1075    ///     .direction(Direction::Falling)
1076    ///     .terminal();
1077    /// let sol = prob.solve_events(Method::Tsit45, 10.0, &[floor]).unwrap();
1078    /// let expected = (2.0 * 10.0 / 9.81f64).sqrt();
1079    /// assert!((sol.t_end - expected).abs() < 1e-6);
1080    /// ```
1081    pub fn solve_events(
1082        &self,
1083        method: Method,
1084        t_final: f64,
1085        events: &[Event],
1086    ) -> Result<EventSolution, OdeError> {
1087        let run = integrate(self, method, t_final, None, events)?;
1088        Ok(EventSolution {
1089            t_end: run.t_end,
1090            y_end: run.y_end,
1091            hits: run.hits,
1092        })
1093    }
1094
1095    /// Integrate at each time in `t_eval` (each strictly increasing and beyond
1096    /// `t0`) and return one state vector per evaluation time.
1097    ///
1098    /// The integrator lands exactly on each `t_eval` point and interpolates with
1099    /// a cubic Hermite polynomial between accepted steps, so output is exact at
1100    /// the requested times.
1101    ///
1102    /// # Errors
1103    ///
1104    /// Returns [`OdeError`] if the integration fails (see [`OdeProblem::solve`]).
1105    ///
1106    /// # Panics
1107    ///
1108    /// Panics if `t_eval` is non-empty but its last element cannot be read
1109    /// (only reachable if `t_eval` is mutated concurrently); for a normal
1110    /// non-empty slice this is unreachable.
1111    pub fn solve_dense(&self, method: Method, t_eval: &[f64]) -> Result<Vec<Vec<f64>>, OdeError> {
1112        if t_eval.is_empty() {
1113            return Ok(Vec::new());
1114        }
1115        Ok(integrate(self, method, *t_eval.last().unwrap(), Some(t_eval), &[])?.outputs)
1116    }
1117}