Many important applications are bottlenecked not by processing speeds, but by I/O cost: the speed to transfer data items between fast memory (e.g., registers or the CPU cache) and slow memory (e.g., RAM or disk). There has thus been considerable interest in designing I/O efficient algorithms and in understanding I/O lower bounds [3,8,12,14].
Past work on I/O lower bounds has largely focused on finding bounds for specific algorithms, such as matrix multiplication or the Fast Fourier Transform [3,8,12,14]. However, these approaches leverage properties specific to the tasks at hand, and do not translate across tasks. In this paper, we explore methods that can be applied to arbitrary computations and can be computed efficiently in an automatic fashion. Such generic bounds can be used to characterize the I/O cost of computations that are too complex to analyze by hand. Our method also provides a new approach for finding closed form theoretical bounds on computation graphs as long as the Laplacian eigenvalues (or bounds on these values) are known.
We approach the problem of minimizing I/O for an arbitrary computation as finding an optimal evaluation order on the underlying directed computation graph. In a computation graph, each vertex represents a single operation: the parents of the vertex indicate the operands of the operation. We assume a two-level memory architecture with a fixed amount of fast memory and infinite slow memory: I/O is incurred when transferring data between fast and slow memory (Section 3).
We present a novel method to provide lower bounds on the I/O for any computation graph using the eigenvalues of the graph Laplacian (Section 4). We further extend this bound to the parallel setting. This spectral bound is efficiently computable and can be applied to arbitrarily large and complex graphs. For graphs with known spectra, this bound can also be computed in closed form. We compute closed form bounds for two computation graphs: the Bellman-Held-Karp algorithm for the traveling salesman problem (TSP) as well as the Fast Fourier Transform (FFT). In the process, we also present a novel result on the multiplicity of the eigenvalues of the butterfly graph, which we use to complete the bound for the FFT. We find that spectral bound for the FFT graph is at most a factor of (1/log M) weaker than the previously published asymptotically tight bound (where M is the size of fast memory), which was computed via direct inspection of the butterfly graph using S partitions [14]. We additionally present a probabilistic bound for random Erdős Rényi graphs.
We evaluate our method empirically by computing lower bounds for four types of computation graphs: the Fast Fourier Transform, matrix multiplication (naive and Strassen), and the Bellman-Held-Karp algorithm (Section 6). We find that our bounds are tighter than current automatic methods [9] and behave similarly to published analytical bounds.
Hong and Kung first framed the problem of I/O complexity as the "red-blue pebble game" and used it to prove several bounds [14]. The game represents slow memory as an infinite pool of blue pebbles and fast memory as a finite set of red pebbles. An evaluation then corresponds to pebbling each vertex of the graph according to the game; I/O is incurred when placing a red pebble on top of a blue pebble (reading from slow memory) or vice-versa (writing to slow memory).
Lower bounds on naïve matrix multiplication often use the Loomis-Whitney theorem, which embeds operations in the voxels of a computation cube [2,12]. However, volume based arguments such as Loomis-Whitney do not apply for more general computations. I/O bounding techniques for algorithms beyond matrix multiplication generally focus on the computation graph itself.
Most current work on lower bounds via computation graphs requires manual inspection of the graph. In [14], the authors find a 2S partition of the computation graph to bound I/O-a proof technique that is non-trivial for complex graphs. In [16] and [5], the authors use path routing and dichotomy width respectively to find lower bounds. In [3], the authors reduce the I/O problem to a graph partitioning problem in order to find a lower bound for Strassen's matrix multiplication algorithm using the edge expansion of the graph, which was computed by hand by recursively decomposing the Strassen computation graph. None of these methods can easily be computed automatically for arbitrary graphs. Instead, lower bounds on each graph must be separately proved by inspecting the specific graph, and are thus difficult to generalize. We instead focus on methods that can automatically compute lower bounds for any input graph, regardless of its structure.
To our knowledge, there are only two works that discuss automated methods for lower bounds for arbitrary graphs. In the first work, the authors find automatic bounds by computing convex min s-t cuts on the sub-graphs [9]. With a runtime O(n 5 ) for a graph with n nodes, this method is significantly slower than our spectral method, which can be computed in O(n 3 ). We compare against this method in Section 6 and find that it yields looser bounds than our proposed spectral method. The second work uses an Integer Linear Program (ILP) to solve for the 2S partition of the computation graph [8]. This method is computationally expensive because it necessitates an exact ILP solver and is thus combinatorial in difficulty. Since this ILP based method is intractable, we do not compare its performance against the spectral bound as the method cannot be performed for large graphs, instead limiting ourselves to methods that can be computed in polynomial time.
A computation can be represented by an underlying directed computation graph G. Each operation, including the inputs and outputs, is represented by a vertex. An edge from u to v indicates that the operation v was computed with u as an operand. The graph is acyclic, with the inputs as sources and the outputs as sinks. For example, the inner product of two vectors with two elements each can be represented as a 7 vertex graph: 4 vertices for inputs, 2 vertices for the intermediate products, and a single vertex for the sum. (Figure 1).
We assume a two level memory hierarchy on a single processor with infinite slow memory and a limited cache of fast memory of size M elements, where the result of each operation in the computation graph is a single element. Every operation in the computation graph must be evaluated. When a vertex v is evaluated, the parents of v must be loaded into fast memory from slow memory if they are not already present. As in [3,8,16], we disallow recomputation of the same vertex: therefore, if a computed result is needed elsewhere in the computation graph and is about to be evicted, the result must first be written to slow memory.
I/O can be separated into trivial (reading inputs and writing outputs) and non-trivial I/O. We focus on non-trivial I/O: we thus do not directly include the cost of reading inputs or writing outputs. Instead, we assume that inputs can be read from the user directly into fast memory, and outputs are reported to the user immediately as they are computed. However: if an input is evicted from fast memory and is still needed elsewhere in the computation, it must be written to slow memory. This assumption is inherent in the proof in [3,9]. Because we seek lower bounds, we do not constrain the eviction policy of fast memory. I/O is incurred when, during computation, an element is written to slow memory from fast memory or read from slow memory into fast memory.
An evaluation order is then the order that operations are evaluated in the graph. Since a vertex can only be evaluated after its parents, a valid evaluation order must be topological with respect to the graph. We thus seek lower bounds on the I/O incurred by the optimal evaluation order.
Formally, let G = (V , E) be a computation graph with vertices V and edges E. Let n = |V | be the number of operations in the graph, and let M be the size of fast memory. Note that each vertex in the graph is evaluated exactly once; therefore, the total computation takes exactly n time-steps.
We formalize an evaluation order on G as a permutation matrix X ∈ R n×n , where X i j is one if v j is computed at time-step i. Let O G be the set of valid topological orders on G. Since vertices must be evaluated after their operands, X ∈ O G .
An I/O is incurred every time an element must be read into fast memory from slow memory or written to slow memory from fast memory. Let J G (X ) be the number of nontrivial I/Os that were incurred by evaluating G in the order specified by X on G. We seek a lower bound on J * G , the optimal I/O incurred by any evaluation order:
In this section, we find a lower bound based on the eigenvalues of the graph Laplacian. We first link the problem to the edge expansion of the graph, by counting the number of edges that cross boundaries over a graph partition as in [3]. We frame this problem as a quadratic program (QP) with respect to the graph Laplacian. Finally we use the Laplacian's spectra to find a lower bound on the solution to the QP.
, and d(v) be the indegree, out-degree, and total degree of v respectively. Finally, for any subset S ⊆ V , we define ∂S as the edge boundary of S:
For any evaluation X on G, we can choose a partition P ⊆ 2 V that divides V into disjoint subsets of vertices so each S ∈ P is contiguously ordered by X . P thus defines breakpoints on X . Figure 2 depicts an example of a partition on a graph. The numbers on the vertices indicate the evaluation order determined by X . The graph is then partitioned into green, yellow, and blue segments. Each segment is contiguous with respect to the order.
Let P X be the set of valid partitions on X according to the ordering constraint. We leverage the following key lemma from [3], which divides the I/O cost of a subset of a computation graph into reads (edges entering the subgraph), and writes (edges leaving the subgraph). For each subset S ∈ P, define the following sets:
R S is the vertices not in S with an edge into S, and W S is the vertices in S with an edge outside of S. Ballard et. al in [3] then present the following lemma:
Proof. We summarize the proof of their lemma here. To evaluate the nodes in S, the vertices in R S must be read into fast memory (or were already in fast memory before beginning computation of S). Similarly, the vertices in W S are freshly computed and needed elsewhere in the evaluation and thus must be written out or left in fast memory at the end of S. (Figure 3). Since the fast memory size is only M, at least |R S | + |W S | -2M I/O's are incurred by evaluating the nodes in S.
Summing over all S ∈ P leads to a bound on the IO incurred by G. Any P is valid so long as P splits V into components contiguous in X . Specifically, if P X is the set of valid partitions with respect to X :
It is easier to compute the number of edges crossing into and out of S rather than the vertex sets R S and W S . Ballard et. al use this lemma to bound the I/O of the computation graph for Strassen matrix multiplication. However, they make several assumptions that weaken the bound for general graphs. Firstly, rather than computing a bound for all segments in the partition, they derive a bound for any single n/|P | sized sub-graph within the Strassen computation graph. They then compute this bound specifically for Strassen-like graphs, and multiply this bound by |P | to achieve a bound for the entire graph. This approach succeeds for the Strassen graph where the I/O is evenly distributed across the graph. However, this relaxation can be loose for graphs where the I/O is concentrated in a small portion of the vertices. Secondly, they deal strictly with regular graphs by adding loops to the computation graph. As a result, they link the size of |R S | + |W S | to the size of the edge boundary by dividing by the maximum undirected degree, i.e
While this assumption is convenient for closed form bounds, it is not necessary for automatic methods where we can retain access to the graph.
The following theorem links the partition to the I/O cost. We diverge from [3] by bounding over all segments and maintaining access to the individual degrees of the vertices.
Theorem 2. For fast memory size M and graph G, the optimal I/O is lower bounded by:
Proof. We bound |R S | and |W S | as:
Summing reads and writes, we have:
.
Minimizing over all X , we get the full bound
Intuitively, an adversary picks some evaluation order X on G. We pick a hard partition P on X to maximize the I/O incurred. In the next section, we formalize Theorem 2 as a quadratic program using the graph Laplacian of an out-degree normalized graph. We then lower bound the I/O cost via the eigenvalues of the Laplacian.
In Theorem 2, we solved for the minimum order over a maximum partition. However, since any partition will give us a lower bound, we can choose to split our graph into evenly sized segments. We pick some k ≤ n as our number of segments: splitting into k subsets of as equally as possible (such that the first n mod k segments have ⌊n/k⌋ + 1 vertices and the rest have ⌊n/k⌋ vertices). For an evaluation order X , let P (X,k) ∈ P X be the k-partition described above. If P (I,k) would be the above partition assuming an identity evaluation order X = I k , then we can define
We transform our graph directed G into a weighted undirected graph as follows: for each directed edge (u, v) ∈ G, we add the undirected edge (u, v) to G with weight 1 d out (u) . Henceforth, we indicate the degree function, degree matrix, and adjacency matrix of the original G as d(v), D, and A respectively; we analogously denote d, D, Ã as the degree function, degree matrix, and adjacency matrix of G.
Let L = D -Ã be the graph Laplacian of G. L is positive semidefinite, so all of its eigenvalues are nonnegative. The Laplacian is convenient for expressing the edge boundaries of vertex subsets. Specifically, for subset S ⊆ V , let x ∈ R n be the one-hot encoding of S (i.e x i = I{v i ∈ S }). Then:
Using this property we can bound the edge crossing as:
.
, and rewriting Equation 1 leads to the following quadratic program: Theorem 3 (I/O Bound via Graph Laplacian). For a computation graph G and any k ≤ n with L and W (k) defined as above, J * G is lower bounded by the solution of:
In the next section, we relax the above optimization problem to find a lower bound on the objective using the eigenvalues of L and W (k ) .
We derive the following eigenvalue bound: Theorem 4 (Spectral Method).
Proof. We relax the topological constraint X ∈ O G , and instead constrain over orthogonal X . We thus have for any k:
For symmetric L,W and orthogonal matrix X , where λ 1 , ..., λ n and µ 1 , ..., µ n are the eigenvalues in increasing order of L and W respectively, we have tr(X T LXW ) ≥ n i=1 λ i µ n-i , or the minimal dot product of λ and µ (see [10], Theorem 3). Here W (k ) is a block diagonal matrix, with nk zero eigenvalues and k eigenvalues that are at least ⌊n/k⌋. Therefore, we apply our lower bound as a sum of the first k eigenvalues of L:
This bound can be found in O(n 3 ) time. We first find the eigenvalues λ( L) in O(n 3 ). We then iterate over possible values of k which takes constant time per iteration to find the best eigenvalue. However, we generally only need small number of eigenvalues to find a good k. Since any value of k is a lower bound, it suffices to find the h smallest eigenvalues of L. These values can be found using a method such as Lanczos-Arnoldi with time complexity O(hn 2 ): this complexity decreases even further with sparse L using sparse eigenvalue solvers.
For closed form analysis, sometimes the exact form of the original Laplacian spectra λ(L) are known, but the spectra of our out-degree normalized Laplacian λ( L) are not. While λ( L) can be easily computed automatically, they can be harder to derive for closed form analysis. We can naturally loosen the bound in Theorem 4 to be in terms of L rather than L.
Theorem 5 (Spectral Method with Original Graph Laplacian).
Proof. We follow the same steps of Theorem 4, but we bound Equation 1 as
We can then reframe Equation 3 in terms of L, noting that, if x ∈ R n is the one-hot encoding of S ⊆ V , then x T Lx = |∂S |. Using the same partitioning argument and definition of W (k ) , we can reframe the quadratic program in Theorem 3 with L instead of L:
Then, following the same spectral argument as in Theorem 4, we arrive at a looser, but more convenient bound:
We generalize Theorem 4 to the parallel setting as follows. Suppose that we have p processors, each with memory M. As in [3,12] we count I/O as the communication with a processor to slow memory or between processors. We make no assumptions about the distribution of the workload.
Theorem 6 (Parallel Spectral Bound). For a computation graph G distributed across p processors, at least one of the processors has I/O J * G lower bounded by:
Proof. For a given evaluation of G, each vertex in G is evaluated by one processor. Let V 1 , ..., V p be the vertex sets associated with each processor. Then given the optimal evaluation order X we can define p evaluation orders X 1 , ..., X p where X i indicates the evaluation order of processor i on its vertex set V i . Since memory is local to each processor, we can use the same graph partitioning machinery in Theorem 4 per-processor. For processor i, if P X i is the set of valid partitions over X i , the I/O of processor i is lower bounded by
There must exist one processor i * for which |V i * | ≥ n/p. For this processor, we can partition V i * into k equal parts of n kp vertices each (call this partition P). Since any partition of V i * is a lower bound, we have
However, as a looser lower bound, instead of restricting P to equal partitions of V i * , we can consider the set of equal partitions of the entire graph into kp parts of n kp , and simply pick the k sections incurring the least I/O cost. This is then equivalent to the bound in Theorem 4 with kp partitions, but we only count I/O from the first k parts (which correspond to the smallest k eigenvalues). We then have
For computation graphs with known eigenvalues, we can compute the bound in Theorem 5 directly. We perform this analysis for the Bellman-Held-Karp algorithm for the Traveling Salesman Problem and as well as the Fast Fourier Transform, which have a hypercube and butterfly computation graph respectively. For both of these problems, we consider solely nontrivial I/O, which does not count reading inputs or writing outputs. In the process, we derive the spectrum of the FFT graph; to our knowledge, this is the first closed form of the spectrum of the unwrapped butterfly graph that includes multiplicity. Finally, we present a probabilistic bound on the I/O of a random Erdős Rényi graph.
Previously, [14] found an asymptotically tight bound of Ω( l 2 l log M ) for a 2 l point FFT through manual inspection of 2S partitions. We find that our spectral bound of Ω( l 2 l log 2 M
) is only a factor of 1/log M off from this published tight bound.
The hypercube is a computation graph that appears as a result of many hard dynamic programming problems [1]. For example, consider the well-known Bellman-Held-Karp algorithm which uses dynamic programming to solve the traveling salesman problem [4,11]. The approach solves for the optimal path visiting a subset of the cities by leveraging the computed optimal paths through adjacent subsets with one fewer city.
The Bellman-Held-Karp algorithm with l cities can be naturally formulated as an iteration on the vertices of a boolean hypercube. We encode "cities visited" as a length l binary string. Let Q l be a boolean l-dimensional hypercube, where each vertex k is a length l binary string, and (k 1 , k 2 ) ∈ E if k 2 can be constructed by setting a 0 in k 1 to 1. Let S(k, i) be the shortest path visiting all the cities active in k and ending up at the i'th city. Then to solve TSP, we seek to find the solution set The I/O bound for this formulation of the Bellman-Held-Karp algorithm can then be found via our spectral method, because the hypercube has relatively simple eigenvalues. The l-dimensional hypercube has n = 2 l vertices and Laplacian eigenvalues 2i for i = 0, ..., l with multiplicity l i . If we choose k to encompass the top eigenvalues up to i = α, we have k = α i=0 l i . The maximal out degree is l. For any α < 2 l :
While any α < l would be a lower bound, for simplicity we here choose α = 1 (i.e k = l + 1):
-2M(l + 1).
For a tighter bound we can optimize more specifically over α. We see that this bound is nontrivial as long as M ≤ 2 l (l +1) 2 .
The Fast Fourier Transform (FFT) computation graph is a butterfly graph. For a 2 l point FFT, the butterfly graph B l has (l +1)2 l vertices, which can be arranged into l + 1 columns. A 2 l = 4 point FFT can be seen in Figure 5. The butterfly graph can be defined inductively: allow B 0 to be defined as a single vertex. Then B l can be constructed as two copies of B l -1 that are joined by an extra final column of (l + 1) vertices.
We derive the eigenvalues of the Laplacian of B l (see the Appendix of the full version of this paper, [13]). To our knowledge, closed forms with multiplicities were only previously known for the wrapped butterfly graph [7]. The eigenvalues we derive are:
The smallest eigenvalue is 0 (from the first expression), but the next eigenvalues are governed by the second expression with j = 0 as long as 2i + 1 ≥ l + 1. We choose some α and set k = 2 α +1 . We compute the lowest k eigenvalues of the Laplacian of B l . Of these eigenvalues, 2 α have (with i = lα):
To compute our lower bound, we assume the other eigenvalues are 0. We note that n = (l + 1)2 l . Then we have (dividing by our maximal out-degree 2):
Suppose that we set α = llog 2 M, under the assumption that M ≪ l. Then:
To see how this behaves, we can use the small angle approximation θ 2 /2 ≈ 1cos(θ ) for small θ to get:
Thus, for large M and l where M ≪ l, our bound behaves at least as well as Ω(
). This bound is only a 1/log 2 M factor worse than the tight lower bound for butterfly graphs: Ω( l 2 l log M ), which is computed by inspection on the specific graph using S-partitions [14].
The spectral bound is flexible, and can perform well on most graphs with high connectivity regardless of its structure. In the following section, we characterize the performance of this spectral bound given a random graph, and show that the spectral bound provides nontrivial results for as long as the graph is well-connected. While this graph is not a specific computation graph, examining random graphs allows us to understand the performance of the bound as we increase the connectivity of the graph.
We consider an Erdős Rényi graph G(n, p) on n vertices, where each edge is determined by flipping a coin with probability p. We will only deal with the regime where p ≥ log n n , where the graph is almost surely connected [15].
We begin with the case where p = Θ( log n n ), but the graph is still connected. More specifically, we specify p = p 0 log n n-1 for some p 0 > 6. By [15], in this regime:
We first concentrate the maximum degree of the graph using Chernoff's bound as in [6]. We first note that the degree d of a single vertex is governed by the sum of n -1 Bernoulli random variables with probability p. The expected degree is µ = p(n -1) = p 0 log n. Then using Chernoff's bound, we have:
).
If we set δ = 6/p 0 , we concentrate individual degrees as P(d ≥ (1 + 6/p 0 )p 0 log n) ≤ 1/n 2 . Then, using the union bound, we can concentrate the maximum degree as:
Thus, with high probability (1/n → 0 as n → ∞), we have
Setting k = 2 in Theorem 5, we have with high probability:
As n → ∞ this bound scales roughly with n
, and is linear in M. Our bound becomes weaker, but still nontrivial, when we consider regimes with higher p. This is because as p increases, the maximum degree scales to almost np (and our bound requires dividing by the maximum out degree). For example, consider the case where np log n → ∞, as in this regime the graph is essentially regular with degree np. Then from [15], we have that with high probability as n → ∞:
We then can apply Theorem 5 to lower bound the non-trivial I/O (setting k = 2) and dividing by the max degree np:
As n → ∞, O( log n np ) will decay to zero resulting in a bound linear in n.
We evaluate our two lower bounds on four common computation graphs. To facilitate our evaluation, we develop a solver that traces operations during a Python computation and thus extracts a computation graph 1 . The solver inter-operates with standard arithmetic operations and supports the inclusion of custom operations.
When computing Theorem 4, any choice of k < n produces a valid bound. We set h = 100, computing up to the first 100 values of the graph Laplacian, and choose the optimal k from k ∈ {2...h}. We discuss this choice in Section 6.5.
We evaluate the following graphs. Examples of these graphs can be found in Figure 6.
(1) Fast Fourier Transform (FFT): We evaluate the l level FFT of an 2 l element array, which is a butterfly graph. This graph has a published bound [14] of Ω l2 l /log M .
1 Our code found at Ω n 3 / √ M .
(3) Strassen Multiplication We evaluate the graph formed by multiplying to n × n matrices C = AB via Strassen's method. Since Strassen's method is a recursive method that splits matrices into quadrants, we evaluate on values of n that are powers of 2. This graph has a published bound [3] of
M .
(4) Bellman-Held-Karp We evaluate the hypercube computation graph formed by performing the Bellman-Held-Karp algorithm for a l city TSP. We could not find a prior I/O bound for this problem in the current literature. However, in Section 5.1 we derive using the spectral method a bound of:
Ω 2 l /l -2Ml .
The only current methods for creating automatic lower bounds for any arbitrary graph that we could find are the convex min-cut method [9] and the 2S partition method [8] (see Section 2). The 2S partition method involves solving a Mixed Integer Program, and is combinatorial in complexity: we could thus not perform this method for large graphs. The convex min-cut method is polynomial in time but still extremely expensive at O(n 5 ). We evaluate the convex min-cut method for as large graphs as possible, cutting off evaluation at 1 day.
Convex-Min Cut: The convex min-cut method transforms the graph with respect to a vertex v into a flow problem and then where n is the number of vertices in the graph. In order to reduce runtime, the authors suggest loosening the bound by partitioning the graph into smaller sub-graphs using METIS and running convex min-cut on each sub-graph. If C(v, G) is the minimum convex cut for G transformed with respect to v, and P is the partition reported by METIS, the authors report the bound:
More details can be found in their paper. The authors suggest that each sub-graph have at most 2 * M vertices, and evaluate their bounds on a series of small, simple computation graphs with very uniform structure. However, when evaluating on more complex computation graphs such as matrix multiplication or FFT, we found that the above bound gave trivial results (J * ≥ 0) for every one of the graphs. We hypothesize that the prescribed sub-graph size of 2 * M is too small for more complex graphs . In our evaluation, we display results of the convex min-cut method run over the entire graph (without partitioning):
The above bound is linear in M for any graph. In the worst case, this bound can take O(n 5 ) time to compute.
We examine graph behavior for varying graph sizes and varying M.
We plot the the spectral method and the convex min-cut method against the graph size parameter (l for the 2 l FFT, the matrix side length n for matrix multiplication, and the number of cities for the TSP). To compare against the published bounds, we also plot the computed I/O for the spectral bound against the graph parameter term in the analytical bounds in Section 6.2. For example, we plot the computed I/O for the 2 l point FFT graph against l2 l . If our bounds follow the growth patterns of the analytical bounds, then these plots should be roughly linear. We do not display points where the maximum in-degree is greater than M, because then the computation of some operations would not fit all their operands inside fast memory.
For all four graphs, we find that the bound computed from the spectral method is both tighter and more scalable than the convex min-cut method. In particular, the convex min-cut method is trivial for the naive matrix multiplication graph.
Moreover, we find that our bounds roughly match the analytical growth of the published bounds, as the I/O vs the published bound is roughly linear for all four graphs. Finally, we note that our bound does not significantly degrade with M, and can thus be computed for large memory sizes.
Our spectral method is fast to compute, with a runtime complexity of O(hn 2 ) where h ≤ n is the number of eigenvalues computed. Since any number of partitions k in Theorem 4 gives a valid lower bound, h can be set to trade off the bound strength with runtime complexity, with a maximum runtime of O(n 3 ) by computing all the eigenvalues of the graph Laplacian. However, empirically we found that even when computing all of the eigenvalues, the best k is usually far below 100 even for large graphs, so the higher level eigenvalues remain unused: we therefore can set h = 100 without losing bound strength. In contrast, the convex min-cut method has runtime complexity of O(n 5 ), which does not scale well to large graphs. In Figure 11, we plot the runtime in seconds of computing the convex min-cut and the spectral method for successively larger l for evaluating Bellman-Held-Karp on an l city TSP. We find that the convex-min-cut runtime explodes, taking close to 8.5 hours for the 15 city TSP, while our spectral method takes 98 seconds.
Finding I/O bounds for general computations remains a challenging problem. In this paper, we propose a novel method to find I/O bounds for computation graphs, using the spectra of the graph Laplacian. The spectra can be computed efficiently even for large graphs and can also be computed in closed form for some graphs, yielding a proof technique to find new closed-form bounds. We used the spectral method to derive closed-form bounds for several graphs, including the hypercube for the Bellman-Held-Karp algorithm and the butterfly graph for the Fast Fourier Transform. We evaluated our method empirically on four computation graphs and showed that it finds tighter bounds than previous automated methods at a fraction of the runtime and behaves similarly to published analytical bounds.