Skip to main content

qualia_core_db/solvers/calculus/
differential.rs

1//! Numerical and automatic differential calculus.
2
3use super::analysis::{AnalysisError, Complex64, LinearMap, Vector};
4
5#[repr(C)]
6#[derive(Debug, Clone, Copy, PartialEq)]
7pub struct DerivativeEstimate {
8    pub value: f64,
9    pub absolute_error: f64,
10    pub step: f64,
11}
12
13/// Central-difference derivative with adaptive step refinement until the error estimate converges; returns estimate + error bound.
14pub fn adaptive_central_difference<F>(
15    function: F,
16    x: f64,
17) -> Result<DerivativeEstimate, AnalysisError>
18where
19    F: Fn(f64) -> f64,
20{
21    if !x.is_finite() {
22        return Err(AnalysisError::NonFinite);
23    }
24    let h = f64::EPSILON.cbrt() * (1.0 + x.abs());
25    let coarse = central_difference(&function, x, h)?;
26    let fine = central_difference(&function, x, h * 0.5)?;
27    Ok(DerivativeEstimate {
28        value: fine + (fine - coarse) / 3.0,
29        absolute_error: (fine - coarse).abs() / 3.0,
30        step: h * 0.5,
31    })
32}
33
34fn central_difference<F>(function: &F, x: f64, h: f64) -> Result<f64, AnalysisError>
35where
36    F: Fn(f64) -> f64,
37{
38    let high = function(x + h);
39    let low = function(x - h);
40    if !high.is_finite() || !low.is_finite() {
41        return Err(AnalysisError::InvalidDomain);
42    }
43    Ok((high - low) / (2.0 * h))
44}
45
46/// Complex-step derivative `Im(f(x+ih))/h` — machine-precision accuracy for real-analytic `function`.
47pub fn complex_step_derivative<F>(function: F, x: f64) -> Result<DerivativeEstimate, AnalysisError>
48where
49    F: Fn(Complex64) -> Complex64,
50{
51    if !x.is_finite() {
52        return Err(AnalysisError::NonFinite);
53    }
54    let h = 1e-20;
55    let value = function(Complex64::new(x, h));
56    if !value.re.is_finite() || !value.im.is_finite() {
57        return Err(AnalysisError::InvalidDomain);
58    }
59    Ok(DerivativeEstimate {
60        value: value.im / h,
61        absolute_error: h,
62        step: h,
63    })
64}
65
66/// `M`×`N` Jacobian of `f` by central finite differences per input column,
67/// step `EPSILON^(1/3) · (1+|x_j|)`. `InvalidDomain` on non-finite values.
68pub fn jacobian<const M: usize, const N: usize, F>(
69    function: F,
70    point: Vector<N>,
71) -> Result<LinearMap<M, N>, AnalysisError>
72where
73    F: Fn(Vector<N>) -> Vector<M>,
74{
75    point.validate()?;
76    let mut coefficients = [[0.0; N]; M];
77    for column in 0..N {
78        let h = f64::EPSILON.cbrt() * (1.0 + point.data[column].abs());
79        let mut high = point;
80        let mut low = point;
81        high.data[column] += h;
82        low.data[column] -= h;
83        let high_value = function(high);
84        let low_value = function(low);
85        high_value.validate()?;
86        low_value.validate()?;
87        for row in 0..M {
88            coefficients[row][column] = (high_value.data[row] - low_value.data[row]) / (2.0 * h);
89        }
90    }
91    Ok(LinearMap::new(coefficients))
92}
93
94/// Jacobian-vector product `J · direction` — plain matrix apply on an
95/// already-computed `LinearMap`.
96pub fn jvp<const M: usize, const N: usize>(
97    derivative: &LinearMap<M, N>,
98    direction: Vector<N>,
99) -> Result<Vector<M>, AnalysisError> {
100    derivative.apply(direction)
101}
102
103/// Vector-Jacobian product `Jᵀ · cotangent` — transpose apply on an
104/// already-computed `LinearMap`.
105pub fn vjp<const M: usize, const N: usize>(
106    derivative: &LinearMap<M, N>,
107    cotangent: Vector<M>,
108) -> Result<Vector<N>, AnalysisError> {
109    derivative.transpose().apply(cotangent)
110}
111
112#[repr(C)]
113#[derive(Debug, Clone, Copy, PartialEq)]
114pub struct Dual<const N: usize> {
115    pub value: f64,
116    pub derivative: [f64; N],
117}
118
119impl<const N: usize> Dual<N> {
120    /// `Dual::constant`.
121    pub const fn constant(value: f64) -> Self {
122        Self {
123            value,
124            derivative: [0.0; N],
125        }
126    }
127
128    /// Creates a dual number seeding derivative direction `index` (errors when `index` out of range).
129    pub fn variable(value: f64, index: usize) -> Result<Self, AnalysisError> {
130        if index >= N || !value.is_finite() {
131            return Err(AnalysisError::InvalidDomain);
132        }
133        let mut derivative = [0.0; N];
134        derivative[index] = 1.0;
135        Ok(Self { value, derivative })
136    }
137
138    /// Dual addition — value adds, derivatives add.
139    pub fn add(self, other: Self) -> Self {
140        let mut derivative = [0.0; N];
141        for (index, value) in derivative.iter_mut().enumerate() {
142            *value = self.derivative[index] + other.derivative[index];
143        }
144        Self {
145            value: self.value + other.value,
146            derivative,
147        }
148    }
149
150    /// Dual multiplication — product rule on derivatives.
151    pub fn mul(self, other: Self) -> Self {
152        let mut derivative = [0.0; N];
153        for (index, value) in derivative.iter_mut().enumerate() {
154            *value = self.derivative[index] * other.value + self.value * other.derivative[index];
155        }
156        Self {
157            value: self.value * other.value,
158            derivative,
159        }
160    }
161
162    /// Dual sin — derivative scales by cos(x).
163    pub fn sin(self) -> Self {
164        let scale = self.value.cos();
165        let mut derivative = self.derivative;
166        for value in &mut derivative {
167            *value *= scale;
168        }
169        Self {
170            value: self.value.sin(),
171            derivative,
172        }
173    }
174
175    /// Dual exp — derivative scales by e^x.
176    pub fn exp(self) -> Self {
177        let value = self.value.exp();
178        let mut derivative = self.derivative;
179        for component in &mut derivative {
180            *component *= value;
181        }
182        Self { value, derivative }
183    }
184}
185
186/// Finite-difference `N`×`N` Hessian of `f` at `point`: central difference on
187/// the diagonal, four-point mixed difference off-diagonal, step scaled by
188/// `EPSILON^0.25 · (1+|x_i|)` per dimension. `InvalidDomain` on non-finite
189/// base or any coefficient.
190pub fn hessian<const N: usize, F>(
191    function: F,
192    point: Vector<N>,
193) -> Result<LinearMap<N, N>, AnalysisError>
194where
195    F: Fn(Vector<N>) -> f64,
196{
197    point.validate()?;
198    let mut coefficients = [[0.0; N]; N];
199    let base = function(point);
200    if !base.is_finite() {
201        return Err(AnalysisError::InvalidDomain);
202    }
203    for row in 0..N {
204        let hr = f64::EPSILON.powf(0.25) * (1.0 + point.data[row].abs());
205        for column in row..N {
206            let hc = f64::EPSILON.powf(0.25) * (1.0 + point.data[column].abs());
207            let value = if row == column {
208                let mut high = point;
209                let mut low = point;
210                high.data[row] += hr;
211                low.data[row] -= hr;
212                (function(high) - 2.0 * base + function(low)) / (hr * hr)
213            } else {
214                let mut pp = point;
215                let mut pm = point;
216                let mut mp = point;
217                let mut mm = point;
218                pp.data[row] += hr;
219                pp.data[column] += hc;
220                pm.data[row] += hr;
221                pm.data[column] -= hc;
222                mp.data[row] -= hr;
223                mp.data[column] += hc;
224                mm.data[row] -= hr;
225                mm.data[column] -= hc;
226                (function(pp) - function(pm) - function(mp) + function(mm)) / (4.0 * hr * hc)
227            };
228            if !value.is_finite() {
229                return Err(AnalysisError::InvalidDomain);
230            }
231            coefficients[row][column] = value;
232            coefficients[column][row] = value;
233        }
234    }
235    Ok(LinearMap::new(coefficients))
236}
237
238#[repr(C)]
239#[derive(Debug, Clone, Copy, PartialEq)]
240pub struct NewtonReport<const N: usize> {
241    pub solution: Vector<N>,
242    pub iterations: u32,
243    pub residual_norm: f64,
244    pub step_norm: f64,
245}
246
247/// Damped Newton root-finding: iterates `point ← point − step` solving
248/// `function(point) = 0` for `F: Vector<N> → Vector<N>` (e.g. a gradient),
249/// with a damped step, residual-norm convergence at `tolerance`, and a
250/// `max_iterations` bound. Returns a `NewtonReport` (solution, iterations,
251/// residual/step norms); `InvalidDomain` on non-finite input or zero tolerance.
252pub fn damped_newton<const N: usize, F>(
253    function: F,
254    initial: Vector<N>,
255    tolerance: f64,
256    max_iterations: u32,
257) -> Result<NewtonReport<N>, AnalysisError>
258where
259    F: Fn(Vector<N>) -> Vector<N>,
260{
261    if !tolerance.is_finite() || tolerance <= 0.0 {
262        return Err(AnalysisError::InvalidDomain);
263    }
264    initial.validate()?;
265    let mut point = initial;
266    let mut last_step = 0.0;
267    for iteration in 0..=max_iterations {
268        let residual = function(point);
269        residual.validate()?;
270        let residual_norm = residual.norm()?;
271        if residual_norm <= tolerance {
272            return Ok(NewtonReport {
273                solution: point,
274                iterations: iteration,
275                residual_norm,
276                step_norm: last_step,
277            });
278        }
279        if iteration == max_iterations {
280            return Err(AnalysisError::IterationLimit {
281                residual: residual_norm,
282            });
283        }
284        let derivative = jacobian(&function, point)?;
285        let step = derivative.solve(residual.scale(-1.0)?)?;
286        last_step = step.norm()?;
287
288        let mut damping = 1.0;
289        let mut accepted = false;
290        for _ in 0..20 {
291            let candidate = point.add(step.scale(damping)?);
292            let candidate_norm = function(candidate).norm()?;
293            if candidate_norm < residual_norm {
294                point = candidate;
295                accepted = true;
296                break;
297            }
298            damping *= 0.5;
299        }
300        if !accepted {
301            return Err(AnalysisError::IterationLimit {
302                residual: residual_norm,
303            });
304        }
305    }
306    unreachable!()
307}
308
309#[cfg(test)]
310mod tests {
311    use super::*;
312
313    #[test]
314    fn adaptive_and_complex_step_derivatives_match_analytic_values() {
315        let central = adaptive_central_difference(|x| x.sin(), 0.4).unwrap();
316        assert!((central.value - 0.4_f64.cos()).abs() < 1e-10);
317
318        let complex = complex_step_derivative(|z| z.exp(), 0.4).unwrap();
319        assert!((complex.value - 0.4_f64.exp()).abs() < 1e-14);
320    }
321
322    #[test]
323    fn jvp_vjp_duality_holds() {
324        let derivative = LinearMap::new([[1.0, 2.0], [-3.0, 4.0], [0.5, -2.0]]);
325        let direction = Vector::new([2.0, -1.0]);
326        let cotangent = Vector::new([3.0, 0.25, -4.0]);
327        let left = cotangent.dot(jvp(&derivative, direction).unwrap()).unwrap();
328        let right = vjp(&derivative, cotangent).unwrap().dot(direction).unwrap();
329        assert!((left - right).abs() < 1e-14);
330    }
331
332    #[test]
333    fn forward_dual_gradient_matches_analytic_gradient() {
334        let x = Dual::<2>::variable(2.0, 0).unwrap();
335        let y = Dual::<2>::variable(0.3, 1).unwrap();
336        let value = x.mul(x).add(y.sin());
337        assert!((value.value - (4.0 + 0.3_f64.sin())).abs() < 1e-14);
338        assert!((value.derivative[0] - 4.0).abs() < 1e-14);
339        assert!((value.derivative[1] - 0.3_f64.cos()).abs() < 1e-14);
340    }
341
342    #[test]
343    fn hessian_and_damped_newton_match_quadratic_oracle() {
344        let point = Vector::new([1.2, -0.7]);
345        let matrix = hessian(
346            |x: Vector<2>| {
347                3.0 * x.data[0] * x.data[0]
348                    + 2.0 * x.data[0] * x.data[1]
349                    + 4.0 * x.data[1] * x.data[1]
350            },
351            point,
352        )
353        .unwrap();
354        assert!((matrix.coefficients[0][0] - 6.0).abs() < 1e-6);
355        assert!((matrix.coefficients[0][1] - 2.0).abs() < 1e-6);
356        assert!((matrix.coefficients[1][1] - 8.0).abs() < 1e-6);
357
358        let report = damped_newton(
359            |x: Vector<2>| Vector::new([x.data[0] * x.data[0] - 2.0, x.data[1] - 3.0]),
360            Vector::new([1.0, 0.0]),
361            1e-12,
362            20,
363        )
364        .unwrap();
365        assert!((report.solution.data[0] - 2.0_f64.sqrt()).abs() < 1e-12);
366        assert!((report.solution.data[1] - 3.0).abs() < 1e-12);
367    }
368}