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. Two such theories are in fact Deterministic Network Calculus and Real-time Calculus, used in real-time networks and systems, respectively. In both algebras, computing expressions can be computationally expensive. In particular, the convolution operation, which is quite frequent, 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 the 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, in general, a much smaller bound than said lcm, which allows one to greatly reduce the number of elementary operations required for a convolution. Accordingly, we devise a new algorithm for (min,+) and (max,+) convolution, called super-isospeed, which avoids unnecessary computations. The super-isospeed algorithm is considerably faster than the ones known so far, and it reduces the computation times by orders of magnitude. Unlike other works that address 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.).