When Addition Becomes Optimization: Tropical Algebra, Paths, Schedules, and Semiring Computation
Abstract
Changing the arithmetic changes what linear algebra means. In tropical algebra, ordinary addition is replaced by min or max, and ordinary multiplication is replaced by addition. That one substitution turns shortest-path computation, Bellman recurrences, critical-path scheduling, and synchronized event systems into variations on the same matrix-algebraic theme. This paper traces a single small weighted graph through min-plus and max-plus arithmetic, connecting each algebraic operation to a concrete computational or scheduling interpretation. Tropical algebra does not make hard problems easy; what it offers is the algebraic structure underneath a wide class of path, timing, and propagation computations.
Interactive supporting information
The paper’s computations can be explored step by step in the browser — five self-contained artifacts, one per part of the story, all built on the same running example:
- Matrix multiplication, three arithmetics — the interactive twin of Figure 2: click a product cell, see its candidates, switch the semiring (Section 3).
- Shortest paths as relaxation schedules — Bellman–Ford (synchronous and in-place), Dijkstra, min-plus powers (raw W and A = I ⊕ W), and the full max-plus CPM with backward pass and slack (Sections 4–8).
- All-pairs distances by admitting intermediates — Floyd–Warshall filling the whole distance matrix until it equals the tropical closure W, with negative-cycle detection (Section 4, Appendix A)*.
- Inside a tropical GEMM kernel — the tiled (min, +) kernel animated: shared-memory staging and the accumulator loop with no FMA (Section 11).
- Cyclic schedules and the max-plus eigenvalue — trajectories, transients, eigenvectors, and the bottleneck cycle’s cadence, with weight sliders and the exact λ(w) sensitivity curve (Sections 9–10).
The Zenodo deposit also carries frozen copies of these five artifacts and of the benchmark code behind Section 11, so the supporting material stays retrievable independently of this site.