Distance-k Graph Coloring Algorithms for Numerical Optimization

用于数值优化的距离 k 图着色算法

• 批准号: 0306334
• 负责人: Alex Pothen
• 金额: $ 37.07万
• 依托单位: Old Dominion University Research Foundation
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2003
• 资助国家: 美国
• 起止时间: 2003-08-15 至 2006-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0306334&HistoricalAwards=false
• 关键词: Distance; Graph; Coloring; Algorithms; Numerical

Algorithms for large-scale numerical optimization that rely on derivative information require the repeated estimation of Jacobian and Hessian matrices. Since this is an expensive part of the computation, efficient methods for estimating these matrices via finite differences or automatic differentiation are needed. The problem of minimizing the number of function computations can be formulated as variants of distance-k graph coloring problems. In this research project, graph coloring algorithms to aid the solution of large-scale optimization problems are designed, analyzed, and implemented on serial and parallel computers. The specific coloring problem depends on the optimization context: whether the Jacobian or the Hessian is evaluated; whether all the nonzeros or only a subset need to be estimated; whether a direct method or substitution method is employed; and whether elements are estimated by partitions of columns alone, or partitions of both columns and rows. These variations lead to ten different matrix estimation problems and their graph coloring formulations. By unifying graph-theoretic formulations for estimating Jacobians and Hessians, a few general coloring problems that can be adapted to the different cases are identified. The focus is on developing new graph coloring algorithms and software for partial matrix estimation to precondition optimization problems.Optimization involves choosing the best option among many possible scenarios from a computational model of a physical situation, such as a manufacturing process involving chemically reacting fluid flows, or the simulation of electronic devices and circuits. In many such large-scale applications of optimization, computing the derivatives is a tedious, error-prone, and expensive task. Automatic differentiation methods and finite difference techniques have been devised in recent years to make this task less demanding and more reliable. This research project provides software infrastructure to reduce the computational time and storage needed to compute the derivatives using automatic differentiation or finite differences in large-scale optimization. One postdoctoral research associate and a graduate student, the former from an under-represented group in computer science, are being trained in combinatorial scientific computing. A module on graph coloring for estimating Jacobians via finite differences is being incorporated into an undergraduate scientific computing course, and undergraduate students are involved in developing and testing components of the software. With the involvement of colleagues at the Department of Energy's Argonne National Laboratory and Sandia National Laboratories, the software from this research is being applied to simulate chemically reacting flows and circuit models.

依赖导数信息的大规模数值优化算法需要重复估计雅可比矩阵和海森矩阵。由于这是计算的昂贵部分，因此需要通过有限差分或自动微分来估计这些矩阵的有效方法。最小化函数计算次数的问题可以用距离k图着色问题的变体来表示。在这个研究项目中，图着色算法，以帮助解决大规模的优化问题的设计，分析，并在串行和并行计算机上实现。具体的着色问题取决于优化的背景：是否雅可比或海森的评估;是否所有的非零或只有一个子集需要估计;是否采用直接方法或替代方法;以及是否元素估计的分区列单独，或分区的列和行。这些变化导致十个不同的矩阵估计问题和他们的图形着色公式。通过统一的图论公式估计雅可比和海森，一些一般的着色问题，可以适应不同的情况下确定。重点是开发新的图着色算法和软件，用于部分矩阵估计以预处理优化问题。优化涉及从物理情况的计算模型中的许多可能方案中选择最佳方案，例如涉及化学反应流体流动的制造过程，或电子设备和电路的模拟。在许多这样的大规模优化应用中，计算导数是一项繁琐、容易出错且昂贵的任务。近年来，自动微分方法和有限差分技术已经被设计出来，使这项任务要求更低，更可靠。该研究项目提供了软件基础设施，以减少计算所需的计算时间和存储使用自动微分或有限差分在大规模优化的衍生物。一名博士后研究助理和一名研究生（前者来自计算机科学领域代表性不足的群体）正在接受组合科学计算方面的培训。一个关于通过有限差分估计雅可比矩阵的图着色模块正在纳入本科科学计算课程，本科生参与开发和测试软件的组成部分。在能源部阿贡国家实验室和桑迪亚国家实验室的同事的参与下，这项研究的软件正在被应用于模拟化学反应流和电路模型。