Semiring Types

A semiring is an algebraic structure with two operations that generalize addition and multiplication. Tropical semirings replace standard operations with max/min and addition.

Available Semirings

MaxPlus Semiring

The MaxPlus (or max-plus) semiring uses:

• Addition: a ⊕ b = max(a, b)
• Multiplication: a ⊗ b = a + b

#![allow(unused)]
fn main() {
use tropical_gemm::{MaxPlus, TropicalSemiring};

let a = MaxPlus::from_scalar(3.0f32);
let b = MaxPlus::from_scalar(5.0f32);

// Tropical add: max(3, 5) = 5
let sum = MaxPlus::tropical_add(a, b);
assert_eq!(sum.value(), 5.0);

// Tropical mul: 3 + 5 = 8
let product = MaxPlus::tropical_mul(a, b);
assert_eq!(product.value(), 8.0);
}

Applications:

• Longest path in graphs (Bellman-Ford with negated weights)
• Viterbi algorithm for HMM decoding
• Log-probability computations

MinPlus Semiring

The MinPlus (or min-plus) semiring uses:

• Addition: a ⊕ b = min(a, b)
• Multiplication: a ⊗ b = a + b

#![allow(unused)]
fn main() {
use tropical_gemm::{MinPlus, TropicalSemiring};

let a = MinPlus::from_scalar(3.0f32);
let b = MinPlus::from_scalar(5.0f32);

// Tropical add: min(3, 5) = 3
let sum = MinPlus::tropical_add(a, b);
assert_eq!(sum.value(), 3.0);

// Tropical mul: 3 + 5 = 8
let product = MinPlus::tropical_mul(a, b);
assert_eq!(product.value(), 8.0);
}

Applications:

• Shortest path (Floyd-Warshall, Dijkstra)
• Edit distance computation
• Resource allocation

MaxMul Semiring

The MaxMul semiring uses:

• Addition: a ⊕ b = max(a, b)
• Multiplication: a ⊗ b = a × b

#![allow(unused)]
fn main() {
use tropical_gemm::{MaxMul, TropicalSemiring};

let a = MaxMul::from_scalar(3.0f32);
let b = MaxMul::from_scalar(5.0f32);

// Tropical add: max(3, 5) = 5
let sum = MaxMul::tropical_add(a, b);
assert_eq!(sum.value(), 5.0);

// Tropical mul: 3 × 5 = 15
let product = MaxMul::tropical_mul(a, b);
assert_eq!(product.value(), 15.0);
}

Applications:

• Maximum probability paths (non-log space)
• Fuzzy set operations
• Reliability analysis

Boolean and bit-sliced operations

AndOr works through the public CPU matrix/slice APIs using a portable Boolean kernel, and through the CUDA backend. CPU argmax returns the first true contribution’s index, or zero when no contribution is true.

Bitwise<u32> and Bitwise<u64> pack independent Boolean problems into each word’s 32 or 64 bits. Their CPU value kernels use AVX2/NEON where available, with portable fallback; CUDA kernels are also available. This is distinct from packing the contraction axis of one Boolean matrix product.

#![allow(unused)]
fn main() {
use tropical_gemm::{tropical_matmul, Bitwise};
let c = tropical_matmul::<Bitwise<u32>>(&[0b11], 1, 1, &[0b10], 1);
assert_eq!(c[0].0, 0b10);
}

Bitwise has no TropicalWithArgmax implementation: each bit lane can have a different winning K index. Per-lane indices are deliberately deferred rather than returning a misleading single index for the entire word.

Supported Scalar Types

Each semiring supports multiple scalar types:

Type Aliases

For convenience, shorter type aliases are provided:

#![allow(unused)]
fn main() {
use tropical_gemm::{MaxPlus, MinPlus, MaxMul, AndOr};

// These are equivalent:
type A = tropical_gemm::TropicalMaxPlus<f32>;
type B = MaxPlus<f32>;  // Preferred
}