Exploiting (min,+)/(max,+) Isomorphism to Speed up Convolutions

(min,+) and (max,+) algebra lie at the core of theories for the analysis of worst-case performance bounds, such as Deterministic Network Calculus and Real-Time Calculus. In both algebras, computing expressions can be computationally expensive. In particular, the convolution operation can be very time-consuming, sometimes taking hours or not completing at all. In fact, its operands are represented as pseudo-periodic sequences of segments and points (henceforth elements for short), which may have different periods. As already observed in literature, a convolution requires that every couple of elements belonging to different operands be elaborated, up to the least common multiple (lcm) of their periods. In this paper, leveraging the isomorphism between (min,+) and (max,+) algebras, we prove formally that there is a much smaller bound than said lcm, allowing to greatly reduce the elementary operations required. We devise a new algorithm for (min,+) and (max,+) convolution, called super-isospeed, which avoids unnecessary computations and is considerably faster than the ones known so far, reducing the computation times by orders of magnitude. Unlike other works on the same problem, our method is both exact (i.e., does not introduce any approximation), and is not limited to operands of particular shapes (e.g., concave/convex, sub-/superadditive, etc.). A preliminary version of this paper was presented at ECRTS 2023, [Zippo, Nikolaus, et al. 2023b].