cs.DS math.CO
Engineering Data Reduction for Nested Dissection. Many applications rely on time intensive matrix operations, such as factorization, which can be sped up significantly for large sparse matrices by interpreting the matrix as a sparse graph and computing a node ordering that minimizes the so called fill in. In this paper, we engineer new data reduction rules for the minimum fill in problem, which significantly reduce the size of the graph while producing an equivalent (or near equivalent) instance. By applying both new and existing data reduction rules exhaustively before nested dissection, we obtain improved quality and at the same time large improvements in running time on a variety of instances. Our overall algorithm outperforms the state of the art significantly it not only yields better elimination orders, but it does so significantly faster than previously possible. For example, on road networks, where nested dissection algorithms are typically used as a preprocessing step for shortest path computations, our algorithms are on average six times faster than Metis while computing orderings with less fill in.