Parallel tridiagonal matrix inversion with a hybrid multigrid-Thomas algorithm method
Hill, P. A. 1Parker, J. T. 2Dickinson, D. 1Dudson, B. D.1
扫码查看
点击上方二维码区域，可以放大扫码查看
作者信息
1. Univ York
2. United Kingdom Atom Energy Author
折叠
Abstract
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 multigridThomas 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. Crown Copyright (c) 2021 Published by Elsevier B.V. All rights reserved.
NSTL
Elsevier