AF:Small: Combinatorial Algorithms to Enable Derivative Computations on Multicore Architectures

导数在计算科学和工程的许多背景下都是必需的，包括非线性优化和非线性微分方程的算法。该项目针对当前最先进的计算衍生技术，自动微分（AD）及其对多核架构的适应。这项工作的算法和软件将对高性能计算和计算科学与工程社区有用。AD技术的进步将直接有助于改进不确定性量化和灵敏度分析的方法，这两者在国家利益的科学应用的高保真预测计算机模拟中发挥关键作用。基于该项目部分内容的模块将纳入适当的研究生课程。作为该项目的一部分，主要研究人员将访问并在印第安纳州的一所四年制本科学院举办研讨会，介绍这项研究，以激励学生攻读科学和工程专业的研究生课程。自动（或微分）微分（AD）是用于准确和有效地评估衍生物的日益重要的现代技术，但它产生了许多组合问题，有效的算法仍有待发现。多核计算平台，通过将大量的计算能力带到桌面，很好地定位于加速科学和工程的创新和发现，只要它们配备有适当的使能算法和软件。该项目专注于通用组合抽象，旨在加速基础AD算法和在多核平台上实现衍生计算所需的算法的进展。具体目标是：（1）开发基于图的、利用冗余度的模型和算法，用于通过AD进行Hessian的高效计算，（2）开发组合算法，以支持在多核架构上使用AD进行大型稀疏雅可比矩阵和Hessian矩阵的高效计算，以及（3）开发组合算法，用于在多核架构上进行不规则计算中的并发发现。 许多目标组合问题都是NP难最优解决的，并且将强调产生接近最优解的快速算法。为了确保算法在快速发展的多核平台上正确、可靠和可扩展地运行，将仔细关注编程模型、算法和数据结构设计以及内存管理。适当的大规模非线性优化问题将被用来指导算法的开发工作，并作为一种工具，以证明影响。

Derivatives are required in numerous contexts in computational science and engineering, including in algorithms for nonlinear optimization and nonlinear differential equations. This project targets the current state-of-the-art technology for computing derivatives, Automatic Differentiation (AD), and its adaptation to multi-core architectures. Algorithms and software from this effort will be useful to the high-performance computing and computational science and engineering communities. Advances in AD technology will directly contribute to improved methods for uncertainty quantification and sensitivity analysis, both of which play crucial roles in high-fidelity predictive computer simulations for scientific applications of national interest. Modules based on parts of this project will be included in suitable graduate courses. As part of this project, the Principle Investigators will visit and give seminars describing this research at a four-year undergraduate college in Indiana to motivate students to pursue graduate studies in science and engineering.Automatic (or Algorithmic) Differentiation (AD) is a modern technology of growing importance for evaluating derivatives accurately and efficiently, but it generates a number of combinatorial problems for which efficient algorithms remain to be found. Multi-core computing platforms, by bringing substantial computing power to the desktop, are well positioned to accelerate innovation and discovery in science and engineering, as long as they are furnished with suitable enabling algorithms and software. Focusing on general-purpose combinatorial abstractions, this project seeks to accelerate progress on both fundamental AD algorithms and those needed to enable derivative computation on multi-core platforms. The specific goals are to: (1) Develop graph-based, symmetry-exploiting models and algorithms for efficient computation of Hessians via AD, (2) Develop combinatorial algorithms to support efficient computation of large, sparse Jacobian and Hessian matrices using AD on multi-core architectures, and (3) Develop combinatorial algorithms for concurrency discovery in irregular computations on multi-core architectures. Many of the targeted combinatorial problems are NP-hard to solve optimally, and fast algorithms that yield near-optimal solutions will be emphasized. To ensure that the algorithms would run correctly, reliably and in a scalable manner on the rapidly evolving multi-core platforms, careful attention will be paid to programming models, algorithm and data structure design, and memory management. Suitable large-scale nonlinear optimization problems will be used to guide the algorithm development effort and as a vehicle for demonstrating impact.