tenferro_ext_tropical/
lib.rs

1//! Tropical semiring tensor operations for the tenferro workspace.
2//!
3//! This crate extends the tenferro algebra-parameterized architecture with
4//! three tropical semirings:
5//!
6//! | Semiring | ⊕ (add) | ⊗ (mul) | Zero | One | Use case |
7//! |----------|---------|---------|------|-----|----------|
8//! | MaxPlus  | max     | +       | −∞   | 0   | Shortest path, optimal alignment |
9//! | MinPlus  | min     | +       | +∞   | 0   | Shortest path (Dijkstra) |
10//! | MaxMul   | max     | ×       | 0    | 1   | Viterbi, max-probability paths |
11//!
12//! # Architecture
13//!
14//! The crate provides:
15//!
16//! - **Scalar wrappers** ([`MaxPlus<T>`], [`MinPlus<T>`], [`MaxMul<T>`]):
17//!   `#[repr(transparent)]` newtypes that redefine `Add`/`Mul` with tropical
18//!   semantics. Satisfy the [`Scalar`](tenferro_algebra::Scalar) blanket impl.
19//!
20//! - **Algebra markers** ([`MaxPlusAlgebra<T>`], [`MinPlusAlgebra<T>`], [`MaxMulAlgebra<T>`]):
21//!   Zero-sized types used as the algebra parameter `Alg` in
22//!   semiring-family execution traits such as
23//!   [`TensorSemiringCore<Alg>`](tenferro_prims::TensorSemiringCore).
24//!
25//! - **Semiring-family implementations**:
26//!   `impl TensorSemiringCore<MaxPlusAlgebra<f64>> for CpuBackend` etc. Orphan
27//!   rule compatible because algebra markers are defined locally.
28//!
29//! - **[`ArgmaxTracker`]**: Records winner indices during tropical forward
30//!   pass for use in automatic differentiation.
31//!
32//! # Examples
33//!
34//! ## Scalar arithmetic
35//!
36//! ```
37//! use tenferro_ext_tropical::MaxPlus;
38//!
39//! let a = MaxPlus(3.0_f64);
40//! let b = MaxPlus(5.0_f64);
41//! let c = a + b;   // MaxPlus(5.0) -- tropical add = max
42//! assert_eq!(c, MaxPlus(5.0));
43//! let d = a * b;   // MaxPlus(8.0) -- tropical mul = ordinary +
44//! assert_eq!(d, MaxPlus(8.0));
45//! ```
46//!
47//! ## Algebra dispatch
48//!
49//! ```
50//! use tenferro_algebra::HasAlgebra;
51//! use tenferro_ext_tropical::{MaxPlus, MaxPlusAlgebra};
52//!
53//! // MaxPlus<f64> maps to MaxPlusAlgebra<f64>
54//! fn check_f64<T: HasAlgebra<Algebra = MaxPlusAlgebra<f64>>>() {}
55//! check_f64::<MaxPlus<f64>>();
56//!
57//! // MaxPlus<f32> maps to MaxPlusAlgebra<f32>
58//! fn check_f32<T: HasAlgebra<Algebra = MaxPlusAlgebra<f32>>>() {}
59//! check_f32::<MaxPlus<f32>>();
60//! ```
61//!
62//! ## Plan-based tropical contraction
63//!
64//! ```ignore
65//! use tenferro_device::LogicalMemorySpace;
66//! use tenferro_prims::{
67//!     CpuBackend, CpuContext, SemiringCoreDescriptor, TensorSemiringCore,
68//! };
69//! use tenferro_tensor::{MemoryOrder, Tensor};
70//! use tenferro_ext_tropical::{MaxPlus, MaxPlusAlgebra};
71//!
72//! let mut ctx = CpuContext::new(1);
73//! let col = MemoryOrder::ColumnMajor;
74//! let mem = LogicalMemorySpace::MainMemory;
75//! let a = Tensor::<MaxPlus<f64>>::zeros(&[3, 4], mem, col);
76//! let b = Tensor::<MaxPlus<f64>>::zeros(&[4, 5], mem, col);
77//! let mut c = Tensor::<MaxPlus<f64>>::zeros(&[3, 5], mem, col);
78//! let desc = SemiringCoreDescriptor::BatchedGemm {
79//!     batch_dims: vec![], m: 3, n: 5, k: 4,
80//! };
81//! // Under MaxPlusAlgebra<f64>, GEMM computes:
82//! //   C[i,j] = max_k (A[i,k] + B[k,j])
83//! let plan = <CpuBackend as TensorSemiringCore<MaxPlusAlgebra<f64>>>::plan(
84//!     &mut ctx,
85//!     &desc,
86//!     &[&[3, 4], &[4, 5], &[3, 5]],
87//! )
88//! .unwrap();
89//! <CpuBackend as TensorSemiringCore<MaxPlusAlgebra<f64>>>::execute(
90//!     &mut ctx,
91//!     &plan,
92//!     MaxPlus::one(),
93//!     &[&a, &b],
94//!     MaxPlus::zero(),
95//!     &mut c,
96//! )
97//! .unwrap();
98//! ```
99
100pub mod ad;
101pub mod algebra;
102pub mod argmax;
103pub mod prims;
104pub mod scalar;
105
106// Re-export primary types at crate root.
107pub use algebra::{MaxMulAlgebra, MaxPlusAlgebra, MinPlusAlgebra};
108pub use argmax::ArgmaxTracker;
109pub use prims::TropicalPlan;
110pub use scalar::{MaxMul, MaxPlus, MinPlus};
tenferro_ext_tropical/lib.rs

tenferro_ext_tropical/
lib.rs
