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}