Skip to main content

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 / &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}