qualia_core_db/solvers/calculus/
differential.rs1use 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
13pub 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
46pub 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
66pub 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
94pub 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
103pub 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 pub const fn constant(value: f64) -> Self {
122 Self {
123 value,
124 derivative: [0.0; N],
125 }
126 }
127
128 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 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 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 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 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
186pub 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
247pub 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}