1use crate::error::{ArrayRole, Error, Result};
13use crate::fpu_check::FpuGuard;
14use crate::gemm::{GemmBackendHandle, GemmScalar, apply_along_axis};
15use num_complex::Complex;
16use tenferro_tensor::{TypedTensor, TypedTensorView, TypedTensorViewMut};
17
18pub trait InplaceFitter {
49 fn n_points(&self) -> usize;
51
52 fn basis_size(&self) -> usize;
54
55 fn evaluate_nd_dd_to(
57 &self,
58 backend: Option<&GemmBackendHandle>,
59 coeffs: &TypedTensorView<'_, f64>,
60 dim: usize,
61 out: &mut TypedTensorViewMut<'_, f64>,
62 ) -> Result<()> {
63 let _ = (backend, coeffs, dim, out);
64 Err(not_supported(
65 "evaluate_nd_dd_to (real coefficients to real values)",
66 ))
67 }
68
69 fn evaluate_nd_dz_to(
71 &self,
72 backend: Option<&GemmBackendHandle>,
73 coeffs: &TypedTensorView<'_, f64>,
74 dim: usize,
75 out: &mut TypedTensorViewMut<'_, Complex<f64>>,
76 ) -> Result<()> {
77 let _ = (backend, coeffs, dim, out);
78 Err(not_supported(
79 "evaluate_nd_dz_to (real coefficients to complex values)",
80 ))
81 }
82
83 fn evaluate_nd_zd_to(
85 &self,
86 backend: Option<&GemmBackendHandle>,
87 coeffs: &TypedTensorView<'_, Complex<f64>>,
88 dim: usize,
89 out: &mut TypedTensorViewMut<'_, f64>,
90 ) -> Result<()> {
91 let _ = (backend, coeffs, dim, out);
92 Err(not_supported(
93 "evaluate_nd_zd_to (complex coefficients to real values)",
94 ))
95 }
96
97 fn evaluate_nd_zz_to(
99 &self,
100 backend: Option<&GemmBackendHandle>,
101 coeffs: &TypedTensorView<'_, Complex<f64>>,
102 dim: usize,
103 out: &mut TypedTensorViewMut<'_, Complex<f64>>,
104 ) -> Result<()> {
105 let _ = (backend, coeffs, dim, out);
106 Err(not_supported(
107 "evaluate_nd_zz_to (complex coefficients to complex values)",
108 ))
109 }
110
111 fn fit_nd_dd_to(
113 &self,
114 backend: Option<&GemmBackendHandle>,
115 values: &TypedTensorView<'_, f64>,
116 dim: usize,
117 out: &mut TypedTensorViewMut<'_, f64>,
118 ) -> Result<()> {
119 let _ = (backend, values, dim, out);
120 Err(not_supported(
121 "fit_nd_dd_to (real values to real coefficients)",
122 ))
123 }
124
125 fn fit_nd_dz_to(
127 &self,
128 backend: Option<&GemmBackendHandle>,
129 values: &TypedTensorView<'_, f64>,
130 dim: usize,
131 out: &mut TypedTensorViewMut<'_, Complex<f64>>,
132 ) -> Result<()> {
133 let _ = (backend, values, dim, out);
134 Err(not_supported(
135 "fit_nd_dz_to (real values to complex coefficients)",
136 ))
137 }
138
139 fn fit_nd_zd_to(
141 &self,
142 backend: Option<&GemmBackendHandle>,
143 values: &TypedTensorView<'_, Complex<f64>>,
144 dim: usize,
145 out: &mut TypedTensorViewMut<'_, f64>,
146 ) -> Result<()> {
147 let _ = (backend, values, dim, out);
148 Err(not_supported(
149 "fit_nd_zd_to (complex values to real coefficients)",
150 ))
151 }
152
153 fn fit_nd_zz_to(
155 &self,
156 backend: Option<&GemmBackendHandle>,
157 values: &TypedTensorView<'_, Complex<f64>>,
158 dim: usize,
159 out: &mut TypedTensorViewMut<'_, Complex<f64>>,
160 ) -> Result<()> {
161 let _ = (backend, values, dim, out);
162 Err(not_supported(
163 "fit_nd_zz_to (complex values to complex coefficients)",
164 ))
165 }
166}
167
168fn not_supported(operation: &str) -> Error {
170 Error::NotSupported {
171 what: format!("{operation} for this sampling"),
172 }
173}
174
175fn layout_error(what: impl Into<String>) -> Error {
178 Error::NotSupported { what: what.into() }
179}
180
181pub trait FitScalar: GemmScalar {
191 const REAL_WIDTH: usize;
193 fn as_f64(s: &[Self]) -> &[f64];
195 fn as_f64_mut(s: &mut [Self]) -> &mut [f64];
197}
198
199impl FitScalar for f64 {
200 const REAL_WIDTH: usize = 1;
201 fn as_f64(s: &[f64]) -> &[f64] {
202 s
203 }
204 fn as_f64_mut(s: &mut [f64]) -> &mut [f64] {
205 s
206 }
207}
208
209impl FitScalar for Complex<f64> {
210 const REAL_WIDTH: usize = 2;
211 fn as_f64(s: &[Self]) -> &[f64] {
214 bytemuck::cast_slice(s)
215 }
216 fn as_f64_mut(s: &mut [Self]) -> &mut [f64] {
217 bytemuck::cast_slice_mut(s)
218 }
219}
220
221#[derive(Clone, Copy, Debug, PartialEq, Eq)]
227pub(crate) struct AxisSplit {
228 pub pre: usize,
229 pub post: usize,
230}
231
232pub(crate) fn check_input_shape(input_dims: &[usize], dim: usize, n_in: usize) -> Result<()> {
244 let rank = input_dims.len();
245 if dim >= rank {
246 return Err(Error::AxisOutOfRange { axis: dim, rank });
247 }
248 if input_dims[dim] != n_in {
249 let mut expected = input_dims.to_vec();
250 expected[dim] = n_in;
251 return Err(Error::ShapeMismatch {
252 which: ArrayRole::Input,
253 expected,
254 actual: input_dims.to_vec(),
255 });
256 }
257 Ok(())
258}
259
260pub(crate) fn check_nd_shapes(
269 input_dims: &[usize],
270 dim: usize,
271 n_in: usize,
272 out_dims: &[usize],
273 n_out: usize,
274) -> Result<()> {
275 check_input_shape(input_dims, dim, n_in)?;
276 let expected = replace_axis(input_dims, dim, n_out);
277 if out_dims != expected.as_slice() {
278 return Err(Error::ShapeMismatch {
279 which: ArrayRole::Output,
280 expected,
281 actual: out_dims.to_vec(),
282 });
283 }
284 Ok(())
285}
286
287pub(crate) fn check_len(which: ArrayRole, len: usize, expected: usize) -> Result<()> {
293 if len == expected {
294 Ok(())
295 } else {
296 Err(Error::ShapeMismatch {
297 which,
298 expected: vec![expected],
299 actual: vec![len],
300 })
301 }
302}
303
304pub(crate) fn split_axis(shape: &[usize], dim: usize, expected: usize) -> Result<AxisSplit> {
306 check_input_shape(shape, dim, expected)?;
307 Ok(AxisSplit {
308 pre: shape[..dim].iter().product(),
309 post: shape[dim + 1..].iter().product(),
310 })
311}
312
313pub(crate) fn replace_axis(shape: &[usize], dim: usize, extent: usize) -> Vec<usize> {
315 let mut out = shape.to_vec();
316 out[dim] = extent;
317 out
318}
319
320pub(crate) enum InputSlice<'a, T: tenferro_tensor::TensorScalar> {
322 Borrowed(&'a [T]),
323 Owned(Vec<T>),
324}
325
326impl<T: tenferro_tensor::TensorScalar> InputSlice<'_, T> {
327 pub(crate) fn get(&self) -> Result<&[T]> {
328 match self {
329 InputSlice::Borrowed(s) => Ok(s),
330 InputSlice::Owned(v) => Ok(v),
331 }
332 }
333}
334
335pub(crate) fn input_slice<'a, T: tenferro_tensor::TensorScalar>(
336 view: &TypedTensorView<'a, T>,
337) -> Result<InputSlice<'a, T>> {
338 if view.is_col_major_contiguous()? {
339 Ok(InputSlice::Borrowed(view.as_slice()?))
340 } else {
341 Ok(InputSlice::Owned(gather_col_major(view)?))
342 }
343}
344
345fn gather_col_major<T: tenferro_tensor::TensorScalar>(
347 view: &TypedTensorView<'_, T>,
348) -> Result<Vec<T>> {
349 let shape = view.shape();
350 let strides = view.strides();
351 let storage = view.host_storage()?;
352 let len = view.n_elements();
353 if len == 0 {
354 return Ok(Vec::new());
355 }
356 let (mut lo, mut hi) = (view.offset(), view.offset());
358 for (&n, &st) in shape.iter().zip(strides) {
359 let span = isize::try_from(n - 1)
360 .ok()
361 .and_then(|m| m.checked_mul(st))
362 .ok_or_else(|| layout_error("input view stride overflow"))?;
363 if span < 0 {
364 lo += span;
365 } else {
366 hi += span;
367 }
368 }
369 if lo < 0 || usize::try_from(hi).map_or(true, |h| h >= storage.len()) {
370 return Err(layout_error("input view exceeds its storage"));
371 }
372 let mut out = Vec::with_capacity(len);
373 let mut idx = vec![0usize; shape.len()];
374 let mut pos = view.offset();
375 for _ in 0..len {
376 out.push(storage[pos as usize].clone());
378 for (k, i) in idx.iter_mut().enumerate() {
379 *i += 1;
380 pos += strides[k];
381 if *i < shape[k] {
382 break;
383 }
384 pos -= strides[k] * shape[k] as isize;
385 *i = 0;
386 }
387 }
388 Ok(out)
389}
390
391pub(crate) fn output_slice<'a, T: tenferro_tensor::TensorScalar>(
393 view: &'a mut TypedTensorViewMut<'_, T>,
394) -> Result<&'a mut [T]> {
395 if !view.is_col_major_contiguous()? {
396 return Err(layout_error(format!(
397 "output view must be compact column-major, got {}",
398 view.layout_summary()
399 )));
400 }
401 let offset = usize::try_from(view.offset())
402 .map_err(|_| layout_error("output view has a negative offset"))?;
403 let len = view.n_elements();
404 let storage = view
405 .host_storage_mut()
406 .map_err(|e| layout_error(e.to_string()))?;
407 storage
408 .get_mut(offset..offset + len)
409 .ok_or_else(|| layout_error("output view exceeds its storage"))
410}
411
412pub(crate) fn run_to<Tin, Tout, F>(
417 input: &TypedTensorView<'_, Tin>,
418 dim: usize,
419 n_in: usize,
420 n_out: usize,
421 out: &mut TypedTensorViewMut<'_, Tout>,
422 op: F,
423) -> Result<()>
424where
425 Tin: tenferro_tensor::TensorScalar,
426 Tout: tenferro_tensor::TensorScalar,
427 F: FnOnce(&[Tin], AxisSplit, &mut [Tout]) -> Result<()>,
428{
429 check_nd_shapes(input.shape(), dim, n_in, out.shape(), n_out)?;
430 let split = split_axis(input.shape(), dim, n_in)?;
431 let x = input_slice(input)?;
432 let y = output_slice(out)?;
433 op(x.get()?, split, y)
434}
435
436pub(crate) fn run_alloc<Tin, Tout, F>(
438 input: &TypedTensor<Tin>,
439 dim: usize,
440 n_in: usize,
441 n_out: usize,
442 op: F,
443) -> Result<TypedTensor<Tout>>
444where
445 Tin: tenferro_tensor::TensorScalar,
446 Tout: tenferro_tensor::TensorScalar + num_traits::Zero,
447 F: FnOnce(&[Tin], AxisSplit, &mut [Tout]) -> Result<()>,
448{
449 let split = split_axis(input.shape(), dim, n_in)?;
450 let out_shape = replace_axis(input.shape(), dim, n_out);
451 let x = input.host_data()?;
454 debug_assert_eq!(x.len(), input.n_elements());
455 let mut y = vec![Tout::zero(); split.pre * n_out * split.post];
456 op(x, split, &mut y)?;
457 Ok(TypedTensor::from_vec_col_major(out_shape, y)?)
458}
459
460pub(crate) fn stacked_to_complex(
467 t: &[f64],
468 pre: usize,
469 n: usize,
470 post: usize,
471 y: &mut [Complex<f64>],
472) {
473 for q in 0..post {
474 for i in 0..n {
475 let re = &t[pre * (i + 2 * n * q)..][..pre];
476 let im = &t[pre * (n + i + 2 * n * q)..][..pre];
477 let dst = &mut y[pre * (i + n * q)..][..pre];
478 for p in 0..pre {
479 dst[p] = Complex::new(re[p], im[p]);
480 }
481 }
482 }
483}
484
485pub(crate) fn complex_to_stacked(
488 x: &[Complex<f64>],
489 pre: usize,
490 n: usize,
491 post: usize,
492) -> Vec<f64> {
493 let mut t = vec![0.0; 2 * pre * n * post];
494 for q in 0..post {
495 for i in 0..n {
496 let src = &x[pre * (i + n * q)..][..pre];
497 let base_re = pre * (i + 2 * n * q);
498 let base_im = pre * (n + i + 2 * n * q);
499 for p in 0..pre {
500 t[base_re + p] = src[p].re;
501 t[base_im + p] = src[p].im;
502 }
503 }
504 }
505 t
506}
507
508#[doc(hidden)]
518pub struct PinvFactors<T> {
519 pub uh: Vec<T>,
521 pub v_scaled: Vec<T>,
523 pub s: Vec<f64>,
526 pub n: usize,
527 pub m: usize,
528 pub rank: usize,
529}
530
531impl<T: GemmScalar> PinvFactors<T> {
532 pub fn solve(
535 &self,
536 backend: Option<&GemmBackendHandle>,
537 values: &[T],
538 pre: usize,
539 post: usize,
540 out: &mut [T],
541 ) -> Result<()> {
542 let mut tmp = vec![T::zero(); pre * self.rank * post];
543 apply_along_axis(
544 backend, &self.uh, self.rank, self.n, values, pre, post, &mut tmp,
545 )?;
546 apply_along_axis(
547 backend,
548 &self.v_scaled,
549 self.m,
550 self.rank,
551 &tmp,
552 pre,
553 post,
554 out,
555 )?;
556 Ok(())
557 }
558}
559
560pub trait SvdScalar: GemmScalar + tenferro_linalg::LinalgScalar {
562 fn conj_(self) -> Self;
563 fn scale(self, s: f64) -> Self;
564 fn real_part(v: <Self as tenferro_tensor::TensorScalar>::Real) -> f64;
565}
566
567impl SvdScalar for f64 {
568 fn conj_(self) -> Self {
569 self
570 }
571 fn scale(self, s: f64) -> Self {
572 self * s
573 }
574 fn real_part(v: f64) -> f64 {
575 v
576 }
577}
578
579impl SvdScalar for Complex<f64> {
580 fn conj_(self) -> Self {
581 self.conj()
582 }
583 fn scale(self, s: f64) -> Self {
584 self * s
585 }
586 fn real_part(v: f64) -> f64 {
587 v
588 }
589}
590
591#[doc(hidden)]
597pub fn compute_pinv<T: SvdScalar>(a: &[T], n: usize, m: usize) -> Result<PinvFactors<T>> {
598 compute_pinv_impl(a, n, m, None, || sampling_matrix((n, m)))
599}
600
601#[doc(hidden)]
607pub fn compute_pinv_truncated<T: SvdScalar>(
608 a: &[T],
609 n: usize,
610 m: usize,
611 rtol: f64,
612) -> Result<PinvFactors<T>> {
613 compute_pinv_impl(a, n, m, Some(rtol), || sampling_matrix((n, m)))
614}
615
616pub(crate) fn sampling_matrix((rows, cols): (usize, usize)) -> String {
618 format!("{rows} x {cols} sampling matrix")
619}
620
621fn svd_failed(matrix: String, err: impl std::fmt::Display) -> Error {
624 Error::DecompositionFailed {
625 reason: format!("the SVD of the {matrix} failed: {err}"),
626 }
627}
628
629pub(super) fn pinv_rank(s: &[f64], rtol: Option<f64>) -> std::result::Result<usize, String> {
637 if let Some(l) = s.iter().position(|v| !v.is_finite()) {
638 return Err(format!("non-finite singular value s[{l}] = {}", s[l]));
639 }
640 Ok(match rtol {
641 Some(rtol) => {
642 let s0 = s.first().copied().unwrap_or(0.0);
643 s.iter().take_while(|&&v| v > rtol * s0).count()
644 }
645 None => s.len(),
646 })
647}
648
649pub(crate) fn compute_pinv_of<T: SvdScalar>(
655 a: &[T],
656 n: usize,
657 m: usize,
658 name: impl FnOnce() -> String,
659) -> Result<PinvFactors<T>> {
660 compute_pinv_impl(a, n, m, None, name)
661}
662
663fn compute_pinv_impl<T: SvdScalar>(
664 a: &[T],
665 n: usize,
666 m: usize,
667 rtol: Option<f64>,
668 name: impl FnOnce() -> String,
669) -> Result<PinvFactors<T>> {
670 use tenferro_cpu::CpuBackend;
671 use tenferro_linalg::TypedTensorLinalgExt;
672 use tenferro_tensor::BackendSessionHost;
673
674 let _guard = FpuGuard::new_protect_computation();
676
677 let rank = n.min(m);
678 if rank == 0 {
679 return Ok(PinvFactors {
680 uh: Vec::new(),
681 v_scaled: vec![T::zero(); m * rank],
682 s: Vec::new(),
683 n,
684 m,
685 rank,
686 });
687 }
688 let tensor = TypedTensor::<T>::from_vec_col_major(vec![n, m], a.to_vec())?;
689 let mut host = CpuBackend::new();
690 let (u, s, vt) = match host.with_backend_session(|session| tensor.svd(session)) {
691 Ok(f) => f,
692 Err(e) => return Err(svd_failed(name(), e)),
693 };
694
695 let (u_shape, vt_shape) = (u.shape().to_vec(), vt.shape().to_vec());
696 let (u, s, vt) = (u.host_data()?, s.host_data()?, vt.host_data()?);
697 if u_shape[0] != n || u_shape[1] < rank || vt_shape[1] != m || vt_shape[0] < rank {
698 return Err(svd_failed(
699 name(),
700 format!("factors U {u_shape:?}, Vt {vt_shape:?}"),
701 ));
702 }
703 let (ldu, ldvt) = (u_shape[0], vt_shape[0]);
704 let singular_values: Vec<f64> = s[..rank].iter().map(|&v| T::real_part(v)).collect();
705 let rank = pinv_rank(&singular_values, rtol).map_err(|err| svd_failed(name(), err))?;
706
707 let mut uh = vec![T::zero(); rank * n];
709 for i in 0..n {
710 for l in 0..rank {
711 uh[l + rank * i] = u[i + ldu * l].conj_();
712 }
713 }
714 let mut v_scaled = vec![T::zero(); m * rank];
716 for l in 0..rank {
717 let inv_s = 1.0 / T::real_part(s[l]);
718 for j in 0..m {
719 v_scaled[j + m * l] = vt[l + ldvt * j].conj_().scale(inv_s);
720 }
721 }
722 Ok(PinvFactors {
723 uh,
724 v_scaled,
725 s: singular_values,
726 n,
727 m,
728 rank,
729 })
730}
731
732pub fn singular_values<T: SvdScalar>(a: &[T], n: usize, m: usize) -> Result<Vec<f64>> {
737 use tenferro_cpu::CpuBackend;
738 use tenferro_linalg::TypedTensorLinalgExt;
739 use tenferro_tensor::BackendSessionHost;
740
741 let _guard = FpuGuard::new_protect_computation();
742 if n.min(m) == 0 {
743 return Ok(Vec::new());
744 }
745 let tensor = TypedTensor::<T>::from_vec_col_major(vec![n, m], a.to_vec())?;
746 let mut host = CpuBackend::new();
747 let s = host
748 .with_backend_session(|session| tensor.svdvals(session))
749 .map_err(|e| svd_failed(sampling_matrix((n, m)), e))?;
750 Ok(s.host_data()?.iter().map(|&v| T::real_part(v)).collect())
751}
752
753pub(crate) fn condition_number_from_singular_values(s: &[f64]) -> f64 {
762 if s.is_empty() {
763 return 1.0;
764 }
765 if s.iter().any(|x| x.is_nan()) {
766 return f64::NAN;
767 }
768 let s_max = s.iter().copied().fold(f64::NEG_INFINITY, f64::max);
769 let s_min = s.iter().copied().fold(f64::INFINITY, f64::min);
770 if s_min.abs() < 1e-15 {
771 return f64::INFINITY;
772 }
773 s_max / s_min
774}