Skip to main content

tensor4all_core/
krylov.rs

1//! Krylov subspace methods for solving linear equations with abstract tensors.
2//!
3//! This module provides iterative solvers that work with any type implementing [`TensorVectorSpace`],
4//! enabling their use in tensor network algorithms without requiring dense vector representations.
5//!
6//! # Solvers
7//!
8//! - [`gmres`]: Generalized Minimal Residual Method (GMRES) for non-symmetric systems
9//! - [`cg`]: Conjugate gradients for Hermitian positive-definite systems
10//! - [`bicgstab`]: BiCGSTAB for real nonsymmetric and complex non-Hermitian systems
11//! - [`hermitian_lanczos_lowest_eigenpair`]: Matrix-free lowest eigenpair solver for Hermitian operators
12//!
13//! # Example
14//!
15//! ```
16//! use tensor4all_core::{
17//!     krylov::{gmres, GmresOptions},
18//!     DynIndex, IdxTensor, TensorVectorSpace,
19//! };
20//!
21//! # fn main() -> anyhow::Result<()> {
22//! let i = DynIndex::new_dyn(2);
23//! let rhs = IdxTensor::from_dense(vec![i.clone()], vec![1.0, -1.0])?;
24//! let initial_guess = IdxTensor::from_dense(vec![i.clone()], vec![0.0, 0.0])?;
25//!
26//! let apply_operator = |x: &IdxTensor| Ok(x.clone());
27//! let result = gmres(apply_operator, &rhs, &initial_guess, &GmresOptions::default())?;
28//!
29//! assert!(result.converged);
30//! assert!(result.solution.sub(&rhs)?.maxabs()? < 1e-12);
31//! # Ok(())
32//! # }
33//! ```
34
35use crate::any_scalar::AnyScalar;
36use crate::TensorVectorSpace;
37use anyhow::Result;
38use num_complex::Complex64;
39use std::sync::atomic::{AtomicUsize, Ordering};
40use std::time::{Duration, Instant};
41use tensor4all_tensorbackend::{
42    hermitian_exponential_first_column, lowest_hermitian_eigenpair, Matrix,
43};
44
45mod cg;
46mod vector_ops;
47pub use cg::{cg, CgOptions, CgResult};
48mod bicgstab;
49pub use bicgstab::{bicgstab, BiCgStabOptions, BiCgStabResult};
50
51/// Error returned by the matrix-free Krylov solvers.
52#[derive(Debug, thiserror::Error)]
53pub enum KrylovError {
54    /// Invalid solver options.
55    #[error("{solver}: invalid options: {reason}")]
56    InvalidOptions {
57        /// Solver that rejected the options.
58        solver: &'static str,
59        /// Description of the invalid option combination.
60        reason: String,
61    },
62    /// The initial vector is numerically zero.
63    #[error("{solver}: initial vector has norm below the breakdown tolerance; provide a nonzero initial vector")]
64    ZeroInitialVector {
65        /// Solver that rejected the initial vector.
66        solver: &'static str,
67    },
68    /// An affine GMRES call supplied only zero coefficients.
69    #[error("gmres_affine: at least one affine coefficient must be nonzero")]
70    NoAffineCoefficient,
71    /// CG encountered a direction with zero or negative curvature.
72    #[error("{solver}: nonpositive curvature {curvature} at iteration {iteration}; use GMRES for operators that are not positive definite")]
73    NonPositiveCurvature {
74        /// Solver that detected the invalid direction.
75        solver: &'static str,
76        /// One-based iteration in which the direction was encountered.
77        iteration: usize,
78        /// Real `p^H A p` for the power-of-two normalized search direction.
79        curvature: f64,
80    },
81    /// A recurrence encountered nonfinite arithmetic or a vanishing divisor.
82    #[error("{solver}: numerical breakdown in {quantity} at iteration {iteration}")]
83    NumericalBreakdown {
84        /// Solver that detected the numerical failure.
85        solver: &'static str,
86        /// Completed or attempted iteration, with zero for initialization.
87        iteration: usize,
88        /// Quantity that was nonfinite or unusable as a divisor.
89        quantity: &'static str,
90    },
91    /// A value the solve needs is outside the `f64` range for every scaling
92    /// the solver may apply, so no finite answer exists to return; the input
93    /// is outside the supported range rather than numerically unlucky.
94    #[error("{solver}: {quantity} is outside the f64 range")]
95    OutOfRange {
96        /// Solver that rejected the input.
97        solver: &'static str,
98        /// Quantity that cannot be represented.
99        quantity: &'static str,
100    },
101    /// The projected operator was not Hermitian.
102    #[error("{solver}: projected operator is not Hermitian: {source}")]
103    NonHermitian {
104        /// Solver that performed the projection.
105        solver: &'static str,
106        /// Original projected-matrix diagnostic.
107        #[source]
108        source: anyhow::Error,
109    },
110    /// An underlying tensor operation (operator application, vector-space
111    /// arithmetic, or backend call) failed.
112    #[error("{solver}: {source}")]
113    Operation {
114        /// Solver that performed the operation.
115        solver: &'static str,
116        /// Original tensor or backend diagnostic, preserving the full chain.
117        #[source]
118        source: anyhow::Error,
119    },
120}
121
122impl From<anyhow::Error> for KrylovError {
123    fn from(source: anyhow::Error) -> Self {
124        Self::Operation {
125            solver: "krylov",
126            source,
127        }
128    }
129}
130
131impl KrylovError {
132    fn from_anyhow_with_classification(source: anyhow::Error) -> Self {
133        match source.downcast::<KrylovError>() {
134            Ok(classified) => classified,
135            Err(source) => Self::from(source),
136        }
137    }
138}
139
140static GMRES_OP_PROFILE_COUNTER: AtomicUsize = AtomicUsize::new(0);
141
142#[derive(Debug, Clone)]
143struct GmresOpProfile {
144    started: Instant,
145    b_norm: Duration,
146    apply: Duration,
147    inner_product: Duration,
148    axpby: Duration,
149    norm: Duration,
150    scale: Duration,
151    triangular_solve: Duration,
152    solution_update: Duration,
153    apply_calls: usize,
154    inner_product_calls: usize,
155    axpby_calls: usize,
156    norm_calls: usize,
157    scale_calls: usize,
158    triangular_solve_calls: usize,
159    solution_update_calls: usize,
160}
161
162impl Default for GmresOpProfile {
163    fn default() -> Self {
164        Self {
165            started: Instant::now(),
166            b_norm: Duration::ZERO,
167            apply: Duration::ZERO,
168            inner_product: Duration::ZERO,
169            axpby: Duration::ZERO,
170            norm: Duration::ZERO,
171            scale: Duration::ZERO,
172            triangular_solve: Duration::ZERO,
173            solution_update: Duration::ZERO,
174            apply_calls: 0,
175            inner_product_calls: 0,
176            axpby_calls: 0,
177            norm_calls: 0,
178            scale_calls: 0,
179            triangular_solve_calls: 0,
180            solution_update_calls: 0,
181        }
182    }
183}
184
185impl GmresOpProfile {
186    fn measured(&self) -> Duration {
187        self.b_norm
188            + self.apply
189            + self.inner_product
190            + self.axpby
191            + self.norm
192            + self.scale
193            + self.triangular_solve
194            + self.solution_update
195    }
196
197    fn print(&self, id: usize, iterations: usize, residual_norm: f64, converged: bool) {
198        let total = self.started.elapsed();
199        let other = total.saturating_sub(self.measured());
200        let report = format!(
201            "T4A gmres_op_profile #{id}: iterations={iterations} residual={residual_norm:.6e} converged={converged} total_ms={:.3} apply_ms={:.3} apply_calls={} inner_ms={:.3} inner_calls={} axpby_ms={:.3} axpby_calls={} norm_ms={:.3} norm_calls={} scale_ms={:.3} scale_calls={} update_ms={:.3} update_calls={} triangular_ms={:.3} triangular_calls={} b_norm_ms={:.3} other_ms={:.3}",
202            total.as_secs_f64() * 1000.0,
203            self.apply.as_secs_f64() * 1000.0,
204            self.apply_calls,
205            self.inner_product.as_secs_f64() * 1000.0,
206            self.inner_product_calls,
207            self.axpby.as_secs_f64() * 1000.0,
208            self.axpby_calls,
209            self.norm.as_secs_f64() * 1000.0,
210            self.norm_calls,
211            self.scale.as_secs_f64() * 1000.0,
212            self.scale_calls,
213            self.solution_update.as_secs_f64() * 1000.0,
214            self.solution_update_calls,
215            self.triangular_solve.as_secs_f64() * 1000.0,
216            self.triangular_solve_calls,
217            self.b_norm.as_secs_f64() * 1000.0,
218            other.as_secs_f64() * 1000.0,
219        );
220        eprintln!("{report}");
221        #[cfg(test)]
222        LAST_GMRES_PROFILE.with(|last| *last.borrow_mut() = Some(report));
223    }
224}
225
226#[cfg(test)]
227thread_local! {
228    /// The last profile line printed on this thread, for tests of the counts.
229    static LAST_GMRES_PROFILE: std::cell::RefCell<Option<String>> =
230        const { std::cell::RefCell::new(None) };
231}
232
233/// Options for GMRES solver.
234/// # Examples
235/// ```
236/// use tensor4all_core::krylov::GmresOptions;
237/// let opts = GmresOptions {
238///     max_iter: 50,
239///     rtol: 1e-8,
240///     max_restarts: 5,
241///     verbose: false,
242///     check_true_residual: true,
243/// };
244/// assert_eq!(opts.max_iter, 50);
245/// assert_eq!(opts.rtol, 1e-8);
246/// ```
247#[derive(Debug, Clone)]
248pub struct GmresOptions {
249    /// Maximum number of iterations (restart cycle length).
250    /// Default: 100
251    pub max_iter: usize,
252
253    /// Convergence tolerance for relative residual norm.
254    /// The solver stops when `||r|| / ||b|| < rtol`.
255    /// A zero initial residual stops it for every `rtol`, including `0`.
256    /// Default: 1e-10
257    pub rtol: f64,
258
259    /// Maximum number of restarts.
260    /// Total iterations = max_iter * max_restarts.
261    /// Default: 10
262    pub max_restarts: usize,
263
264    /// Whether to print convergence information.
265    /// Default: false
266    pub verbose: bool,
267
268    /// When true, verify convergence by computing the true residual `||b - A*x|| / ||b||`
269    /// before declaring convergence. This prevents false convergence caused by
270    /// truncation corrupting the Krylov basis orthogonality (see Issue #207).
271    /// Costs one additional `apply_a` call when convergence is detected.
272    /// Default: false
273    pub check_true_residual: bool,
274}
275
276impl Default for GmresOptions {
277    fn default() -> Self {
278        Self {
279            max_iter: 100,
280            rtol: 1e-10,
281            max_restarts: 10,
282            verbose: false,
283            check_true_residual: false,
284        }
285    }
286}
287
288#[derive(Debug, Clone, Copy, PartialEq)]
289enum GmresTolerance {
290    Relative(f64),
291    Absolute(f64),
292}
293
294impl GmresTolerance {
295    fn residual_value(self, residual_norm: f64, b_norm: f64) -> f64 {
296        match self {
297            Self::Relative(_) => residual_norm / b_norm,
298            Self::Absolute(_) => residual_norm,
299        }
300    }
301
302    fn is_converged(self, residual_norm: f64, b_norm: f64) -> bool {
303        match self {
304            Self::Relative(rtol) => residual_norm / b_norm < rtol,
305            Self::Absolute(atol) => residual_norm < atol,
306        }
307    }
308}
309
310/// Result of GMRES solver.
311/// Contains the solution, iteration count, final residual norm, and
312/// convergence status.
313/// # Examples
314/// ```
315/// use tensor4all_core::{DynIndex, IdxTensor, TensorVectorSpace};
316/// use tensor4all_core::krylov::{gmres, GmresOptions};
317/// let i = DynIndex::new_dyn(2);
318/// let b = IdxTensor::from_dense(vec![i.clone()], vec![3.0, 7.0]).unwrap();
319/// let x0 = IdxTensor::from_dense(vec![i.clone()], vec![0.0, 0.0]).unwrap();
320/// let result = gmres(|x: &IdxTensor| Ok(x.clone()), &b, &x0, &GmresOptions::default()).unwrap();
321/// assert!(result.converged);
322/// assert!(result.residual_norm < 1e-10);
323/// ```
324#[derive(Debug, Clone)]
325pub struct GmresResult<T> {
326    /// The solution vector.
327    pub solution: T,
328
329    /// Number of iterations performed.
330    pub iterations: usize,
331
332    /// Final relative residual norm.
333    pub residual_norm: f64,
334
335    /// Whether the solver converged.
336    pub converged: bool,
337}
338
339/// Options for [`hermitian_lanczos_lowest_eigenpair`].
340/// These options control the maximum Krylov subspace dimension, convergence
341/// tolerance, and validation tolerance for the small projected Hermitian matrix.
342/// When in doubt, use [`Default::default`].
343/// # Examples
344/// ```
345/// use tensor4all_core::krylov::HermitianLanczosOptions;
346/// let opts = HermitianLanczosOptions {
347///     max_iter: 32,
348///     rtol: 1.0e-9,
349///     ..HermitianLanczosOptions::default()
350/// };
351/// assert_eq!(opts.max_iter, 32);
352/// assert_eq!(opts.rtol, 1.0e-9);
353/// ```
354#[derive(Debug, Clone)]
355pub struct HermitianLanczosOptions {
356    /// Maximum Krylov subspace dimension.
357    ///
358    /// Larger values usually improve convergence but increase memory and the
359    /// cost of the small Rayleigh-Ritz eigensolve. Default: `64`.
360    pub max_iter: usize,
361
362    /// Relative residual tolerance.
363    ///
364    /// Convergence requires `||A v - lambda v|| <= max(atol, rtol *
365    /// max(1, |lambda|))`. Default: `1e-10`.
366    pub rtol: f64,
367
368    /// Absolute residual tolerance.
369    ///
370    /// This is useful when targeting eigenvalues near zero. Default: `0.0`.
371    pub atol: f64,
372
373    /// Breakdown threshold for the next Krylov vector norm.
374    ///
375    /// If the orthogonalized vector norm is at or below this value, the current
376    /// Krylov subspace is treated as invariant and iteration stops. Default:
377    /// `1e-14`.
378    pub breakdown_tol: f64,
379
380    /// Hermitian validation tolerance for the projected Rayleigh-Ritz matrix.
381    ///
382    /// The projected operator is rejected when `V^dagger A V` is not Hermitian
383    /// within this absolute tolerance. Default: `1e-10`.
384    pub hermitian_tol: f64,
385
386    /// Whether to print per-iteration residual information.
387    ///
388    /// Default: `false`.
389    pub verbose: bool,
390}
391
392impl Default for HermitianLanczosOptions {
393    fn default() -> Self {
394        Self {
395            max_iter: 64,
396            rtol: 1.0e-10,
397            atol: 0.0,
398            breakdown_tol: 1.0e-14,
399            hermitian_tol: 1.0e-10,
400            verbose: false,
401        }
402    }
403}
404
405/// Result of [`hermitian_lanczos_lowest_eigenpair`].
406/// Contains the lowest Ritz eigenpair, the final true residual norm, iteration
407/// count, and convergence status.
408/// # Examples
409/// ```
410/// use tensor4all_core::krylov::HermitianLanczosResult;
411/// let result = HermitianLanczosResult {
412///     eigenvalue: 1.0,
413///     eigenvector: vec![1.0_f64],
414///     iterations: 1,
415///     residual_norm: 0.0,
416///     converged: true,
417/// };
418/// assert!(result.converged);
419/// assert_eq!(result.eigenvalue, 1.0);
420/// ```
421#[derive(Debug, Clone)]
422pub struct HermitianLanczosResult<T> {
423    /// Lowest Ritz eigenvalue.
424    pub eigenvalue: f64,
425
426    /// Corresponding Ritz eigenvector in the original vector space.
427    pub eigenvector: T,
428
429    /// Number of Krylov operator applications used to build the final subspace.
430    pub iterations: usize,
431
432    /// True residual norm `||A v - lambda v||`.
433    pub residual_norm: f64,
434
435    /// Whether the true residual satisfied the requested tolerance.
436    pub converged: bool,
437}
438
439/// Options for [`hermitian_krylov_expm_multiply`].
440/// The routine builds a Hermitian Lanczos basis for a matrix-free operator,
441/// exponentiates the small projected Hermitian matrix, and combines the basis
442/// vectors without materializing the full operator. Scalar convergence checks
443/// and projected eigendecompositions are explicit non-differentiable
444/// boundaries; vector-space tensor operations preserve backend metadata when
445/// the underlying tensor implementation supports it.
446/// # Examples
447/// ```
448/// use tensor4all_core::krylov::HermitianKrylovExpmOptions;
449/// let options = HermitianKrylovExpmOptions {
450///     max_iter: 32,
451///     tol: 1.0e-10,
452///     ..HermitianKrylovExpmOptions::default()
453/// };
454/// assert_eq!(options.max_iter, 32);
455/// assert_eq!(options.tol, 1.0e-10);
456/// ```
457#[derive(Debug, Clone)]
458pub struct HermitianKrylovExpmOptions {
459    /// Maximum Krylov subspace dimension for one exponential application.
460    pub max_iter: usize,
461    /// Maximum number of equal time splits attempted after non-convergence.
462    pub max_time_splits: usize,
463    /// Relative convergence tolerance for the Krylov residual estimate.
464    pub tol: f64,
465    /// Breakdown threshold for zero vectors and invariant Krylov subspaces.
466    pub breakdown_tol: f64,
467    /// Hermitian validation tolerance for projected matrices.
468    pub hermitian_tol: f64,
469    /// Whether to print per-attempt diagnostics.
470    pub verbose: bool,
471}
472
473impl Default for HermitianKrylovExpmOptions {
474    fn default() -> Self {
475        Self {
476            max_iter: 30,
477            max_time_splits: 100,
478            tol: 1.0e-12,
479            breakdown_tol: 1.0e-14,
480            hermitian_tol: 1.0e-10,
481            verbose: false,
482        }
483    }
484}
485
486/// Result of [`hermitian_krylov_expm_multiply`].
487/// # Examples
488/// ```
489/// use tensor4all_core::krylov::HermitianKrylovExpmResult;
490/// let result = HermitianKrylovExpmResult {
491///     output: vec![1.0_f64, 0.0],
492///     iterations: 1,
493///     matvecs: 1,
494///     error_estimate: 0.0,
495///     converged: true,
496///     time_splits: 1,
497/// };
498/// assert!(result.converged);
499/// assert_eq!(result.output[0], 1.0);
500/// ```
501#[derive(Debug, Clone)]
502pub struct HermitianKrylovExpmResult<T> {
503    /// Approximation to `exp(exponent * A) * initial`.
504    pub output: T,
505    /// Total Krylov iterations over all accepted substeps.
506    pub iterations: usize,
507    /// Total matrix-vector products over all accepted substeps.
508    pub matvecs: usize,
509    /// Maximum Krylov residual estimate over accepted substeps.
510    pub error_estimate: f64,
511    /// Whether the requested tolerance was met.
512    pub converged: bool,
513    /// Number of equal time splits used.
514    pub time_splits: usize,
515}
516
517#[derive(Debug, Clone)]
518struct HermitianRitzState {
519    eigenvalue: f64,
520    coefficients: Vec<Complex64>,
521    iterations: usize,
522    residual_estimate: f64,
523}
524
525/// Compute the lowest eigenpair of a Hermitian matrix-free operator.
526/// The operator is supplied as `apply_a`, which maps a vector to `A * vector`.
527/// The algorithm builds an orthonormal Krylov basis using modified
528/// Gram-Schmidt with a second reorthogonalization pass, forms the small
529/// projected matrix `V^dagger A V`, and solves that small Hermitian problem via
530/// tensorbackend. The full operator matrix is never materialized.
531/// # Arguments
532/// * `apply_a` - Matrix-free Hermitian operator application.
533/// * `initial` - Nonzero initial vector that defines the starting Krylov vector.
534/// * `options` - Krylov dimension, convergence tolerances, and Hermitian
535///
536///   validation settings.
537/// # Returns
538/// The lowest Ritz eigenpair and the true residual norm.
539/// # Errors
540/// Returns [`KrylovError::NonHermitian`] when the projected operator is not
541/// Hermitian, [`KrylovError::InvalidOptions`] when an option is invalid
542/// (including a `max_iter` whose Krylov workspace cannot be allocated),
543/// [`KrylovError::ZeroInitialVector`] when `initial` is numerically zero, and
544/// [`KrylovError::Operation`] when an operator application or backend call
545/// fails. Non-convergence is reported through
546/// [`HermitianLanczosResult::converged`] and does not produce an error.
547/// # Examples
548/// ```
549/// use tensor4all_core::{DynIndex, IdxTensor, TensorVectorSpace};
550/// use tensor4all_core::krylov::{hermitian_lanczos_lowest_eigenpair, HermitianLanczosOptions};
551/// let i = DynIndex::new_dyn(2);
552/// let initial = IdxTensor::from_dense(vec![i.clone()], vec![1.0_f64, 1.0]).unwrap();
553/// let result = hermitian_lanczos_lowest_eigenpair(
554///     |x: &IdxTensor| Ok(x.clone()),
555///     &initial,
556///     &HermitianLanczosOptions::default(),
557/// ).unwrap();
558/// assert!(result.converged);
559/// assert!((result.eigenvalue - 1.0).abs() < 1.0e-12);
560/// ```
561pub fn hermitian_lanczos_lowest_eigenpair<T, F>(
562    apply_a: F,
563    initial: &T,
564    options: &HermitianLanczosOptions,
565) -> std::result::Result<HermitianLanczosResult<T>, KrylovError>
566where
567    T: TensorVectorSpace,
568    F: Fn(&T) -> Result<T>,
569{
570    hermitian_lanczos_lowest_eigenpair_impl(apply_a, initial, options)
571        .map_err(KrylovError::from_anyhow_with_classification)
572}
573
574fn hermitian_lanczos_lowest_eigenpair_impl<T, F>(
575    apply_a: F,
576    initial: &T,
577    options: &HermitianLanczosOptions,
578) -> Result<HermitianLanczosResult<T>>
579where
580    T: TensorVectorSpace,
581    F: Fn(&T) -> Result<T>,
582{
583    let basis_capacity = validate_hermitian_lanczos_options(options)?;
584    initial.validate()?;
585
586    let initial_norm = initial.norm()?;
587    if initial_norm <= options.breakdown_tol {
588        return Err(anyhow::Error::new(KrylovError::ZeroInitialVector {
589            solver: "hermitian_lanczos_lowest_eigenpair",
590        }));
591    }
592
593    let mut basis = krylov_workspace(basis_capacity, "hermitian_lanczos_lowest_eigenpair")?;
594    basis.push(initial.scale(AnyScalar::new_real(1.0 / initial_norm))?);
595    let mut h_cols: Vec<Vec<Complex64>> =
596        krylov_workspace(options.max_iter, "hermitian_lanczos_lowest_eigenpair")?;
597    let mut last_ritz: Option<HermitianRitzState> = None;
598
599    for j in 0..options.max_iter {
600        let w = apply_a(&basis[j])?;
601        if j == 0 {
602            w.validate()?;
603        }
604
605        let mut h_col = krylov_workspace(j + 2, "hermitian_lanczos_lowest_eigenpair")?;
606        let mut w_orth = w;
607
608        for v_i in basis.iter().take(j + 1) {
609            let h_ij = v_i.inner_product(&w_orth)?;
610            h_col.push(any_scalar_to_complex(&h_ij));
611            let neg_h_ij = AnyScalar::new_real(0.0) - h_ij;
612            w_orth = w_orth.axpby(AnyScalar::new_real(1.0), v_i, neg_h_ij)?;
613        }
614
615        for (i, v_i) in basis.iter().take(j + 1).enumerate() {
616            let correction = v_i.inner_product(&w_orth)?;
617            h_col[i] += any_scalar_to_complex(&correction);
618            let neg_correction = AnyScalar::new_real(0.0) - correction;
619            w_orth = w_orth.axpby(AnyScalar::new_real(1.0), v_i, neg_correction)?;
620        }
621
622        let beta = w_orth.norm()?;
623        h_col.push(Complex64::new(beta, 0.0));
624        h_cols.push(h_col);
625
626        let subspace_dim = j + 1;
627        let projected = projected_matrix_from_columns(
628            &h_cols,
629            subspace_dim,
630            "hermitian_lanczos_lowest_eigenpair",
631        )?;
632        let ritz =
633            lowest_hermitian_eigenpair(&projected, options.hermitian_tol).map_err(|err| {
634                anyhow::Error::new(KrylovError::NonHermitian {
635                    solver: "hermitian_lanczos_lowest_eigenpair",
636                    source: anyhow::anyhow!("projected operator is not Hermitian: {err}"),
637                })
638            })?;
639        let residual_estimate = beta * ritz.eigenvector[subspace_dim - 1].norm();
640        let threshold = hermitian_lanczos_threshold(ritz.eigenvalue, options);
641        let estimate_converged = residual_estimate <= threshold;
642
643        if options.verbose {
644            eprintln!(
645                "Hermitian Lanczos iter {}: eigenvalue={:.16e} residual_estimate={:.6e} threshold={:.6e}",
646                subspace_dim, ritz.eigenvalue, residual_estimate, threshold
647            );
648        }
649
650        let ritz_state = HermitianRitzState {
651            eigenvalue: ritz.eigenvalue,
652            iterations: subspace_dim,
653            residual_estimate,
654            coefficients: ritz.eigenvector,
655        };
656        if estimate_converged || beta <= options.breakdown_tol {
657            let result = finalize_hermitian_lanczos_result(
658                &apply_a,
659                &basis[..subspace_dim],
660                &ritz_state,
661                options,
662            )?;
663            if result.converged || beta <= options.breakdown_tol {
664                return Ok(result);
665            }
666        }
667        last_ritz = Some(ritz_state);
668        basis.push(w_orth.scale(AnyScalar::new_real(1.0 / beta))?);
669    }
670
671    let ritz_state = last_ritz.ok_or_else(|| {
672        anyhow::Error::new(KrylovError::InvalidOptions {
673            solver: "hermitian_lanczos_lowest_eigenpair",
674            reason: "max_iter must be greater than zero".to_string(),
675        })
676    })?;
677    finalize_hermitian_lanczos_result(
678        &apply_a,
679        &basis[..ritz_state.iterations],
680        &ritz_state,
681        options,
682    )
683}
684
685/// Apply `exp(exponent * A)` to a vector using a matrix-free Hermitian Krylov method.
686/// This routine only materializes small projected Krylov matrices. It never
687/// forms the full matrix for `A`, so it can be used by tensor-network local
688/// solvers whose operator application is available as a closure.
689/// # Arguments
690/// * `apply_a` - Matrix-free Hermitian operator application.
691/// * `exponent` - Scalar exponent, for example `-im * dt` for real-time TDVP.
692/// * `initial` - Initial vector.
693/// * `options` - Krylov dimension, tolerance, and Hermitian validation options.
694/// # Returns
695/// A [`HermitianKrylovExpmResult`] containing the evolved vector and diagnostics.
696/// # Errors
697/// Returns [`KrylovError::NonHermitian`] when the projected operator is not
698/// Hermitian, [`KrylovError::InvalidOptions`] when an option is invalid
699/// (including a `max_iter` whose Krylov workspace cannot be allocated),
700/// [`KrylovError::ZeroInitialVector`] when `initial` is numerically zero, and
701/// [`KrylovError::Operation`] when an operator application or backend call
702/// fails. Non-convergence is reported through
703/// [`HermitianKrylovExpmResult::converged`] and does not produce an error.
704/// # Examples
705/// ```
706/// use num_complex::Complex64;
707/// use tensor4all_core::krylov::{
708///     hermitian_krylov_expm_multiply, HermitianKrylovExpmOptions,
709/// };
710/// use tensor4all_core::{DynIndex, IdxTensor};
711/// # fn main() -> anyhow::Result<()> {
712/// let index = DynIndex::new_dyn(2);
713/// let initial = IdxTensor::from_dense(
714///     vec![index.clone()],
715///     vec![Complex64::new(1.0, 0.0), Complex64::new(0.0, 0.0)],
716/// )?;
717/// let options = HermitianKrylovExpmOptions {
718///     max_iter: 4,
719///     tol: 1.0e-12,
720///     ..Default::default()
721/// };
722/// let result = hermitian_krylov_expm_multiply(
723///     |x: &IdxTensor| {
724///         let data = x.to_vec::<Complex64>()?;
725///         IdxTensor::from_dense(
726///             vec![index.clone()],
727///             vec![data[0], Complex64::new(2.0, 0.0) * data[1]],
728///         )
729///         .map_err(anyhow::Error::from)
730///     },
731///     Complex64::new(0.0, -0.25),
732///     &initial,
733///     &options,
734/// )?;
735/// let evolved = result.output.to_vec::<Complex64>()?;
736/// let expected = Complex64::new(0.25_f64.cos(), -0.25_f64.sin());
737/// assert!((evolved[0] - expected).norm() < 1.0e-10);
738/// assert!(evolved[1].norm() < 1.0e-12);
739/// # Ok(())
740/// # }
741/// ```
742pub fn hermitian_krylov_expm_multiply<T, F>(
743    apply_a: F,
744    exponent: Complex64,
745    initial: &T,
746    options: &HermitianKrylovExpmOptions,
747) -> std::result::Result<HermitianKrylovExpmResult<T>, KrylovError>
748where
749    T: TensorVectorSpace,
750    F: FnMut(&T) -> Result<T>,
751{
752    hermitian_krylov_expm_multiply_impl(apply_a, exponent, initial, options)
753        .map_err(KrylovError::from_anyhow_with_classification)
754}
755
756fn hermitian_krylov_expm_multiply_impl<T, F>(
757    mut apply_a: F,
758    exponent: Complex64,
759    initial: &T,
760    options: &HermitianKrylovExpmOptions,
761) -> Result<HermitianKrylovExpmResult<T>>
762where
763    T: TensorVectorSpace,
764    F: FnMut(&T) -> Result<T>,
765{
766    validate_hermitian_krylov_expm_options(options)?;
767    initial.validate()?;
768
769    if exponent == Complex64::new(0.0, 0.0) {
770        return Ok(HermitianKrylovExpmResult {
771            output: initial.clone(),
772            iterations: 0,
773            matvecs: 0,
774            error_estimate: 0.0,
775            converged: true,
776            time_splits: 1,
777        });
778    }
779    if initial.norm()? <= options.breakdown_tol {
780        return Ok(HermitianKrylovExpmResult {
781            output: initial.clone(),
782            iterations: 0,
783            matvecs: 0,
784            error_estimate: 0.0,
785            converged: true,
786            time_splits: 1,
787        });
788    }
789
790    let mut splits = 1usize;
791    loop {
792        let step_exponent = exponent / splits as f64;
793        let mut output = initial.clone();
794        let mut iterations = 0usize;
795        let mut matvecs = 0usize;
796        let mut max_error = 0.0_f64;
797        let mut converged = true;
798
799        for _ in 0..splits {
800            let result =
801                hermitian_krylov_expm_multiply_once(&mut apply_a, step_exponent, &output, options)?;
802            iterations += result.iterations;
803            matvecs += result.matvecs;
804            max_error = max_error.max(result.error_estimate);
805            output = result.output;
806            if !result.converged {
807                converged = false;
808                break;
809            }
810        }
811
812        if converged {
813            return Ok(HermitianKrylovExpmResult {
814                output,
815                iterations,
816                matvecs,
817                error_estimate: max_error,
818                converged: true,
819                time_splits: splits,
820            });
821        }
822
823        if options.verbose {
824            eprintln!(
825                "Hermitian Krylov expm did not converge with {splits} time split(s); retrying"
826            );
827        }
828        if splits >= options.max_time_splits {
829            return Err(anyhow::anyhow!(
830                "hermitian_krylov_expm_multiply did not converge within max_time_splits={} and max_iter={}",
831                options.max_time_splits,
832                options.max_iter
833            ));
834        }
835        splits = splits.saturating_mul(2).min(options.max_time_splits);
836    }
837}
838
839fn hermitian_krylov_expm_multiply_once<T, F>(
840    apply_a: &mut F,
841    exponent: Complex64,
842    initial: &T,
843    options: &HermitianKrylovExpmOptions,
844) -> Result<HermitianKrylovExpmResult<T>>
845where
846    T: TensorVectorSpace,
847    F: FnMut(&T) -> Result<T>,
848{
849    let initial_norm = initial.norm()?;
850    if initial_norm <= options.breakdown_tol {
851        return Ok(HermitianKrylovExpmResult {
852            output: initial.clone(),
853            iterations: 0,
854            matvecs: 0,
855            error_estimate: 0.0,
856            converged: true,
857            time_splits: 1,
858        });
859    }
860
861    let basis_capacity =
862        checked_krylov_capacity(options.max_iter, "hermitian_krylov_expm_multiply")?;
863    let mut basis = krylov_workspace(basis_capacity, "hermitian_krylov_expm_multiply")?;
864    basis.push(initial.scale(AnyScalar::new_real(1.0 / initial_norm))?);
865    let mut h_cols: Vec<Vec<Complex64>> =
866        krylov_workspace(options.max_iter, "hermitian_krylov_expm_multiply")?;
867    let mut last_coefficients: Option<Vec<Complex64>> = None;
868    let mut last_error_estimate = f64::INFINITY;
869    let mut last_subspace_dim = 0usize;
870    let threshold = options.tol * initial_norm.max(1.0);
871
872    for j in 0..options.max_iter {
873        let w = apply_a(&basis[j])?;
874        if j == 0 {
875            w.validate()?;
876        }
877        let mut w_orth = w;
878        let mut h_col = krylov_workspace(j + 2, "hermitian_krylov_expm_multiply")?;
879
880        for v_i in basis.iter().take(j + 1) {
881            let h_ij = v_i.inner_product(&w_orth)?;
882            h_col.push(any_scalar_to_complex(&h_ij));
883            let neg_h_ij = AnyScalar::new_real(0.0) - h_ij;
884            w_orth = w_orth.axpby(AnyScalar::new_real(1.0), v_i, neg_h_ij)?;
885        }
886
887        for (i, v_i) in basis.iter().take(j + 1).enumerate() {
888            let correction = v_i.inner_product(&w_orth)?;
889            h_col[i] += any_scalar_to_complex(&correction);
890            let neg_correction = AnyScalar::new_real(0.0) - correction;
891            w_orth = w_orth.axpby(AnyScalar::new_real(1.0), v_i, neg_correction)?;
892        }
893
894        let beta_next = w_orth.norm()?;
895        h_col.push(Complex64::new(beta_next, 0.0));
896        h_cols.push(h_col);
897
898        let subspace_dim = j + 1;
899        let projected =
900            projected_matrix_from_columns(&h_cols, subspace_dim, "hermitian_krylov_expm_multiply")?;
901        let coefficients =
902            hermitian_exponential_first_column(&projected, exponent, options.hermitian_tol)
903                .map_err(|err| anyhow::anyhow!("projected operator is not Hermitian: {err}"))?;
904        let error_estimate = if beta_next <= options.breakdown_tol {
905            0.0
906        } else {
907            initial_norm * beta_next * coefficients[subspace_dim - 1].norm()
908        };
909        let converged = beta_next <= options.breakdown_tol || error_estimate <= threshold;
910
911        if options.verbose {
912            eprintln!(
913                "Hermitian Krylov expm iter {}: residual_estimate={:.6e} threshold={:.6e}",
914                subspace_dim, error_estimate, threshold
915            );
916        }
917
918        if converged {
919            let output = finalize_hermitian_krylov_expm_output(
920                &basis[..subspace_dim],
921                &coefficients,
922                initial_norm,
923                options.hermitian_tol,
924            )?;
925            return Ok(HermitianKrylovExpmResult {
926                output,
927                iterations: subspace_dim,
928                matvecs: subspace_dim,
929                error_estimate,
930                converged: true,
931                time_splits: 1,
932            });
933        }
934        last_coefficients = Some(coefficients);
935        last_error_estimate = error_estimate;
936        last_subspace_dim = subspace_dim;
937        basis.push(w_orth.scale(AnyScalar::new_real(1.0 / beta_next))?);
938    }
939
940    let coefficients = last_coefficients.ok_or_else(|| {
941        anyhow::anyhow!("hermitian_krylov_expm_multiply: max_iter must be greater than zero")
942    })?;
943    let output = finalize_hermitian_krylov_expm_output(
944        &basis[..last_subspace_dim],
945        &coefficients,
946        initial_norm,
947        options.hermitian_tol,
948    )?;
949    Ok(HermitianKrylovExpmResult {
950        output,
951        iterations: last_subspace_dim,
952        matvecs: last_subspace_dim,
953        error_estimate: last_error_estimate,
954        converged: false,
955        time_splits: 1,
956    })
957}
958
959fn finalize_hermitian_krylov_expm_output<T>(
960    basis: &[T],
961    coefficients: &[Complex64],
962    initial_norm: f64,
963    hermitian_tol: f64,
964) -> Result<T>
965where
966    T: TensorVectorSpace,
967{
968    let unit_output = combine_basis_with_complex_coefficients(
969        basis,
970        coefficients,
971        hermitian_tol,
972        "hermitian_krylov_expm_multiply",
973    )?;
974    unit_output
975        .scale(AnyScalar::new_real(initial_norm))
976        .map_err(anyhow::Error::new)
977}
978
979/// Solve `A x = b` using GMRES (Generalized Minimal Residual Method).
980/// This implements the restarted GMRES algorithm that works with abstract tensor types
981/// through the [`TensorVectorSpace`] trait's vector space operations.
982/// # Algorithm
983/// GMRES builds an orthonormal basis for the Krylov subspace
984/// `K_m = span{r_0, A r_0, A^2 r_0, ..., A^{m-1} r_0}` and finds the
985/// solution that minimizes `||b - A x||` over this subspace.
986/// # Type Parameters
987/// * `T` - A tensor type implementing `TensorVectorSpace`
988/// * `F` - A function that applies the linear operator: `F(x) = A x`
989/// # Arguments
990/// * `apply_a` - Function that applies the linear operator A to a tensor
991/// * `b` - Right-hand side tensor
992/// * `x0` - Initial guess
993/// * `options` - Solver options
994/// # Returns
995/// A `GmresResult` containing the solution and convergence information.
996/// # Errors
997/// Returns an error when `max_iter` needs a Krylov workspace whose capacity
998/// overflows or cannot be allocated (a [`KrylovError::InvalidOptions`]), when the operator and vectors have
999/// incompatible shapes, when the affine coefficients are all zero (a
1000/// [`KrylovError::NoAffineCoefficient`] for affine solves), or when an
1001/// underlying tensor or backend operation fails (a [`KrylovError::Operation`]).
1002/// Non-convergence is reported through the result's `converged` flag and does
1003/// not produce an error.
1004/// A right-hand side whose norm is not finite, which would make every relative
1005/// residual zero, is a [`KrylovError::NumericalBreakdown`].
1006///
1007pub fn gmres<T, F>(
1008    apply_a: F,
1009    b: &T,
1010    x0: &T,
1011    options: &GmresOptions,
1012) -> std::result::Result<GmresResult<T>, KrylovError>
1013where
1014    T: TensorVectorSpace,
1015    F: Fn(&T) -> Result<T>,
1016{
1017    gmres_impl(
1018        apply_a,
1019        b,
1020        x0,
1021        options,
1022        GmresTolerance::Relative(options.rtol),
1023        None,
1024    )
1025    .map_err(KrylovError::from_anyhow_with_classification)
1026}
1027
1028/// Solve `A x = b` using GMRES with an absolute residual tolerance.
1029/// A zero-norm RHS returns the zero vector rather than the initial guess.
1030/// This variant stops when `||b - A*x|| < atol`. The default [`gmres`] API uses
1031/// relative residual tolerance and is preferred for scale-independent solves.
1032/// # Errors
1033/// Returns an error when `max_iter` needs a Krylov workspace whose capacity
1034/// overflows or cannot be allocated (a [`KrylovError::InvalidOptions`]), when the operator and vectors have
1035/// incompatible shapes, when the affine coefficients are all zero (a
1036/// [`KrylovError::NoAffineCoefficient`] for affine solves), or when an
1037/// underlying tensor or backend operation fails (a [`KrylovError::Operation`]).
1038/// Non-convergence is reported through the result's `converged` flag and does
1039/// not produce an error.
1040/// A right-hand side whose norm is not finite, which would make every relative
1041/// residual zero, is a [`KrylovError::NumericalBreakdown`].
1042///
1043pub fn gmres_with_absolute_tolerance<T, F>(
1044    apply_a: F,
1045    b: &T,
1046    x0: &T,
1047    options: &GmresOptions,
1048    atol: f64,
1049) -> std::result::Result<GmresResult<T>, KrylovError>
1050where
1051    T: TensorVectorSpace,
1052    F: Fn(&T) -> Result<T>,
1053{
1054    gmres_impl(
1055        apply_a,
1056        b,
1057        x0,
1058        options,
1059        GmresTolerance::Absolute(atol),
1060        None,
1061    )
1062    .map_err(KrylovError::from_anyhow_with_classification)
1063}
1064
1065/// Solve `(a0 I + a1 A) x = b` using GMRES with relative residual tolerance.
1066/// A zero-norm RHS returns the zero vector after validating the affine coefficients.
1067/// `a1 = 0` gives `x = b / a0` in closed form, with the residual of that `x`
1068/// reported; a subnormal quotient component can round to zero, so the closed
1069/// form is not always converged. A gradient-tracked `a1 = 0` adds
1070/// `-a1 (A(b / a0) / a0)`, which is zero in value and makes the first
1071/// derivatives those of the exact solution, at the cost of one call to
1072/// `apply_a`. When `A(b / a0)` has a NaN or infinite component, `A` is
1073/// applied again to `b / a0 2^-s` for the smallest `s` that keeps it finite,
1074/// found in about `2 log2(s)` further calls; components of `b / a0` that this
1075/// scaling rounds away are applied as separate exact parts until none is
1076/// left. The search covers every `s` for which `b / a0 2^-s` keeps its largest
1077/// component nonzero. For
1078/// single-precision `b` the closed form requires every factor of
1079/// [`AnyScalar::reciprocal_factors`] to be in the `f32` range.
1080/// A zero initial residual, also that of the closed form, is converged for
1081/// every `rtol`, including `0`.
1082/// The Arnoldi basis is built from the unshifted `A` callback, while affine
1083/// coefficients are applied in the projected Hessenberg problem, matching
1084/// KrylovKit's affine linear-solve convention.
1085/// # Errors
1086/// Returns [`KrylovError::InvalidOptions`] when an option is invalid
1087/// (including a `max_iter` whose Krylov workspace cannot be allocated),
1088/// [`KrylovError::InvalidOptions`] also when `a0` or `a1` has a NaN or
1089/// infinite component, checked before the zero-RHS return, when `b` or `x0` is
1090/// single precision and `a0` or `a1` is outside the `f32` range, or when an
1091/// untracked `a1 = 0` and single-precision `b` need a factor of `1 / a0` outside
1092/// the `f32` range,
1093/// [`KrylovError::NoAffineCoefficient`] when both affine coefficients are zero,
1094/// and [`KrylovError::Operation`] when the operator application, vector-space
1095/// arithmetic, or a backend call fails. Non-convergence is reported through the
1096/// result's `converged` flag and does not produce an error.
1097/// A right-hand side whose norm is not finite, which would make every relative
1098/// residual zero, is a [`KrylovError::NumericalBreakdown`].
1099/// A gradient-tracked `a1 = 0` whose derivative `-A(b / a0) / a0` has a real
1100/// or imaginary component outside the `f64` range, or whose `A` is not finite
1101/// on `b / a0 2^-s` for any `s` that keeps `b / a0` nonzero, is a
1102/// [`KrylovError::OutOfRange`] naming that quantity: the input is outside the
1103/// supported range, and no NaN or partial gradient is returned.
1104///
1105pub fn gmres_affine<T, F>(
1106    apply_a: F,
1107    b: &T,
1108    x0: &T,
1109    a0: AnyScalar,
1110    a1: AnyScalar,
1111    options: &GmresOptions,
1112) -> std::result::Result<GmresResult<T>, KrylovError>
1113where
1114    T: TensorVectorSpace,
1115    F: Fn(&T) -> Result<T>,
1116{
1117    gmres_affine_impl(
1118        apply_a,
1119        b,
1120        x0,
1121        a0,
1122        a1,
1123        options,
1124        GmresTolerance::Relative(options.rtol),
1125    )
1126    .map_err(KrylovError::from_anyhow_with_classification)
1127}
1128
1129/// Solve `(a0 I + a1 A) x = b` using GMRES with an absolute residual tolerance.
1130/// The Arnoldi basis is built from the unshifted `A` callback, while the affine
1131/// coefficients are applied to the small Hessenberg problem. This mirrors
1132/// KrylovKit's `linsolve(operator, b, a0, a1)` algorithm and avoids changing the
1133/// Krylov basis when affine coefficients are present.
1134/// # Errors
1135/// Returns [`KrylovError::InvalidOptions`] when an option is invalid
1136/// (including a `max_iter` whose Krylov workspace cannot be allocated),
1137/// [`KrylovError::InvalidOptions`] also when `a0` or `a1` has a NaN or
1138/// infinite component, checked before the zero-RHS return, when `b` or `x0` is
1139/// single precision and `a0` or `a1` is outside the `f32` range, or when an
1140/// untracked `a1 = 0` and single-precision `b` need a factor of `1 / a0` outside
1141/// the `f32` range,
1142/// [`KrylovError::NoAffineCoefficient`] when both affine coefficients are zero,
1143/// and [`KrylovError::Operation`] when the operator application, vector-space
1144/// arithmetic, or a backend call fails. Non-convergence is reported through the
1145/// result's `converged` flag and does not produce an error.
1146/// A right-hand side whose norm is not finite, which would make every relative
1147/// residual zero, is a [`KrylovError::NumericalBreakdown`].
1148///
1149pub fn gmres_affine_with_absolute_tolerance<T, F>(
1150    apply_a: F,
1151    b: &T,
1152    x0: &T,
1153    a0: AnyScalar,
1154    a1: AnyScalar,
1155    options: &GmresOptions,
1156    atol: f64,
1157) -> std::result::Result<GmresResult<T>, KrylovError>
1158where
1159    T: TensorVectorSpace,
1160    F: Fn(&T) -> Result<T>,
1161{
1162    gmres_affine_impl(
1163        apply_a,
1164        b,
1165        x0,
1166        a0,
1167        a1,
1168        options,
1169        GmresTolerance::Absolute(atol),
1170    )
1171    .map_err(KrylovError::from_anyhow_with_classification)
1172}
1173
1174fn gmres_affine_impl<T, F>(
1175    apply_a: F,
1176    b: &T,
1177    x0: &T,
1178    a0: AnyScalar,
1179    a1: AnyScalar,
1180    options: &GmresOptions,
1181    tolerance: GmresTolerance,
1182) -> Result<GmresResult<T>>
1183where
1184    T: TensorVectorSpace,
1185    F: Fn(&T) -> Result<T>,
1186{
1187    b.validate()?;
1188    x0.validate()?;
1189
1190    let profile_enabled = std::env::var_os("T4A_GMRES_OP_PROFILE").is_some();
1191    let profile_id = if profile_enabled {
1192        GMRES_OP_PROFILE_COUNTER.fetch_add(1, Ordering::Relaxed)
1193    } else {
1194        0
1195    };
1196    let mut profile = GmresOpProfile::default();
1197    let mut total_iters = 0usize;
1198
1199    macro_rules! finish {
1200        ($result:expr) => {{
1201            let result = $result;
1202            if profile_enabled {
1203                profile.print(
1204                    profile_id,
1205                    result.iterations,
1206                    result.residual_norm,
1207                    result.converged,
1208                );
1209            }
1210            return Ok(result);
1211        }};
1212    }
1213
1214    if a0.is_zero() && a1.is_zero() {
1215        return Err(anyhow::Error::new(KrylovError::NoAffineCoefficient));
1216    }
1217    // Checked before the zero-RHS and closed-form returns, which would
1218    // otherwise accept them.
1219    for (name, value) in [("a0", &a0), ("a1", &a1)] {
1220        if !(value.real().is_finite() && value.imag().is_finite()) {
1221            return Err(anyhow::Error::new(KrylovError::InvalidOptions {
1222                solver: "gmres",
1223                reason: format!("{name} must be finite, got {value:?}"),
1224            }));
1225        }
1226    }
1227    // `scale` and `axpby` convert a coefficient to the storage precision, so
1228    // single-precision vectors need both coefficients in the `f32` range.
1229    if b.is_single_precision() || x0.is_single_precision() {
1230        for (name, value) in [("a0", &a0), ("a1", &a1)] {
1231            if !value.is_in_single_precision_range() {
1232                return Err(anyhow::Error::new(KrylovError::InvalidOptions {
1233                    solver: "gmres",
1234                    reason: format!(
1235                        "{name} = {value:?} is outside the f32 range of the single-precision \
1236                         vectors"
1237                    ),
1238                }));
1239            }
1240        }
1241    }
1242
1243    let started = Instant::now();
1244    // A norm that overflows would make every relative residual zero.
1245    let b_norm = vector_ops::finite_norm(b, "gmres", 0, "right-hand-side norm")?;
1246    if profile_enabled {
1247        profile.b_norm += started.elapsed();
1248    }
1249    if b_norm == 0.0 {
1250        finish!(GmresResult {
1251            solution: b.scale(AnyScalar::new_real(0.0))?,
1252            iterations: 0,
1253            residual_norm: 0.0,
1254            converged: true,
1255        });
1256    }
1257    if a1.is_zero() {
1258        let started = Instant::now();
1259        // `a0 x = b` in closed form; the factors keep `b / a0` in range when
1260        // `1 / a0` itself is not.
1261        let factors = a0.reciprocal_factors()?;
1262        if b.is_single_precision() {
1263            if let Some(factor) = factors.iter().find(|f| !f.is_in_single_precision_range()) {
1264                return Err(anyhow::Error::new(KrylovError::InvalidOptions {
1265                    solver: "gmres",
1266                    reason: format!(
1267                        "dividing single-precision entries by a0 = {a0:?} needs the factor \
1268                         {factor:?}, outside the f32 range"
1269                    ),
1270                }));
1271            }
1272        }
1273        let scale_calls = factors.len();
1274        let divide = |value: T| {
1275            factors
1276                .iter()
1277                .try_fold(value, |value, factor| value.scale(factor.clone()))
1278        };
1279        let mut solution = divide(b.clone())?;
1280        if profile_enabled {
1281            profile.scale += started.elapsed();
1282            profile.scale_calls += scale_calls;
1283        }
1284        if a1.tracks_grad() {
1285            // `x = b / a0 - a1 (A(b / a0) / a0)` equals `b / a0` at `a1 = 0`,
1286            // and its first derivatives are those of `(a0 I + a1 A)^-1 b`
1287            // there, which the Krylov iterates would only approximate. `a1`
1288            // multiplies the finished quotient, so its cotangent is
1289            // `<A(x) / a0, g>` and never passes through `1 / a0`.
1290            //
1291            // `A` is applied to `x` itself, so no component of `x` is scaled
1292            // away before `A` sees it. When the image has a NaN or infinite
1293            // component, `A` is applied to `x 2^-s` for the smallest `s` that
1294            // keeps it finite (`A` linear, exact powers of two), and `2^s`
1295            // goes into the quotient. If `x 2^-s` rounds some components of
1296            // `x` away (no single power of two keeps both a huge and a tiny
1297            // component, as for `x = (2^500, 2^-1000)`, `A = 2^600 I`), the
1298            // part it kept, `(x 2^-s) 2^s`, is exact, the rest
1299            // `x - (x 2^-s) 2^s` is exact too, and `A` is applied to that rest
1300            // in the same way: `A(x) / a0` is the sum of the parts' quotients.
1301            //
1302            // Nothing is given up early. The search for `s` covers every
1303            // exponent for which `x 2^-s` keeps a nonzero component, found on
1304            // the scaled vector itself, so it follows the storage precision
1305            // (`2^-1074` for `f64`, `2^-149` for `f32`) and the mantissa of
1306            // the largest component, and parts are taken
1307            // until nothing of `x` is left: each part keeps its largest
1308            // component, so the largest component of the rest drops by at least
1309            // one binade per part and the parts end within about 2100 steps.
1310            // When no exponent in that range makes the image finite, the input
1311            // is outside the range this closed form supports, and the solve
1312            // returns `KrylovError::OutOfRange` naming the operator image,
1313            // never NaN and never a silently dropped component.
1314            let out_of_range = |quantity: &'static str| {
1315                anyhow::Error::new(KrylovError::OutOfRange {
1316                    solver: "gmres",
1317                    quantity,
1318                })
1319            };
1320            const IMAGE: &str = "operator image A(x 2^-s) for every s that keeps x nonzero";
1321            let started = Instant::now();
1322            let mut apply_calls = 0;
1323            let mut quotient_scale_calls = 0;
1324            let mut quotient: Option<T> = None;
1325            let mut remaining = Some(solution.clone());
1326            while let Some(part) = remaining.take() {
1327                apply_calls += 1;
1328                let applied = apply_a(&part)?;
1329                let (image, exponent) = if applied.is_all_finite()? {
1330                    (applied, 0)
1331                } else {
1332                    let Some(limit) = vector_ops::largest_informative_exponent(&part)? else {
1333                        // A(0) is not finite: no scaling helps.
1334                        return Err(out_of_range(IMAGE));
1335                    };
1336                    let (found, calls) =
1337                        vector_ops::smallest_finite_scaling(&apply_a, &part, limit)?;
1338                    apply_calls += calls;
1339                    let Some((exponent, image)) = found else {
1340                        return Err(out_of_range(IMAGE));
1341                    };
1342                    let kept = vector_ops::scale_pow2(
1343                        vector_ops::scale_pow2(part.clone(), -exponent)?,
1344                        exponent,
1345                    )?;
1346                    let lost =
1347                        part.axpby(AnyScalar::new_real(1.0), &kept, AnyScalar::new_real(-1.0))?;
1348                    let lost_largest = lost.maxabs()?;
1349                    if lost_largest > 0.0 {
1350                        // Exact arithmetic halves the largest component at
1351                        // least; a vector type whose `axpby` is not exact
1352                        // (truncating) could fail to shrink and loop.
1353                        // `maxabs` errors on NaN, so both values are ordered.
1354                        if lost_largest >= part.maxabs()? {
1355                            return Err(anyhow::Error::new(KrylovError::NumericalBreakdown {
1356                                solver: "gmres",
1357                                iteration: 0,
1358                                quantity: "closed-form part split (rest did not shrink)",
1359                            }));
1360                        }
1361                        remaining = Some(lost);
1362                    }
1363                    (image, exponent)
1364                };
1365                let (part_quotient, calls) =
1366                    vector_ops::scaled_quotient(image, exponent, &a0, "gmres")?;
1367                quotient_scale_calls += calls;
1368                quotient = Some(match quotient {
1369                    None => part_quotient,
1370                    Some(sum) => sum.axpby(
1371                        AnyScalar::new_real(1.0),
1372                        &part_quotient,
1373                        AnyScalar::new_real(1.0),
1374                    )?,
1375                });
1376            }
1377            let Some(quotient) = quotient else {
1378                return Err(out_of_range(IMAGE));
1379            };
1380            if profile_enabled {
1381                profile.apply += started.elapsed();
1382                profile.apply_calls += apply_calls;
1383            }
1384            let started = Instant::now();
1385            // `dx/da1 = -A(b / a0) / a0` can itself exceed the `f64` range
1386            // (`A = f64::MAX I`, `b = 1`, `a0 = 1/2` gives `-4 f64::MAX`). No
1387            // rescaling makes it representable, and `a1 = 0` times an
1388            // infinite entry would be NaN, so that is reported here.
1389            if !quotient.is_all_finite()? {
1390                return Err(out_of_range("a1 derivative A(x) / a0"));
1391            }
1392            let correction = quotient.scale(AnyScalar::new_real(0.0) - a1.clone())?;
1393            if profile_enabled {
1394                profile.scale += started.elapsed();
1395                profile.scale_calls += quotient_scale_calls + 1;
1396            }
1397            let started = Instant::now();
1398            solution = solution.axpby(
1399                AnyScalar::new_real(1.0),
1400                &correction,
1401                AnyScalar::new_real(1.0),
1402            )?;
1403            if profile_enabled {
1404                profile.axpby += started.elapsed();
1405                profile.axpby_calls += 1;
1406            }
1407        }
1408        // The closed form can lose a subnormal quotient component, so the
1409        // residual is measured rather than assumed to be zero.
1410        let started = Instant::now();
1411        let affine_x = solution.scale(a0.clone())?;
1412        if profile_enabled {
1413            profile.scale += started.elapsed();
1414            profile.scale_calls += 1;
1415        }
1416        let started = Instant::now();
1417        let residual = b.axpby(
1418            AnyScalar::new_real(1.0),
1419            &affine_x,
1420            AnyScalar::new_real(-1.0),
1421        )?;
1422        if profile_enabled {
1423            profile.axpby += started.elapsed();
1424            profile.axpby_calls += 1;
1425        }
1426        let started = Instant::now();
1427        let residual_norm = residual.norm()?;
1428        if profile_enabled {
1429            profile.norm += started.elapsed();
1430            profile.norm_calls += 1;
1431        }
1432        finish!(GmresResult {
1433            solution,
1434            iterations: 0,
1435            residual_norm: tolerance.residual_value(residual_norm, b_norm),
1436            // A zero residual is converged for every tolerance, including
1437            // `rtol = 0`, as on the iterative path.
1438            converged: residual_norm == 0.0 || tolerance.is_converged(residual_norm, b_norm),
1439        });
1440    }
1441
1442    let mut x = x0.clone();
1443
1444    for restart in 0..options.max_restarts {
1445        let started = Instant::now();
1446        let ax = apply_a(&x)?;
1447        if profile_enabled {
1448            profile.apply += started.elapsed();
1449            profile.apply_calls += 1;
1450        }
1451        if restart == 0 {
1452            ax.validate()?;
1453        }
1454        let started = Instant::now();
1455        let affine_x = x.axpby(a0.clone(), &ax, a1.clone())?;
1456        if profile_enabled {
1457            profile.axpby += started.elapsed();
1458            profile.axpby_calls += 1;
1459        }
1460        let started = Instant::now();
1461        let r = b.axpby(
1462            AnyScalar::new_real(1.0),
1463            &affine_x,
1464            AnyScalar::new_real(-1.0),
1465        )?;
1466        if profile_enabled {
1467            profile.axpby += started.elapsed();
1468            profile.axpby_calls += 1;
1469        }
1470        let started = Instant::now();
1471        let r_norm = r.norm()?;
1472        if profile_enabled {
1473            profile.norm += started.elapsed();
1474            profile.norm_calls += 1;
1475        }
1476        let residual_value = tolerance.residual_value(r_norm, b_norm);
1477        if options.verbose {
1478            eprintln!(
1479                "GMRES restart {}: initial residual = {:.6e}",
1480                restart, residual_value
1481            );
1482        }
1483        // A zero initial residual is converged for every tolerance, including
1484        // `0`: the Arnoldi start vector `r / |r|` needs `|r| > 0`.
1485        if r_norm == 0.0 || tolerance.is_converged(r_norm, b_norm) {
1486            finish!(GmresResult {
1487                solution: x,
1488                iterations: total_iters,
1489                residual_norm: residual_value,
1490                converged: true,
1491            });
1492        }
1493
1494        let cycle_max_iter = options.max_iter;
1495        let mut v_basis: Vec<T> =
1496            krylov_workspace(checked_krylov_capacity(cycle_max_iter, "gmres")?, "gmres")?;
1497        let started = Instant::now();
1498        let (v0, scale_calls) = vector_ops::divide_by_norm(&r, r_norm)?;
1499        v_basis.push(v0);
1500        if profile_enabled {
1501            profile.scale += started.elapsed();
1502            profile.scale_calls += scale_calls;
1503        }
1504
1505        let mut h_matrix: Vec<Vec<AnyScalar>> = krylov_workspace(cycle_max_iter, "gmres")?;
1506        let mut cs: Vec<AnyScalar> = krylov_workspace(cycle_max_iter, "gmres")?;
1507        let mut sn: Vec<AnyScalar> = krylov_workspace(cycle_max_iter, "gmres")?;
1508        let mut g: Vec<AnyScalar> =
1509            krylov_workspace(checked_krylov_capacity(cycle_max_iter, "gmres")?, "gmres")?;
1510        g.push(AnyScalar::new_real(r_norm));
1511        let mut solution_already_updated = false;
1512
1513        for j in 0..cycle_max_iter {
1514            total_iters += 1;
1515
1516            let started = Instant::now();
1517            let w = apply_a(&v_basis[j])?;
1518            if profile_enabled {
1519                profile.apply += started.elapsed();
1520                profile.apply_calls += 1;
1521            }
1522            let mut h_a_col: Vec<AnyScalar> = krylov_workspace(j + 2, "gmres")?;
1523            let mut w_orth = w;
1524
1525            for v_i in v_basis.iter().take(j + 1) {
1526                let started = Instant::now();
1527                let h_ij = v_i.inner_product(&w_orth)?;
1528                if profile_enabled {
1529                    profile.inner_product += started.elapsed();
1530                    profile.inner_product_calls += 1;
1531                }
1532                h_a_col.push(h_ij.clone());
1533                let neg_h_ij = AnyScalar::new_real(0.0) - h_ij;
1534                let started = Instant::now();
1535                w_orth = w_orth.axpby(AnyScalar::new_real(1.0), v_i, neg_h_ij)?;
1536                if profile_enabled {
1537                    profile.axpby += started.elapsed();
1538                    profile.axpby_calls += 1;
1539                }
1540            }
1541            for (i, v_i) in v_basis.iter().take(j + 1).enumerate() {
1542                let started = Instant::now();
1543                let correction = v_i.inner_product(&w_orth)?;
1544                if profile_enabled {
1545                    profile.inner_product += started.elapsed();
1546                    profile.inner_product_calls += 1;
1547                }
1548                h_a_col[i] = h_a_col[i].clone() + correction.clone();
1549                let neg_correction = AnyScalar::new_real(0.0) - correction;
1550                let started = Instant::now();
1551                w_orth = w_orth.axpby(AnyScalar::new_real(1.0), v_i, neg_correction)?;
1552                if profile_enabled {
1553                    profile.axpby += started.elapsed();
1554                    profile.axpby_calls += 1;
1555                }
1556            }
1557
1558            let started = Instant::now();
1559            let h_jp1_j_real = w_orth.norm()?;
1560            if profile_enabled {
1561                profile.norm += started.elapsed();
1562                profile.norm_calls += 1;
1563            }
1564            h_a_col.push(AnyScalar::new_real(h_jp1_j_real));
1565
1566            let mut h_col: Vec<AnyScalar> = krylov_workspace(j + 2, "gmres")?;
1567            for h in h_a_col.iter().take(j) {
1568                h_col.push(a1.clone() * h.clone());
1569            }
1570            h_col.push(a0.clone() + a1.clone() * h_a_col[j].clone());
1571            h_col.push(a1.clone() * h_a_col[j + 1].clone());
1572
1573            #[allow(clippy::needless_range_loop)]
1574            for i in 0..j {
1575                let h_i = h_col[i].clone();
1576                let h_ip1 = h_col[i + 1].clone();
1577                let (new_hi, new_hip1) = apply_givens_rotation(&cs[i], &sn[i], &h_i, &h_ip1);
1578                h_col[i] = new_hi;
1579                h_col[i + 1] = new_hip1;
1580            }
1581
1582            let (c_j, s_j) = compute_givens_rotation(&h_col[j], &h_col[j + 1]);
1583            cs.push(c_j.clone());
1584            sn.push(s_j.clone());
1585
1586            let (new_hj, _) = apply_givens_rotation(&c_j, &s_j, &h_col[j], &h_col[j + 1]);
1587            h_col[j] = new_hj;
1588            h_col[j + 1] = AnyScalar::new_real(0.0);
1589
1590            let g_j = g[j].clone();
1591            let g_jp1 = AnyScalar::new_real(0.0);
1592            let (new_gj, new_gjp1) = apply_givens_rotation(&c_j, &s_j, &g_j, &g_jp1);
1593            g[j] = new_gj;
1594            let res_norm = new_gjp1.abs();
1595            g.push(new_gjp1);
1596
1597            h_matrix.push(h_col);
1598            let residual_value = tolerance.residual_value(res_norm, b_norm);
1599            if options.verbose {
1600                eprintln!("GMRES iter {}: residual = {:.6e}", j + 1, residual_value);
1601            }
1602
1603            if tolerance.is_converged(res_norm, b_norm) {
1604                let started = Instant::now();
1605                let y = solve_upper_triangular(&h_matrix, &g[..=j], "gmres")?;
1606                if profile_enabled {
1607                    profile.triangular_solve += started.elapsed();
1608                    profile.triangular_solve_calls += 1;
1609                }
1610                let started = Instant::now();
1611                x = update_solution(&x, &v_basis[..=j], &y)?;
1612                if profile_enabled {
1613                    profile.solution_update += started.elapsed();
1614                    profile.solution_update_calls += 1;
1615                }
1616                if options.check_true_residual {
1617                    let started = Instant::now();
1618                    let ax_check = apply_a(&x)?;
1619                    if profile_enabled {
1620                        profile.apply += started.elapsed();
1621                        profile.apply_calls += 1;
1622                    }
1623                    let started = Instant::now();
1624                    let affine_check = x.axpby(a0.clone(), &ax_check, a1.clone())?;
1625                    if profile_enabled {
1626                        profile.axpby += started.elapsed();
1627                        profile.axpby_calls += 1;
1628                    }
1629                    let started = Instant::now();
1630                    let r_check = b.axpby(
1631                        AnyScalar::new_real(1.0),
1632                        &affine_check,
1633                        AnyScalar::new_real(-1.0),
1634                    )?;
1635                    if profile_enabled {
1636                        profile.axpby += started.elapsed();
1637                        profile.axpby_calls += 1;
1638                    }
1639                    let started = Instant::now();
1640                    let true_abs_res = r_check.norm()?;
1641                    if profile_enabled {
1642                        profile.norm += started.elapsed();
1643                        profile.norm_calls += 1;
1644                    }
1645                    let true_residual_value = tolerance.residual_value(true_abs_res, b_norm);
1646                    if options.verbose {
1647                        eprintln!(
1648                            "GMRES true residual check: hessenberg={:.6e}, checked={:.6e}",
1649                            residual_value, true_residual_value
1650                        );
1651                    }
1652                    if tolerance.is_converged(true_abs_res, b_norm) {
1653                        finish!(GmresResult {
1654                            solution: x,
1655                            iterations: total_iters,
1656                            residual_norm: true_residual_value,
1657                            converged: true,
1658                        });
1659                    }
1660                    solution_already_updated = true;
1661                    break;
1662                } else {
1663                    finish!(GmresResult {
1664                        solution: x,
1665                        iterations: total_iters,
1666                        residual_norm: residual_value,
1667                        converged: true,
1668                    });
1669                }
1670            }
1671
1672            if h_jp1_j_real > 1e-14 {
1673                let started = Instant::now();
1674                let (v_next, scale_calls) = vector_ops::divide_by_norm(&w_orth, h_jp1_j_real)?;
1675                v_basis.push(v_next);
1676                if profile_enabled {
1677                    profile.scale += started.elapsed();
1678                    profile.scale_calls += scale_calls;
1679                }
1680            } else {
1681                let started = Instant::now();
1682                let y = solve_upper_triangular(&h_matrix, &g[..=j], "gmres")?;
1683                if profile_enabled {
1684                    profile.triangular_solve += started.elapsed();
1685                    profile.triangular_solve_calls += 1;
1686                }
1687                let started = Instant::now();
1688                x = update_solution(&x, &v_basis[..=j], &y)?;
1689                if profile_enabled {
1690                    profile.solution_update += started.elapsed();
1691                    profile.solution_update_calls += 1;
1692                }
1693                let started = Instant::now();
1694                let ax_final = apply_a(&x)?;
1695                if profile_enabled {
1696                    profile.apply += started.elapsed();
1697                    profile.apply_calls += 1;
1698                }
1699                let started = Instant::now();
1700                let affine_final = x.axpby(a0.clone(), &ax_final, a1.clone())?;
1701                if profile_enabled {
1702                    profile.axpby += started.elapsed();
1703                    profile.axpby_calls += 1;
1704                }
1705                let started = Instant::now();
1706                let r_final = b.axpby(
1707                    AnyScalar::new_real(1.0),
1708                    &affine_final,
1709                    AnyScalar::new_real(-1.0),
1710                )?;
1711                if profile_enabled {
1712                    profile.axpby += started.elapsed();
1713                    profile.axpby_calls += 1;
1714                }
1715                let started = Instant::now();
1716                let final_abs_res = r_final.norm()?;
1717                if profile_enabled {
1718                    profile.norm += started.elapsed();
1719                    profile.norm_calls += 1;
1720                }
1721                let final_res = tolerance.residual_value(final_abs_res, b_norm);
1722                finish!(GmresResult {
1723                    solution: x,
1724                    iterations: total_iters,
1725                    residual_norm: final_res,
1726                    converged: tolerance.is_converged(final_abs_res, b_norm),
1727                });
1728            }
1729        }
1730
1731        if !solution_already_updated {
1732            let actual_iters = h_matrix.len();
1733            let started = Instant::now();
1734            let y = solve_upper_triangular(&h_matrix, &g[..actual_iters], "gmres")?;
1735            if profile_enabled {
1736                profile.triangular_solve += started.elapsed();
1737                profile.triangular_solve_calls += 1;
1738            }
1739            let started = Instant::now();
1740            x = update_solution(&x, &v_basis[..actual_iters], &y)?;
1741            if profile_enabled {
1742                profile.solution_update += started.elapsed();
1743                profile.solution_update_calls += 1;
1744            }
1745        }
1746    }
1747
1748    let started = Instant::now();
1749    let ax_final = apply_a(&x)?;
1750    if profile_enabled {
1751        profile.apply += started.elapsed();
1752        profile.apply_calls += 1;
1753    }
1754    let started = Instant::now();
1755    let affine_final = x.axpby(a0, &ax_final, a1)?;
1756    if profile_enabled {
1757        profile.axpby += started.elapsed();
1758        profile.axpby_calls += 1;
1759    }
1760    let started = Instant::now();
1761    let r_final = b.axpby(
1762        AnyScalar::new_real(1.0),
1763        &affine_final,
1764        AnyScalar::new_real(-1.0),
1765    )?;
1766    if profile_enabled {
1767        profile.axpby += started.elapsed();
1768        profile.axpby_calls += 1;
1769    }
1770    let started = Instant::now();
1771    let final_abs_res = r_final.norm()?;
1772    if profile_enabled {
1773        profile.norm += started.elapsed();
1774        profile.norm_calls += 1;
1775    }
1776    let final_res = tolerance.residual_value(final_abs_res, b_norm);
1777
1778    finish!(GmresResult {
1779        solution: x,
1780        iterations: total_iters,
1781        residual_norm: final_res,
1782        converged: tolerance.is_converged(final_abs_res, b_norm),
1783    })
1784}
1785
1786/// Solve `A x = b` using GMRES while enforcing a total iteration limit.
1787/// [`GmresOptions::max_iter`] remains the restart cycle length and
1788/// [`GmresOptions::max_restarts`] remains the maximum number of restart cycles.
1789/// `max_total_iter` caps the total number of Arnoldi steps across all restart
1790/// cycles; the final cycle is shortened when necessary.
1791/// # Errors
1792/// Returns an error when `max_iter` needs a Krylov workspace whose capacity
1793/// overflows or cannot be allocated (a [`KrylovError::InvalidOptions`]), when the operator and vectors have
1794/// incompatible shapes, when the affine coefficients are all zero (a
1795/// [`KrylovError::NoAffineCoefficient`] for affine solves), or when an
1796/// underlying tensor or backend operation fails (a [`KrylovError::Operation`]).
1797/// Non-convergence is reported through the result's `converged` flag and does
1798/// not produce an error.
1799/// A right-hand side whose norm is not finite, which would make every relative
1800/// residual zero, is a [`KrylovError::NumericalBreakdown`].
1801///
1802pub fn gmres_with_total_iteration_limit<T, F>(
1803    apply_a: F,
1804    b: &T,
1805    x0: &T,
1806    options: &GmresOptions,
1807    max_total_iter: usize,
1808) -> std::result::Result<GmresResult<T>, KrylovError>
1809where
1810    T: TensorVectorSpace,
1811    F: Fn(&T) -> Result<T>,
1812{
1813    gmres_impl(
1814        apply_a,
1815        b,
1816        x0,
1817        options,
1818        GmresTolerance::Relative(options.rtol),
1819        Some(max_total_iter),
1820    )
1821    .map_err(KrylovError::from_anyhow_with_classification)
1822}
1823
1824fn gmres_impl<T, F>(
1825    apply_a: F,
1826    b: &T,
1827    x0: &T,
1828    options: &GmresOptions,
1829    tolerance: GmresTolerance,
1830    max_total_iter: Option<usize>,
1831) -> Result<GmresResult<T>>
1832where
1833    T: TensorVectorSpace,
1834    F: Fn(&T) -> Result<T>,
1835{
1836    checked_krylov_capacity(options.max_iter, "gmres")?;
1837
1838    // Validate structural consistency of inputs
1839    b.validate()?;
1840    x0.validate()?;
1841
1842    // A norm that overflows would make every relative residual zero.
1843    let b_norm = vector_ops::finite_norm(b, "gmres", 0, "right-hand-side norm")?;
1844    if b_norm == 0.0 {
1845        // The zero vector solves every homogeneous linear system.
1846        return Ok(GmresResult {
1847            solution: b.scale(AnyScalar::new_real(0.0))?,
1848            iterations: 0,
1849            residual_norm: 0.0,
1850            converged: true,
1851        });
1852    }
1853
1854    let mut x = x0.clone();
1855    let mut total_iters = 0;
1856
1857    for _restart in 0..options.max_restarts {
1858        let cycle_max_iter = match max_total_iter {
1859            Some(limit) => {
1860                let remaining = limit.saturating_sub(total_iters);
1861                if remaining == 0 {
1862                    break;
1863                }
1864                options.max_iter.min(remaining)
1865            }
1866            None => options.max_iter,
1867        };
1868        if cycle_max_iter == 0 {
1869            break;
1870        }
1871
1872        // Compute initial residual: r = b - A*x
1873        let ax = apply_a(&x)?;
1874        // Validate operator output on first restart
1875        if _restart == 0 {
1876            ax.validate()?;
1877        }
1878        // r = 1.0 * b + (-1.0) * ax
1879        let r = b.axpby(AnyScalar::new_real(1.0), &ax, AnyScalar::new_real(-1.0))?;
1880        let r_norm = r.norm()?;
1881        let residual_value = tolerance.residual_value(r_norm, b_norm);
1882
1883        if options.verbose {
1884            eprintln!(
1885                "GMRES restart {}: initial residual = {:.6e}",
1886                _restart, residual_value
1887            );
1888        }
1889
1890        // A zero initial residual is converged for every tolerance, including
1891        // `0`: the Arnoldi start vector `r / |r|` needs `|r| > 0`.
1892        if r_norm == 0.0 || tolerance.is_converged(r_norm, b_norm) {
1893            return Ok(GmresResult {
1894                solution: x,
1895                iterations: total_iters,
1896                residual_norm: residual_value,
1897                converged: true,
1898            });
1899        }
1900
1901        // Arnoldi process with modified Gram-Schmidt
1902        let mut v_basis: Vec<T> =
1903            krylov_workspace(checked_krylov_capacity(cycle_max_iter, "gmres")?, "gmres")?;
1904        let mut h_matrix: Vec<Vec<AnyScalar>> = krylov_workspace(cycle_max_iter, "gmres")?;
1905
1906        // v_0 = r / ||r||
1907        let v0 = vector_ops::divide_by_norm(&r, r_norm)?.0;
1908        v_basis.push(v0);
1909
1910        // Initialize Givens rotation storage
1911        let mut cs: Vec<AnyScalar> = krylov_workspace(cycle_max_iter, "gmres")?;
1912        let mut sn: Vec<AnyScalar> = krylov_workspace(cycle_max_iter, "gmres")?;
1913        let mut g: Vec<AnyScalar> =
1914            krylov_workspace(checked_krylov_capacity(cycle_max_iter, "gmres")?, "gmres")?;
1915        g.push(AnyScalar::new_real(r_norm)); // residual in upper Hessenberg space
1916        let mut solution_already_updated = false;
1917
1918        for j in 0..cycle_max_iter {
1919            total_iters += 1;
1920
1921            // w = A * v_j
1922            let w = apply_a(&v_basis[j])?;
1923
1924            // Modified Gram-Schmidt orthogonalization
1925            let mut h_col: Vec<AnyScalar> = krylov_workspace(j + 2, "gmres")?;
1926            let mut w_orth = w;
1927
1928            for v_i in v_basis.iter().take(j + 1) {
1929                let h_ij = v_i.inner_product(&w_orth)?;
1930                h_col.push(h_ij.clone());
1931                // w_orth = w_orth - h_ij * v_i = 1.0 * w_orth + (-h_ij) * v_i
1932                let neg_h_ij = AnyScalar::new_real(0.0) - h_ij;
1933                w_orth = w_orth.axpby(AnyScalar::new_real(1.0), v_i, neg_h_ij)?;
1934            }
1935
1936            // KrylovKit's default orthogonalizer is ModifiedGramSchmidt2.
1937            // The second pass is important for long Krylov bases and complex
1938            // non-Hermitian local problems.
1939            for (i, v_i) in v_basis.iter().take(j + 1).enumerate() {
1940                let correction = v_i.inner_product(&w_orth)?;
1941                h_col[i] = h_col[i].clone() + correction.clone();
1942                let neg_correction = AnyScalar::new_real(0.0) - correction;
1943                w_orth = w_orth.axpby(AnyScalar::new_real(1.0), v_i, neg_correction)?;
1944            }
1945
1946            let h_jp1_j_real = w_orth.norm()?;
1947            let h_jp1_j = AnyScalar::new_real(h_jp1_j_real);
1948            h_col.push(h_jp1_j);
1949
1950            // Apply previous Givens rotations to new column
1951            #[allow(clippy::needless_range_loop)]
1952            for i in 0..j {
1953                let h_i = h_col[i].clone();
1954                let h_ip1 = h_col[i + 1].clone();
1955                let (new_hi, new_hip1) = apply_givens_rotation(&cs[i], &sn[i], &h_i, &h_ip1);
1956                h_col[i] = new_hi;
1957                h_col[i + 1] = new_hip1;
1958            }
1959
1960            // Compute new Givens rotation for h_col[j] and h_col[j+1]
1961            let (c_j, s_j) = compute_givens_rotation(&h_col[j], &h_col[j + 1]);
1962            cs.push(c_j.clone());
1963            sn.push(s_j.clone());
1964
1965            // Apply new rotation to eliminate h_col[j+1]
1966            let (new_hj, _) = apply_givens_rotation(&c_j, &s_j, &h_col[j], &h_col[j + 1]);
1967            h_col[j] = new_hj;
1968            h_col[j + 1] = AnyScalar::new_real(0.0);
1969
1970            // Apply rotation to g
1971            let g_j = g[j].clone();
1972            let g_jp1 = AnyScalar::new_real(0.0);
1973            let (new_gj, new_gjp1) = apply_givens_rotation(&c_j, &s_j, &g_j, &g_jp1);
1974            g[j] = new_gj;
1975            let res_norm = new_gjp1.abs();
1976            g.push(new_gjp1);
1977
1978            h_matrix.push(h_col);
1979
1980            // Check convergence
1981            let residual_value = tolerance.residual_value(res_norm, b_norm);
1982
1983            if options.verbose {
1984                eprintln!("GMRES iter {}: residual = {:.6e}", j + 1, residual_value);
1985            }
1986
1987            if tolerance.is_converged(res_norm, b_norm) {
1988                // Solve upper triangular system and update x
1989                let y = solve_upper_triangular(&h_matrix, &g[..=j], "gmres")?;
1990                x = update_solution(&x, &v_basis[..=j], &y)?;
1991                if options.check_true_residual {
1992                    let ax_check = apply_a(&x)?;
1993                    let r_check = b.axpby(
1994                        AnyScalar::new_real(1.0),
1995                        &ax_check,
1996                        AnyScalar::new_real(-1.0),
1997                    )?;
1998                    let true_abs_res = r_check.norm()?;
1999                    let true_residual_value = tolerance.residual_value(true_abs_res, b_norm);
2000
2001                    if options.verbose {
2002                        eprintln!(
2003                            "GMRES true residual check: hessenberg={:.6e}, checked={:.6e}",
2004                            residual_value, true_residual_value
2005                        );
2006                    }
2007
2008                    if tolerance.is_converged(true_abs_res, b_norm) {
2009                        return Ok(GmresResult {
2010                            solution: x,
2011                            iterations: total_iters,
2012                            residual_norm: true_residual_value,
2013                            converged: true,
2014                        });
2015                    }
2016                    solution_already_updated = true;
2017                    break;
2018                } else {
2019                    return Ok(GmresResult {
2020                        solution: x,
2021                        iterations: total_iters,
2022                        residual_norm: residual_value,
2023                        converged: true,
2024                    });
2025                }
2026            }
2027
2028            // Add new basis vector (if not converged and h_jp1_j is not too small)
2029            if h_jp1_j_real > 1e-14 {
2030                let v_jp1 = vector_ops::divide_by_norm(&w_orth, h_jp1_j_real)?.0;
2031                v_basis.push(v_jp1);
2032            } else {
2033                // Lucky breakdown - we've found the exact solution in the Krylov subspace
2034                let y = solve_upper_triangular(&h_matrix, &g[..=j], "gmres")?;
2035                x = update_solution(&x, &v_basis[..=j], &y)?;
2036                let ax_final = apply_a(&x)?;
2037                let r_final = b.axpby(
2038                    AnyScalar::new_real(1.0),
2039                    &ax_final,
2040                    AnyScalar::new_real(-1.0),
2041                )?;
2042                let final_abs_res = r_final.norm()?;
2043                let final_res = tolerance.residual_value(final_abs_res, b_norm);
2044                return Ok(GmresResult {
2045                    solution: x,
2046                    iterations: total_iters,
2047                    residual_norm: final_res,
2048                    converged: tolerance.is_converged(final_abs_res, b_norm),
2049                });
2050            }
2051        }
2052
2053        // End of restart cycle - update x with current solution
2054        if !solution_already_updated {
2055            let actual_iters = h_matrix.len();
2056            let y = solve_upper_triangular(&h_matrix, &g[..actual_iters], "gmres")?;
2057            x = update_solution(&x, &v_basis[..actual_iters], &y)?;
2058        }
2059    }
2060
2061    // Compute final residual
2062    let ax_final = apply_a(&x)?;
2063    let r_final = b.axpby(
2064        AnyScalar::new_real(1.0),
2065        &ax_final,
2066        AnyScalar::new_real(-1.0),
2067    )?;
2068    let final_abs_res = r_final.norm()?;
2069    let final_res = tolerance.residual_value(final_abs_res, b_norm);
2070
2071    Ok(GmresResult {
2072        solution: x,
2073        iterations: total_iters,
2074        residual_norm: final_res,
2075        converged: tolerance.is_converged(final_abs_res, b_norm),
2076    })
2077}
2078
2079/// Solve `A x = b` using GMRES with optional truncation after each iteration.
2080/// This is an extension of [`gmres`] that allows truncating Krylov basis vectors
2081/// to control bond dimension growth in tensor network representations.
2082/// # Type Parameters
2083/// * `T` - A tensor type implementing `TensorVectorSpace`
2084/// * `F` - A function that applies the linear operator: `F(x) = A x`
2085/// * `Tr` - A function that truncates a tensor in-place: `Tr(&mut x)`
2086/// # Arguments
2087/// * `apply_a` - Function that applies the linear operator A to a tensor
2088/// * `b` - Right-hand side tensor
2089/// * `x0` - Initial guess
2090/// * `options` - Solver options
2091/// * `truncate` - Function that truncates a tensor to control bond dimension
2092/// # Note
2093/// Truncation is applied after each Gram-Schmidt orthogonalization step
2094/// and after the final solution update. This helps control the bond dimension
2095/// growth that would otherwise occur in MPS/MPO representations.
2096/// # Errors
2097/// Returns an error when `max_iter` needs a Krylov workspace whose capacity
2098/// overflows or cannot be allocated (a [`KrylovError::InvalidOptions`]), when the operator and vectors have
2099/// incompatible shapes, when the affine coefficients are all zero (a
2100/// [`KrylovError::NoAffineCoefficient`] for affine solves), or when an
2101/// underlying tensor or backend operation fails (a [`KrylovError::Operation`]).
2102/// Non-convergence is reported through the result's `converged` flag and does
2103/// not produce an error.
2104/// A right-hand side whose norm is not finite, which would make every relative
2105/// residual zero, is a [`KrylovError::NumericalBreakdown`].
2106/// # Examples
2107/// Solve `2x = b` with a no-op truncation function:
2108/// ```
2109/// use tensor4all_core::{DynIndex, IdxTensor, TensorVectorSpace, AnyScalar};
2110/// use tensor4all_core::krylov::{gmres_with_truncation, GmresOptions};
2111/// let i = DynIndex::new_dyn(2);
2112/// let b = IdxTensor::from_dense(vec![i.clone()], vec![4.0, 6.0]).unwrap();
2113/// let x0 = IdxTensor::from_dense(vec![i.clone()], vec![0.0, 0.0]).unwrap();
2114/// // Operator A = 2*I (scales input by 2)
2115/// let apply_a = |x: &IdxTensor| {
2116///     x.scale(AnyScalar::new_real(2.0)).map_err(anyhow::Error::from)
2117/// };
2118/// // No-op truncation
2119/// let truncate = |_x: &mut IdxTensor| Ok(());
2120/// let result = gmres_with_truncation(apply_a, &b, &x0, &GmresOptions::default(), truncate).unwrap();
2121/// assert!(result.converged);
2122/// // Solution should be [2.0, 3.0]
2123/// let expected = IdxTensor::from_dense(vec![i], vec![2.0, 3.0]).unwrap();
2124/// assert!(result.solution.sub(&expected).unwrap().maxabs().unwrap() < 1e-8);
2125/// ```
2126pub fn gmres_with_truncation<T, F, Tr>(
2127    apply_a: F,
2128    b: &T,
2129    x0: &T,
2130    options: &GmresOptions,
2131    truncate: Tr,
2132) -> std::result::Result<GmresResult<T>, KrylovError>
2133where
2134    T: TensorVectorSpace,
2135    F: Fn(&T) -> Result<T>,
2136    Tr: Fn(&mut T) -> Result<()>,
2137{
2138    gmres_with_truncation_impl(apply_a, b, x0, options, truncate)
2139        .map_err(KrylovError::from_anyhow_with_classification)
2140}
2141
2142fn gmres_with_truncation_impl<T, F, Tr>(
2143    apply_a: F,
2144    b: &T,
2145    x0: &T,
2146    options: &GmresOptions,
2147    truncate: Tr,
2148) -> Result<GmresResult<T>>
2149where
2150    T: TensorVectorSpace,
2151    F: Fn(&T) -> Result<T>,
2152    Tr: Fn(&mut T) -> Result<()>,
2153{
2154    checked_krylov_capacity(options.max_iter, "gmres_with_truncation")?;
2155
2156    // Validate structural consistency of inputs
2157    b.validate()?;
2158    x0.validate()?;
2159
2160    // A norm that overflows would make every relative residual zero.
2161    let b_norm = vector_ops::finite_norm(b, "gmres", 0, "right-hand-side norm")?;
2162    if b_norm == 0.0 {
2163        return Ok(GmresResult {
2164            solution: b.scale(AnyScalar::new_real(0.0))?,
2165            iterations: 0,
2166            residual_norm: 0.0,
2167            converged: true,
2168        });
2169    }
2170
2171    let mut x = x0.clone();
2172    let mut total_iters = 0;
2173
2174    for _restart in 0..options.max_restarts {
2175        let ax = apply_a(&x)?;
2176        // Validate operator output on first restart
2177        if _restart == 0 {
2178            ax.validate()?;
2179        }
2180        let mut r = b.axpby(AnyScalar::new_real(1.0), &ax, AnyScalar::new_real(-1.0))?;
2181        truncate(&mut r)?;
2182        let r_norm = r.norm()?;
2183        let rel_res = r_norm / b_norm;
2184
2185        if options.verbose {
2186            eprintln!(
2187                "GMRES restart {}: initial residual = {:.6e}",
2188                _restart, rel_res
2189            );
2190        }
2191
2192        // A zero residual is converged for every `rtol`, including `0`.
2193        if r_norm == 0.0 || rel_res < options.rtol {
2194            return Ok(GmresResult {
2195                solution: x,
2196                iterations: total_iters,
2197                residual_norm: rel_res,
2198                converged: true,
2199            });
2200        }
2201
2202        let mut v_basis: Vec<T> = krylov_workspace(
2203            checked_krylov_capacity(options.max_iter, "gmres_with_truncation")?,
2204            "gmres_with_truncation",
2205        )?;
2206        let mut h_matrix: Vec<Vec<AnyScalar>> =
2207            krylov_workspace(options.max_iter, "gmres_with_truncation")?;
2208
2209        let mut v0 = vector_ops::divide_by_norm(&r, r_norm)?.0;
2210        truncate(&mut v0)?;
2211        // After truncation, v0 might not be unit norm and might point in a different direction.
2212        // We need to:
2213        // 1. Renormalize v0 to unit norm for numerical stability
2214        // 2. Recompute g[0] = <r, v0> to maintain the correct relationship
2215        let v0_norm = v0.norm()?;
2216        let effective_g0 = if v0_norm > 1e-15 {
2217            v0 = vector_ops::divide_by_norm(&v0, v0_norm)?.0;
2218            // g[0] should be the component of r in the direction of v0
2219            // Since r was truncated and v0 = truncate(r/||r||)/||truncate(r/||r||)||,
2220            // g[0] = <r, v0> ≈ ||r|| * ||truncate(r/||r||)|| = r_norm * v0_norm
2221            r_norm * v0_norm
2222        } else {
2223            r_norm
2224        };
2225        v_basis.push(v0);
2226
2227        let mut cs: Vec<AnyScalar> = krylov_workspace(options.max_iter, "gmres_with_truncation")?;
2228        let mut sn: Vec<AnyScalar> = krylov_workspace(options.max_iter, "gmres_with_truncation")?;
2229        let mut g: Vec<AnyScalar> = krylov_workspace(
2230            checked_krylov_capacity(options.max_iter, "gmres_with_truncation")?,
2231            "gmres_with_truncation",
2232        )?;
2233        g.push(AnyScalar::new_real(effective_g0));
2234        let mut solution_already_updated = false;
2235
2236        for j in 0..options.max_iter {
2237            total_iters += 1;
2238
2239            let w = apply_a(&v_basis[j])?;
2240
2241            let mut h_col: Vec<AnyScalar> = krylov_workspace(j + 2, "gmres_with_truncation")?;
2242            let mut w_orth = w;
2243
2244            for v_i in v_basis.iter().take(j + 1) {
2245                let h_ij = v_i.inner_product(&w_orth)?;
2246                h_col.push(h_ij.clone());
2247                let neg_h_ij = AnyScalar::new_real(0.0) - h_ij;
2248                w_orth = w_orth.axpby(AnyScalar::new_real(1.0), v_i, neg_h_ij)?;
2249            }
2250
2251            // Iterative reorthogonalization with truncation
2252            // Truncation can change the direction of w_orth, breaking orthogonality.
2253            // We iterate until all corrections are below a threshold to ensure
2254            // the Krylov basis remains orthogonal despite truncation.
2255            const REORTH_THRESHOLD: f64 = 1e-12;
2256            const MAX_REORTH_ITERS: usize = 10;
2257
2258            let mut reorth_iter_count = 0;
2259            for reorth_iter in 0..MAX_REORTH_ITERS {
2260                reorth_iter_count = reorth_iter + 1;
2261                let norm_before_truncate = w_orth.norm()?;
2262                truncate(&mut w_orth)?;
2263                let norm_after_truncate = w_orth.norm()?;
2264
2265                let mut max_correction = 0.0;
2266                for (i, v_i) in v_basis.iter().enumerate() {
2267                    let correction = v_i.inner_product(&w_orth)?;
2268                    let correction_abs = correction.abs();
2269                    if correction_abs > max_correction {
2270                        max_correction = correction_abs;
2271                    }
2272                    if correction_abs > REORTH_THRESHOLD {
2273                        let neg_correction = AnyScalar::new_real(0.0) - correction.clone();
2274                        w_orth = w_orth.axpby(AnyScalar::new_real(1.0), v_i, neg_correction)?;
2275                        // Update Hessenberg matrix entry to include correction
2276                        h_col[i] = h_col[i].clone() + correction;
2277                    }
2278                }
2279
2280                if options.verbose {
2281                    eprintln!(
2282                        "  reorth iter {}: norm {:.6e} -> {:.6e}, max_correction = {:.6e}",
2283                        reorth_iter, norm_before_truncate, norm_after_truncate, max_correction
2284                    );
2285                }
2286
2287                // If all corrections are small enough, we're done
2288                if max_correction < REORTH_THRESHOLD {
2289                    break;
2290                }
2291            }
2292
2293            if options.verbose && reorth_iter_count > 1 {
2294                eprintln!("  (needed {} reorth iterations)", reorth_iter_count);
2295            }
2296
2297            let h_jp1_j_real = w_orth.norm()?;
2298            let h_jp1_j = AnyScalar::new_real(h_jp1_j_real);
2299            h_col.push(h_jp1_j);
2300
2301            #[allow(clippy::needless_range_loop)]
2302            for i in 0..j {
2303                let h_i = h_col[i].clone();
2304                let h_ip1 = h_col[i + 1].clone();
2305                let (new_hi, new_hip1) = apply_givens_rotation(&cs[i], &sn[i], &h_i, &h_ip1);
2306                h_col[i] = new_hi;
2307                h_col[i + 1] = new_hip1;
2308            }
2309
2310            let (c_j, s_j) = compute_givens_rotation(&h_col[j], &h_col[j + 1]);
2311            cs.push(c_j.clone());
2312            sn.push(s_j.clone());
2313
2314            let (new_hj, _) = apply_givens_rotation(&c_j, &s_j, &h_col[j], &h_col[j + 1]);
2315            h_col[j] = new_hj;
2316            h_col[j + 1] = AnyScalar::new_real(0.0);
2317
2318            let g_j = g[j].clone();
2319            let g_jp1 = AnyScalar::new_real(0.0);
2320            let (new_gj, new_gjp1) = apply_givens_rotation(&c_j, &s_j, &g_j, &g_jp1);
2321            g[j] = new_gj;
2322            let res_norm = new_gjp1.abs();
2323            g.push(new_gjp1);
2324
2325            h_matrix.push(h_col);
2326
2327            let rel_res = res_norm / b_norm;
2328
2329            if options.verbose {
2330                eprintln!("GMRES iter {}: residual = {:.6e}", j + 1, rel_res);
2331            }
2332
2333            if rel_res < options.rtol {
2334                let y = solve_upper_triangular(&h_matrix, &g[..=j], "gmres_with_truncation")?;
2335                x = update_solution_truncated(&x, &v_basis[..=j], &y, &truncate)?;
2336
2337                if options.check_true_residual {
2338                    // Verify with true residual to prevent false convergence
2339                    let ax_check = apply_a(&x)?;
2340                    let mut r_check = b.axpby(
2341                        AnyScalar::new_real(1.0),
2342                        &ax_check,
2343                        AnyScalar::new_real(-1.0),
2344                    )?;
2345                    truncate(&mut r_check)?;
2346                    let true_rel_res = r_check.norm()? / b_norm;
2347
2348                    if options.verbose {
2349                        eprintln!(
2350                            "GMRES true residual check: hessenberg={:.6e}, checked={:.6e}",
2351                            rel_res, true_rel_res
2352                        );
2353                    }
2354
2355                    if true_rel_res < options.rtol {
2356                        return Ok(GmresResult {
2357                            solution: x,
2358                            iterations: total_iters,
2359                            residual_norm: true_rel_res,
2360                            converged: true,
2361                        });
2362                    }
2363                    // False convergence detected: x is already updated above,
2364                    // so skip the end-of-cycle update and go to next restart
2365                    solution_already_updated = true;
2366                    break;
2367                } else {
2368                    return Ok(GmresResult {
2369                        solution: x,
2370                        iterations: total_iters,
2371                        residual_norm: rel_res,
2372                        converged: true,
2373                    });
2374                }
2375            }
2376
2377            if h_jp1_j_real > 1e-14 {
2378                // Create v_{j+1} = w_orth / ||w_orth||
2379                // w_orth has already been truncated twice (after orthogonalization and after reorthogonalization)
2380                // so we don't need to truncate again. Scale doesn't increase bond dimensions.
2381                let v_jp1 = vector_ops::divide_by_norm(&w_orth, h_jp1_j_real)?.0;
2382                // v_jp1 should have norm ~1.0 by construction
2383                // The Arnoldi relation h_{j+1,j} * v_{j+1} = w_orth is maintained exactly
2384                v_basis.push(v_jp1);
2385            } else {
2386                let y = solve_upper_triangular(&h_matrix, &g[..=j], "gmres_with_truncation")?;
2387                x = update_solution_truncated(&x, &v_basis[..=j], &y, &truncate)?;
2388                let ax_final = apply_a(&x)?;
2389                let r_final = b.axpby(
2390                    AnyScalar::new_real(1.0),
2391                    &ax_final,
2392                    AnyScalar::new_real(-1.0),
2393                )?;
2394                let final_res = r_final.norm()? / b_norm;
2395                return Ok(GmresResult {
2396                    solution: x,
2397                    iterations: total_iters,
2398                    residual_norm: final_res,
2399                    converged: final_res < options.rtol,
2400                });
2401            }
2402        }
2403
2404        if !solution_already_updated {
2405            let actual_iters = v_basis.len().min(options.max_iter);
2406            let y = solve_upper_triangular(&h_matrix, &g[..actual_iters], "gmres_with_truncation")?;
2407            x = update_solution_truncated(&x, &v_basis[..actual_iters], &y, &truncate)?;
2408        }
2409    }
2410
2411    let ax_final = apply_a(&x)?;
2412    let r_final = b.axpby(
2413        AnyScalar::new_real(1.0),
2414        &ax_final,
2415        AnyScalar::new_real(-1.0),
2416    )?;
2417    let final_res = r_final.norm()? / b_norm;
2418
2419    Ok(GmresResult {
2420        solution: x,
2421        iterations: total_iters,
2422        residual_norm: final_res,
2423        converged: final_res < options.rtol,
2424    })
2425}
2426
2427/// Options for restarted GMRES with truncation.
2428/// This is used by [`restart_gmres_with_truncation`] which wraps the standard GMRES
2429/// with an outer loop that recomputes the true residual at each restart.
2430/// # Examples
2431/// ```
2432/// use tensor4all_core::krylov::RestartGmresOptions;
2433/// let opts = RestartGmresOptions::new()
2434///     .with_max_outer_iters(10)
2435///     .with_rtol(1e-6)
2436///     .with_inner_max_iter(20)
2437///     .with_inner_max_restarts(2)
2438///     .with_min_reduction(0.99)
2439///     .with_inner_rtol(0.01)
2440///     .with_verbose(false);
2441/// assert_eq!(opts.max_outer_iters, 10);
2442/// assert_eq!(opts.rtol, 1e-6);
2443/// assert_eq!(opts.inner_max_iter, 20);
2444/// assert_eq!(opts.inner_max_restarts, 2);
2445/// assert_eq!(opts.min_reduction, Some(0.99));
2446/// assert_eq!(opts.inner_rtol, Some(0.01));
2447/// ```
2448#[derive(Debug, Clone)]
2449pub struct RestartGmresOptions {
2450    /// Maximum number of outer restart iterations.
2451    /// Default: 20
2452    pub max_outer_iters: usize,
2453
2454    /// Convergence tolerance for relative residual norm (based on true residual).
2455    /// The solver stops when `||b - A*x|| / ||b|| < rtol`.
2456    /// Default: 1e-10
2457    pub rtol: f64,
2458
2459    /// Maximum iterations per inner GMRES cycle.
2460    /// Default: 10
2461    pub inner_max_iter: usize,
2462
2463    /// Number of restarts within each inner GMRES (usually 0).
2464    /// Default: 0
2465    pub inner_max_restarts: usize,
2466
2467    /// Stagnation detection threshold.
2468    /// If the residual reduction ratio exceeds this value (i.e., residual doesn't decrease enough),
2469    /// the solver considers it stagnated.
2470    /// For example, 0.99 means stagnation is detected when residual decreases by less than 1%.
2471    /// Default: None (no stagnation detection)
2472    pub min_reduction: Option<f64>,
2473
2474    /// Inner GMRES relative tolerance.
2475    /// If None, uses 0.1 (solve inner problem loosely).
2476    /// Default: None
2477    pub inner_rtol: Option<f64>,
2478
2479    /// Whether to print convergence information.
2480    /// Default: false
2481    pub verbose: bool,
2482}
2483
2484impl Default for RestartGmresOptions {
2485    fn default() -> Self {
2486        Self {
2487            max_outer_iters: 20,
2488            rtol: 1e-10,
2489            inner_max_iter: 10,
2490            inner_max_restarts: 0,
2491            min_reduction: None,
2492            inner_rtol: None,
2493            verbose: false,
2494        }
2495    }
2496}
2497
2498impl RestartGmresOptions {
2499    /// Create new options with default values.
2500    pub fn new() -> Self {
2501        Self::default()
2502    }
2503
2504    /// Set maximum number of outer iterations.
2505    pub fn with_max_outer_iters(mut self, max_outer_iters: usize) -> Self {
2506        self.max_outer_iters = max_outer_iters;
2507        self
2508    }
2509
2510    /// Set convergence tolerance.
2511    pub fn with_rtol(mut self, rtol: f64) -> Self {
2512        self.rtol = rtol;
2513        self
2514    }
2515
2516    /// Set maximum iterations per inner GMRES cycle.
2517    pub fn with_inner_max_iter(mut self, inner_max_iter: usize) -> Self {
2518        self.inner_max_iter = inner_max_iter;
2519        self
2520    }
2521
2522    /// Set number of restarts within each inner GMRES.
2523    pub fn with_inner_max_restarts(mut self, inner_max_restarts: usize) -> Self {
2524        self.inner_max_restarts = inner_max_restarts;
2525        self
2526    }
2527
2528    /// Set stagnation detection threshold.
2529    pub fn with_min_reduction(mut self, min_reduction: f64) -> Self {
2530        self.min_reduction = Some(min_reduction);
2531        self
2532    }
2533
2534    /// Set inner GMRES relative tolerance.
2535    pub fn with_inner_rtol(mut self, inner_rtol: f64) -> Self {
2536        self.inner_rtol = Some(inner_rtol);
2537        self
2538    }
2539
2540    /// Enable verbose output.
2541    pub fn with_verbose(mut self, verbose: bool) -> Self {
2542        self.verbose = verbose;
2543        self
2544    }
2545}
2546
2547/// Result of restarted GMRES solver.
2548/// # Examples
2549/// ```
2550/// use tensor4all_core::{DynIndex, IdxTensor, AnyScalar};
2551/// use tensor4all_core::krylov::{restart_gmres_with_truncation, RestartGmresOptions};
2552/// let i = DynIndex::new_dyn(2);
2553/// let b = IdxTensor::from_dense(vec![i.clone()], vec![3.0, 5.0]).unwrap();
2554/// let apply_a = |x: &IdxTensor| {
2555///     x.scale(AnyScalar::new_real(3.0)).map_err(anyhow::Error::from)
2556/// };
2557/// let truncate = |_x: &mut IdxTensor| Ok(());
2558/// let result = restart_gmres_with_truncation(
2559///     apply_a, &b, None, &RestartGmresOptions::default(), truncate,
2560/// ).unwrap();
2561/// assert!(result.converged);
2562/// assert!(result.residual_norm < 1e-10);
2563/// assert!(result.outer_iterations <= 20);
2564/// ```
2565#[derive(Debug, Clone)]
2566pub struct RestartGmresResult<T> {
2567    /// The solution vector.
2568    pub solution: T,
2569
2570    /// Total number of inner GMRES iterations performed.
2571    pub iterations: usize,
2572
2573    /// Number of outer restart iterations performed.
2574    pub outer_iterations: usize,
2575
2576    /// Final relative residual norm (true residual).
2577    pub residual_norm: f64,
2578
2579    /// Whether the solver converged.
2580    pub converged: bool,
2581}
2582
2583/// Solve `A x = b` using restarted GMRES with truncation.
2584/// This wraps [`gmres_with_truncation`] with an outer loop that recomputes the true residual
2585/// at each restart. This is particularly useful for MPS/MPO computations where truncation
2586/// can cause the inner GMRES residual to be inaccurate.
2587/// # Algorithm
2588/// ```text
2589/// for outer_iter in 0..max_outer_iters:
2590///     r = b - A*x0          // Compute true residual
2591///     r = truncate(r)
2592///     if ||r|| / ||b|| < rtol:
2593///         return x0         // Converged
2594///     x' = gmres_with_truncation(A, r, 0, inner_options, truncate)
2595///     x0 = truncate(x0 + x')
2596/// ```
2597/// # Type Parameters
2598/// * `T` - A tensor type implementing `TensorVectorSpace`
2599/// * `F` - A function that applies the linear operator: `F(x) = A x`
2600/// * `Tr` - A function that truncates a tensor in-place: `Tr(&mut x)`
2601/// # Arguments
2602/// * `apply_a` - Function that applies the linear operator A to a tensor
2603/// * `b` - Right-hand side tensor
2604/// * `x0` - Initial guess (if None, starts from zero)
2605/// * `options` - Solver options
2606/// * `truncate` - Function that truncates a tensor to control bond dimension
2607/// # Returns
2608/// A `RestartGmresResult` containing the solution and convergence information.
2609/// # Errors
2610/// Returns an error when `max_iter` needs a Krylov workspace whose capacity
2611/// overflows or cannot be allocated (a [`KrylovError::InvalidOptions`]), when the operator and vectors have
2612/// incompatible shapes, when the affine coefficients are all zero (a
2613/// [`KrylovError::NoAffineCoefficient`] for affine solves), or when an
2614/// underlying tensor or backend operation fails (a [`KrylovError::Operation`]).
2615/// Non-convergence is reported through the result's `converged` flag and does
2616/// not produce an error.
2617/// A right-hand side whose norm is not finite, which would make every relative
2618/// residual zero, is a [`KrylovError::NumericalBreakdown`].
2619/// # Examples
2620/// Solve `5x = b` with no truncation:
2621/// ```
2622/// use tensor4all_core::{DynIndex, IdxTensor, TensorVectorSpace, AnyScalar};
2623/// use tensor4all_core::krylov::{restart_gmres_with_truncation, RestartGmresOptions};
2624/// let i = DynIndex::new_dyn(3);
2625/// let b = IdxTensor::from_dense(vec![i.clone()], vec![5.0, 10.0, 15.0]).unwrap();
2626/// let apply_a = |x: &IdxTensor| {
2627///     x.scale(AnyScalar::new_real(5.0)).map_err(anyhow::Error::from)
2628/// };
2629/// let truncate = |_x: &mut IdxTensor| Ok(());
2630/// let result = restart_gmres_with_truncation(
2631///     apply_a, &b, None, &RestartGmresOptions::default(), truncate,
2632/// ).unwrap();
2633/// assert!(result.converged);
2634/// let expected = IdxTensor::from_dense(vec![i], vec![1.0, 2.0, 3.0]).unwrap();
2635/// assert!(result.solution.sub(&expected).unwrap().maxabs().unwrap() < 1e-8);
2636/// ```
2637pub fn restart_gmres_with_truncation<T, F, Tr>(
2638    apply_a: F,
2639    b: &T,
2640    x0: Option<&T>,
2641    options: &RestartGmresOptions,
2642    truncate: Tr,
2643) -> std::result::Result<RestartGmresResult<T>, KrylovError>
2644where
2645    T: TensorVectorSpace,
2646    F: Fn(&T) -> Result<T>,
2647    Tr: Fn(&mut T) -> Result<()>,
2648{
2649    restart_gmres_with_truncation_impl(apply_a, b, x0, options, truncate)
2650        .map_err(KrylovError::from_anyhow_with_classification)
2651}
2652
2653fn restart_gmres_with_truncation_impl<T, F, Tr>(
2654    apply_a: F,
2655    b: &T,
2656    x0: Option<&T>,
2657    options: &RestartGmresOptions,
2658    truncate: Tr,
2659) -> Result<RestartGmresResult<T>>
2660where
2661    T: TensorVectorSpace,
2662    F: Fn(&T) -> Result<T>,
2663    Tr: Fn(&mut T) -> Result<()>,
2664{
2665    // Validate structural consistency of inputs
2666    b.validate()?;
2667    if let Some(x) = x0 {
2668        x.validate()?;
2669    }
2670
2671    // A norm that overflows would make every relative residual zero.
2672    let b_norm = vector_ops::finite_norm(
2673        b,
2674        "restart_gmres_with_truncation",
2675        0,
2676        "right-hand-side norm",
2677    )?;
2678    if b_norm == 0.0 {
2679        let solution = b.scale(AnyScalar::new_real(0.0))?;
2680        return Ok(RestartGmresResult {
2681            solution,
2682            iterations: 0,
2683            outer_iterations: 0,
2684            residual_norm: 0.0,
2685            converged: true,
2686        });
2687    }
2688
2689    // Initialize x: use x0 if provided, otherwise start from zero.
2690    // Track whether x is zero to avoid unnecessary bond dimension doubling
2691    // when adding the first correction via axpby.
2692    let mut x_is_zero = x0.is_none();
2693    let mut x = match x0 {
2694        Some(x) => x.clone(),
2695        None => b.scale(AnyScalar::new_real(0.0))?,
2696    };
2697
2698    let mut total_inner_iters = 0;
2699    let mut prev_residual_norm = f64::INFINITY;
2700
2701    // Inner GMRES options
2702    let inner_options = GmresOptions {
2703        max_iter: options.inner_max_iter,
2704        rtol: options.inner_rtol.unwrap_or(0.1), // Solve loosely by default
2705        max_restarts: options.inner_max_restarts.checked_add(1).ok_or_else(|| {
2706            anyhow::Error::new(KrylovError::InvalidOptions {
2707                solver: "restart_gmres_with_truncation",
2708                reason: "inner_max_restarts + 1 overflows usize".to_string(),
2709            })
2710        })?, // +1 because max_restarts=0 means 1 cycle
2711        verbose: options.verbose,
2712        check_true_residual: true, // Always check in restart context to avoid false convergence
2713    };
2714
2715    for outer_iter in 0..options.max_outer_iters {
2716        // Compute true residual: r = b - A*x
2717        let ax = apply_a(&x)?;
2718        // Validate operator output on first outer iteration
2719        if outer_iter == 0 {
2720            ax.validate()?;
2721        }
2722        let mut r = b.axpby(AnyScalar::new_real(1.0), &ax, AnyScalar::new_real(-1.0))?;
2723        truncate(&mut r)?;
2724
2725        let r_norm = r.norm()?;
2726        let rel_res = r_norm / b_norm;
2727
2728        if options.verbose {
2729            eprintln!(
2730                "Restart GMRES outer iter {}: true residual = {:.6e}",
2731                outer_iter, rel_res
2732            );
2733        }
2734
2735        // Check convergence
2736        if rel_res < options.rtol {
2737            return Ok(RestartGmresResult {
2738                solution: x,
2739                iterations: total_inner_iters,
2740                outer_iterations: outer_iter,
2741                residual_norm: rel_res,
2742                converged: true,
2743            });
2744        }
2745
2746        // Check stagnation
2747        if let Some(min_reduction) = options.min_reduction {
2748            if outer_iter > 0 && rel_res > prev_residual_norm * min_reduction {
2749                if options.verbose {
2750                    eprintln!(
2751                        "Restart GMRES stagnated: residual ratio = {:.6e} > {:.6e}",
2752                        rel_res / prev_residual_norm,
2753                        min_reduction
2754                    );
2755                }
2756                return Ok(RestartGmresResult {
2757                    solution: x,
2758                    iterations: total_inner_iters,
2759                    outer_iterations: outer_iter,
2760                    residual_norm: rel_res,
2761                    converged: false,
2762                });
2763            }
2764        }
2765        prev_residual_norm = rel_res;
2766
2767        // Solve A*x' = r using inner GMRES with zero initial guess
2768        // The zero initial guess is created by scaling r by 0
2769        let zero = r.scale(AnyScalar::new_real(0.0))?;
2770        let inner_result =
2771            gmres_with_truncation_impl(&apply_a, &r, &zero, &inner_options, &truncate)?;
2772
2773        total_inner_iters += inner_result.iterations;
2774
2775        if options.verbose {
2776            eprintln!(
2777                "  Inner GMRES: {} iterations, residual = {:.6e}, converged = {}",
2778                inner_result.iterations, inner_result.residual_norm, inner_result.converged
2779            );
2780        }
2781
2782        // Update solution: x = x + x'
2783        // When x is zero (first iteration with no initial guess), use x' directly
2784        // to avoid bond dimension doubling from axpby with a zero tensor.
2785        if x_is_zero {
2786            x = inner_result.solution;
2787            x_is_zero = false;
2788        } else {
2789            x = x.axpby(
2790                AnyScalar::new_real(1.0),
2791                &inner_result.solution,
2792                AnyScalar::new_real(1.0),
2793            )?;
2794        }
2795        truncate(&mut x)?;
2796    }
2797
2798    // Did not converge within max_outer_iters
2799    // Compute final residual
2800    let ax = apply_a(&x)?;
2801    let mut r = b.axpby(AnyScalar::new_real(1.0), &ax, AnyScalar::new_real(-1.0))?;
2802    truncate(&mut r)?;
2803    let final_rel_res = r.norm()? / b_norm;
2804
2805    Ok(RestartGmresResult {
2806        solution: x,
2807        iterations: total_inner_iters,
2808        outer_iterations: options.max_outer_iters,
2809        residual_norm: final_rel_res,
2810        converged: false,
2811    })
2812}
2813
2814fn validate_hermitian_lanczos_options(options: &HermitianLanczosOptions) -> Result<usize> {
2815    if options.max_iter == 0 {
2816        return Err(anyhow::Error::new(KrylovError::InvalidOptions {
2817            solver: "hermitian_lanczos_lowest_eigenpair",
2818            reason: "max_iter must be greater than zero".to_string(),
2819        }));
2820    }
2821    let basis_capacity =
2822        checked_krylov_capacity(options.max_iter, "hermitian_lanczos_lowest_eigenpair")?;
2823    anyhow::ensure!(
2824        options.rtol.is_finite() && options.rtol >= 0.0,
2825        "hermitian_lanczos_lowest_eigenpair: rtol must be finite and non-negative"
2826    );
2827    anyhow::ensure!(
2828        options.atol.is_finite() && options.atol >= 0.0,
2829        "hermitian_lanczos_lowest_eigenpair: atol must be finite and non-negative"
2830    );
2831    anyhow::ensure!(
2832        options.breakdown_tol.is_finite() && options.breakdown_tol >= 0.0,
2833        "hermitian_lanczos_lowest_eigenpair: breakdown_tol must be finite and non-negative"
2834    );
2835    anyhow::ensure!(
2836        options.hermitian_tol.is_finite() && options.hermitian_tol >= 0.0,
2837        "hermitian_lanczos_lowest_eigenpair: hermitian_tol must be finite and non-negative"
2838    );
2839    Ok(basis_capacity)
2840}
2841
2842fn validate_hermitian_krylov_expm_options(options: &HermitianKrylovExpmOptions) -> Result<()> {
2843    checked_krylov_capacity(options.max_iter, "hermitian_krylov_expm_multiply")?;
2844    anyhow::ensure!(
2845        options.max_iter > 0,
2846        "hermitian_krylov_expm_multiply: max_iter must be greater than zero"
2847    );
2848    anyhow::ensure!(
2849        options.max_time_splits > 0,
2850        "hermitian_krylov_expm_multiply: max_time_splits must be greater than zero"
2851    );
2852    anyhow::ensure!(
2853        options.tol.is_finite() && options.tol >= 0.0,
2854        "hermitian_krylov_expm_multiply: tol must be finite and non-negative"
2855    );
2856    anyhow::ensure!(
2857        options.breakdown_tol.is_finite() && options.breakdown_tol >= 0.0,
2858        "hermitian_krylov_expm_multiply: breakdown_tol must be finite and non-negative"
2859    );
2860    anyhow::ensure!(
2861        options.hermitian_tol.is_finite() && options.hermitian_tol >= 0.0,
2862        "hermitian_krylov_expm_multiply: hermitian_tol must be finite and non-negative"
2863    );
2864    Ok(())
2865}
2866
2867fn projected_matrix_from_columns(
2868    h_cols: &[Vec<Complex64>],
2869    dim: usize,
2870    solver: &'static str,
2871) -> Result<Matrix<Complex64>> {
2872    let matrix_len = dim.checked_mul(dim).ok_or_else(|| {
2873        anyhow::anyhow!("Krylov projected matrix shape ({dim}, {dim}) overflows usize")
2874    })?;
2875    let mut data = krylov_workspace(matrix_len, solver)?;
2876    data.resize(matrix_len, Complex64::new(0.0, 0.0));
2877    for col in 0..dim {
2878        for row in 0..dim {
2879            if let Some(value) = h_cols.get(col).and_then(|h_col| h_col.get(row)) {
2880                data[row + dim * col] = *value;
2881            }
2882        }
2883    }
2884    Ok(Matrix::from_col_major_vec(dim, dim, data))
2885}
2886
2887/// Allocate an empty Krylov workspace with room for `capacity` entries.
2888///
2889/// Every iteration-sized buffer the solvers own (Krylov basis, Hessenberg
2890/// columns, Givens rotations, projected residual and matrix, back-substitution
2891/// result) is allocated here. Its size follows from a user-supplied iteration
2892/// count, so an allocation that cannot be satisfied is reported as invalid
2893/// options instead of aborting.
2894fn krylov_workspace<T>(capacity: usize, solver: &'static str) -> Result<Vec<T>> {
2895    let mut workspace = Vec::new();
2896    workspace.try_reserve_exact(capacity).map_err(|source| {
2897        anyhow::Error::new(KrylovError::InvalidOptions {
2898            solver,
2899            reason: format!(
2900                "a Krylov workspace of {capacity} entries cannot be allocated ({source}); \
2901                 reduce max_iter or the restart length"
2902            ),
2903        })
2904    })?;
2905    Ok(workspace)
2906}
2907
2908fn checked_krylov_capacity(max_iter: usize, solver: &'static str) -> Result<usize> {
2909    max_iter.checked_add(1).ok_or_else(|| {
2910        anyhow::Error::new(KrylovError::InvalidOptions {
2911            solver,
2912            reason: "max_iter + 1 overflows usize".to_string(),
2913        })
2914    })
2915}
2916
2917fn any_scalar_to_complex(value: &AnyScalar) -> Complex64 {
2918    value
2919        .as_c64()
2920        .unwrap_or_else(|| Complex64::new(value.real(), 0.0))
2921}
2922
2923fn any_scalar_from_complex(value: Complex64, tolerance: f64) -> Result<AnyScalar> {
2924    if value.im.abs() <= tolerance {
2925        Ok(AnyScalar::new_real(value.re))
2926    } else {
2927        Ok(AnyScalar::new_complex(value.re, value.im))
2928    }
2929}
2930
2931fn hermitian_lanczos_threshold(eigenvalue: f64, options: &HermitianLanczosOptions) -> f64 {
2932    options.atol.max(options.rtol * eigenvalue.abs().max(1.0))
2933}
2934
2935fn hermitian_true_residual_norm<T, F>(apply_a: &F, eigenvector: &T, eigenvalue: f64) -> Result<f64>
2936where
2937    T: TensorVectorSpace,
2938    F: Fn(&T) -> Result<T>,
2939{
2940    let av = apply_a(eigenvector)?;
2941    let lambda_v = eigenvector.scale(AnyScalar::new_real(eigenvalue))?;
2942    let residual = av.axpby(
2943        AnyScalar::new_real(1.0),
2944        &lambda_v,
2945        AnyScalar::new_real(-1.0),
2946    )?;
2947    Ok(residual.norm()?)
2948}
2949
2950fn finalize_hermitian_lanczos_result<T, F>(
2951    apply_a: &F,
2952    basis: &[T],
2953    ritz: &HermitianRitzState,
2954    options: &HermitianLanczosOptions,
2955) -> Result<HermitianLanczosResult<T>>
2956where
2957    T: TensorVectorSpace,
2958    F: Fn(&T) -> Result<T>,
2959{
2960    let eigenvector = combine_basis_with_coefficients(basis, &ritz.coefficients, options)?;
2961    let residual_norm = hermitian_true_residual_norm(apply_a, &eigenvector, ritz.eigenvalue)?;
2962    let threshold = hermitian_lanczos_threshold(ritz.eigenvalue, options);
2963    let converged = residual_norm <= threshold;
2964
2965    if options.verbose {
2966        eprintln!(
2967            "Hermitian Lanczos final check iter {}: residual_estimate={:.6e} true_residual={:.6e} threshold={:.6e}",
2968            ritz.iterations, ritz.residual_estimate, residual_norm, threshold
2969        );
2970    }
2971
2972    Ok(HermitianLanczosResult {
2973        eigenvalue: ritz.eigenvalue,
2974        eigenvector,
2975        iterations: ritz.iterations,
2976        residual_norm,
2977        converged,
2978    })
2979}
2980
2981fn combine_basis_with_coefficients<T>(
2982    basis: &[T],
2983    coefficients: &[Complex64],
2984    options: &HermitianLanczosOptions,
2985) -> Result<T>
2986where
2987    T: TensorVectorSpace,
2988{
2989    anyhow::ensure!(
2990        !basis.is_empty(),
2991        "hermitian_lanczos_lowest_eigenpair: empty Krylov basis"
2992    );
2993    anyhow::ensure!(
2994        basis.len() == coefficients.len(),
2995        "hermitian_lanczos_lowest_eigenpair: coefficient length {} does not match basis length {}",
2996        coefficients.len(),
2997        basis.len()
2998    );
2999
3000    let mut result = basis[0].scale(any_scalar_from_complex(
3001        coefficients[0],
3002        options.hermitian_tol,
3003    )?)?;
3004    for (basis_vector, coefficient) in basis.iter().zip(coefficients.iter()).skip(1) {
3005        result = result.axpby(
3006            AnyScalar::new_real(1.0),
3007            basis_vector,
3008            any_scalar_from_complex(*coefficient, options.hermitian_tol)?,
3009        )?;
3010    }
3011    Ok(result)
3012}
3013
3014fn combine_basis_with_complex_coefficients<T>(
3015    basis: &[T],
3016    coefficients: &[Complex64],
3017    hermitian_tol: f64,
3018    context: &'static str,
3019) -> Result<T>
3020where
3021    T: TensorVectorSpace,
3022{
3023    anyhow::ensure!(!basis.is_empty(), "{context}: empty Krylov basis");
3024    anyhow::ensure!(
3025        basis.len() == coefficients.len(),
3026        "{context}: coefficient length {} does not match basis length {}",
3027        coefficients.len(),
3028        basis.len()
3029    );
3030
3031    let mut result = basis[0].scale(any_scalar_from_complex(coefficients[0], hermitian_tol)?)?;
3032    for (basis_vector, coefficient) in basis.iter().zip(coefficients.iter()).skip(1) {
3033        result = result.axpby(
3034            AnyScalar::new_real(1.0),
3035            basis_vector,
3036            any_scalar_from_complex(*coefficient, hermitian_tol)?,
3037        )?;
3038    }
3039    Ok(result)
3040}
3041
3042/// Compute Givens rotation coefficients to eliminate b in (a, b).
3043/// This function keeps computation in `AnyScalar` space to preserve AD metadata
3044/// as much as possible.
3045fn compute_givens_rotation(a: &AnyScalar, b: &AnyScalar) -> (AnyScalar, AnyScalar) {
3046    let a_abs = a.abs();
3047    let b_abs = b.abs();
3048    let r = (a_abs * a_abs + b_abs * b_abs).sqrt();
3049    if r < 1e-15 {
3050        (AnyScalar::new_real(1.0), AnyScalar::new_real(0.0))
3051    } else if a_abs < 1e-15 {
3052        (
3053            AnyScalar::new_real(0.0),
3054            b.clone().conj() / AnyScalar::new_real(r),
3055        )
3056    } else {
3057        let phase = a.clone() / AnyScalar::new_real(a_abs);
3058        (
3059            AnyScalar::new_real(a_abs / r),
3060            phase * b.clone().conj() / AnyScalar::new_real(r),
3061        )
3062    }
3063}
3064
3065/// Apply Givens rotation: (c, s) @ (x, y) -> (c*x + s*y, -conj(s)*x + c*y) for complex
3066/// or (c*x + s*y, -s*x + c*y) for real.
3067/// This function keeps computation in `AnyScalar` space to preserve AD metadata
3068/// as much as possible.
3069fn apply_givens_rotation(
3070    c: &AnyScalar,
3071    s: &AnyScalar,
3072    x: &AnyScalar,
3073    y: &AnyScalar,
3074) -> (AnyScalar, AnyScalar) {
3075    let new_x = c.clone() * x.clone() + s.clone() * y.clone();
3076    let new_y = -(s.clone().conj() * x.clone()) + c.clone() * y.clone();
3077    (new_x, new_y)
3078}
3079
3080/// Solve upper triangular system R y = g using back substitution.
3081fn solve_upper_triangular(
3082    h: &[Vec<AnyScalar>],
3083    g: &[AnyScalar],
3084    solver: &'static str,
3085) -> Result<Vec<AnyScalar>> {
3086    let n = g.len();
3087    if n == 0 {
3088        return Ok(vec![]);
3089    }
3090
3091    let mut y = krylov_workspace(n, solver)?;
3092    y.resize(n, AnyScalar::new_real(0.0));
3093
3094    for i in (0..n).rev() {
3095        let mut sum = g[i].clone();
3096
3097        for j in (i + 1)..n {
3098            // sum = sum - h[j][i] * y[j]
3099            let prod = h[j][i].clone() * y[j].clone();
3100            sum = sum - prod;
3101        }
3102
3103        let h_ii = &h[i][i];
3104        if h_ii.abs() < 1e-15 {
3105            return Err(anyhow::anyhow!(
3106                "Near-singular upper triangular matrix in GMRES"
3107            ));
3108        }
3109
3110        y[i] = sum / h_ii.clone();
3111    }
3112
3113    Ok(y)
3114}
3115
3116/// Update solution: x_new = x + sum_i y_i * v_i
3117fn update_solution<T: TensorVectorSpace>(x: &T, v_basis: &[T], y: &[AnyScalar]) -> Result<T> {
3118    let mut result = x.clone();
3119
3120    for (vi, yi) in v_basis.iter().zip(y.iter()) {
3121        let scaled_vi = vi.scale(yi.clone())?;
3122        // result = result + scaled_vi = 1.0 * result + 1.0 * scaled_vi
3123        result = result.axpby(
3124            AnyScalar::new_real(1.0),
3125            &scaled_vi,
3126            AnyScalar::new_real(1.0),
3127        )?;
3128    }
3129
3130    Ok(result)
3131}
3132
3133/// Update solution with truncation: x_new = truncate(x + sum_i y_i * v_i)
3134fn update_solution_truncated<T, Tr>(
3135    x: &T,
3136    v_basis: &[T],
3137    y: &[AnyScalar],
3138    truncate: &Tr,
3139) -> Result<T>
3140where
3141    T: TensorVectorSpace,
3142    Tr: Fn(&mut T) -> Result<()>,
3143{
3144    let mut result = x.clone();
3145    // Detect if x is effectively zero.
3146    // When x is created via scale(0.0), it preserves the original bond structure
3147    // (e.g., bond dim 4), causing axpby to double bond dimensions unnecessarily.
3148    // By detecting zero, we can use scaled_vi directly, avoiding the doubling.
3149    let mut result_is_zero = x.norm()? == 0.0;
3150
3151    for (vi, yi) in v_basis.iter().zip(y.iter()) {
3152        let scaled_vi = vi.scale(yi.clone())?;
3153        if result_is_zero {
3154            result = scaled_vi;
3155            result_is_zero = false;
3156        } else {
3157            result = result.axpby(
3158                AnyScalar::new_real(1.0),
3159                &scaled_vi,
3160                AnyScalar::new_real(1.0),
3161            )?;
3162        }
3163        // Truncate after each addition to control bond dimension growth
3164        truncate(&mut result)?;
3165    }
3166
3167    Ok(result)
3168}
3169
3170#[cfg(test)]
3171mod tests;