I/O complexity

TLDR

The paper introduces the red‑blue pebble game to model the input‑output complexity of algorithms. The authors use the pebble game formulation to derive lower bounds on I/O requirements. They prove tight lower bounds for I/O, showing that n‑point FFT and n×n matrix multiplication with O(S) memory require Ω(n log n / log S) and Ω(n³ / S) time, respectively, and similar bounds hold for other problems, all of which are achievable by decomposition schemes.

Abstract

In this paper, the red-blue pebble game is proposed to model the input-output complexity of algorithms. Using the pebble game formulation, a number of lower bound results for the I/O requirement are proven. For example, it is shown that to perform the n-point FFT or the ordinary n×n matrix multiplication algorithm with O(S) memory, at least Ω(n log n/log S) or Ω(n3/@@@@S), respectively, time is needed for the I/O. Similar results are obtained for algorithms for several other problems. All of the lower bounds presented are the best possible in the sense that they are achievable by certain decomposition schemes.