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

NSF-CNPq 合作研究：并行消除顺序及其在运筹学和科学计算中的应用

• 批准号: 9900304
• 负责人: Gary Miller
• 金额: $ 19.91万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1999
• 资助国家: 美国
• 起止时间: 1999-09-15 至 2003-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9900304&HistoricalAwards=false
• 关键词: NSF; CNPq; Collaborative; Research; Parallel

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.

这个项目关注的是使用直接方法求解大型线性方程组的算法的设计和实现。特别地，重点是在高斯消去过程中找到变量应该消除的顺序的问题。我们的目标是开发一种算法，这种算法既可以证明是高效的，又可以高度调优，适用于运筹学和科学计算中出现的矩阵类型。这项工作既有分析部分，也有实验部分。在分析方面，它涉及对已知排序算法（如最小度启发式算法）在特定图类（如区间图和网格图）上的性能进行严格评估。目的是了解这些算法何时以及为什么在实践中表现良好。在实验方面，它涉及到用于查找消除顺序的软件的实现，该软件与最小程度、嵌套分解和混合算法的最新实现相竞争。