1use 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#[derive(Debug, thiserror::Error)]
53pub enum KrylovError {
54 #[error("{solver}: invalid options: {reason}")]
56 InvalidOptions {
57 solver: &'static str,
59 reason: String,
61 },
62 #[error("{solver}: initial vector has norm below the breakdown tolerance; provide a nonzero initial vector")]
64 ZeroInitialVector {
65 solver: &'static str,
67 },
68 #[error("gmres_affine: at least one affine coefficient must be nonzero")]
70 NoAffineCoefficient,
71 #[error("{solver}: nonpositive curvature {curvature} at iteration {iteration}; use GMRES for operators that are not positive definite")]
73 NonPositiveCurvature {
74 solver: &'static str,
76 iteration: usize,
78 curvature: f64,
80 },
81 #[error("{solver}: numerical breakdown in {quantity} at iteration {iteration}")]
83 NumericalBreakdown {
84 solver: &'static str,
86 iteration: usize,
88 quantity: &'static str,
90 },
91 #[error("{solver}: {quantity} is outside the f64 range")]
95 OutOfRange {
96 solver: &'static str,
98 quantity: &'static str,
100 },
101 #[error("{solver}: projected operator is not Hermitian: {source}")]
103 NonHermitian {
104 solver: &'static str,
106 #[source]
108 source: anyhow::Error,
109 },
110 #[error("{solver}: {source}")]
113 Operation {
114 solver: &'static str,
116 #[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 static LAST_GMRES_PROFILE: std::cell::RefCell<Option<String>> =
230 const { std::cell::RefCell::new(None) };
231}
232
233#[derive(Debug, Clone)]
248pub struct GmresOptions {
249 pub max_iter: usize,
252
253 pub rtol: f64,
258
259 pub max_restarts: usize,
263
264 pub verbose: bool,
267
268 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#[derive(Debug, Clone)]
325pub struct GmresResult<T> {
326 pub solution: T,
328
329 pub iterations: usize,
331
332 pub residual_norm: f64,
334
335 pub converged: bool,
337}
338
339#[derive(Debug, Clone)]
355pub struct HermitianLanczosOptions {
356 pub max_iter: usize,
361
362 pub rtol: f64,
367
368 pub atol: f64,
372
373 pub breakdown_tol: f64,
379
380 pub hermitian_tol: f64,
385
386 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#[derive(Debug, Clone)]
422pub struct HermitianLanczosResult<T> {
423 pub eigenvalue: f64,
425
426 pub eigenvector: T,
428
429 pub iterations: usize,
431
432 pub residual_norm: f64,
434
435 pub converged: bool,
437}
438
439#[derive(Debug, Clone)]
458pub struct HermitianKrylovExpmOptions {
459 pub max_iter: usize,
461 pub max_time_splits: usize,
463 pub tol: f64,
465 pub breakdown_tol: f64,
467 pub hermitian_tol: f64,
469 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#[derive(Debug, Clone)]
502pub struct HermitianKrylovExpmResult<T> {
503 pub output: T,
505 pub iterations: usize,
507 pub matvecs: usize,
509 pub error_estimate: f64,
511 pub converged: bool,
513 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
525pub 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
685pub 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
979pub 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
1028pub 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
1065pub 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
1129pub 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 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 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 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 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 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 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 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 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 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 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 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
1786pub 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 b.validate()?;
1840 x0.validate()?;
1841
1842 let b_norm = vector_ops::finite_norm(b, "gmres", 0, "right-hand-side norm")?;
1844 if b_norm == 0.0 {
1845 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 let ax = apply_a(&x)?;
1874 if _restart == 0 {
1876 ax.validate()?;
1877 }
1878 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 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 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 let v0 = vector_ops::divide_by_norm(&r, r_norm)?.0;
1908 v_basis.push(v0);
1909
1910 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)); let mut solution_already_updated = false;
1917
1918 for j in 0..cycle_max_iter {
1919 total_iters += 1;
1920
1921 let w = apply_a(&v_basis[j])?;
1923
1924 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 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 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 #[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 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 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 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 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 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 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 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 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 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
2079pub 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 b.validate()?;
2158 x0.validate()?;
2159
2160 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 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 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 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 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 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 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 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 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 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 let v_jp1 = vector_ops::divide_by_norm(&w_orth, h_jp1_j_real)?.0;
2382 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#[derive(Debug, Clone)]
2449pub struct RestartGmresOptions {
2450 pub max_outer_iters: usize,
2453
2454 pub rtol: f64,
2458
2459 pub inner_max_iter: usize,
2462
2463 pub inner_max_restarts: usize,
2466
2467 pub min_reduction: Option<f64>,
2473
2474 pub inner_rtol: Option<f64>,
2478
2479 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 pub fn new() -> Self {
2501 Self::default()
2502 }
2503
2504 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 pub fn with_rtol(mut self, rtol: f64) -> Self {
2512 self.rtol = rtol;
2513 self
2514 }
2515
2516 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 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 pub fn with_min_reduction(mut self, min_reduction: f64) -> Self {
2530 self.min_reduction = Some(min_reduction);
2531 self
2532 }
2533
2534 pub fn with_inner_rtol(mut self, inner_rtol: f64) -> Self {
2536 self.inner_rtol = Some(inner_rtol);
2537 self
2538 }
2539
2540 pub fn with_verbose(mut self, verbose: bool) -> Self {
2542 self.verbose = verbose;
2543 self
2544 }
2545}
2546
2547#[derive(Debug, Clone)]
2566pub struct RestartGmresResult<T> {
2567 pub solution: T,
2569
2570 pub iterations: usize,
2572
2573 pub outer_iterations: usize,
2575
2576 pub residual_norm: f64,
2578
2579 pub converged: bool,
2581}
2582
2583pub 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 b.validate()?;
2667 if let Some(x) = x0 {
2668 x.validate()?;
2669 }
2670
2671 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 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 let inner_options = GmresOptions {
2703 max_iter: options.inner_max_iter,
2704 rtol: options.inner_rtol.unwrap_or(0.1), 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 })?, verbose: options.verbose,
2712 check_true_residual: true, };
2714
2715 for outer_iter in 0..options.max_outer_iters {
2716 let ax = apply_a(&x)?;
2718 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 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 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 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 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 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
2887fn 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
3042fn 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
3065fn 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
3080fn 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 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
3116fn 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.axpby(
3124 AnyScalar::new_real(1.0),
3125 &scaled_vi,
3126 AnyScalar::new_real(1.0),
3127 )?;
3128 }
3129
3130 Ok(result)
3131}
3132
3133fn 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 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(&mut result)?;
3165 }
3166
3167 Ok(result)
3168}
3169
3170#[cfg(test)]
3171mod tests;