Distance-k Graph Coloring Algorithms for Numerical Optimization

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

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.