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.