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;