Skip to main content

tensor4all_core/krylov/
bicgstab.rs

1//! Matrix-free BiCGSTAB for general real and complex linear operators.
2//!
3//! Derived from KrylovKit.jl's `src/linsolve/bicgstab.jl` at revision
4//! d51fa25adfa4cda5530d8e3d42eedfb288cca447.
5//! <https://github.com/Jutho/KrylovKit.jl/blob/d51fa25adfa4cda5530d8e3d42eedfb288cca447/src/linsolve/bicgstab.jl>
6//!
7//! Copyright (c) 2017: Jutho. MIT license; see ../../LICENSE-KrylovKit.md.
8
9use super::vector_ops::{
10    finite_norm, normalization_exponent, scale_pow2, scale_real_pow2, true_residual,
11};
12use super::KrylovError;
13use crate::{AnyScalar, TensorVectorSpace};
14use anyhow::Result;
15
16/// Convergence controls for [`bicgstab`], which retains a fixed number of vectors.
17/// Start with the defaults for double precision and use `rtol = 1e-5` for
18/// single precision.
19///
20/// # Examples
21/// ```
22/// use tensor4all_core::{krylov::{bicgstab, BiCgStabOptions}, DynIndex, IdxTensor};
23/// # fn main() -> anyhow::Result<()> {
24/// let i = DynIndex::new_dyn(2);
25/// let b = IdxTensor::from_dense(vec![i.clone()], vec![1.0_f64, -2.0])?;
26/// let x0 = IdxTensor::zeros::<f64>(vec![i])?;
27/// let options = BiCgStabOptions { max_iter: 1, ..BiCgStabOptions::default() };
28/// let result = bicgstab(|x: &IdxTensor| Ok(x.clone()), &b, &x0, &options)?;
29/// assert_eq!(result.solution.to_vec::<f64>()?, vec![1.0, -2.0]);
30/// assert_eq!(result.iterations, 1);
31/// # Ok(())
32/// # }
33/// ```
34#[derive(Debug, Clone)]
35pub struct BiCgStabOptions {
36    /// Maximum BiCGSTAB cycles, including cycles restarted after residual
37    /// replacement. Default: `100`. Zero checks the initial residual only.
38    pub max_iter: usize,
39    /// Finite, nonnegative relative tolerance. Default: `1e-10`.
40    /// The stopping threshold is `max(atol, rtol * ||b||)`.
41    pub rtol: f64,
42    /// Finite, nonnegative absolute tolerance. Default: `0.0`.
43    /// Set a positive value for an absolute target with a tiny RHS.
44    /// Both tolerances zero require an exactly zero true residual.
45    pub atol: f64,
46}
47
48impl Default for BiCgStabOptions {
49    fn default() -> Self {
50        Self {
51            max_iter: 100,
52            rtol: 1e-10,
53            atol: 0.0,
54        }
55    }
56}
57
58impl BiCgStabOptions {
59    /// Validate finite, nonnegative static tolerances without applying an operator.
60    ///
61    /// A zero iteration budget and zero tolerances are valid. The RHS-dependent
62    /// stopping threshold is checked when solving.
63    ///
64    /// # Errors
65    /// Returns [`KrylovError::InvalidOptions`] when a tolerance is negative or
66    /// non-finite.
67    ///
68    /// # Examples
69    /// ```
70    /// use tensor4all_core::krylov::{BiCgStabOptions, KrylovError};
71    /// let options = BiCgStabOptions { rtol: f64::NAN, ..Default::default() };
72    /// assert!(matches!(options.validate(), Err(KrylovError::InvalidOptions { .. })));
73    /// assert!(BiCgStabOptions::default().validate().is_ok());
74    /// ```
75    pub fn validate(&self) -> std::result::Result<(), KrylovError> {
76        for (name, tolerance) in [("rtol", self.rtol), ("atol", self.atol)] {
77            if !tolerance.is_finite() || tolerance < 0.0 {
78                return Err(KrylovError::InvalidOptions {
79                    solver: "bicgstab",
80                    reason: format!("{name} must be finite and nonnegative"),
81                });
82            }
83        }
84        Ok(())
85    }
86}
87
88/// Solution and true-residual diagnostics returned by [`bicgstab`].
89/// Like [`super::CgResult`], the residual is absolute; [`super::GmresResult`]
90/// reports a relative residual by default.
91///
92/// # Examples
93/// ```
94/// use tensor4all_core::{krylov::{bicgstab, BiCgStabOptions}, DynIndex, IdxTensor, TensorVectorSpace};
95/// # fn main() -> anyhow::Result<()> {
96/// let i = DynIndex::new_dyn(2);
97/// let b = IdxTensor::from_dense(vec![i.clone()], vec![2.0_f64, 4.0])?;
98/// let x0 = IdxTensor::zeros::<f64>(vec![i])?;
99/// let result = bicgstab(|x: &IdxTensor| Ok(x.scale(2.0.into())?), &b, &x0, &BiCgStabOptions::default())?;
100/// assert!(result.converged);
101/// assert_eq!(result.solution.to_vec::<f64>()?, vec![1.0, 2.0]);
102/// assert_eq!(result.residual_norm, 0.0);
103/// # Ok(())
104/// # }
105/// ```
106#[derive(Debug, Clone)]
107pub struct BiCgStabResult<T> {
108    /// Approximate solution, including the initial guess's contribution.
109    pub solution: T,
110    /// Consumed cycles, bounded by [`BiCgStabOptions::max_iter`].
111    /// Convergence at the intermediate BiCG step counts as one cycle.
112    ///
113    /// This counts cycles, not operator applications. A full cycle applies
114    /// the operator twice, and each true-residual check applies it once more.
115    /// [`super::GmresResult::iterations`] counts inner GMRES steps, one
116    /// operator application each, so compare the two by operator applications.
117    pub iterations: usize,
118    /// Absolute true residual norm `||b - A*x||`, also on budget exhaustion.
119    pub residual_norm: f64,
120    /// Whether the true residual met `max(atol, rtol * ||b||)`.
121    pub converged: bool,
122}
123
124/// Solve `A x = b` with matrix-free BiCGSTAB.
125///
126/// # Arguments
127/// * `apply_a` - Fixed linear operator preserving the vector space. It may be
128///   nonsymmetric or complex non-Hermitian.
129/// * `b` - Right-hand side in the same vector space as `x0`.
130/// * `x0` - Initial guess. A zero-norm RHS returns the zero vector, the exact
131///   solution, after checking that `x0` and `b` share a vector space.
132/// * `options` - Cycle budget and tolerances; start with the defaults for
133///   double precision.
134///
135/// # Returns
136/// The approximate solution, consumed cycles, absolute true residual, and
137/// convergence flag. True residuals are checked at intermediate and full-step
138/// convergence and at budget exhaustion. Residual replacement restarts the
139/// recurrence within the original budget.
140/// Working vectors and operator images are normalized by powers of two before
141/// inner products. Intermediate arithmetic remains in `TensorVectorSpace` and
142/// `AnyScalar`; norm, range, and stopping decisions cross scalar control-flow boundaries.
143/// This solver does not promise a differentiable solve. The caller's vector
144/// space must provide a norm preserving the required dynamic range.
145///
146/// BiCGSTAB may break down even for an invertible operator. In that case,
147/// [`super::gmres`] provides an alternative with different memory requirements.
148///
149/// # Errors
150/// Returns [`KrylovError::InvalidOptions`] for invalid tolerances or an
151/// overflowing stopping threshold, [`KrylovError::NumericalBreakdown`] for
152/// unusable recurrence quantities, and [`KrylovError::Operation`] for invalid
153/// or incompatible vector spaces, callback failures, or tensor errors.
154/// Underlying operation errors retain their source chains.
155///
156/// # Examples
157/// ```
158/// use tensor4all_core::{contract, krylov::{bicgstab, BiCgStabOptions}, DynIndex, IdxTensor, TensorIndex};
159/// # fn main() -> anyhow::Result<()> {
160/// let i = DynIndex::new_dyn(2);
161/// let input = i.prime();
162/// // Column-major [[1, 1], [0, 2]], with solution [-0.5, 0.5].
163/// let a = IdxTensor::from_dense(vec![i.clone(), input.clone()], vec![1.0_f64, 0.0, 1.0, 2.0])?;
164/// let b = IdxTensor::from_dense(vec![i.clone()], vec![0.0_f64, 1.0])?;
165/// let x0 = IdxTensor::zeros::<f64>(vec![i.clone()])?;
166/// let result = bicgstab(
167///     |x: &IdxTensor| Ok(contract(&[&a, &x.replaceind(&i, &input)?])?),
168///     &b, &x0, &BiCgStabOptions::default(),
169/// )?;
170/// assert!(result.converged);
171/// assert_eq!(result.solution.to_vec::<f64>()?, vec![-0.5, 0.5]);
172/// assert_eq!(result.residual_norm, 0.0);
173/// # Ok(())
174/// # }
175/// ```
176pub fn bicgstab<T, F>(
177    apply_a: F,
178    b: &T,
179    x0: &T,
180    options: &BiCgStabOptions,
181) -> std::result::Result<BiCgStabResult<T>, KrylovError>
182where
183    T: TensorVectorSpace,
184    F: Fn(&T) -> Result<T>,
185{
186    bicgstab_impl(apply_a, b, x0, options).map_err(|source| {
187        match source.downcast::<KrylovError>() {
188            Ok(classified) => classified,
189            Err(source) => KrylovError::Operation {
190                solver: "bicgstab",
191                source,
192            },
193        }
194    })
195}
196
197fn bicgstab_impl<T, F>(
198    apply_a: F,
199    b: &T,
200    x0: &T,
201    options: &BiCgStabOptions,
202) -> Result<BiCgStabResult<T>>
203where
204    T: TensorVectorSpace,
205    F: Fn(&T) -> Result<T>,
206{
207    options.validate()?;
208    b.validate()?;
209    x0.validate()?;
210    let b_norm = finite_norm(b, "bicgstab", 0, "right-hand-side norm")?;
211    let threshold = options.atol.max(options.rtol * b_norm);
212    if !threshold.is_finite() {
213        return Err(KrylovError::InvalidOptions {
214            solver: "bicgstab",
215            reason: "rtol * ||b|| must be finite".into(),
216        }
217        .into());
218    }
219    // Callback failures keep their origin, including nested Krylov failures;
220    // only this solver's own numerical breakdowns may enter recovery.
221    let apply_a = |x: &T| {
222        apply_a(x).map_err(|source| {
223            anyhow::Error::new(KrylovError::Operation {
224                solver: "bicgstab",
225                source,
226            })
227        })
228    };
229    let mut x = x0.clone();
230    let mut r = true_residual(&apply_a, b, &x)?;
231    let mut residual_norm = finite_norm(&r, "bicgstab", 0, "initial residual norm")?;
232    if b_norm == 0.0 {
233        return Ok(BiCgStabResult {
234            solution: b.scale(AnyScalar::new_real(0.0))?,
235            iterations: 0,
236            residual_norm: 0.0,
237            converged: true,
238        });
239    }
240    if residual_norm <= threshold || options.max_iter == 0 {
241        return Ok(BiCgStabResult {
242            solution: x,
243            iterations: 0,
244            residual_norm,
245            converged: residual_norm <= threshold,
246        });
247    }
248    let mut residual_exponent = normalization_exponent(residual_norm);
249    r = scale_pow2(r, -residual_exponent)?;
250    let mut shadow = r.clone();
251    let mut p = r.clone();
252    let mut rho = shadow.inner_product(&r)?;
253    let mut iteration = 0;
254    let run = (|| -> Result<()> {
255        loop {
256            // INVARIANT: the initial path returned for zero budget, and the final
257            // cycle returns at its intermediate or full residual check.
258            iteration += 1;
259            if !usable(&rho) {
260                return Err(breakdown(iteration, "shadow residual inner product"));
261            }
262            let p_norm = finite_norm(&p, "bicgstab", iteration, "search direction norm")?;
263            if p_norm == 0.0 {
264                return Err(breakdown(iteration, "search direction norm"));
265            }
266            p = scale_pow2(p, -normalization_exponent(p_norm))?;
267            let v = apply_a(&p)?;
268            v.validate()?;
269            let v_norm = finite_norm(&v, "bicgstab", iteration, "first operator image norm")?;
270            if v_norm == 0.0 {
271                return Err(breakdown(iteration, "alpha denominator"));
272            }
273            let image_exponent = normalization_exponent(v_norm);
274            let v = scale_pow2(v, -image_exponent)?;
275            let sigma = shadow.inner_product(&v)?;
276            if !usable(&sigma) {
277                return Err(breakdown(iteration, "alpha denominator"));
278            }
279            let alpha = &rho / sigma;
280            if !usable(&alpha) {
281                return Err(breakdown(iteration, "alpha"));
282            }
283            let s = r.axpby(1.0.into(), &v, -alpha.clone())?;
284            let step = scale_pow2(p.scale(alpha.clone())?, residual_exponent - image_exponent)?;
285            x = x.axpby(1.0.into(), &step, 1.0.into())?;
286            let s_norm = finite_norm(&s, "bicgstab", iteration, "intermediate residual norm")?;
287            let estimate = scale_real_pow2(s_norm, residual_exponent);
288            if !estimate.is_finite() {
289                return Err(breakdown(iteration, "physical intermediate residual norm"));
290            }
291            if estimate <= threshold {
292                r = true_residual(&apply_a, b, &x)?;
293                residual_norm = finite_norm(&r, "bicgstab", iteration, "true residual norm")?;
294                if residual_norm <= threshold || iteration == options.max_iter {
295                    return Ok(());
296                }
297                residual_exponent = normalization_exponent(residual_norm);
298                r = scale_pow2(r, -residual_exponent)?;
299                shadow = r.clone();
300                p = r.clone();
301                rho = shadow.inner_product(&r)?;
302                continue;
303            }
304            // R = 2^er r, A p = 2^ev v; S = 2^(er+es) s after this normalization.
305            let intermediate_exponent = normalization_exponent(s_norm);
306            let s = scale_pow2(s, -intermediate_exponent)?;
307            let t = apply_a(&s)?;
308            t.validate()?;
309            let t_norm = finite_norm(&t, "bicgstab", iteration, "second operator image norm")?;
310            if t_norm == 0.0 {
311                return Err(breakdown(iteration, "stabilization denominator"));
312            }
313            let stabilization_exponent = normalization_exponent(t_norm);
314            let t = scale_pow2(t, -stabilization_exponent)?;
315            let denominator = t.inner_product(&t)?.real_part();
316            if !usable(&denominator) {
317                return Err(breakdown(iteration, "stabilization denominator"));
318            }
319            let omega = t.inner_product(&s)? / denominator;
320            if !usable(&omega) {
321                return Err(breakdown(iteration, "omega"));
322            }
323            let step = scale_pow2(
324                s.scale(omega.clone())?,
325                residual_exponent + intermediate_exponent - stabilization_exponent,
326            )?;
327            x = x.axpby(1.0.into(), &step, 1.0.into())?;
328            r = s.axpby(1.0.into(), &t, -omega.clone())?;
329            residual_exponent += intermediate_exponent;
330            let r_norm = finite_norm(&r, "bicgstab", iteration, "recursive residual norm")?;
331            let estimate = scale_real_pow2(r_norm, residual_exponent);
332            if !estimate.is_finite() {
333                return Err(breakdown(iteration, "physical residual norm"));
334            }
335            if estimate <= threshold || iteration == options.max_iter {
336                r = true_residual(&apply_a, b, &x)?;
337                residual_norm = finite_norm(&r, "bicgstab", iteration, "true residual norm")?;
338                if residual_norm <= threshold || iteration == options.max_iter {
339                    return Ok(());
340                }
341                residual_exponent = normalization_exponent(residual_norm);
342                r = scale_pow2(r, -residual_exponent)?;
343                shadow = r.clone();
344                p = r.clone();
345                rho = shadow.inner_product(&r)?;
346                continue;
347            }
348            let next_exponent = normalization_exponent(r_norm);
349            r = scale_pow2(r, -next_exponent)?;
350            residual_exponent += next_exponent;
351            let next_rho = shadow.inner_product(&r)?;
352            if !usable(&next_rho) {
353                return Err(breakdown(iteration, "shadow residual inner product"));
354            }
355            let gamma = scaled_mul_div(&next_rho, &alpha, &rho);
356            let beta = &gamma / omega;
357            if !usable(&gamma) || !usable(&beta) {
358                return Err(breakdown(iteration, "direction coefficient"));
359            }
360            // P_new / 2^er = r + 2^(et-ev) beta p - gamma v. A common
361            // scale makes all power-of-two factors nonpositive before adding.
362            let shift = stabilization_exponent - image_exponent;
363            let common = shift.max(0);
364            let direction =
365                scale_pow2(p, shift - common)?.axpby(beta, &scale_pow2(v, -common)?, -gamma)?;
366            p = scale_pow2(r.clone(), -common)?.axpby(1.0.into(), &direction, 1.0.into())?;
367            rho = next_rho;
368        }
369    })();
370    if let Err(source) = run {
371        match source.downcast::<KrylovError>() {
372            Ok(
373                error @ KrylovError::NumericalBreakdown {
374                    solver: "bicgstab", ..
375                },
376            ) => {
377                // A rounded recurrence can break down after reaching a true
378                // solution. Only a callback failure outranks the breakdown; a
379                // residual that cannot be evaluated reports the breakdown.
380                let check = true_residual(&apply_a, b, &x)
381                    .and_then(|r| finite_norm(&r, "bicgstab", iteration, "true residual norm"));
382                match check {
383                    Ok(norm) if norm <= threshold => residual_norm = norm,
384                    Ok(_) => return Err(error.into()),
385                    Err(check) => {
386                        return Err(match check.downcast::<KrylovError>() {
387                            Ok(callback @ KrylovError::Operation { .. }) => callback.into(),
388                            _ => error.into(),
389                        })
390                    }
391                }
392            }
393            Ok(error) => return Err(error.into()),
394            Err(source) => return Err(source),
395        }
396    }
397    Ok(BiCgStabResult {
398        solution: x,
399        iterations: iteration,
400        residual_norm,
401        converged: residual_norm <= threshold,
402    })
403}
404
405fn usable(value: &AnyScalar) -> bool {
406    value.real().is_finite() && value.imag().is_finite() && !value.is_zero()
407}
408
409fn scaled_mul_div(x: &AnyScalar, y: &AnyScalar, z: &AnyScalar) -> AnyScalar {
410    // INVARIANT: the recurrence checked that all three operands are finite
411    // and nonzero. Their component exponents are in [-1074, 1024].
412    let exponent = |v: &AnyScalar| normalization_exponent(v.real().abs().max(v.imag().abs()));
413    let (xe, ye, ze) = (exponent(x), exponent(y), exponent(z));
414    // Four exponent bits of headroom cover normalized complex products/sums;
415    // retain the usual evaluation order when both intermediates are in range.
416    if (-1020..=1020).contains(&(xe - ze)) && (-1020..=1020).contains(&(xe + ye - ze)) {
417        return (x / z) * y;
418    }
419    let normalized = (scale_scalar_pow2(x.clone(), -xe) * scale_scalar_pow2(y.clone(), -ye))
420        / scale_scalar_pow2(z.clone(), -ze);
421    scale_scalar_pow2(normalized, xe + ye - ze)
422}
423
424fn scale_scalar_pow2(mut value: AnyScalar, mut exponent: i32) -> AnyScalar {
425    while exponent != 0 {
426        let chunk = exponent.clamp(-126, 126);
427        value = value * AnyScalar::new_real(2.0_f64.powi(chunk));
428        exponent -= chunk;
429    }
430    value
431}
432
433fn breakdown(iteration: usize, quantity: &'static str) -> anyhow::Error {
434    KrylovError::NumericalBreakdown {
435        solver: "bicgstab",
436        iteration,
437        quantity,
438    }
439    .into()
440}
441
442#[cfg(test)]
443mod tests;