tensor4all_core/krylov/cg.rs
1//! Matrix-free conjugate gradients for Hermitian positive-definite operators.
2//!
3//! Derived from KrylovKit.jl's `src/linsolve/cg.jl` at revision
4//! d51fa25adfa4cda5530d8e3d42eedfb288cca447, including residual replacement
5//! and recurrence restart after an unsuccessful true-residual check.
6//! <https://github.com/Jutho/KrylovKit.jl/blob/d51fa25adfa4cda5530d8e3d42eedfb288cca447/src/linsolve/cg.jl>
7//!
8//! Copyright (c) 2017: Jutho. MIT license; see ../../LICENSE-KrylovKit.md.
9
10use super::vector_ops::{
11 finite_norm, normalization_exponent, scale_pow2, scale_real_pow2, true_residual,
12};
13use super::KrylovError;
14use crate::{AnyScalar, TensorVectorSpace};
15use anyhow::Result;
16
17/// Convergence and iteration controls for [`cg`].
18/// Unlike [`super::GmresOptions`], CG needs no restart dimension: it keeps a
19/// fixed number of vectors. Start with the defaults for double precision;
20/// use looser tolerances (for example `rtol = hermitian_tol = 1e-5`) for
21/// single precision.
22///
23/// # Examples
24/// ```
25/// use tensor4all_core::{krylov::{cg, CgOptions}, DynIndex, IdxTensor};
26/// # fn main() -> anyhow::Result<()> {
27/// let b = IdxTensor::from_dense(vec![DynIndex::new_dyn(2)], vec![1.0_f64, 2.0])?;
28/// let options = CgOptions { max_iter: 2, ..CgOptions::default() };
29/// let x0 = IdxTensor::zeros::<f64>(b.external_indices())?;
30/// # use tensor4all_core::TensorIndex;
31/// let result = cg(|x: &IdxTensor| Ok(x.clone()), &b, &x0, &options)?;
32/// assert_eq!(result.solution.to_vec::<f64>()?, vec![1.0, 2.0]);
33/// # Ok(())
34/// # }
35/// ```
36#[derive(Debug, Clone)]
37pub struct CgOptions {
38 /// Maximum completed CG steps; zero only evaluates the initial residual.
39 /// Default: `100`. Increase this when the true residual has not converged.
40 pub max_iter: usize,
41 /// Nonnegative, finite residual tolerance relative to `||b||`.
42 /// Default: `1e-10`. The stopping threshold is `max(atol, rtol * ||b||)`.
43 pub rtol: f64,
44 /// Nonnegative, finite absolute residual tolerance; default: `0.0`.
45 /// Set a positive value when a very small RHS needs an absolute error
46 /// target. With both tolerances zero, only an exact residual passes.
47 pub atol: f64,
48 /// Nonnegative, finite allowance for the imaginary part of the directional
49 /// Rayleigh quotient `q = p^H A p / p^H p`:
50 /// `|Im(q)| <= hermitian_tol * max(1, |q|)`. Default: `1e-10`.
51 /// The absolute floor admits cancellation roundoff, matching the projected
52 /// Hermitian solvers. This checks visited directions, not the full operator,
53 /// and does not relax the positive-definiteness requirement.
54 pub hermitian_tol: f64,
55}
56
57impl Default for CgOptions {
58 fn default() -> Self {
59 Self {
60 max_iter: 100,
61 rtol: 1e-10,
62 atol: 0.0,
63 hermitian_tol: 1e-10,
64 }
65 }
66}
67
68impl CgOptions {
69 /// Validate finite, nonnegative static tolerances without applying an operator.
70 ///
71 /// A zero iteration budget and zero tolerances are valid. The RHS-dependent
72 /// stopping threshold is checked when solving.
73 ///
74 /// # Errors
75 /// Returns [`KrylovError::InvalidOptions`] when a tolerance is negative or
76 /// non-finite.
77 ///
78 /// # Examples
79 /// ```
80 /// use tensor4all_core::krylov::{CgOptions, KrylovError};
81 /// let options = CgOptions { rtol: f64::NAN, ..Default::default() };
82 /// assert!(matches!(options.validate(), Err(KrylovError::InvalidOptions { .. })));
83 /// assert!(CgOptions::default().validate().is_ok());
84 /// ```
85 pub fn validate(&self) -> std::result::Result<(), KrylovError> {
86 for (name, tolerance) in [
87 ("rtol", self.rtol),
88 ("atol", self.atol),
89 ("hermitian_tol", self.hermitian_tol),
90 ] {
91 if !tolerance.is_finite() || tolerance < 0.0 {
92 return Err(KrylovError::InvalidOptions {
93 solver: "cg",
94 reason: format!("{name} must be finite and nonnegative"),
95 });
96 }
97 }
98 Ok(())
99 }
100}
101
102/// Solution and true-residual diagnostics returned by [`cg`].
103/// As with [`super::HermitianLanczosResult`], `residual_norm` is an absolute
104/// norm; [`super::GmresResult`] instead reports a relative norm by default.
105///
106/// # Examples
107/// ```
108/// use tensor4all_core::{krylov::{cg, CgOptions}, DynIndex, IdxTensor, TensorIndex};
109/// # fn main() -> anyhow::Result<()> {
110/// let b = IdxTensor::from_dense(vec![DynIndex::new_dyn(2)], vec![3.0_f64, -1.0])?;
111/// let x0 = IdxTensor::zeros::<f64>(b.external_indices())?;
112/// let result = cg(|x: &IdxTensor| Ok(x.clone()), &b, &x0, &CgOptions::default())?;
113/// assert!(result.converged);
114/// assert_eq!(result.solution.to_vec::<f64>()?, vec![3.0, -1.0]);
115/// assert_eq!(result.residual_norm, 0.0);
116/// # Ok(())
117/// # }
118/// ```
119#[derive(Debug, Clone)]
120pub struct CgResult<T> {
121 /// Approximate solution, including the initial guess's contribution.
122 pub solution: T,
123 /// Number of completed CG steps, bounded by [`CgOptions::max_iter`].
124 pub iterations: usize,
125 /// Absolute true residual norm `||b - A*x||`, also on iteration exhaustion.
126 pub residual_norm: f64,
127 /// Whether the true residual met `max(atol, rtol * ||b||)`.
128 pub converged: bool,
129}
130
131/// Solve `A x = b` with matrix-free conjugate gradients.
132///
133/// # Arguments
134/// * `apply_a` - Fixed linear operator `x -> A*x`, preserving the vector space.
135/// The caller must supply a Hermitian positive-definite operator; checking
136/// visited curvatures cannot certify the full matrix-free operator.
137/// * `b` - Right-hand side, in the same vector space as `x0`.
138/// * `x0` - Initial guess, which may be zero. A zero-norm RHS returns the zero
139/// vector, the exact solution, after the initial residual confirms that `x0`
140/// and `b` share a vector space.
141/// * `options` - Iteration budget and finite, nonnegative tolerances. In doubt,
142/// start with [`CgOptions::default`] for double precision.
143///
144/// # Returns
145/// The approximate solution, completed step count, absolute true residual norm,
146/// and convergence flag. Iteration exhaustion returns `converged = false`.
147/// Working vectors are rescaled by exact powers of two before inner products
148/// to keep CG reductions in range.
149/// The true residual is recomputed before declaring convergence. If the
150/// recursive residual was optimistic, CG restarts from the true residual
151/// within the original iteration budget, following KrylovKit.
152///
153/// Vector and recurrence arithmetic stays in `TensorVectorSpace`/`AnyScalar`
154/// operations. Norm, curvature, and stopping decisions are scalar control-flow
155/// boundaries; this API does not promise a differentiable solve. No dense
156/// operator, preconditioner, or tensor-network truncation is introduced.
157///
158/// # Errors
159/// Returns [`KrylovError::InvalidOptions`] for invalid tolerances or an
160/// overflowing stopping threshold, [`KrylovError::NonHermitian`] for a visited
161/// curvature with an excessive imaginary part,
162/// [`KrylovError::NonPositiveCurvature`] for zero or negative curvature,
163/// [`KrylovError::NumericalBreakdown`] for nonfinite or unusable recurrence
164/// quantities, and [`KrylovError::Operation`] for incompatible vector spaces,
165/// invalid tensor structures, operator errors, or failed tensor operations.
166/// Underlying operation errors retain their source chains; an error returned by
167/// `apply_a`, including a `KrylovError` from a nested solve, is always wrapped in
168/// [`KrylovError::Operation`].
169///
170/// # Examples
171/// ```
172/// use tensor4all_core::{krylov::{cg, CgOptions}, DynIndex, IdxTensor, TensorVectorSpace};
173/// # fn main() -> anyhow::Result<()> {
174/// let i = DynIndex::new_dyn(2);
175/// let b = IdxTensor::from_dense(vec![i.clone()], vec![2.0_f64, 4.0])?;
176/// let x0 = IdxTensor::zeros::<f64>(vec![i])?;
177/// let result = cg(
178/// |x: &IdxTensor| Ok(x.scale(2.0.into())?), &b, &x0, &CgOptions::default(),
179/// )?;
180/// assert!(result.converged);
181/// assert_eq!(result.solution.to_vec::<f64>()?, vec![1.0, 2.0]);
182/// # Ok(())
183/// # }
184/// ```
185pub fn cg<T, F>(
186 apply_a: F,
187 b: &T,
188 x0: &T,
189 options: &CgOptions,
190) -> std::result::Result<CgResult<T>, KrylovError>
191where
192 T: TensorVectorSpace,
193 F: Fn(&T) -> Result<T>,
194{
195 cg_impl(apply_a, b, x0, options).map_err(|source| match source.downcast::<KrylovError>() {
196 Ok(classified) => classified,
197 Err(source) => KrylovError::Operation {
198 solver: "cg",
199 source,
200 },
201 })
202}
203
204fn cg_impl<T, F>(apply_a: F, b: &T, x0: &T, options: &CgOptions) -> Result<CgResult<T>>
205where
206 T: TensorVectorSpace,
207 F: Fn(&T) -> Result<T>,
208{
209 options.validate()?;
210 b.validate()?;
211 x0.validate()?;
212 let b_norm = finite_norm(b, "cg", 0, "right-hand-side norm")?;
213 let threshold = options.atol.max(options.rtol * b_norm);
214 if !threshold.is_finite() {
215 return Err(KrylovError::InvalidOptions {
216 solver: "cg",
217 reason: "rtol * ||b|| must be finite".to_string(),
218 }
219 .into());
220 }
221 // A KrylovError from the callback belongs to the callback, not to this
222 // solver; wrapping it keeps it from being reported as CG's own failure.
223 let apply_a = |x: &T| {
224 apply_a(x).map_err(|source| {
225 anyhow::Error::new(KrylovError::Operation {
226 solver: "cg",
227 source,
228 })
229 })
230 };
231 let mut x = x0.clone();
232 let mut r = true_residual(&apply_a, b, &x)?;
233 let mut residual_norm = finite_norm(&r, "cg", 0, "initial residual norm")?;
234 let mut iterations = 0;
235 if b_norm == 0.0 {
236 return Ok(CgResult {
237 solution: b.scale(AnyScalar::new_real(0.0))?,
238 iterations,
239 residual_norm: 0.0,
240 converged: true,
241 });
242 }
243 if residual_norm <= threshold || options.max_iter == 0 {
244 return Ok(CgResult {
245 solution: x,
246 iterations,
247 residual_norm,
248 converged: residual_norm <= threshold,
249 });
250 }
251 // INVARIANT: r represents the physical residual divided by 2^residual_exponent.
252 // Common power-of-two rescaling preserves the CG recurrence exactly in real
253 // arithmetic, while keeping self-inner-products in the scalar dtype's range.
254 let mut residual_exponent = normalization_exponent(residual_norm);
255 r = scale_pow2(r, -residual_exponent)?;
256 let mut p = r.clone();
257 let mut rho = residual_inner_product(&r, 0)?;
258 for iteration in 1..=options.max_iter {
259 let p_norm = finite_norm(&p, "cg", iteration, "search direction norm")?;
260 if p_norm == 0.0 {
261 return Err(KrylovError::NumericalBreakdown {
262 solver: "cg",
263 iteration,
264 quantity: "search direction norm",
265 }
266 .into());
267 }
268 let direction_exponent = normalization_exponent(p_norm);
269 p = scale_pow2(p, -direction_exponent)?;
270 let ap = apply_a(&p)?;
271 ap.validate()?;
272 let ap_norm = finite_norm(&ap, "cg", iteration, "operator image norm")?;
273 if ap_norm == 0.0 {
274 return Err(KrylovError::NonPositiveCurvature {
275 solver: "cg",
276 iteration,
277 curvature: 0.0,
278 }
279 .into());
280 }
281 let image_exponent = normalization_exponent(ap_norm);
282 let ap = scale_pow2(ap, -image_exponent)?;
283 let curvature = p.inner_product(&ap)?;
284 finite_scalar(&curvature, iteration, "directional curvature")?;
285 let normalized_p_norm = scale_real_pow2(p_norm, -direction_exponent);
286 let rayleigh_imaginary = scale_real_pow2(
287 curvature.imag().abs() / normalized_p_norm.powi(2),
288 image_exponent,
289 );
290 if curvature.imag().abs() > options.hermitian_tol * curvature.abs()
291 && rayleigh_imaginary > options.hermitian_tol
292 {
293 return Err(KrylovError::NonHermitian {
294 solver: "cg",
295 source: anyhow::anyhow!(
296 "directional Rayleigh quotient = {} + {}i at iteration {iteration}",
297 scale_real_pow2(curvature.real() / normalized_p_norm.powi(2), image_exponent),
298 scale_real_pow2(curvature.imag() / normalized_p_norm.powi(2), image_exponent),
299 ),
300 }
301 .into());
302 }
303 if curvature.real() <= 0.0 {
304 return Err(KrylovError::NonPositiveCurvature {
305 solver: "cg",
306 iteration,
307 curvature: scale_real_pow2(curvature.real(), image_exponent),
308 }
309 .into());
310 }
311 // HPD CG coefficients are mathematically real. Use the backend real
312 // projection, preserving scalar metadata instead of extracting f64.
313 let alpha = &rho / curvature.real_part();
314 finite_scalar(&alpha, iteration, "step length")?;
315 // Undo the residual/direction/image scales on vectors, not on scalar
316 // coefficients: a representable update must not need an overflowing ratio.
317 let step = scale_pow2(
318 p.scale(alpha.clone())?,
319 residual_exponent - direction_exponent - image_exponent,
320 )?;
321 x = x.axpby(AnyScalar::new_real(1.0), &step, AnyScalar::new_real(1.0))?;
322 let image = scale_pow2(ap, -direction_exponent)?;
323 r = r.axpby(AnyScalar::new_real(1.0), &image, -alpha)?;
324 iterations = iteration;
325 let working_norm = finite_norm(&r, "cg", iteration, "recursive residual norm")?;
326 residual_norm = scale_real_pow2(working_norm, residual_exponent);
327 if !residual_norm.is_finite() {
328 return Err(KrylovError::NumericalBreakdown {
329 solver: "cg",
330 iteration,
331 quantity: "physical residual norm",
332 }
333 .into());
334 }
335 if residual_norm <= threshold || iteration == options.max_iter {
336 r = true_residual(&apply_a, b, &x)?;
337 residual_norm = finite_norm(&r, "cg", iteration, "true residual norm")?;
338 if residual_norm <= threshold || iteration == options.max_iter {
339 break;
340 }
341 // Replacing r invalidates the old conjugacy recurrence.
342 residual_exponent = normalization_exponent(residual_norm);
343 r = scale_pow2(r, -residual_exponent)?;
344 p = r.clone();
345 rho = residual_inner_product(&r, iteration)?;
346 continue;
347 }
348 let next_exponent = normalization_exponent(working_norm);
349 r = scale_pow2(r, -next_exponent)?;
350 let next_rho = residual_inner_product(&r, iteration)?;
351 let beta = &next_rho / ρ
352 finite_scalar(&beta, iteration, "direction coefficient")?;
353 // If r_new = 2^next_exponent * r_normalized, the usual squared-residual
354 // beta becomes this ratio times 2^(next_exponent + direction_exponent)
355 // in the newly scaled vector space.
356 p = scale_pow2(p, next_exponent + direction_exponent)?;
357 p = r.axpby(AnyScalar::new_real(1.0), &p, beta)?;
358 rho = next_rho;
359 // INVARIANT: the physical residual on this path is finite and positive;
360 // its rescaled exponent stays within the finite f64 range. All exponent
361 // sums/differences above are therefore bounded by a few thousand.
362 residual_exponent += next_exponent;
363 }
364 Ok(CgResult {
365 solution: x,
366 iterations,
367 residual_norm,
368 converged: residual_norm <= threshold,
369 })
370}
371
372fn finite_scalar(value: &AnyScalar, iteration: usize, quantity: &'static str) -> Result<()> {
373 if !value.real().is_finite() || !value.imag().is_finite() {
374 return Err(KrylovError::NumericalBreakdown {
375 solver: "cg",
376 iteration,
377 quantity,
378 }
379 .into());
380 }
381 Ok(())
382}
383
384fn residual_inner_product<T: TensorVectorSpace>(r: &T, iteration: usize) -> Result<AnyScalar> {
385 let rho = r.inner_product(r)?.real_part();
386 finite_scalar(&rho, iteration, "residual inner product")?;
387 if rho.real() <= 0.0 {
388 return Err(KrylovError::NumericalBreakdown {
389 solver: "cg",
390 iteration,
391 quantity: "residual inner product",
392 }
393 .into());
394 }
395 Ok(rho)
396}