NSF-CNPq Collaborative Research: Parallel Elimination Orders with Applications in Operations Research and Scientific Computing

点击翻译按钮获取中文摘要

This project is concerned with the design and implementation of algorithms for solving large linear systems of equations using direct methods. In particular, the focus is on the problem of finding the order in which variables should be eliminated during the course of Gaussian elimination. The goal is to develop algorithms that are both provably efficient and highly tuned for the types of matrices that arise in operations research and scientific computing. The work has both analytical and experimental components. On the analytical side, it involves rigorous evaluation of performance of known ordering algorithms such as the minimum-degree heuristic, on specific classes of graphs, such as interval graphs and grid graphs. The aim is to understand when and why these algorithms work well in practice. On the experimental side, it involves implementation of software for finding elimination orders that is competitive with state-of-the art implementations of the minimum-degree, nested dissection, and hybrid algorithms.