amari-tropical

Tropical (max-plus) algebra implementation for optimization and neural network applications.

Overview

amari-tropical implements tropical algebra, also known as max-plus algebra, where the traditional operations (+, ×) are replaced with (max, +). This transformation converts expensive softmax and multiplication operations into simple max and addition operations, making it particularly useful for:

• Finding most likely sequences (Viterbi algorithm)
• Shortest path optimization
• Neural network inference optimization
• Dynamic programming

Features

• TropicalNumber: Core scalar type with max-plus operations
• TropicalMatrix: Matrix operations in tropical algebra
• TropicalMultivector: Integration with geometric algebra
• Viterbi Decoder: Efficient sequence decoding using tropical operations
• Tropical Polytopes: Geometric structures in tropical space
• High-Precision Support: Optional extended precision arithmetic

Installation

Add to your Cargo.toml:

[dependencies]
amari-tropical = "0.12"

Feature Flags

[dependencies]
# Default features
amari-tropical = "0.12"

# With serialization
amari-tropical = { version = "0.12", features = ["serialize"] }

# With GPU acceleration
amari-tropical = { version = "0.12", features = ["gpu"] }

# High-precision arithmetic
amari-tropical = { version = "0.12", features = ["high-precision"] }

Quick Start

use amari_tropical::TropicalNumber;

// Create tropical numbers
let a = TropicalNumber::new(3.0);
let b = TropicalNumber::new(5.0);

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

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

// Tropical identities
let zero = TropicalNumber::<f64>::tropical_zero(); // -∞ (additive identity)
let one = TropicalNumber::<f64>::tropical_one();   // 0 (multiplicative identity)

Mathematical Background

Tropical Semiring

In tropical algebra, we define:

Why "Tropical"?

The name honors Brazilian mathematician Imre Simon, who pioneered this field. The algebra is particularly powerful because:

1. Exponentiation becomes linear: e^(a+b) → max(a, b) in log-space
2. Products become sums: Reduces computational complexity
3. Softmax approximation: max approximates log-sum-exp

Applications

• Viterbi Algorithm: Find most likely state sequences in HMMs
• Shortest Paths: Tropical matrix multiplication solves all-pairs shortest paths
• Neural Networks: Approximate attention mechanisms efficiently
• Optimization: Linear programming in tropical geometry

Key Types

TropicalNumber

use amari_tropical::TropicalNumber;

let x = TropicalNumber::new(2.5);

// Access the underlying value
let val = x.value();

// Tropical operations (take references)
let y = TropicalNumber::new(3.0);
let sum = x.tropical_add(&y);  // max(2.5, 3.0) = 3.0
let prod = x.tropical_mul(&y); // 2.5 + 3.0 = 5.5

TropicalMatrix

use amari_tropical::TropicalMatrix;

// Create matrices for shortest path computation
let distances = TropicalMatrix::new(/* ... */);

// Tropical matrix multiplication gives shortest paths
let paths = distances.tropical_matmul(&distances);

Viterbi Decoder

use amari_tropical::viterbi::ViterbiDecoder;

// Efficient sequence decoding using tropical algebra
let decoder = ViterbiDecoder::new(&transitions, &emissions);
let best_path = decoder.decode(&observations);

Modules

Performance

Tropical algebra offers significant performance benefits:

• O(n) vs O(n log n): Max operation vs softmax
• No overflow: Log-space operations avoid numerical issues
• Parallelizable: Element-wise max operations are embarrassingly parallel
• GPU-friendly: Simple operations map well to GPU architectures

v0.12.0 API Changes

The API was updated in v0.12.0 for better encapsulation:

// Before (v0.11.x)
let a = TropicalNumber(3.0);
let sum = a.tropical_add(b);
let val = a.0;

// After (v0.12.0+)
let a = TropicalNumber::new(3.0);
let sum = a.tropical_add(&b);  // Now takes reference
let val = a.value();

License

Licensed under either of Apache License, Version 2.0 or MIT License at your option.

Part of Amari

This crate is part of the Amari mathematical computing library.