next up previous contents index CD CD Algorithms
Next: Matrix Multiplication Up: Numerical Problems Previous: Solving Linear Equations

Bandwidth Reduction



Input description: A graph G=(V,E), representing an tex2html_wrap_inline26950 matrix M of zero and nonzero elements.

Problem description: Which permutation p of the vertices of V minimizes the length of the longest edge when the vertices are ordered on a line, i.e. minimizes tex2html_wrap_inline26952 ?

Discussion: Bandwidth reduction lurks as a hidden but important problem for both graphs and matrices, and it is important to see how it arises so as to properly recognize it. Applied to matrices, it permutes the rows and columns of a sparse matrix so as to minimize the distance b of any nonzero entry from the center diagonal. This is important in solving linear systems, because Gaussian elimination (see Section gif) can be performed in tex2html_wrap_inline26954 on matrices of bandwidth b. This is a big win over the general tex2html_wrap_inline26956 algorithm if b << n.     

Bandwidth minimization on graphs arises in more subtle ways. Arranging a set of n circuit components in a line on a circuit board so as to minimize the length of the longest wire (and hence time delay) is a bandwidth problem, where each vertex of our graph corresponds to a circuit component and there is an edge for every wire linking two components. Alternatively, consider a hypertext application where we must store large objects (say images) on a magnetic tape. From each image there is a set of possible images we can go to next (i.e. the hyperlinks). To minimize the search time, we seek to place linked images near each other on the tape. This is exactly the bandwidth problem. More general formulations, such as rectangular circuit layouts and magnetic disks, inherit the same hardness and classes of heuristics from the linear versions.              

Unfortunately, bandwidth minimization is NP-complete. It stays NP-complete even if the input graph is a tree whose maximum vertex degree is 3, which is an unusually strong condition.   Further, there is no known approximation algorithm for bandwidth reduction, even for trees.   Thus our only options are brute-force search or ad hoc heuristics.

Fortunately, ad hoc heuristics have been well-studied in the numerical analysis community, and production-quality implementations of the best heuristics are available.   These are based on performing a breadth-first search from a given vertex v, where v is placed at the leftmost point of the ordering.   All of the vertices that are distance 1 from v are placed to its immediate right, followed by all the vertices at distance 2, and so forth until we reach the vertex furthest from v. We then continue the breadth-first search from the vertex immediately to the right of v until all vertices in G are accounted for. The popular heuristics differ according to how many different start vertices are considered and how equidistant vertices are ordered among themselves. However, breaking ties with low-degree vertices over to the left seems to be a good idea.

Implementations of the most popular heuristics, the Cuthill-McKee and Gibbs-Poole-Stockmeyer algorithms, are discussed in the implementation section. The worst case of the Gibbs-Poole-Stockmeyer algorithm is tex2html_wrap_inline26960 , which would wash out any possible savings in solving linear systems, but its performance in practice is close to linear.    

Brute-force search programs can find the exact minimum bandwidth work by backtracking through the set of n! possible permutations of vertices.   Considerable pruning can be achieved to reduce the search space by starting with a good heuristic bandwidth solution and alternately adding vertices to the left- and rightmost open slots in the partial permutation.   The first edge connecting a vertex on the left to a vertex on the right will likely define an edge whose length is greater than our best example to date, thus leading to fast pruning. In our experience, graphs of size n=30 or so can be solved to optimality. See the discussion on backtracking in Section gif. However, for almost any application such an exact solution will not be worth the expense of finding it.

Implementations: Fortran language implementations of both the Cuthill-McKee algorithm [CGPS76, Gib76, CM69] and the Gibbs-Poole-Stockmeyer algorithm [Lew82, GPS76] are available from Netlib. See Section gif.     Empirical evaluations of these and other algorithms on a test suite of 30 matrices are discussed in [Eve79b], showing Gibbs-Poole-Stockmeyer to be the consistent winner.

Brute-force implementations written by Ingmar Bitter, Christian Joita, and Dario Vlah in C and C++ as Stony Brook class   projects and capable of solving instances of size n=30 to optimality are provided on the algorithm repository tex2html_wrap_inline26968 algorith.   

Notes: An excellent survey on graph-theoretic and algorithmic results on the bandwidth problem to 1981 appears in [CCDG82]. Ad hoc heuristics have been widely studied, a tribute to its importance in numerical computation. Everstine [Eve79b] cites no less than 49 different bandwidth reduction algorithms!

The hardness of the bandwidth problem was first established by Papadimitriou [Pap76b], and its hardness on trees of maximum degree 3 in [GGJK78].   There are algorithms that run in polynomial time for fixed bandwidth k [Sax80]. An exposition on the hardness of the linear arrangement problem appears in [Eve79a].

Related Problems: Solving linear equations (see page gif), topological sorting (see page gif).    

next up previous contents index CD CD Algorithms
Next: Matrix Multiplication Up: Numerical Problems Previous: Solving Linear Equations

Mon Jun 2 23:33:50 EDT 1997