tropical_gemm/
lib.rs

1//! High-performance tropical matrix multiplication.
2//!
3//! This library provides BLAS-level performance for tropical matrix
4//! multiplication across multiple semiring types.
5//!
6//! # GPU Acceleration
7//!
8//! For GPU-accelerated operations, add the `tropical-gemm-cuda` crate:
9//!
10//! ```toml
11//! [dependencies]
12//! tropical-gemm = "0.1"
13//! tropical-gemm-cuda = "0.1"
14//! ```
15//!
16//! Then use the GPU API:
17//!
18//! ```ignore
19//! use tropical_gemm::TropicalMaxPlus;
20//! use tropical_gemm_cuda::{tropical_matmul_gpu, CudaContext};
21//!
22//! let c = tropical_matmul_gpu::<TropicalMaxPlus<f32>>(&a, m, k, &b, n)?;
23//! ```
24//!
25//! # Tropical Semirings
26//!
27//! Tropical algebra replaces standard arithmetic operations:
28//! - Standard addition → tropical addition (typically max or min)
29//! - Standard multiplication → tropical multiplication (typically + or ×)
30//!
31//! | Type | ⊕ (add) | ⊗ (mul) | Zero | One | Use Case |
32//! |------|---------|---------|------|-----|----------|
33//! | [`TropicalMaxPlus<T>`] | max | + | -∞ | 0 | Viterbi, longest path |
34//! | [`TropicalMinPlus<T>`] | min | + | +∞ | 0 | Shortest path |
35//! | [`TropicalMaxMul<T>`] | max | × | 0 | 1 | Probability (non-log) |
36//! | [`TropicalAndOr`] | OR | AND | false | true | Graph reachability |
37//! | [`TropicalBitwise`] | OR | AND | 0 | ~0 | Batched (bit-sliced) boolean matmul |
38//! | [`CountingTropical<T,C>`] | max+count | +,× | (-∞,0) | (0,1) | Path counting |
39//!
40//! `TropicalBitwise<u32/u64>` packs 32/64 **independent** boolean problems into the
41//! bit-lanes of one word. It is for *many independent dense* boolean problems, not a
42//! single large sparse boolean graph — for that use a sparse GraphBLAS tool.
43//!
44//! # Quick Start
45//!
46//! ## Function-based API
47//!
48//! ```
49//! use tropical_gemm::{tropical_matmul, TropicalMaxPlus, TropicalSemiring};
50//!
51//! // Create 2x3 and 3x2 matrices
52//! let a = vec![1.0f32, 2.0, 3.0, 4.0, 5.0, 6.0];
53//! let b = vec![1.0f32, 2.0, 3.0, 4.0, 5.0, 6.0];
54//!
55//! // Compute C = A ⊗ B using TropicalMaxPlus semiring
56//! let c = tropical_matmul::<TropicalMaxPlus<f32>>(&a, 2, 3, &b, 2);
57//!
58//! // C[i,j] = max_k(A[i,k] + B[k,j])
59//! assert_eq!(c[0].value(), 8.0); // max(1+1, 2+3, 3+5) = 8
60//! ```
61//!
62//! ## Matrix-based API (faer-style)
63//!
64//! ```
65//! use tropical_gemm::{Mat, MatRef, MaxPlus, TropicalSemiring};
66//!
67//! // Create matrix views from raw data
68//! let a_data = [1.0f32, 2.0, 3.0, 4.0, 5.0, 6.0];
69//! let b_data = [1.0f32, 2.0, 3.0, 4.0, 5.0, 6.0];
70//!
71//! let a = MatRef::<MaxPlus<f32>>::from_slice(&a_data, 2, 3);
72//! let b = MatRef::<MaxPlus<f32>>::from_slice(&b_data, 3, 2);
73//!
74//! // Matrix multiplication using operators
75//! let c = &a * &b;
76//! assert_eq!(c[(0, 0)].value(), 8.0);
77//!
78//! // Or using methods
79//! let c = a.matmul(&b);
80//!
81//! // Factory methods
82//! let zeros = Mat::<MaxPlus<f32>>::zeros(3, 3);
83//! let identity = Mat::<MaxPlus<f32>>::identity(3);
84//! ```
85//!
86//! # Argmax Tracking (Backpropagation)
87//!
88//! For gradient routing in neural networks, you can track which k index
89//! produced each optimal value:
90//!
91//! ```
92//! use tropical_gemm::{tropical_matmul_with_argmax, TropicalMaxPlus, TropicalSemiring};
93//!
94//! let a = vec![1.0f64, 2.0, 3.0, 4.0, 5.0, 6.0];
95//! let b = vec![1.0f64, 2.0, 3.0, 4.0, 5.0, 6.0];
96//!
97//! let result = tropical_matmul_with_argmax::<TropicalMaxPlus<f64>>(&a, 2, 3, &b, 2);
98//!
99//! // Get the optimal value and which k produced it
100//! let value = result.get(0, 0).value(); // 8.0
101//! let k_idx = result.get_argmax(0, 0);  // 2 (k=2 gave max)
102//! ```
103//!
104//! # Performance
105//!
106//! The library uses:
107//! - BLIS-style cache blocking for memory efficiency
108//! - Runtime CPU feature detection for optimal SIMD kernels
109//! - AVX2/AVX-512 on x86-64, NEON on ARM
110//!
111//! ```
112//! use tropical_gemm::Backend;
113//!
114//! println!("Using: {}", Backend::description());
115//! ```
116//!
117//! # BLAS-style API
118//!
119//! For fine-grained control:
120//!
121//! ```
122//! use tropical_gemm::{TropicalGemm, TropicalMaxPlus, TropicalSemiring};
123//!
124//! let a = vec![1.0f32; 64 * 64];
125//! let b = vec![1.0f32; 64 * 64];
126//! let mut c = vec![TropicalMaxPlus::tropical_zero(); 64 * 64];
127//!
128//! TropicalGemm::<TropicalMaxPlus<f32>>::new(64, 64, 64)
129//!     .execute(&a, 64, &b, 64, &mut c, 64);
130//! ```
131
132// Internal modules
133pub mod core;
134pub mod mat;
135pub mod simd;
136pub mod types;
137
138mod api;
139mod backend;
140
141// Public API
142pub use api::{
143    tropical_backward_a, tropical_backward_a_batched, tropical_backward_b,
144    tropical_backward_b_batched, tropical_gemm, tropical_matmul, tropical_matmul_batched,
145    tropical_matmul_batched_with_argmax, tropical_matmul_strided_batched,
146    tropical_matmul_with_argmax, tropical_matmul_with_argmax_with_workspace, TropicalGemm,
147};
148pub use backend::{version_info, Backend};
149
150// Re-export commonly used types at crate root
151pub use core::{GemmWithArgmax, GemmWorkspace, Layout, Transpose};
152pub use mat::{Mat, MatMut, MatRef, MatWithArgmax};
153pub use simd::{simd_level, KernelDispatch, SimdLevel};
154pub use types::{
155    AdditiveTropical, BitwiseScalar, CountingTropical, SimdTropical, TropicalAndOr,
156    TropicalBitwise, TropicalMaxMul, TropicalMaxPlus, TropicalMinPlus, TropicalScalar,
157    TropicalSemiring, TropicalWithArgmax,
158};
159
160// Convenient type aliases
161/// Alias for [`TropicalMaxPlus`].
162pub type MaxPlus<T> = TropicalMaxPlus<T>;
163/// Alias for [`TropicalMinPlus`].
164pub type MinPlus<T> = TropicalMinPlus<T>;
165/// Alias for [`TropicalMaxMul`].
166pub type MaxMul<T> = TropicalMaxMul<T>;
167/// Alias for [`TropicalAndOr`].
168pub type AndOr = TropicalAndOr;
169/// Alias for [`TropicalBitwise`].
170pub type Bitwise<T> = TropicalBitwise<T>;
171
172/// Prelude module for convenient imports.
173pub mod prelude {
174    pub use super::{
175        tropical_backward_a, tropical_backward_a_batched, tropical_backward_b,
176        tropical_backward_b_batched, tropical_matmul, tropical_matmul_batched,
177        tropical_matmul_batched_with_argmax, tropical_matmul_strided_batched,
178        tropical_matmul_with_argmax, tropical_matmul_with_argmax_with_workspace, AndOr, Backend,
179        Bitwise, CountingTropical, GemmWithArgmax, GemmWorkspace, Mat, MatMut, MatRef,
180        MatWithArgmax, MaxMul, MaxPlus, MinPlus, Transpose, TropicalAndOr, TropicalBitwise,
181        TropicalGemm, TropicalMaxMul, TropicalMaxPlus, TropicalMinPlus, TropicalSemiring,
182        TropicalWithArgmax,
183    };
184}
tropical_gemm/lib.rs

tropical_gemm/
lib.rs
