GPU-accelerated path tracker for polyhedral homotopy
GPU-accelerated path tracker for polyhedral homotopy
复制标题
用于多面体同伦的 GPU 加速路径跟踪器
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Tianran Chen
中科院分区：
文献类型：
--
作者：
Tianran Chen
Huber和Sturmfels的多面体同伦方法是求解（Laurent）多项式方程组的一种特别有效和鲁棒的数值方法。该方法的实现中的中心组件是高效且可扩展的路径跟踪器。虽然计算机集群或多核CPU的可扩展路径跟踪器的实现问题已经彻底解决，但设计良好的基于GPU的实现仍然是一个活跃的研究课题。本文解决了有效地评估一个多元系统的洛朗多项式及其所有的偏导数的核心问题。我们提出了一个简单的方法，特别是映射到现代GPU的并行计算架构。作为一个副产品，我们还简化和加速路径跟踪器合并的欧拉和牛顿方向的计算。
The polyhedral homotopy method of Huber and Sturmfels is a particularly efficient and robust numerical method for solving system of (Laurent) polynomial equations. A central component in an implementation of this method is an efficient and scalable path tracker. While the implementation issues in a scalable path tracker for computer clusters or multi-core CPUs have been solved thoroughly, designing good GPU-based implementations is still an active research topic. This paper addresses the core issue of efficiently evaluate a multivariate system of Laurent polynomials together with all its partial derivatives. We propose a simple approach that maps particularly well onto the parallel computing architectures of modern GPUs. As a by-product, we also simplify and accelerate the path tracker by consolidating the computation of Euler and Newton directions.