Skip to main content

tenferro_linalg/
extension.rs

1use std::any::Any;
2use std::hash::{Hash, Hasher};
3use std::sync::Arc;
4
5use num_complex::{Complex32, Complex64};
6use tenferro_cpu::with_cpu_engine;
7use tenferro_extension_macros::define_extension_runtime;
8use tenferro_ops::SymDim;
9use tenferro_runtime::extension::ExtensionOp;
10use tenferro_tensor::{DType, Engine, Error, ErrorKind, Tensor, TensorRead};
11
12#[cfg(feature = "cuda")]
13use tenferro_gpu::cuda::raw::with_cuda_engine;
14
15use crate::backend::LinalgBackend;
16use crate::flags::SvdShape;
17use crate::RankRevealingQrOptions;
18
19#[cfg(all(test, feature = "cuda"))]
20#[path = "extension/cuda_tests.rs"]
21mod cuda_tests;
22mod gauge;
23#[cfg(all(test, not(feature = "cuda")))]
24mod tests;
25
26pub(crate) use gauge::{apply_eigh_gauge, apply_qr_gauge};
27
28pub const LINALG_EXTENSION_FAMILY_ID: &str = "tenferro-linalg.linalg.v1";
29
30/// Default derivative regularization used by decomposition AD rules.
31///
32/// This epsilon is used only when differentiating decomposition formulas with
33/// repeated or nearly repeated spectral values. It is not a solver tolerance.
34///
35/// # Examples
36///
37/// ```rust
38/// use tenferro_linalg::{SvdOptions, DEFAULT_DECOMPOSITION_DERIVATIVE_EPS};
39///
40/// let options = SvdOptions::default();
41/// assert_eq!(options.derivative_eps, DEFAULT_DECOMPOSITION_DERIVATIVE_EPS);
42/// ```
43pub const DEFAULT_DECOMPOSITION_DERIVATIVE_EPS: f64 = 1e-12;
44
45/// Singular-vector gauge convention used by [`SvdOptions`].
46///
47/// # Examples
48///
49/// ```rust
50/// use tenferro_linalg::{SvdGauge, SvdOptions};
51///
52/// let options = SvdOptions::default().gauge(SvdGauge::CanonicalPivot);
53/// assert_eq!(options.gauge, SvdGauge::CanonicalPivot);
54/// ```
55#[derive(Clone, Copy, Debug, PartialEq, Eq)]
56pub enum SvdGauge {
57    /// Leave the backend's raw singular vector signs or phases unchanged.
58    Raw,
59    /// Make each left singular vector's max-absolute pivot entry positive-real
60    /// and adjust the matching `VT` row so reconstruction is preserved.
61    CanonicalPivot,
62}
63
64/// Eigenvector gauge convention used by [`EighOptions`].
65///
66/// # Examples
67///
68/// ```rust
69/// use tenferro_linalg::{EighGauge, EighOptions};
70///
71/// let options = EighOptions::default().gauge(EighGauge::CanonicalPivot);
72/// assert_eq!(options.gauge, EighGauge::CanonicalPivot);
73/// ```
74#[derive(Clone, Copy, Debug, PartialEq, Eq)]
75pub enum EighGauge {
76    /// Leave the backend's raw eigenvector signs or phases unchanged.
77    Raw,
78    /// Make each eigenvector's max-absolute pivot entry positive-real.
79    CanonicalPivot,
80}
81
82/// QR factor gauge convention used by [`QrOptions`].
83///
84/// # Examples
85///
86/// ```rust
87/// use tenferro_linalg::{QrGauge, QrOptions};
88///
89/// let options = QrOptions::default().gauge(QrGauge::PositiveDiagonal);
90/// assert_eq!(options.gauge, QrGauge::PositiveDiagonal);
91/// ```
92#[derive(Clone, Copy, Debug, PartialEq, Eq)]
93pub enum QrGauge {
94    /// Leave the backend's raw QR signs or phases unchanged.
95    Raw,
96    /// Make each `R` diagonal entry positive-real, compensating `Q`.
97    PositiveDiagonal,
98}
99
100/// Algorithm family used by [`SvdOptions`].
101///
102/// A provider may ignore the selection and run its single SVD kernel; where a
103/// selection is honoured it changes speed and numerical behavior, not the
104/// decomposition contract, so gauge handling and AD rule selection are
105/// unaffected. [`Self::Polar`] may perturb near-singular inputs. Equivalent to
106/// `jax.lax.linalg.svd(..., algorithm=...)` and
107/// `torch.linalg.svd(..., driver=...)`.
108///
109/// # Examples
110///
111/// ```rust
112/// use tenferro_linalg::{SvdDriver, SvdOptions};
113///
114/// let options = SvdOptions::default().driver(SvdDriver::QrBased);
115/// assert_eq!(options.driver, SvdDriver::QrBased);
116/// assert_eq!(SvdOptions::default().driver, SvdDriver::Auto);
117/// ```
118#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
119pub enum SvdDriver {
120    /// The provider's default policy for this input.
121    ///
122    /// Never selects [`Self::Polar`]: its small singular values are only
123    /// accurate to about `1e-6` of the largest, which an `eps`-scale
124    /// truncation cannot tolerate, so the accurate families stay the default
125    /// unless the caller opts in. A provider with one SVD kernel returns the
126    /// same factors for every selection.
127    ///
128    /// On the CUDA provider this is the accuracy-preserving, JAX-compatible
129    /// rule: [`Self::Jacobi`] when both matrix dimensions are at most 1024,
130    /// otherwise [`Self::QrBased`].
131    #[default]
132    Auto,
133    /// One-sided Jacobi rotations: the accurate family for small and medium
134    /// orders, and more work than [`Self::QrBased`] on large or wide spectra.
135    /// On the CUDA provider this selects `cusolverDn<t>gesvdj`.
136    Jacobi,
137    /// Bidiagonalization followed by an implicit-QR iteration: the general
138    /// purpose family, and the faster of the two accurate families on large
139    /// and wide spectra.
140    /// On the CUDA provider this selects `cusolverDn<t>gesvd`.
141    QrBased,
142    /// Polar decomposition: the fastest family for `min(m, n) >= 256` on an
143    /// A100 (see the `cuda_svd_driver` benchmark), and the least accurate on
144    /// small singular values.
145    ///
146    /// Explicit only: [`Self::Auto`] never selects it. Its small singular
147    /// values are only accurate to about `1e-6` of the largest, so do not use
148    /// it for an `eps`-scale truncation (a pseudoinverse or a tensor-network
149    /// truncation at `1e-12`..`1e-14`): the perturbation can change the
150    /// retained rank. Accuracy is input-dependent rather than uniformly worse
151    /// than [`Self::QrBased`]: on ten-decade spectra built as `U diag(s) Vᴴ` it
152    /// was the most accurate of the three families on an A100, but on a
153    /// circulant-like matrix with the same spectrum it lost about two digits
154    /// against [`Self::QrBased`]. Measure on your own inputs before relying on
155    /// it for small singular values.
156    ///
157    /// A provider that can bound its own perturbation returns a typed backend
158    /// failure instead of silently wrong factors when the bound is not small
159    /// relative to the largest singular value.
160    /// On the CUDA provider this selects `cusolverDnXgesvdp`.
161    Polar,
162}
163
164/// Options for singular value decomposition.
165///
166/// # Examples
167///
168/// ```rust
169/// use tenferro_linalg::{SvdDriver, SvdGauge, SvdOptions};
170///
171/// let options = SvdOptions::default()
172///     .gauge(SvdGauge::CanonicalPivot)
173///     .derivative_eps(1.0e-10)
174///     .driver(SvdDriver::QrBased);
175/// assert_eq!(options.gauge, SvdGauge::CanonicalPivot);
176/// assert_eq!(options.derivative_eps, 1.0e-10);
177/// assert_eq!(options.driver, SvdDriver::QrBased);
178/// ```
179#[derive(Clone, Copy, Debug, PartialEq)]
180#[non_exhaustive]
181pub struct SvdOptions {
182    /// Thin or full-matrices factors. The default is [`SvdShape::Thin`].
183    pub shape: SvdShape,
184    /// Singular-vector gauge convention.
185    pub gauge: SvdGauge,
186    /// AD derivative regularization for repeated or nearly repeated singular values.
187    pub derivative_eps: f64,
188    /// Algorithm family for the SVD: a hint for providers that can choose a
189    /// driver; the current CPU provider ignores it.
190    pub driver: SvdDriver,
191}
192
193impl Default for SvdOptions {
194    fn default() -> Self {
195        Self {
196            shape: SvdShape::Thin,
197            gauge: SvdGauge::Raw,
198            derivative_eps: DEFAULT_DECOMPOSITION_DERIVATIVE_EPS,
199            driver: SvdDriver::Auto,
200        }
201    }
202}
203
204impl SvdOptions {
205    /// Return options with the requested factor shape.
206    ///
207    /// # Examples
208    ///
209    /// ```rust
210    /// use tenferro_linalg::{SvdOptions, SvdShape};
211    ///
212    /// let options = SvdOptions::default().shape(SvdShape::Full);
213    /// assert_eq!(options.shape, SvdShape::Full);
214    /// ```
215    pub fn shape(mut self, shape: SvdShape) -> Self {
216        self.shape = shape;
217        self
218    }
219
220    /// Return options with the requested singular-vector gauge.
221    ///
222    /// # Examples
223    ///
224    /// ```rust
225    /// use tenferro_linalg::{SvdGauge, SvdOptions};
226    ///
227    /// let options = SvdOptions::default().gauge(SvdGauge::CanonicalPivot);
228    /// assert_eq!(options.gauge, SvdGauge::CanonicalPivot);
229    /// ```
230    pub fn gauge(mut self, gauge: SvdGauge) -> Self {
231        self.gauge = gauge;
232        self
233    }
234
235    /// Return options with an explicit derivative epsilon.
236    ///
237    /// # Examples
238    ///
239    /// ```rust
240    /// use tenferro_linalg::SvdOptions;
241    ///
242    /// let options = SvdOptions::default().derivative_eps(1.0e-9);
243    /// assert_eq!(options.derivative_eps, 1.0e-9);
244    /// ```
245    pub fn derivative_eps(mut self, derivative_eps: f64) -> Self {
246        self.derivative_eps = derivative_eps;
247        self
248    }
249
250    /// Return options with an explicit SVD driver.
251    ///
252    /// # Examples
253    ///
254    /// ```rust
255    /// use tenferro_linalg::{SvdDriver, SvdOptions};
256    ///
257    /// let options = SvdOptions::default().driver(SvdDriver::Jacobi);
258    /// assert_eq!(options.driver, SvdDriver::Jacobi);
259    /// ```
260    pub fn driver(mut self, driver: SvdDriver) -> Self {
261        self.driver = driver;
262        self
263    }
264}
265
266/// Algorithm family used by [`EighOptions`].
267///
268/// The family changes speed and rounding, not the decomposition contract, so
269/// gauges and AD rules are unaffected by the choice. A provider may ignore the
270/// selection and run its single eigh kernel. Analogous to [`SvdDriver`] and to
271/// `scipy.linalg.eigh(..., driver=...)`.
272///
273/// # Examples
274///
275/// ```rust
276/// use tenferro_linalg::{EighDriver, EighOptions};
277///
278/// let options = EighOptions::default().driver(EighDriver::Jacobi);
279/// assert_eq!(options.driver, EighDriver::Jacobi);
280/// assert_eq!(EighOptions::default().driver, EighDriver::Auto);
281/// ```
282#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
283pub enum EighDriver {
284    /// The provider's default policy: the fastest divide-and-conquer kernel it
285    /// can reach, including a single-launch batched entry point where one
286    /// exists.
287    ///
288    /// Measured on an A100, the batched entry point is about 100x to 280x
289    /// faster than the per-matrix loop this default used before. It is a
290    /// different vendor routine, so a batched result can differ from the
291    /// per-matrix loop in the last ULPs.
292    #[default]
293    Auto,
294    /// Divide-and-conquer, which is what [`Self::Auto`] already selects. Kept
295    /// as an explicit spelling of the same choice.
296    /// On the CUDA provider this selects `cusolverDn<t>syevd`.
297    DivideAndConquer,
298    /// Jacobi rotations: worth asking for only on batches of small matrices.
299    ///
300    /// Measured on an A100 it is slightly ahead of the default up to about
301    /// order 32 and loses from there, by about 4x at order 128 and far more on
302    /// wide spectra, where it is also the less accurate of the two.
303    /// On the CUDA provider this selects `cusolverDn<t>syevj`, `heevj` for
304    /// complex input, and their batched forms.
305    Jacobi,
306}
307
308/// Options for Hermitian eigenvalue decomposition.
309///
310/// # Examples
311///
312/// ```rust
313/// use tenferro_linalg::{EighDriver, EighOptions};
314///
315/// let options = EighOptions::default()
316///     .derivative_eps(1.0e-10)
317///     .driver(EighDriver::Jacobi);
318/// assert_eq!(options.derivative_eps, 1.0e-10);
319/// assert_eq!(options.driver, EighDriver::Jacobi);
320/// ```
321#[derive(Clone, Copy, Debug, PartialEq)]
322#[non_exhaustive]
323pub struct EighOptions {
324    /// Eigenvector gauge convention.
325    pub gauge: EighGauge,
326    /// AD derivative regularization for repeated or nearly repeated eigenvalues.
327    pub derivative_eps: f64,
328    /// Algorithm family for the eigensolver; a provider may ignore it.
329    pub driver: EighDriver,
330    /// Whether a real batch may fall back to one launch per matrix.
331    pub batch_policy: EighBatchPolicy,
332}
333
334impl Default for EighOptions {
335    fn default() -> Self {
336        Self {
337            gauge: EighGauge::Raw,
338            derivative_eps: DEFAULT_DECOMPOSITION_DERIVATIVE_EPS,
339            driver: EighDriver::Auto,
340            batch_policy: EighBatchPolicy::AllowPerMatrixFallback,
341        }
342    }
343}
344
345/// Whether a batched [`EighOptions`] call may fall back to one launch per
346/// matrix.
347///
348/// [`Self::RequireBatched`] is the strict contract for a caller that promised
349/// one launch per batch: when the selected driver's single-launch entry point
350/// is unavailable, or the provider has no batched routine at all, `eigh`
351/// returns a typed `Unsupported` error naming the missing capability instead of
352/// launching one call per matrix.
353///
354/// A single matrix, and a batch whose size is at most one, already is one call
355/// and is never refused.
356///
357/// # Carve-outs: where the policy is not consulted
358///
359/// The policy belongs to the two-output `eigh`, and it is part of that
360/// operation's identity. A traced graph that keeps only the eigenvalues is
361/// pruned to the values-only operation, which carries the driver but has no
362/// batch policy at all, and whose recompute is free to take the per-matrix
363/// loop:
364///
365/// - The traced extension op `LinalgOp::Eigh` is rewritten to `LinalgOp::EighVals`
366///   when the vectors are dead, so a traced `eigh_with(RequireBatched)` whose
367///   values feed the graph can be recomputed one launch per matrix on a cuSOLVER
368///   below 11.7.1 without reporting anything.
369/// - The values-only entries themselves (`eigvalsh` and friends) are not
370///   strict: they carry no [`EighOptions`] and always accept the loop.
371///
372/// Ask for the two outputs, or check the result rather than the request, when
373/// the launch count has to hold after tracing as well. Both refusals — the CUDA
374/// one and the provider-neutral one — are attached to the two-output operation
375/// for the same reason: the values-only paths reach the very same batched entry
376/// point, so there is no separate capability for them to require.
377///
378/// # Examples
379///
380/// ```rust
381/// use tenferro_linalg::{EighBatchPolicy, EighOptions};
382///
383/// let options = EighOptions::default().batch_policy(EighBatchPolicy::RequireBatched);
384/// assert_eq!(options.batch_policy, EighBatchPolicy::RequireBatched);
385/// assert_eq!(
386///     EighOptions::default().batch_policy,
387///     EighBatchPolicy::AllowPerMatrixFallback,
388/// );
389/// ```
390#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
391pub enum EighBatchPolicy {
392    /// Today's behaviour: a batch takes the single-launch routine when the
393    /// provider has one and the per-matrix loop when it does not.
394    #[default]
395    AllowPerMatrixFallback,
396    /// Refuse the per-matrix loop. On the CUDA provider this requires
397    /// `cusolverDnXsyevBatched`, exported since cuSOLVER 11.7.1.
398    ///
399    /// This binds the two-output `eigh` only; see the type-level carve-outs for
400    /// the values-only operation a traced graph is pruned to.
401    RequireBatched,
402}
403
404impl EighOptions {
405    /// Return options with the requested eigenvector gauge.
406    ///
407    /// # Examples
408    ///
409    /// ```rust
410    /// use tenferro_linalg::{EighGauge, EighOptions};
411    ///
412    /// let options = EighOptions::default().gauge(EighGauge::CanonicalPivot);
413    /// assert_eq!(options.gauge, EighGauge::CanonicalPivot);
414    /// ```
415    pub fn gauge(mut self, gauge: EighGauge) -> Self {
416        self.gauge = gauge;
417        self
418    }
419
420    /// Return options with an explicit derivative epsilon.
421    ///
422    /// # Examples
423    ///
424    /// ```rust
425    /// use tenferro_linalg::EighOptions;
426    ///
427    /// let options = EighOptions::default().derivative_eps(1.0e-9);
428    /// assert_eq!(options.derivative_eps, 1.0e-9);
429    /// ```
430    pub fn derivative_eps(mut self, derivative_eps: f64) -> Self {
431        self.derivative_eps = derivative_eps;
432        self
433    }
434
435    /// Return options with an explicit eigensolver driver.
436    ///
437    /// # Examples
438    ///
439    /// ```rust
440    /// use tenferro_linalg::{EighDriver, EighOptions};
441    ///
442    /// let options = EighOptions::default().driver(EighDriver::DivideAndConquer);
443    /// assert_eq!(options.driver, EighDriver::DivideAndConquer);
444    /// ```
445    pub fn driver(mut self, driver: EighDriver) -> Self {
446        self.driver = driver;
447        self
448    }
449
450    /// Return options that refuse the per-matrix fallback for a real batch.
451    ///
452    /// # Examples
453    ///
454    /// ```rust
455    /// use tenferro_linalg::{EighBatchPolicy, EighOptions};
456    ///
457    /// let options = EighOptions::default().batch_policy(EighBatchPolicy::RequireBatched);
458    /// assert_eq!(options.batch_policy, EighBatchPolicy::RequireBatched);
459    /// ```
460    pub fn batch_policy(mut self, batch_policy: EighBatchPolicy) -> Self {
461        self.batch_policy = batch_policy;
462        self
463    }
464}
465
466/// Options for QR decomposition.
467///
468/// # Examples
469///
470/// ```rust
471/// use tenferro_linalg::{QrGauge, QrOptions};
472///
473/// let options = QrOptions::default().gauge(QrGauge::PositiveDiagonal);
474/// assert_eq!(options.gauge, QrGauge::PositiveDiagonal);
475/// ```
476#[derive(Clone, Copy, Debug, PartialEq, Eq)]
477#[non_exhaustive]
478pub struct QrOptions {
479    /// QR sign or phase convention.
480    pub gauge: QrGauge,
481}
482
483impl Default for QrOptions {
484    fn default() -> Self {
485        Self {
486            gauge: QrGauge::Raw,
487        }
488    }
489}
490
491impl QrOptions {
492    /// Return options with the requested QR gauge.
493    ///
494    /// # Examples
495    ///
496    /// ```rust
497    /// use tenferro_linalg::{QrGauge, QrOptions};
498    ///
499    /// let options = QrOptions::default().gauge(QrGauge::PositiveDiagonal);
500    /// assert_eq!(options.gauge, QrGauge::PositiveDiagonal);
501    /// ```
502    pub fn gauge(mut self, gauge: QrGauge) -> Self {
503        self.gauge = gauge;
504        self
505    }
506}
507
508pub(crate) fn validate_derivative_eps(
509    op: &'static str,
510    derivative_eps: f64,
511) -> tenferro_tensor::Result<()> {
512    if derivative_eps.is_finite() && derivative_eps > 0.0 {
513        Ok(())
514    } else {
515        Err(Error::invalid_argument(
516            op,
517            "derivative_eps",
518            format!("must be positive and finite, got {derivative_eps}"),
519        ))
520    }
521}
522
523/// Refuse [`EighBatchPolicy::RequireBatched`] on a provider with no batched
524/// eigensolver.
525///
526/// A batch of at most one matrix is already one call, so the policy has nothing
527/// to refuse there and the call proceeds. `shape` is the operand's shape; the
528/// batch is every trailing axis.
529pub(crate) fn reject_required_batched(
530    op: &'static str,
531    options: &EighOptions,
532    shape: &[usize],
533) -> tenferro_tensor::Result<()> {
534    // A rank below two is not a matrix at all; leave that to the provider's own
535    // rank validation rather than indexing into it here.
536    let batch = shape.get(2..).map_or(1, |batch| batch.iter().product());
537    if options.batch_policy == EighBatchPolicy::RequireBatched && batch > 1 {
538        return Err(tenferro_tensor::Error::unsupported(
539            op,
540            "EighBatchPolicy::RequireBatched needs a batched eigensolver; this provider solves a \
541             batch with one launch per matrix, so the whole-batch single launch it was asked for \
542             is unavailable. Use EighBatchPolicy::AllowPerMatrixFallback to accept that loop",
543        ));
544    }
545    Ok(())
546}
547
548#[derive(Clone, Copy, Debug, PartialEq)]
549#[doc(hidden)]
550#[allow(dead_code)]
551pub(crate) enum LinalgOp {
552    Cholesky,
553    Lu,
554    LuFactor,
555    LuSolvePrepared {
556        transpose_a: bool,
557        conjugate_a: bool,
558    },
559    SignDetFromLuFactor,
560    LogAbsDetFromLuFactor,
561    FullPivLu,
562    FullPivLuSolve {
563        transpose_a: bool,
564    },
565    /// Solve `a @ x = b` with partial-pivot LU (same kernel as
566    /// `LinalgBackend::solve`). Two inputs (matrix, rhs) to one output.
567    /// The untracked eager surface constructs this variant.
568    Solve,
569    /// Fused partial-pivot solve that also returns its factors: inputs
570    /// `(a, b)`, outputs `(x, packed_lu, pivots)`, with the `LuFactor` packed
571    /// layout and 1-based LAPACK pivots.
572    ///
573    /// Tracked eager and traced `solve` emit this op so one backend call both
574    /// factors and solves while the factors stay available as AD residuals:
575    /// the tangent and the transpose solve reuse them through
576    /// [`LinalgOp::LuSolvePrepared`] instead of refactoring. It is never
577    /// pruned to [`LinalgOp::Solve`]; see `prune_outputs`.
578    LuFactorSolve,
579    Svd {
580        derivative_eps: f64,
581        gauge: SvdGauge,
582        driver: SvdDriver,
583    },
584    /// Full-matrices SVD: `U` is `m x m` and `Vh` is `n x n`, so the trailing
585    /// `Vh` rows span the input's right nullspace. Value-only: AD is
586    /// intentionally unsupported (see the linalg AD support manifest).
587    SvdFull,
588    /// Singular values only.
589    SvdVals {
590        derivative_eps: f64,
591        driver: SvdDriver,
592    },
593    Qr {
594        gauge: QrGauge,
595    },
596    RankRevealingQr {
597        gauge: QrGauge,
598        rtol: f64,
599        atol: f64,
600    },
601    HouseholderQrFactor,
602    HouseholderQrFromFactors,
603    HouseholderQrAppend,
604    HouseholderQrR {
605        gauge: QrGauge,
606    },
607    HouseholderQrQColumns {
608        start: usize,
609        end: usize,
610        gauge: QrGauge,
611    },
612    /// Internal AD residual operation for symbolic full thin-Q recovery.
613    HouseholderQrThinQ {
614        gauge: QrGauge,
615    },
616    /// Internal linear operation for abstract-state column append.
617    HouseholderQrAppendTangent,
618    /// Internal transpose operation that splits an appended state cotangent.
619    HouseholderQrSplitTangent {
620        right: bool,
621    },
622    Eigh {
623        derivative_eps: f64,
624        gauge: EighGauge,
625        driver: EighDriver,
626        batch_policy: EighBatchPolicy,
627    },
628    /// Eigenvalues only.
629    EighVals {
630        derivative_eps: f64,
631        driver: EighDriver,
632    },
633    Eig {
634        input_dtype: DType,
635    },
636    EigVals {
637        input_dtype: DType,
638    },
639    TriangularSolve {
640        left_side: bool,
641        lower: bool,
642        transpose_a: bool,
643        unit_diagonal: bool,
644    },
645}
646
647impl LinalgOp {
648    fn output_count(self) -> usize {
649        match self {
650            Self::Cholesky
651            | Self::EighVals { .. }
652            | Self::EigVals { .. }
653            | Self::FullPivLuSolve { .. }
654            | Self::LogAbsDetFromLuFactor
655            | Self::LuSolvePrepared { .. }
656            | Self::SignDetFromLuFactor
657            | Self::Solve
658            | Self::SvdVals { .. }
659            | Self::TriangularSolve { .. } => 1,
660            Self::Svd { .. } | Self::SvdFull | Self::LuFactorSolve => 3,
661            Self::RankRevealingQr { .. } | Self::Lu => 4,
662            Self::Qr { .. }
663            | Self::HouseholderQrFactor
664            | Self::HouseholderQrFromFactors
665            | Self::HouseholderQrAppend
666            | Self::Eigh { .. }
667            | Self::Eig { .. } => 2,
668            Self::HouseholderQrR { .. }
669            | Self::HouseholderQrQColumns { .. }
670            | Self::HouseholderQrThinQ { .. }
671            | Self::HouseholderQrAppendTangent
672            | Self::HouseholderQrSplitTangent { .. } => 1,
673            Self::LuFactor => 3,
674            Self::FullPivLu => 5,
675        }
676    }
677
678    fn input_count(self) -> usize {
679        match self {
680            Self::FullPivLuSolve { .. }
681            | Self::Solve
682            | Self::LuFactorSolve
683            | Self::TriangularSolve { .. }
684            | Self::HouseholderQrFromFactors
685            | Self::HouseholderQrR { .. }
686            | Self::HouseholderQrQColumns { .. }
687            | Self::HouseholderQrThinQ { .. } => 2,
688            Self::LogAbsDetFromLuFactor => 2,
689            Self::SignDetFromLuFactor | Self::HouseholderQrAppend => 3,
690            Self::HouseholderQrAppendTangent => 4,
691            Self::HouseholderQrSplitTangent { .. } => 3,
692            Self::LuSolvePrepared { .. } => 4,
693            _ => 1,
694        }
695    }
696
697    fn tag(self) -> u8 {
698        match self {
699            Self::Cholesky => 0,
700            Self::Lu => 1,
701            Self::FullPivLu => 2,
702            Self::FullPivLuSolve { .. } => 3,
703            Self::Svd { .. } => 4,
704            Self::Qr { .. } => 5,
705            Self::Eigh { .. } => 6,
706            Self::Eig { .. } => 7,
707            Self::TriangularSolve { .. } => 9,
708            Self::LuFactor => 10,
709            Self::LuSolvePrepared { .. } => 11,
710            Self::SvdVals { .. } => 12,
711            Self::EighVals { .. } => 13,
712            Self::EigVals { .. } => 14,
713            Self::SvdFull => 15,
714            Self::LogAbsDetFromLuFactor => 16,
715            Self::SignDetFromLuFactor => 17,
716            Self::Solve => 18,
717            Self::HouseholderQrFactor => 19,
718            Self::HouseholderQrFromFactors => 20,
719            Self::HouseholderQrAppend => 21,
720            Self::HouseholderQrR { .. } => 22,
721            Self::HouseholderQrQColumns { .. } => 23,
722            Self::HouseholderQrThinQ { .. } => 24,
723            Self::HouseholderQrAppendTangent => 25,
724            Self::HouseholderQrSplitTangent { .. } => 26,
725            Self::RankRevealingQr { .. } => 27,
726            Self::LuFactorSolve => 28,
727        }
728    }
729}
730
731#[derive(Clone, Debug, PartialEq)]
732#[doc(hidden)]
733pub(crate) struct LinalgExtensionOp {
734    op: LinalgOp,
735}
736
737impl LinalgExtensionOp {
738    pub(crate) fn new(op: LinalgOp) -> Self {
739        Self { op }
740    }
741
742    pub(crate) fn op(&self) -> LinalgOp {
743        self.op
744    }
745}
746
747impl ExtensionOp for LinalgExtensionOp {
748    fn family_id(&self) -> &'static str {
749        LINALG_EXTENSION_FAMILY_ID
750    }
751
752    fn payload_hash(&self, hasher: &mut dyn Hasher) {
753        hasher.write_u8(self.op.tag());
754        match self.op {
755            LinalgOp::Svd {
756                derivative_eps,
757                gauge,
758                driver,
759            } => {
760                hasher.write_u64(derivative_eps.to_bits());
761                hash_svd_gauge(hasher, gauge);
762                hash_svd_driver(hasher, driver);
763            }
764            LinalgOp::SvdVals {
765                derivative_eps,
766                driver,
767            } => {
768                hasher.write_u64(derivative_eps.to_bits());
769                hash_svd_driver(hasher, driver);
770            }
771            LinalgOp::EighVals {
772                derivative_eps,
773                driver,
774            } => {
775                hasher.write_u64(derivative_eps.to_bits());
776                hash_eigh_driver(hasher, driver);
777            }
778            LinalgOp::Qr { gauge }
779            | LinalgOp::HouseholderQrR { gauge }
780            | LinalgOp::HouseholderQrThinQ { gauge } => {
781                hash_qr_gauge(hasher, gauge);
782            }
783            LinalgOp::RankRevealingQr { gauge, rtol, atol } => {
784                hash_qr_gauge(hasher, gauge);
785                hasher.write_u64(rtol.to_bits());
786                hasher.write_u64(atol.to_bits());
787            }
788            LinalgOp::HouseholderQrQColumns { start, end, gauge } => {
789                hasher.write_usize(start);
790                hasher.write_usize(end);
791                hash_qr_gauge(hasher, gauge);
792            }
793            LinalgOp::Eigh {
794                derivative_eps,
795                gauge,
796                driver,
797                batch_policy,
798            } => {
799                hasher.write_u64(derivative_eps.to_bits());
800                hash_eigh_gauge(hasher, gauge);
801                hash_eigh_driver(hasher, driver);
802                hash_eigh_batch_policy(hasher, batch_policy);
803            }
804            LinalgOp::Eig { input_dtype } | LinalgOp::EigVals { input_dtype } => {
805                hash_dtype(hasher, input_dtype);
806            }
807            LinalgOp::FullPivLuSolve { transpose_a }
808            | LinalgOp::HouseholderQrSplitTangent { right: transpose_a } => {
809                hasher.write_u8(u8::from(transpose_a));
810            }
811            LinalgOp::LuSolvePrepared {
812                transpose_a,
813                conjugate_a,
814            } => {
815                hasher.write_u8(u8::from(transpose_a));
816                hasher.write_u8(u8::from(conjugate_a));
817            }
818            LinalgOp::TriangularSolve {
819                left_side,
820                lower,
821                transpose_a,
822                unit_diagonal,
823            } => {
824                hasher.write_u8(u8::from(left_side));
825                hasher.write_u8(u8::from(lower));
826                hasher.write_u8(u8::from(transpose_a));
827                hasher.write_u8(u8::from(unit_diagonal));
828            }
829            LinalgOp::Cholesky
830            | LinalgOp::Lu
831            | LinalgOp::LuFactor
832            | LinalgOp::LogAbsDetFromLuFactor
833            | LinalgOp::SignDetFromLuFactor
834            | LinalgOp::FullPivLu
835            | LinalgOp::SvdFull
836            | LinalgOp::Solve
837            | LinalgOp::LuFactorSolve
838            | LinalgOp::HouseholderQrFactor
839            | LinalgOp::HouseholderQrFromFactors
840            | LinalgOp::HouseholderQrAppend
841            | LinalgOp::HouseholderQrAppendTangent => {}
842        }
843    }
844
845    fn payload_eq(&self, other: &dyn ExtensionOp) -> bool {
846        other
847            .as_any()
848            .downcast_ref::<Self>()
849            .is_some_and(|that| self == that)
850    }
851
852    fn clone_arc(&self) -> Arc<dyn ExtensionOp> {
853        Arc::new(self.clone())
854    }
855
856    fn as_any(&self) -> &dyn Any {
857        self
858    }
859
860    fn input_count(&self) -> usize {
861        self.op.input_count()
862    }
863
864    fn output_count(&self) -> usize {
865        self.op.output_count()
866    }
867
868    fn semantic_effects(&self) -> tenferro_ops::ext_op::ExtensionEffectDeclaration<'_> {
869        tenferro_ops::ext_op::ExtensionEffectDeclaration::Declared(&[])
870    }
871
872    fn semantic_aliases(&self) -> tenferro_ops::ext_op::ExtensionAliasDeclaration<'_> {
873        tenferro_ops::ext_op::ExtensionAliasDeclaration::AllFresh
874    }
875
876    fn prune_outputs(&self, live_outputs: &[bool]) -> Option<Arc<dyn ExtensionOp>> {
877        match self.op {
878            LinalgOp::Svd {
879                derivative_eps,
880                driver,
881                ..
882            } if live_outputs == [false, true, false] => {
883                Some(Arc::new(Self::new(LinalgOp::SvdVals {
884                    derivative_eps,
885                    driver,
886                })))
887            }
888            LinalgOp::Eigh {
889                derivative_eps,
890                driver,
891                ..
892            } if live_outputs == [true, false] => Some(Arc::new(Self::new(LinalgOp::EighVals {
893                derivative_eps,
894                driver,
895            }))),
896            LinalgOp::Eig { input_dtype } if live_outputs == [true, false] => {
897                Some(Arc::new(Self::new(LinalgOp::EigVals { input_dtype })))
898            }
899            // `LuFactorSolve` is deliberately never pruned to `Solve`. Traced
900            // AD compiles its source program with this pruning before
901            // differentiating, so a prune would drop the saved factors and
902            // force the adjoint solve to refactor `A`. A primal only program
903            // loses nothing by keeping the op: the fused CPU kernel does the
904            // `Solve` kernel's work, and the factor buffer the plain solve
905            // uses as scratch becomes the (pooled) LU output instead.
906            _ => None,
907        }
908    }
909
910    fn infer_output_meta(
911        &self,
912        ctx: &mut tenferro_ops::ExtensionShapeContext<'_>,
913    ) -> tenferro_tensor::Result<Vec<(DType, Vec<SymDim>)>> {
914        let input_dtypes = (0..self.input_count())
915            .map(|input| ctx.input_dtype(input))
916            .collect::<Result<Vec<_>, _>>()?;
917        let input_shapes = (0..self.input_count())
918            .map(|input| ctx.input_shape(input))
919            .collect::<Result<Vec<_>, _>>()?;
920        let metas = match self.op {
921            LinalgOp::Cholesky => {
922                require_matrix_meta("tenferro-linalg.cholesky", input_shapes[0])?;
923                vec![(promote_dtypes(&input_dtypes), input_shapes[0].to_vec())]
924            }
925            LinalgOp::FullPivLuSolve { .. } => {
926                require_matrix_meta("tenferro-linalg.full_piv_lu_solve", input_shapes[0])?;
927                require_matrix_meta("tenferro-linalg.full_piv_lu_solve", input_shapes[1])?;
928                vec![(promote_dtypes(&input_dtypes), input_shapes[1].to_vec())]
929            }
930            LinalgOp::Solve => {
931                require_matrix_meta("tenferro-linalg.solve", input_shapes[0])?;
932                require_matrix_meta("tenferro-linalg.solve", input_shapes[1])?;
933                vec![(promote_dtypes(&input_dtypes), input_shapes[1].to_vec())]
934            }
935            LinalgOp::LuFactorSolve => {
936                require_matrix_meta("tenferro-linalg.lu_factor_solve", input_shapes[1])?;
937                let mut factors = lu_factor_meta(input_dtypes[0], input_shapes[0])?.into_iter();
938                let (Some(packed_lu), Some(pivots)) = (factors.next(), factors.next()) else {
939                    return Err(Error::Internal(
940                        "lu_factor_solve: lu_factor metadata returned fewer than two outputs"
941                            .into(),
942                    ));
943                };
944                vec![
945                    (promote_dtypes(&input_dtypes), input_shapes[1].to_vec()),
946                    packed_lu,
947                    pivots,
948                ]
949            }
950            LinalgOp::TriangularSolve { .. } => {
951                require_matrix_meta("tenferro-linalg.triangular_solve", input_shapes[0])?;
952                require_matrix_meta("tenferro-linalg.triangular_solve", input_shapes[1])?;
953                vec![(promote_dtypes(&input_dtypes), input_shapes[1].to_vec())]
954            }
955            LinalgOp::LuSolvePrepared { .. } => {
956                require_matrix_meta("tenferro-linalg.lu_solve_prepared_lu", input_shapes[0])?;
957                require_matrix_meta("tenferro-linalg.lu_solve_prepared_rhs", input_shapes[3])?;
958                vec![(
959                    promote_dtypes(&[input_dtypes[0], input_dtypes[3]]),
960                    input_shapes[3].to_vec(),
961                )]
962            }
963            LinalgOp::Lu => lu_meta(input_dtypes[0], input_shapes[0])?,
964            LinalgOp::LuFactor => lu_factor_meta(input_dtypes[0], input_shapes[0])?,
965            LinalgOp::SignDetFromLuFactor => {
966                let input_shape = input_shapes[0].to_vec();
967                let packed_shape = input_shapes[1].to_vec();
968                let parity_shape = input_shapes[2].to_vec();
969                require_matrix_meta("tenferro-linalg.signdet_from_lu_factor", &input_shape)?;
970                ctx.require_axes_equal((0, 0), (0, 1))?;
971                vec![signdet_from_lu_factor_meta(
972                    input_dtypes[0],
973                    &input_shape,
974                    &packed_shape,
975                    &parity_shape,
976                )?]
977            }
978            LinalgOp::LogAbsDetFromLuFactor => {
979                let input_shape = input_shapes[0].to_vec();
980                let packed_shape = input_shapes[1].to_vec();
981                require_matrix_meta("tenferro-linalg.logabsdet_from_lu_factor", &input_shape)?;
982                ctx.require_axes_equal((0, 0), (0, 1))?;
983                vec![logabsdet_from_lu_factor_meta(
984                    input_dtypes[0],
985                    &input_shape,
986                    &packed_shape,
987                )?]
988            }
989            LinalgOp::FullPivLu => full_piv_lu_meta(input_dtypes[0], input_shapes[0])?,
990            LinalgOp::Svd { .. } => svd_meta(input_dtypes[0], input_shapes[0])?,
991            LinalgOp::SvdFull => svd_full_meta(input_dtypes[0], input_shapes[0])?,
992            LinalgOp::SvdVals { .. } => {
993                vec![svd_values_meta(input_dtypes[0], input_shapes[0])?]
994            }
995            LinalgOp::Qr { .. } => qr_meta(input_dtypes[0], input_shapes[0])?,
996            LinalgOp::RankRevealingQr { .. } => {
997                rank_revealing_qr_meta(input_dtypes[0], input_shapes[0])?
998            }
999            LinalgOp::HouseholderQrFactor => {
1000                householder_qr_factor_meta(input_dtypes[0], input_shapes[0])?
1001            }
1002            LinalgOp::HouseholderQrFromFactors => {
1003                householder_qr_from_factors_meta(&input_dtypes, &input_shapes)?
1004            }
1005            LinalgOp::HouseholderQrAppend => {
1006                householder_qr_append_meta(&input_dtypes, &input_shapes)?
1007            }
1008            LinalgOp::HouseholderQrR { .. } => vec![householder_qr_r_meta(
1009                &input_dtypes,
1010                input_shapes[0],
1011                input_shapes[1],
1012            )?],
1013            LinalgOp::HouseholderQrQColumns { start, end, .. } => {
1014                vec![householder_qr_q_columns_meta(
1015                    &input_dtypes,
1016                    input_shapes[0],
1017                    input_shapes[1],
1018                    start,
1019                    end,
1020                )?]
1021            }
1022            LinalgOp::HouseholderQrThinQ { .. } => {
1023                vec![householder_qr_thin_q_meta(
1024                    &input_dtypes,
1025                    input_shapes[0],
1026                    input_shapes[1],
1027                )?]
1028            }
1029            LinalgOp::HouseholderQrAppendTangent => {
1030                vec![householder_qr_append_tangent_meta(
1031                    &input_dtypes,
1032                    &input_shapes,
1033                )?]
1034            }
1035            LinalgOp::HouseholderQrSplitTangent { right } => {
1036                vec![householder_qr_split_tangent_meta(
1037                    &input_dtypes,
1038                    &input_shapes,
1039                    right,
1040                )?]
1041            }
1042            LinalgOp::Eigh { .. } => eigh_meta(input_dtypes[0], input_shapes[0])?,
1043            LinalgOp::EighVals { .. } => vec![eigh_values_meta(input_dtypes[0], input_shapes[0])?],
1044            LinalgOp::Eig { input_dtype } => eig_meta(input_dtype, input_shapes[0])?,
1045            LinalgOp::EigVals { input_dtype } => {
1046                vec![eig_values_meta(input_dtype, input_shapes[0])?]
1047            }
1048        };
1049        Ok(metas)
1050    }
1051}
1052
1053fn execute_linalg_extension_reads_on_session<B: Engine + ?Sized>(
1054    op: &LinalgExtensionOp,
1055    inputs: &[TensorRead<'_>],
1056    session: &mut B,
1057) -> tenferro_tensor::Result<Vec<Tensor>> {
1058    if let Some(result) = with_cpu_engine(session, |session| {
1059        execute_linalg_extension_reads_in_session(op, inputs, session)
1060    }) {
1061        return result;
1062    }
1063    #[cfg(feature = "cuda")]
1064    if let Some(result) = with_cuda_engine(session, |session| {
1065        execute_linalg_extension_reads_in_session(op, inputs, session)
1066    }) {
1067        return result;
1068    }
1069    Err(Error::unsupported(
1070        "linalg_extension",
1071        "selected backend session does not expose a linalg execution capability",
1072    ))
1073}
1074
1075fn execute_linalg_extension_reads_in_session<S: LinalgBackend>(
1076    op: &LinalgExtensionOp,
1077    inputs: &[TensorRead<'_>],
1078    session: &mut S,
1079) -> tenferro_tensor::Result<Vec<Tensor>> {
1080    if op.op() == LinalgOp::HouseholderQrAppendTangent {
1081        let left = session.to_contiguous_read(inputs[0].clone())?;
1082        let right = session.to_contiguous_read(inputs[1].clone())?;
1083        return Ok(vec![session.concatenate(&[&left, &right], 1)?]);
1084    }
1085    if let LinalgOp::HouseholderQrSplitTangent { right } = op.op() {
1086        let cotangent_shape = inputs[0].shape().to_vec();
1087        let left_shape = inputs[1].shape().to_vec();
1088        let right_shape = inputs[2].shape().to_vec();
1089        let config =
1090            householder_qr_split_config(&cotangent_shape, &left_shape, &right_shape, right)?;
1091        let cotangent = session.to_contiguous_read(inputs[0].clone())?;
1092        return Ok(vec![session.slice(&cotangent, &config)?]);
1093    }
1094    // Preserve borrowed layouts through the same provider hooks used by the
1095    // concrete read API. In particular, CPU Faer can consume strided views;
1096    // packing here would defeat that path before provider dispatch.
1097    match op.op() {
1098        LinalgOp::Cholesky => return Ok(vec![session.cholesky_read(inputs[0].clone())?]),
1099        LinalgOp::Lu => return session.lu_read(inputs[0].clone()),
1100        LinalgOp::FullPivLu => return session.full_piv_lu_read(inputs[0].clone()),
1101        LinalgOp::Svd {
1102            derivative_eps,
1103            gauge,
1104            driver,
1105        } => {
1106            return session.svd_with_options_read(
1107                inputs[0].clone(),
1108                SvdOptions::default()
1109                    .derivative_eps(derivative_eps)
1110                    .gauge(gauge)
1111                    .driver(driver),
1112            );
1113        }
1114        LinalgOp::SvdFull => return session.svd_full_read(inputs[0].clone()),
1115        LinalgOp::SvdVals { driver, .. } => {
1116            return Ok(vec![
1117                session.svd_values_with_driver_read(inputs[0].clone(), driver)?
1118            ]);
1119        }
1120        LinalgOp::Qr { gauge } => {
1121            return session.qr_with_options_read(inputs[0].clone(), QrOptions { gauge });
1122        }
1123        LinalgOp::RankRevealingQr { gauge, rtol, atol } => {
1124            return session.rank_revealing_qr_read(
1125                inputs[0].clone(),
1126                RankRevealingQrOptions { gauge, rtol, atol },
1127            );
1128        }
1129        LinalgOp::Eigh {
1130            derivative_eps,
1131            gauge,
1132            driver,
1133            batch_policy,
1134        } => {
1135            return session.eigh_with_options_read(
1136                inputs[0].clone(),
1137                EighOptions {
1138                    derivative_eps,
1139                    gauge,
1140                    driver,
1141                    batch_policy,
1142                },
1143            );
1144        }
1145        LinalgOp::EighVals { driver, .. } => {
1146            return Ok(vec![
1147                session.eigh_values_with_driver_read(inputs[0].clone(), driver)?
1148            ]);
1149        }
1150        LinalgOp::Eig { .. } => return session.eig_read(inputs[0].clone()),
1151        LinalgOp::EigVals { .. } => return Ok(vec![session.eig_values_read(inputs[0].clone())?]),
1152        LinalgOp::Solve => match session.solve_read(inputs[0].clone(), inputs[1].clone()) {
1153            Ok(output) => return Ok(vec![output]),
1154            Err(error) if error.kind() == ErrorKind::Unsupported => {}
1155            Err(error) => return Err(error),
1156        },
1157        _ => {}
1158    }
1159    if let LinalgOp::TriangularSolve {
1160        left_side,
1161        lower,
1162        transpose_a,
1163        unit_diagonal,
1164    } = op.op()
1165    {
1166        match session.triangular_solve_read(
1167            inputs[0].clone(),
1168            inputs[1].clone(),
1169            left_side,
1170            lower,
1171            transpose_a,
1172            unit_diagonal,
1173        ) {
1174            Ok(output) => return Ok(vec![output]),
1175            Err(error) if error.kind() == ErrorKind::Unsupported => {}
1176            Err(error) => return Err(error),
1177        }
1178    }
1179
1180    // The owned-only hooks need materialized views, not copies of inputs that
1181    // are already owned tensors (notably the saved matrix and LU in backward).
1182    let materialized_inputs = inputs
1183        .iter()
1184        .filter(|input| input.as_tensor().is_none())
1185        .cloned()
1186        .map(|input| session.to_contiguous_read(input))
1187        .collect::<tenferro_tensor::Result<Vec<_>>>()?;
1188    let mut views = materialized_inputs.iter();
1189    // INVARIANT: exactly one materialized tensor was produced per View, in
1190    // input order; every input therefore contributes exactly one reference.
1191    let input_refs: Vec<&Tensor> = inputs
1192        .iter()
1193        .filter_map(|input| input.as_tensor().or_else(|| views.next()))
1194        .collect();
1195    execute_linalg(op.op(), &input_refs, session)
1196}
1197
1198fn linalg_session_supported<B: Engine + 'static>(
1199    #[cfg_attr(not(feature = "cuda"), allow(unused_variables))] op: &LinalgExtensionOp,
1200) -> bool {
1201    // The `supports_session` contract (capability.rs) requires that an op is
1202    // admitted to a scheduler session only when the session executor genuinely
1203    // executes it without returning `Unsupported`. Admission is exactly
1204    // per-op/per-backend so `apply_eager` keeps the native prepared path for
1205    // every op the session can actually run (issue #1665).
1206    let type_id = std::any::TypeId::of::<B>();
1207    if type_id == std::any::TypeId::of::<tenferro_cpu::CpuEngine>() {
1208        // Every CPU linalg kernel, including full-matrices SVD, runs in-session
1209        // on the single faer backend, so the type-only seam admits the whole
1210        // family without inspecting a provider kind.
1211        return true;
1212    }
1213    #[cfg(feature = "cuda")]
1214    {
1215        if type_id == std::any::TypeId::of::<tenferro_gpu::cuda::CudaEngine>() {
1216            return match op.op() {
1217                // Complete-pivoting LU and general eig have no CUDA kernels.
1218                LinalgOp::FullPivLu | LinalgOp::FullPivLuSolve { .. } => false,
1219                LinalgOp::Eig { .. } | LinalgOp::EigVals { .. } => false,
1220                // Plain partial-pivot solve runs in-session via cuSOLVER
1221                // getrf plus prepared pivot/triangular solves
1222                // (`gpu/linalg.rs::solve` = lu_factor + lu_solve_prepared, no
1223                // Unsupported path for F32/F64/C32/C64), so it is admitted.
1224                LinalgOp::Solve => true,
1225                // The fused solve runs the trait default on CUDA: getrf then
1226                // the plain prepared solve, both admitted above.
1227                LinalgOp::LuFactorSolve => true,
1228                // Conjugate-only prepared LU solve is unsupported on CUDA.
1229                LinalgOp::LuSolvePrepared {
1230                    transpose_a: false,
1231                    conjugate_a: true,
1232                } => false,
1233                _ => true,
1234            };
1235        }
1236    }
1237    false
1238}
1239
1240fn execute_linalg_extension_in_session(
1241    op: &LinalgExtensionOp,
1242    session: &mut dyn Engine,
1243    _extension_caches: &mut tenferro_runtime::ExtensionCacheStore,
1244    inputs: &[TensorRead<'_>],
1245) -> tenferro_tensor::Result<Vec<Tensor>> {
1246    // Reuse the existing session executor that the eager and scheduler paths
1247    // already share; it downcasts the borrowed session to the CPU/CUDA exec
1248    // session and runs the same forward kernel for every LinalgOp.
1249    execute_linalg_extension_reads_on_session(op, inputs, session)
1250}
1251
1252define_extension_runtime! {
1253    runtime = LinalgRuntime,
1254    family_id = LINALG_EXTENSION_FAMILY_ID,
1255    op_type = LinalgExtensionOp,
1256    execute_in_session = execute_linalg_extension_in_session,
1257    session_supported = linalg_session_supported,
1258    backend_bound = Engine,
1259}
1260
1261fn execute_linalg<B: LinalgBackend>(
1262    op: LinalgOp,
1263    inputs: &[&Tensor],
1264    backend: &mut B,
1265) -> tenferro_tensor::Result<Vec<Tensor>> {
1266    match op {
1267        LinalgOp::Cholesky => Ok(vec![backend.cholesky(inputs[0])?]),
1268        LinalgOp::Lu => backend.lu(inputs[0]),
1269        LinalgOp::LuFactor => backend.lu_factor(inputs[0]),
1270        LinalgOp::SignDetFromLuFactor => {
1271            Ok(vec![signdet_from_lu_factor(inputs[1], inputs[2], backend)?])
1272        }
1273        LinalgOp::LogAbsDetFromLuFactor => Ok(vec![logabsdet_from_lu_factor(inputs[1], backend)?]),
1274        LinalgOp::LuSolvePrepared {
1275            transpose_a,
1276            conjugate_a,
1277        } => Ok(vec![backend.lu_solve_prepared(
1278            inputs[0],
1279            inputs[1],
1280            inputs[2],
1281            inputs[3],
1282            transpose_a,
1283            conjugate_a,
1284        )?]),
1285        LinalgOp::FullPivLu => backend.full_piv_lu(inputs[0]),
1286        LinalgOp::FullPivLuSolve { transpose_a } => Ok(vec![backend.full_piv_lu_solve(
1287            inputs[0],
1288            inputs[1],
1289            transpose_a,
1290        )?]),
1291        LinalgOp::Solve => Ok(vec![backend.solve(inputs[0], inputs[1])?]),
1292        LinalgOp::LuFactorSolve => backend.lu_factor_solve(inputs[0], inputs[1]),
1293        LinalgOp::Svd {
1294            derivative_eps,
1295            gauge,
1296            driver,
1297        } => backend.svd_with_options(
1298            inputs[0],
1299            SvdOptions::default()
1300                .derivative_eps(derivative_eps)
1301                .gauge(gauge)
1302                .driver(driver),
1303        ),
1304        LinalgOp::SvdFull => backend.svd_full(inputs[0]),
1305        LinalgOp::SvdVals { driver, .. } => {
1306            Ok(vec![backend.svd_values_with_driver(inputs[0], driver)?])
1307        }
1308        LinalgOp::Qr { gauge } => backend.qr_with_options(inputs[0], QrOptions { gauge }),
1309        LinalgOp::RankRevealingQr { gauge, rtol, atol } => {
1310            backend.rank_revealing_qr(inputs[0], RankRevealingQrOptions { gauge, rtol, atol })
1311        }
1312        LinalgOp::HouseholderQrFactor => {
1313            let state = backend.householder_qr(inputs[0])?;
1314            Ok(vec![state.packed, state.coeff])
1315        }
1316        LinalgOp::HouseholderQrFromFactors => {
1317            let state = backend.householder_qr_from_factors(inputs[0], inputs[1])?;
1318            Ok(vec![state.packed, state.coeff])
1319        }
1320        LinalgOp::HouseholderQrAppend => {
1321            let state = backend.householder_qr_append(inputs[0], inputs[1], inputs[2])?;
1322            Ok(vec![state.packed, state.coeff])
1323        }
1324        LinalgOp::HouseholderQrR { gauge } => Ok(vec![backend.householder_qr_r(
1325            inputs[0],
1326            inputs[1],
1327            QrOptions { gauge },
1328        )?]),
1329        LinalgOp::HouseholderQrQColumns { start, end, gauge } => Ok(vec![backend
1330            .householder_qr_q_columns(inputs[0], inputs[1], start..end, QrOptions { gauge })?]),
1331        LinalgOp::HouseholderQrThinQ { gauge } => {
1332            let end = inputs[1].shape().first().copied().ok_or_else(|| {
1333                Error::rank_mismatch("tenferro-linalg.householder_qr_thin_q", 1, 0)
1334            })?;
1335            Ok(vec![backend.householder_qr_q_columns(
1336                inputs[0],
1337                inputs[1],
1338                0..end,
1339                QrOptions { gauge },
1340            )?])
1341        }
1342        LinalgOp::HouseholderQrAppendTangent => {
1343            Ok(vec![backend.concatenate(&[inputs[0], inputs[1]], 1)?])
1344        }
1345        LinalgOp::HouseholderQrSplitTangent { right } => {
1346            let config = householder_qr_split_config(
1347                inputs[0].shape(),
1348                inputs[1].shape(),
1349                inputs[2].shape(),
1350                right,
1351            )?;
1352            Ok(vec![backend.slice(inputs[0], &config)?])
1353        }
1354        LinalgOp::Eigh {
1355            derivative_eps,
1356            gauge,
1357            driver,
1358            batch_policy,
1359        } => backend.eigh_with_options(
1360            inputs[0],
1361            EighOptions {
1362                derivative_eps,
1363                gauge,
1364                driver,
1365                batch_policy,
1366            },
1367        ),
1368        LinalgOp::EighVals { driver, .. } => {
1369            Ok(vec![backend.eigh_values_with_driver(inputs[0], driver)?])
1370        }
1371        LinalgOp::Eig { .. } => backend.eig(inputs[0]),
1372        LinalgOp::EigVals { .. } => Ok(vec![backend.eig_values(inputs[0])?]),
1373        LinalgOp::TriangularSolve {
1374            left_side,
1375            lower,
1376            transpose_a,
1377            unit_diagonal,
1378        } => Ok(vec![backend.triangular_solve(
1379            inputs[0],
1380            inputs[1],
1381            left_side,
1382            lower,
1383            transpose_a,
1384            unit_diagonal,
1385        )?]),
1386    }
1387}
1388
1389/// Sign (or complex phase) of the determinant from an LU factorization.
1390///
1391/// The sign is built from the per-pivot signs rather than from the determinant
1392/// product, so it is magnitude-independent: a determinant whose product would
1393/// underflow or overflow still reports its mathematical sign. `Sign` maps an
1394/// exactly zero pivot to zero, so finite singular LU factors report zero sign
1395/// for both real and complex inputs, matching the existing eager composite.
1396fn signdet_from_lu_factor<B: LinalgBackend + ?Sized>(
1397    packed_lu: &Tensor,
1398    parity: &Tensor,
1399    backend: &mut B,
1400) -> tenferro_tensor::Result<Tensor> {
1401    let diag = backend.extract_diagonal(packed_lu, 0, 1)?;
1402    let sign_diag = backend.sign_read(TensorRead::from_tensor(&diag))?;
1403    let sign_u = backend.reduce_prod_read(TensorRead::from_tensor(&sign_diag), &[0])?;
1404    backend.mul_read(
1405        TensorRead::from_tensor(parity),
1406        TensorRead::from_tensor(&sign_u),
1407    )
1408}
1409
1410fn logabsdet_from_lu_factor<B: LinalgBackend + ?Sized>(
1411    packed_lu: &Tensor,
1412    backend: &mut B,
1413) -> tenferro_tensor::Result<Tensor> {
1414    let diag = backend.extract_diagonal(packed_lu, 0, 1)?;
1415    let abs = backend.abs_read(TensorRead::from_tensor(&diag))?;
1416    let log = backend.log_read(TensorRead::from_tensor(&abs))?;
1417    backend.reduce_sum_read(TensorRead::from_tensor(&log), &[0])
1418}
1419
1420pub(crate) fn apply_svd_gauge(
1421    gauge: SvdGauge,
1422    outputs: &mut [Tensor],
1423) -> tenferro_tensor::Result<()> {
1424    match gauge {
1425        SvdGauge::Raw => Ok(()),
1426        SvdGauge::CanonicalPivot => apply_canonical_pivot_svd_gauge(outputs),
1427    }
1428}
1429
1430fn apply_canonical_pivot_svd_gauge(outputs: &mut [Tensor]) -> tenferro_tensor::Result<()> {
1431    if outputs.len() != 3 {
1432        return Err(Error::invalid_argument(
1433            "tenferro-linalg.svd",
1434            "outputs",
1435            format!(
1436                "canonical SVD gauge expected three outputs, got {}",
1437                outputs.len()
1438            ),
1439        ));
1440    }
1441
1442    let (u_slice, rest) = outputs.split_at_mut(1);
1443    let (singular_slice, vt_slice) = rest.split_at_mut(1);
1444    let u = &mut u_slice[0];
1445    let singular_values = &singular_slice[0];
1446    let vt = &mut vt_slice[0];
1447    let u_shape = u.shape().to_vec();
1448    let s_shape = singular_values.shape().to_vec();
1449    let vt_shape = vt.shape().to_vec();
1450    if u_shape.len() < 2 || vt_shape.len() < 2 || s_shape.is_empty() {
1451        return Err(Error::invalid_argument(
1452            "tenferro-linalg.svd",
1453            "outputs",
1454            format!(
1455                "canonical SVD gauge expected U rank >= 2, S rank >= 1, VT rank >= 2; got U={u_shape:?}, S={s_shape:?}, VT={vt_shape:?}"
1456            ),
1457        ));
1458    }
1459
1460    let m = u_shape[0];
1461    let k = u_shape[1];
1462    let n = vt_shape[1];
1463    if s_shape[0] != k
1464        || vt_shape[0] != k
1465        || u_shape[2..] != vt_shape[2..]
1466        || s_shape[1..] != u_shape[2..]
1467    {
1468        return Err(Error::invalid_argument(
1469            "tenferro-linalg.svd",
1470            "outputs",
1471            format!(
1472                "canonical SVD gauge expected compatible compact SVD shapes, got U={u_shape:?}, S={s_shape:?}, VT={vt_shape:?}"
1473            ),
1474        ));
1475    }
1476    let layout = canonical_svd_gauge_layout(m, k, n, &u_shape[2..])?;
1477
1478    match (u.dtype(), vt.dtype()) {
1479        (tenferro_tensor::DType::F64, tenferro_tensor::DType::F64) => {
1480            let (u, vt) = svd_gauge_pair_mut::<f64>(u, vt)?;
1481            canonicalize_svd_gauge_f64(u.host_data_mut()?, vt.host_data_mut()?, layout)
1482        }
1483        (tenferro_tensor::DType::F32, tenferro_tensor::DType::F32) => {
1484            let (u, vt) = svd_gauge_pair_mut::<f32>(u, vt)?;
1485            canonicalize_svd_gauge_f32(u.host_data_mut()?, vt.host_data_mut()?, layout)
1486        }
1487        (tenferro_tensor::DType::C64, tenferro_tensor::DType::C64) => {
1488            let (u, vt) = svd_gauge_pair_mut::<Complex64>(u, vt)?;
1489            canonicalize_svd_gauge_c64(u.host_data_mut()?, vt.host_data_mut()?, layout)
1490        }
1491        (tenferro_tensor::DType::C32, tenferro_tensor::DType::C32) => {
1492            let (u, vt) = svd_gauge_pair_mut::<Complex32>(u, vt)?;
1493            canonicalize_svd_gauge_c32(u.host_data_mut()?, vt.host_data_mut()?, layout)
1494        }
1495        (u_dtype, vt_dtype) => Err(Error::dtype_mismatch(
1496            "tenferro-linalg.svd",
1497            u_dtype,
1498            vt_dtype,
1499        )),
1500    }
1501}
1502
1503/// The typed pair behind a same-dtype pair of mutable tensors, or this module's refusal.
1504fn svd_gauge_pair_mut<'a, T: tenferro_tensor::TensorScalar>(
1505    u: &'a mut Tensor,
1506    vt: &'a mut Tensor,
1507) -> tenferro_tensor::Result<(
1508    &'a mut tenferro_tensor::TypedTensor<T>,
1509    &'a mut tenferro_tensor::TypedTensor<T>,
1510)> {
1511    let (u_dtype, vt_dtype) = (u.dtype(), vt.dtype());
1512    let u_t = u
1513        .as_typed_mut::<T>()
1514        .ok_or_else(|| Error::dtype_mismatch("tenferro-linalg.svd", u_dtype, vt_dtype))?;
1515    let vt_t = vt
1516        .as_typed_mut::<T>()
1517        .ok_or_else(|| Error::dtype_mismatch("tenferro-linalg.svd", u_dtype, vt_dtype))?;
1518    Ok((u_t, vt_t))
1519}
1520
1521#[derive(Clone, Copy, Debug, PartialEq, Eq)]
1522struct CanonicalSvdGaugeLayout {
1523    m: usize,
1524    k: usize,
1525    batch_count: usize,
1526    u_batch_len: usize,
1527    vt_batch_len: usize,
1528    u_len: usize,
1529    vt_len: usize,
1530}
1531
1532impl CanonicalSvdGaugeLayout {
1533    fn validate_storage(self, u_len: usize, vt_len: usize) -> tenferro_tensor::Result<()> {
1534        if u_len != self.u_len {
1535            return Err(Error::invalid_argument(
1536                "tenferro-linalg.svd",
1537                "U storage",
1538                format!(
1539                    "canonical SVD gauge expected U storage length {}, got {u_len}",
1540                    self.u_len
1541                ),
1542            ));
1543        }
1544        if vt_len != self.vt_len {
1545            return Err(Error::invalid_argument(
1546                "tenferro-linalg.svd",
1547                "VT storage",
1548                format!(
1549                    "canonical SVD gauge expected VT storage length {}, got {vt_len}",
1550                    self.vt_len
1551                ),
1552            ));
1553        }
1554        Ok(())
1555    }
1556}
1557
1558fn canonical_svd_gauge_layout(
1559    m: usize,
1560    k: usize,
1561    n: usize,
1562    batch_shape: &[usize],
1563) -> tenferro_tensor::Result<CanonicalSvdGaugeLayout> {
1564    let batch_count = tenferro_tensor::validate::checked_shape_product(
1565        "tenferro-linalg.svd",
1566        "canonical SVD batch",
1567        batch_shape,
1568    )?;
1569    let u_batch_len = tenferro_tensor::validate::checked_shape_product(
1570        "tenferro-linalg.svd",
1571        "canonical SVD U batch",
1572        &[m, k],
1573    )?;
1574    let vt_batch_len = tenferro_tensor::validate::checked_shape_product(
1575        "tenferro-linalg.svd",
1576        "canonical SVD VT batch",
1577        &[k, n],
1578    )?;
1579    let u_len = tenferro_tensor::validate::checked_shape_product(
1580        "tenferro-linalg.svd",
1581        "canonical SVD U storage",
1582        &[u_batch_len, batch_count],
1583    )?;
1584    let vt_len = tenferro_tensor::validate::checked_shape_product(
1585        "tenferro-linalg.svd",
1586        "canonical SVD VT storage",
1587        &[vt_batch_len, batch_count],
1588    )?;
1589    Ok(CanonicalSvdGaugeLayout {
1590        m,
1591        k,
1592        batch_count,
1593        u_batch_len,
1594        vt_batch_len,
1595        u_len,
1596        vt_len,
1597    })
1598}
1599
1600fn canonicalize_svd_gauge_f64(
1601    u: &mut [f64],
1602    vt: &mut [f64],
1603    layout: CanonicalSvdGaugeLayout,
1604) -> tenferro_tensor::Result<()> {
1605    layout.validate_storage(u.len(), vt.len())?;
1606    if layout.batch_count == 0 || layout.u_batch_len == 0 || layout.vt_batch_len == 0 {
1607        return Ok(());
1608    }
1609    for (u_batch, vt_batch) in u
1610        .chunks_exact_mut(layout.u_batch_len)
1611        .zip(vt.chunks_exact_mut(layout.vt_batch_len))
1612    {
1613        for (col, u_column) in u_batch.chunks_exact_mut(layout.m).enumerate() {
1614            let pivot = max_abs_pivot_f64(u_column);
1615            let pivot_value = u_column[pivot];
1616            if pivot_value < 0.0 {
1617                for value in u_column {
1618                    *value = -*value;
1619                }
1620                for vt_column in vt_batch.chunks_exact_mut(layout.k) {
1621                    vt_column[col] = -vt_column[col];
1622                }
1623            }
1624        }
1625    }
1626    Ok(())
1627}
1628
1629fn canonicalize_svd_gauge_f32(
1630    u: &mut [f32],
1631    vt: &mut [f32],
1632    layout: CanonicalSvdGaugeLayout,
1633) -> tenferro_tensor::Result<()> {
1634    layout.validate_storage(u.len(), vt.len())?;
1635    if layout.batch_count == 0 || layout.u_batch_len == 0 || layout.vt_batch_len == 0 {
1636        return Ok(());
1637    }
1638    for (u_batch, vt_batch) in u
1639        .chunks_exact_mut(layout.u_batch_len)
1640        .zip(vt.chunks_exact_mut(layout.vt_batch_len))
1641    {
1642        for (col, u_column) in u_batch.chunks_exact_mut(layout.m).enumerate() {
1643            let pivot = max_abs_pivot_f32(u_column);
1644            let pivot_value = u_column[pivot];
1645            if pivot_value < 0.0 {
1646                for value in u_column {
1647                    *value = -*value;
1648                }
1649                for vt_column in vt_batch.chunks_exact_mut(layout.k) {
1650                    vt_column[col] = -vt_column[col];
1651                }
1652            }
1653        }
1654    }
1655    Ok(())
1656}
1657
1658fn canonicalize_svd_gauge_c64(
1659    u: &mut [Complex64],
1660    vt: &mut [Complex64],
1661    layout: CanonicalSvdGaugeLayout,
1662) -> tenferro_tensor::Result<()> {
1663    layout.validate_storage(u.len(), vt.len())?;
1664    if layout.batch_count == 0 || layout.u_batch_len == 0 || layout.vt_batch_len == 0 {
1665        return Ok(());
1666    }
1667    for (u_batch, vt_batch) in u
1668        .chunks_exact_mut(layout.u_batch_len)
1669        .zip(vt.chunks_exact_mut(layout.vt_batch_len))
1670    {
1671        for (col, u_column) in u_batch.chunks_exact_mut(layout.m).enumerate() {
1672            let pivot = max_abs_pivot_c64(u_column);
1673            let pivot_value = u_column[pivot];
1674            let pivot_norm = pivot_value.norm();
1675            if pivot_norm == 0.0 {
1676                continue;
1677            }
1678            let phase = pivot_value.conj() / pivot_norm;
1679            let vt_phase = phase.conj();
1680            for value in u_column {
1681                *value *= phase;
1682            }
1683            for vt_column in vt_batch.chunks_exact_mut(layout.k) {
1684                vt_column[col] *= vt_phase;
1685            }
1686        }
1687    }
1688    Ok(())
1689}
1690
1691fn canonicalize_svd_gauge_c32(
1692    u: &mut [Complex32],
1693    vt: &mut [Complex32],
1694    layout: CanonicalSvdGaugeLayout,
1695) -> tenferro_tensor::Result<()> {
1696    layout.validate_storage(u.len(), vt.len())?;
1697    if layout.batch_count == 0 || layout.u_batch_len == 0 || layout.vt_batch_len == 0 {
1698        return Ok(());
1699    }
1700    for (u_batch, vt_batch) in u
1701        .chunks_exact_mut(layout.u_batch_len)
1702        .zip(vt.chunks_exact_mut(layout.vt_batch_len))
1703    {
1704        for (col, u_column) in u_batch.chunks_exact_mut(layout.m).enumerate() {
1705            let pivot = max_abs_pivot_c32(u_column);
1706            let pivot_value = u_column[pivot];
1707            let pivot_norm = pivot_value.norm();
1708            if pivot_norm == 0.0 {
1709                continue;
1710            }
1711            let phase = pivot_value.conj() / pivot_norm;
1712            let vt_phase = phase.conj();
1713            for value in u_column {
1714                *value *= phase;
1715            }
1716            for vt_column in vt_batch.chunks_exact_mut(layout.k) {
1717                vt_column[col] *= vt_phase;
1718            }
1719        }
1720    }
1721    Ok(())
1722}
1723
1724fn max_abs_pivot_f64(u_column: &[f64]) -> usize {
1725    let mut pivot = 0;
1726    let mut pivot_abs = u_column[0].abs();
1727    for (row, value) in u_column.iter().enumerate().skip(1) {
1728        let candidate_abs = value.abs();
1729        if candidate_abs > pivot_abs {
1730            pivot = row;
1731            pivot_abs = candidate_abs;
1732        }
1733    }
1734    pivot
1735}
1736
1737fn max_abs_pivot_f32(u_column: &[f32]) -> usize {
1738    let mut pivot = 0;
1739    let mut pivot_abs = u_column[0].abs();
1740    for (row, value) in u_column.iter().enumerate().skip(1) {
1741        let candidate_abs = value.abs();
1742        if candidate_abs > pivot_abs {
1743            pivot = row;
1744            pivot_abs = candidate_abs;
1745        }
1746    }
1747    pivot
1748}
1749
1750fn max_abs_pivot_c64(u_column: &[Complex64]) -> usize {
1751    let mut pivot = 0;
1752    let mut pivot_abs = u_column[0].norm_sqr();
1753    for (row, value) in u_column.iter().enumerate().skip(1) {
1754        let candidate_abs = value.norm_sqr();
1755        if candidate_abs > pivot_abs {
1756            pivot = row;
1757            pivot_abs = candidate_abs;
1758        }
1759    }
1760    pivot
1761}
1762
1763fn max_abs_pivot_c32(u_column: &[Complex32]) -> usize {
1764    let mut pivot = 0;
1765    let mut pivot_abs = u_column[0].norm_sqr();
1766    for (row, value) in u_column.iter().enumerate().skip(1) {
1767        let candidate_abs = value.norm_sqr();
1768        if candidate_abs > pivot_abs {
1769            pivot = row;
1770            pivot_abs = candidate_abs;
1771        }
1772    }
1773    pivot
1774}
1775
1776fn require_matrix_meta(op: &'static str, shape: &[SymDim]) -> tenferro_tensor::Result<()> {
1777    if shape.len() < 2 {
1778        return Err(Error::rank_mismatch(op, 2, shape.len()));
1779    }
1780    Ok(())
1781}
1782
1783fn matrix_meta_parts<'a>(
1784    op: &'static str,
1785    shape: &'a [SymDim],
1786) -> tenferro_tensor::Result<(SymDim, SymDim, &'a [SymDim])> {
1787    require_matrix_meta(op, shape)?;
1788    Ok((shape[0].clone(), shape[1].clone(), &shape[2..]))
1789}
1790
1791fn lu_meta(dtype: DType, shape: &[SymDim]) -> tenferro_tensor::Result<Vec<(DType, Vec<SymDim>)>> {
1792    let (m, n, batch) = matrix_meta_parts("tenferro-linalg.lu", shape)?;
1793    let k = m.clone().min(n.clone());
1794    Ok(vec![
1795        (dtype, matrix_shape(m.clone(), m, batch)),
1796        (dtype, matrix_shape(shape[0].clone(), k.clone(), batch)),
1797        (dtype, matrix_shape(k, n, batch)),
1798        (dtype, batch.to_vec()),
1799    ])
1800}
1801
1802fn lu_factor_meta(
1803    dtype: DType,
1804    shape: &[SymDim],
1805) -> tenferro_tensor::Result<Vec<(DType, Vec<SymDim>)>> {
1806    let (m, n, batch) = matrix_meta_parts("tenferro-linalg.lu_factor", shape)?;
1807    let k = m.min(n);
1808    Ok(vec![
1809        (dtype, shape.to_vec()),
1810        (DType::I32, vector_shape(k, batch)),
1811        (dtype, batch.to_vec()),
1812    ])
1813}
1814
1815fn signdet_from_lu_factor_meta(
1816    input_dtype: DType,
1817    input_shape: &[SymDim],
1818    packed_shape: &[SymDim],
1819    parity_shape: &[SymDim],
1820) -> tenferro_tensor::Result<(DType, Vec<SymDim>)> {
1821    let (_, _, batch) = matrix_meta_parts("tenferro-linalg.signdet_from_lu_factor", input_shape)?;
1822    require_matrix_meta(
1823        "tenferro-linalg.signdet_from_lu_factor_packed",
1824        packed_shape,
1825    )?;
1826    if parity_shape.len() != batch.len() {
1827        return Err(Error::rank_mismatch(
1828            "tenferro-linalg.signdet_from_lu_factor_parity",
1829            batch.len(),
1830            parity_shape.len(),
1831        ));
1832    }
1833    Ok((input_dtype, batch.to_vec()))
1834}
1835
1836fn logabsdet_from_lu_factor_meta(
1837    input_dtype: DType,
1838    input_shape: &[SymDim],
1839    packed_shape: &[SymDim],
1840) -> tenferro_tensor::Result<(DType, Vec<SymDim>)> {
1841    let (_, _, batch) = matrix_meta_parts("tenferro-linalg.logabsdet_from_lu_factor", input_shape)?;
1842    require_matrix_meta(
1843        "tenferro-linalg.logabsdet_from_lu_factor_packed",
1844        packed_shape,
1845    )?;
1846    Ok((singular_values_dtype(input_dtype), batch.to_vec()))
1847}
1848
1849fn full_piv_lu_meta(
1850    dtype: DType,
1851    shape: &[SymDim],
1852) -> tenferro_tensor::Result<Vec<(DType, Vec<SymDim>)>> {
1853    let (n, _, batch) = matrix_meta_parts("tenferro-linalg.full_piv_lu", shape)?;
1854    Ok(vec![
1855        (dtype, matrix_shape(n.clone(), n.clone(), batch)),
1856        (dtype, matrix_shape(n.clone(), n.clone(), batch)),
1857        (dtype, matrix_shape(n.clone(), n.clone(), batch)),
1858        (dtype, matrix_shape(n.clone(), n, batch)),
1859        (singular_values_dtype(dtype), batch.to_vec()),
1860    ])
1861}
1862
1863fn svd_meta(dtype: DType, shape: &[SymDim]) -> tenferro_tensor::Result<Vec<(DType, Vec<SymDim>)>> {
1864    let (m, n, batch) = matrix_meta_parts("tenferro-linalg.svd", shape)?;
1865    let k = m.clone().min(n.clone());
1866    Ok(vec![
1867        (dtype, matrix_shape(m, k.clone(), batch)),
1868        (singular_values_dtype(dtype), vector_shape(k.clone(), batch)),
1869        (dtype, matrix_shape(k, n, batch)),
1870    ])
1871}
1872
1873fn svd_full_meta(
1874    dtype: DType,
1875    shape: &[SymDim],
1876) -> tenferro_tensor::Result<Vec<(DType, Vec<SymDim>)>> {
1877    let (m, n, batch) = matrix_meta_parts("tenferro-linalg.svd_full", shape)?;
1878    let k = m.clone().min(n.clone());
1879    Ok(vec![
1880        (dtype, matrix_shape(m.clone(), m, batch)),
1881        (singular_values_dtype(dtype), vector_shape(k, batch)),
1882        (dtype, matrix_shape(n.clone(), n, batch)),
1883    ])
1884}
1885
1886fn svd_values_meta(
1887    dtype: DType,
1888    shape: &[SymDim],
1889) -> tenferro_tensor::Result<(DType, Vec<SymDim>)> {
1890    let (m, n, batch) = matrix_meta_parts("tenferro-linalg.svd_values", shape)?;
1891    let k = m.min(n);
1892    Ok((singular_values_dtype(dtype), vector_shape(k, batch)))
1893}
1894
1895fn qr_meta(dtype: DType, shape: &[SymDim]) -> tenferro_tensor::Result<Vec<(DType, Vec<SymDim>)>> {
1896    let (m, n, batch) = matrix_meta_parts("tenferro-linalg.qr", shape)?;
1897    let k = m.clone().min(n.clone());
1898    Ok(vec![
1899        (dtype, matrix_shape(m, k.clone(), batch)),
1900        (dtype, matrix_shape(k, n, batch)),
1901    ])
1902}
1903
1904fn rank_revealing_qr_meta(
1905    dtype: DType,
1906    shape: &[SymDim],
1907) -> tenferro_tensor::Result<Vec<(DType, Vec<SymDim>)>> {
1908    let (m, n, batch) = matrix_meta_parts("tenferro-linalg.rank_revealing_qr", shape)?;
1909    let k = m.clone().min(n.clone());
1910    Ok(vec![
1911        (dtype, matrix_shape(m, k.clone(), batch)),
1912        (dtype, matrix_shape(k, n.clone(), batch)),
1913        (DType::I64, vector_shape(n, batch)),
1914        (DType::I64, batch.to_vec()),
1915    ])
1916}
1917
1918fn require_householder_rank2(op: &'static str, shape: &[SymDim]) -> tenferro_tensor::Result<()> {
1919    if shape.len() != 2 {
1920        return Err(Error::rank_mismatch(op, 2, shape.len()));
1921    }
1922    Ok(())
1923}
1924
1925fn householder_qr_factor_meta(
1926    dtype: DType,
1927    shape: &[SymDim],
1928) -> tenferro_tensor::Result<Vec<(DType, Vec<SymDim>)>> {
1929    require_householder_rank2("tenferro-linalg.householder_qr", shape)?;
1930    let k = shape[0].clone().min(shape[1].clone());
1931    Ok(vec![(dtype, shape.to_vec()), (dtype, vec![k])])
1932}
1933
1934fn householder_qr_from_factors_meta(
1935    dtypes: &[DType],
1936    shapes: &[&[SymDim]],
1937) -> tenferro_tensor::Result<Vec<(DType, Vec<SymDim>)>> {
1938    const OP: &str = "tenferro-linalg.householder_qr_from_factors";
1939    require_householder_rank2(OP, shapes[0])?;
1940    require_householder_rank2(OP, shapes[1])?;
1941    if dtypes[0] != dtypes[1] {
1942        return Err(Error::dtype_mismatch(OP, dtypes[0], dtypes[1]));
1943    }
1944    require_static_extent_equal(OP, "q.cols/r.rows", &shapes[0][1], &shapes[1][0])?;
1945    if let (Some(q_cols), Some(q_rows), Some(r_cols)) = (
1946        shapes[0][1].constant_value(),
1947        shapes[0][0].constant_value(),
1948        shapes[1][1].constant_value(),
1949    ) && q_cols > q_rows.min(r_cols)
1950    {
1951        return Err(Error::invalid_argument(
1952            OP,
1953            "shape",
1954            "Q column count exceeds min(Q rows, R columns)",
1955        ));
1956    }
1957    let m = shapes[0][0].clone();
1958    let n = shapes[1][1].clone();
1959    let k = m.clone().min(n.clone());
1960    Ok(vec![(dtypes[0], vec![m, n]), (dtypes[0], vec![k])])
1961}
1962
1963fn householder_qr_append_meta(
1964    dtypes: &[DType],
1965    shapes: &[&[SymDim]],
1966) -> tenferro_tensor::Result<Vec<(DType, Vec<SymDim>)>> {
1967    const OP: &str = "tenferro-linalg.householder_qr_append";
1968    require_householder_state_meta(OP, dtypes, shapes[0], shapes[1])?;
1969    require_householder_rank2(OP, shapes[2])?;
1970    if dtypes[0] != dtypes[2] {
1971        return Err(Error::dtype_mismatch(OP, dtypes[0], dtypes[2]));
1972    }
1973    require_static_extent_equal(OP, "rows", &shapes[0][0], &shapes[2][0])?;
1974    let m = shapes[0][0].clone();
1975    let width = shapes[0][1].clone() + shapes[2][1].clone();
1976    let k = m.clone().min(width.clone());
1977    Ok(vec![(dtypes[0], vec![m, width]), (dtypes[0], vec![k])])
1978}
1979
1980fn require_static_extent_equal(
1981    op: &'static str,
1982    field: &'static str,
1983    lhs: &SymDim,
1984    rhs: &SymDim,
1985) -> tenferro_tensor::Result<()> {
1986    if let (Some(lhs), Some(rhs)) = (lhs.constant_value(), rhs.constant_value())
1987        && lhs != rhs
1988    {
1989        return Err(Error::invalid_argument(
1990            op,
1991            field,
1992            format!("expected equal extents, got {lhs} and {rhs}"),
1993        ));
1994    }
1995    Ok(())
1996}
1997
1998fn require_householder_state_meta(
1999    op: &'static str,
2000    dtypes: &[DType],
2001    packed: &[SymDim],
2002    coeff: &[SymDim],
2003) -> tenferro_tensor::Result<()> {
2004    require_householder_rank2(op, packed)?;
2005    if coeff.len() != 1 {
2006        return Err(Error::rank_mismatch(op, 1, coeff.len()));
2007    }
2008    if dtypes[0] != dtypes[1] {
2009        return Err(Error::dtype_mismatch(op, dtypes[0], dtypes[1]));
2010    }
2011    let expected = packed[0].clone().min(packed[1].clone());
2012    require_static_extent_equal(op, "coeff", &coeff[0], &expected)
2013}
2014
2015fn householder_qr_r_meta(
2016    dtypes: &[DType],
2017    packed: &[SymDim],
2018    coeff: &[SymDim],
2019) -> tenferro_tensor::Result<(DType, Vec<SymDim>)> {
2020    require_householder_state_meta("tenferro-linalg.householder_qr_r", dtypes, packed, coeff)?;
2021    Ok((dtypes[0], vec![coeff[0].clone(), packed[1].clone()]))
2022}
2023
2024fn householder_qr_q_columns_meta(
2025    dtypes: &[DType],
2026    packed: &[SymDim],
2027    coeff: &[SymDim],
2028    start: usize,
2029    end: usize,
2030) -> tenferro_tensor::Result<(DType, Vec<SymDim>)> {
2031    require_householder_state_meta(
2032        "tenferro-linalg.householder_qr_q_columns",
2033        dtypes,
2034        packed,
2035        coeff,
2036    )?;
2037    if start > end {
2038        return Err(Error::invalid_argument(
2039            "tenferro-linalg.householder_qr_q_columns",
2040            "range",
2041            format!("invalid Q-column range {start}..{end}"),
2042        ));
2043    }
2044    // The reachable width is full Q, not thin Q: columns `k..m` span the
2045    // orthogonal complement of the input's column space.
2046    if packed[0].constant_value().is_some_and(|rows| end > rows) {
2047        return Err(Error::invalid_argument(
2048            "tenferro-linalg.householder_qr_q_columns",
2049            "range",
2050            format!("Q-column range {start}..{end} exceeds full-Q width"),
2051        ));
2052    }
2053    Ok((
2054        dtypes[0],
2055        vec![packed[0].clone(), SymDim::from(end - start)],
2056    ))
2057}
2058
2059fn householder_qr_thin_q_meta(
2060    dtypes: &[DType],
2061    packed: &[SymDim],
2062    coeff: &[SymDim],
2063) -> tenferro_tensor::Result<(DType, Vec<SymDim>)> {
2064    require_householder_state_meta(
2065        "tenferro-linalg.householder_qr_thin_q",
2066        dtypes,
2067        packed,
2068        coeff,
2069    )?;
2070    Ok((dtypes[0], vec![packed[0].clone(), coeff[0].clone()]))
2071}
2072
2073fn householder_qr_split_config(
2074    cotangent: &[usize],
2075    left: &[usize],
2076    right_shape: &[usize],
2077    take_right: bool,
2078) -> tenferro_tensor::Result<tenferro_tensor::SliceConfig> {
2079    const OP: &str = "tenferro-linalg.householder_qr_split_tangent";
2080    for shape in [cotangent, left, right_shape] {
2081        if shape.len() != 2 {
2082            return Err(Error::rank_mismatch(OP, 2, shape.len()));
2083        }
2084    }
2085    let total_width = left[1]
2086        .checked_add(right_shape[1])
2087        .ok_or_else(|| Error::invalid_argument(OP, "shape", "column range overflow"))?;
2088    if cotangent[0] != left[0] || cotangent[0] != right_shape[0] || cotangent[1] != total_width {
2089        return Err(Error::invalid_argument(
2090            OP,
2091            "shape",
2092            "cotangent shape does not match appended factors",
2093        ));
2094    }
2095    let selected = if take_right { right_shape } else { left };
2096    let start = if take_right { left[1] } else { 0 };
2097    let end = start
2098        .checked_add(selected[1])
2099        .ok_or_else(|| Error::invalid_argument(OP, "shape", "column range overflow"))?;
2100    Ok(tenferro_tensor::SliceConfig {
2101        starts: vec![0, start],
2102        limits: vec![selected[0], end],
2103        strides: vec![1, 1],
2104    })
2105}
2106
2107fn householder_qr_append_tangent_meta(
2108    dtypes: &[DType],
2109    shapes: &[&[SymDim]],
2110) -> tenferro_tensor::Result<(DType, Vec<SymDim>)> {
2111    const OP: &str = "tenferro-linalg.householder_qr_append_tangent";
2112    for shape in shapes {
2113        require_householder_rank2(OP, shape)?;
2114    }
2115    if dtypes.iter().any(|dtype| *dtype != dtypes[0]) {
2116        return Err(Error::dtype_mismatch(OP, dtypes[0], dtypes[1]));
2117    }
2118    require_static_extent_equal(OP, "rows", &shapes[0][0], &shapes[1][0])?;
2119    require_static_extent_equal(OP, "left tangent", &shapes[0][0], &shapes[2][0])?;
2120    require_static_extent_equal(OP, "right tangent", &shapes[1][0], &shapes[3][0])?;
2121    require_static_extent_equal(OP, "anchor rows", &shapes[2][0], &shapes[3][0])?;
2122    Ok((
2123        dtypes[0],
2124        vec![
2125            shapes[2][0].clone(),
2126            shapes[2][1].clone() + shapes[3][1].clone(),
2127        ],
2128    ))
2129}
2130
2131fn householder_qr_split_tangent_meta(
2132    dtypes: &[DType],
2133    shapes: &[&[SymDim]],
2134    right: bool,
2135) -> tenferro_tensor::Result<(DType, Vec<SymDim>)> {
2136    const OP: &str = "tenferro-linalg.householder_qr_split_tangent";
2137    for shape in shapes {
2138        require_householder_rank2(OP, shape)?;
2139    }
2140    if dtypes.iter().any(|dtype| *dtype != dtypes[0]) {
2141        return Err(Error::dtype_mismatch(OP, dtypes[0], dtypes[1]));
2142    }
2143    require_static_extent_equal(OP, "left rows", &shapes[0][0], &shapes[1][0])?;
2144    require_static_extent_equal(OP, "right rows", &shapes[0][0], &shapes[2][0])?;
2145    let expected_width = shapes[1][1].clone() + shapes[2][1].clone();
2146    require_static_extent_equal(OP, "width", &shapes[0][1], &expected_width)?;
2147    let selected = if right { shapes[2] } else { shapes[1] };
2148    Ok((dtypes[0], selected.to_vec()))
2149}
2150
2151fn eigh_meta(dtype: DType, shape: &[SymDim]) -> tenferro_tensor::Result<Vec<(DType, Vec<SymDim>)>> {
2152    let (n, _, batch) = matrix_meta_parts("tenferro-linalg.eigh", shape)?;
2153    Ok(vec![
2154        (singular_values_dtype(dtype), vector_shape(n.clone(), batch)),
2155        (dtype, matrix_shape(n.clone(), n, batch)),
2156    ])
2157}
2158
2159fn eigh_values_meta(
2160    dtype: DType,
2161    shape: &[SymDim],
2162) -> tenferro_tensor::Result<(DType, Vec<SymDim>)> {
2163    let (n, _, batch) = matrix_meta_parts("tenferro-linalg.eigh_values", shape)?;
2164    Ok((singular_values_dtype(dtype), vector_shape(n, batch)))
2165}
2166
2167fn eig_meta(
2168    input_dtype: DType,
2169    shape: &[SymDim],
2170) -> tenferro_tensor::Result<Vec<(DType, Vec<SymDim>)>> {
2171    let dtype = eig_output_dtype(input_dtype);
2172    let (n, _, batch) = matrix_meta_parts("tenferro-linalg.eig", shape)?;
2173    Ok(vec![
2174        (dtype, vector_shape(n.clone(), batch)),
2175        (dtype, matrix_shape(n.clone(), n, batch)),
2176    ])
2177}
2178
2179fn eig_values_meta(
2180    input_dtype: DType,
2181    shape: &[SymDim],
2182) -> tenferro_tensor::Result<(DType, Vec<SymDim>)> {
2183    let dtype = eig_output_dtype(input_dtype);
2184    let (n, _, batch) = matrix_meta_parts("tenferro-linalg.eig_values", shape)?;
2185    Ok((dtype, vector_shape(n, batch)))
2186}
2187
2188fn matrix_shape(rows: SymDim, cols: SymDim, batch: &[SymDim]) -> Vec<SymDim> {
2189    let mut shape = vec![rows, cols];
2190    shape.extend_from_slice(batch);
2191    shape
2192}
2193
2194fn vector_shape(len: SymDim, batch: &[SymDim]) -> Vec<SymDim> {
2195    let mut shape = vec![len];
2196    shape.extend_from_slice(batch);
2197    shape
2198}
2199
2200fn eig_output_dtype(dtype: DType) -> DType {
2201    match dtype {
2202        DType::F64 | DType::C64 => DType::C64,
2203        DType::F32 | DType::C32 => DType::C32,
2204        DType::I32 | DType::I64 | DType::Bool => DType::C64,
2205        // INVARIANT: linalg validates its input dtype before mapping outputs, so
2206        // an externally defined scalar never reaches this mapping.
2207        DType::External(_) => unreachable!("linalg validates its input dtype first"),
2208    }
2209}
2210
2211fn singular_values_dtype(dtype: DType) -> DType {
2212    match dtype {
2213        DType::C64 => DType::F64,
2214        DType::C32 => DType::F32,
2215        DType::External(id) => {
2216            // Singular values of an externally defined scalar have no declared
2217            // dtype, so the mapping keeps the identity rather than guessing one.
2218            DType::External(id)
2219        }
2220        other => other,
2221    }
2222}
2223
2224fn promote_dtypes(dtypes: &[DType]) -> DType {
2225    dtypes
2226        .iter()
2227        .copied()
2228        .reduce(tenferro_tensor::validate::promote_dtype)
2229        .unwrap_or(DType::F64)
2230}
2231
2232fn hash_dtype(hasher: &mut dyn Hasher, dtype: DType) {
2233    let tag = match dtype {
2234        DType::F64 => 0,
2235        DType::F32 => 1,
2236        DType::I64 => 2,
2237        DType::C64 => 3,
2238        DType::C32 => 4,
2239        DType::I32 => 5,
2240        DType::Bool => 6,
2241        DType::External(id) => {
2242            // The cache key must distinguish two externally defined scalars, so it
2243            // carries the scalar's own identity rather than one shared code.
2244            // `Hash` needs a sized hasher, so the identity is folded into a
2245            // concrete one first. It is stable within a process, which is the
2246            // scope of this cache.
2247            let mut identity = std::collections::hash_map::DefaultHasher::new();
2248            Hash::hash(&id, &mut identity);
2249            hasher.write_u8(7);
2250            hasher.write_u64(identity.finish());
2251            return;
2252        }
2253    };
2254    hasher.write_u8(tag);
2255}
2256
2257fn hash_svd_gauge(hasher: &mut dyn Hasher, gauge: SvdGauge) {
2258    let tag = match gauge {
2259        SvdGauge::Raw => 0,
2260        SvdGauge::CanonicalPivot => 1,
2261    };
2262    hasher.write_u8(tag);
2263}
2264
2265fn hash_svd_driver(hasher: &mut dyn Hasher, driver: SvdDriver) {
2266    let tag = match driver {
2267        SvdDriver::Auto => 0,
2268        SvdDriver::Jacobi => 1,
2269        SvdDriver::QrBased => 2,
2270        SvdDriver::Polar => 3,
2271    };
2272    hasher.write_u8(tag);
2273}
2274
2275fn hash_eigh_driver(hasher: &mut dyn Hasher, driver: EighDriver) {
2276    let tag = match driver {
2277        EighDriver::Auto => 0,
2278        EighDriver::DivideAndConquer => 1,
2279        EighDriver::Jacobi => 2,
2280    };
2281    hasher.write_u8(tag);
2282}
2283
2284fn hash_eigh_batch_policy(hasher: &mut dyn Hasher, policy: EighBatchPolicy) {
2285    let tag = match policy {
2286        EighBatchPolicy::AllowPerMatrixFallback => 0,
2287        EighBatchPolicy::RequireBatched => 1,
2288    };
2289    hasher.write_u8(tag);
2290}
2291
2292fn hash_eigh_gauge(hasher: &mut dyn Hasher, gauge: EighGauge) {
2293    let tag = match gauge {
2294        EighGauge::Raw => 0,
2295        EighGauge::CanonicalPivot => 1,
2296    };
2297    hasher.write_u8(tag);
2298}
2299
2300fn hash_qr_gauge(hasher: &mut dyn Hasher, gauge: QrGauge) {
2301    let tag = match gauge {
2302        QrGauge::Raw => 0,
2303        QrGauge::PositiveDiagonal => 1,
2304    };
2305    hasher.write_u8(tag);
2306}