Parallel tridiagonal matrix inversion with a hybrid multigrid-Thomas algorithm method
Parallel tridiagonal matrix inversion with a hybrid multigrid-Thomas algorithm method
复制标题
混合多重网格-Thomas算法的并行三对角矩阵求逆
DOI：
10.1016/j.cam.2021.113706
复制
发表时间：
2022
影响因子：
2.4
通讯作者：
Parker J
中科院分区：
文献类型：
--
作者：
Parker J
三对角矩阵求逆是一种重要的运算，有着广泛的应用。它经常出现在求解离散的一维椭圆型偏微分方程，并形成了许多算法的基础上块三对角矩阵求逆的离散偏微分方程在更高的维度。在这样的系统中，该操作通常是并行计算中的缩放瓶颈。在本文中，我们推导出一个混合multigrid-Thomas算法，旨在有效地逆三对角矩阵方程的时间演化偏微分方程系统的背景下，在一个高度可扩展的方式。我们分解的处理器之间的域，使用多重网格求解的网格组成的边界点的每个处理器的本地域。然后，我们使用托马斯算法直接求解，在每个处理器上重建解决方案。该算法具有与循环约简和递归倍乘相同的理论最优尺度。我们使用我们的算法来解决泊松方程的时间演化PDE系统的空间离散化的一部分。我们的算法比循环还原每次反演的速度更快，并保留了良好的缩放效率，以两倍的核心。
Tridiagonal matrix inversion is an important operation with many applications. It arises frequently in solving discretized one-dimensional elliptic partial differential equations, and forms the basis for many algorithms for block tridiagonal matrix inversion for discretized PDEs in higher-dimensions. In such systems, this operation is often the scaling bottleneck in parallel computation. In this paper, we derive a hybrid multigrid-Thomas algorithm designed to efficiently invert tridiagonal matrix equations in a highly-scalable fashion in the context of time evolving partial differential equation systems. We decompose the domain between processors, using multigrid to solve on a grid consisting of the boundary points of each processor’s local domain. We then reconstruct the solution on each processor using a direct solve with the Thomas algorithm. This algorithm has the same theoretical optimal scaling as cyclic reduction and recursive doubling. We use our algorithm to solve Poisson’s equation as part of the spatial discretization of a time-evolving PDE system. Our algorithm is faster than cyclic reduction per inversion and retains good scaling efficiency to twice as many cores.