In this paper we demonstrate that parallelism and fill can be traded off in orders for Gaussian elimination.While the well-known nested dissection algorithm produces very parallel elimination orders, we show that by reducing the parallelism it is possible to reduce the fill that the orders generate.In particular, we present a new "less parallel nested dissection" algorithm (LPND).We prove that, unlike standard nested dissection, when applied to a chordal graph LPND finds a zero-fill elimination order.Our implementation of LPND generates less fill than state-of-the-art implementations of the nested dissection (METIS), minimum-degree @MD), and hybrid (BEND) algorithms on a large body of test matrices, at the cost of a small reduction in the paralellism in the orders that it produces.We have also implemented a nested dissection algorithm that is different from METIS and that uses the same separator algorithm used by our implementation of LPND.This algorithm, like LPND, generates less fill than METIS, and on large graphs generates significantly less fill than AMD.The latter comparison is notable, because although it is known that, for certain classes of graphs, minimum-degree produces asymptotically more fill than nested dissection, minimumdegree is believed to produce low-fill orderings in practice.Our experiments contradict this belief.

This paper presents an algorithm for finding parallel elimination orders for Gaussian elimination. Viewing a system of equations as a graph, the algorithm can be applied directly to interval graphs and chordal graphs. For general graphs, the algorithm can be used to parallelize the order produced by some other heuristic such as minimum degree. In this case, the algorithm is applied to the chordal completion that the heuristic generates from the input graph. In general, the input to the algorithm is a chordal graph G with n nodes and m edges. The algorithm produces an order with height at most O(log/sup 3/ n) times optimal, fill at most O(m), and work at most O(W*(G)), where W*(G) is the minimum possible work over all elimination orders for G. Experimental results show that when applied after some other heuristic, the increase in work and fill is usually small. In some instances the algorithm obtains an order that is actually better, in terms of work and fill, than the original one. We also present an algorithm that produces an order with a factor of log n less height, but with a factor of O(/spl radic/log n) more fill.

Achieving high-speed network I/O on distributed memory systems is a hard problem because their architectures are, in general, ill-suited for communication with the external world One of the problems is that messages are distributed over the private memories of the distributed memory system. This can result in poor performance since communication includes a complex scatter/gather operation. This paper presents a strategy in which the task of creating large contiguous messages is performed on the distributed-memory system, thus minimizing the overhead on the network interface. The performance results for an implementation of this strategy for an iWarp system with a HIPPI interface board are presented.>

Clique graphs of chordal and path graphs are characterized. A special class of graphs named expanded trees is discussed. It consists of a subclass of disk-Helly graphs. It is shown that the clique graph of every chordal (hence path) graph is an expanded tree. In addition, every expanded tree is the clique graph of some path (hence chordal) graph. Different characterizations of expanded trees are described, leading to a polynomial time algorithm for recognizing them.