摘要: Gaussian elimination applied to a sparse matrix creates non-zero entries, filling in the original matrix. One major goal of sparse factorization research is minimizing this fill, a NP-complete problem. A sparse matrix’s non-zero pattern can be represented as a graph. For a symmetric matrix, the graph is an undirected graph with a vertex for each column of the matrix. The minimum fill from factoring a sparse symmetric graph is directly related to the size of the smallest balancing vertex separator [1]. Finding a reasonable upper bound on the size of a vertex separator is easy. There are many algorithms that produce apparently good separators in undirected graphs. These algorithms are only compared to each other or to their performance on overly simple graphs. Finding the smallest vertex separator is NP hard, and little effort been spent towards finding hard lower bounds. Optimization-based techniques have long been …