Parallel tridiagonal matrix inversion with a hybrid multigrid-Thomas algorithm method
| Autor: | Ben Dudson, Joseph Thomas Parker, P. Hill, David Dickinson |
|---|---|
| Rok vydání: | 2022 |
| Předmět: |
Computational Mathematics
Partial differential equation Multigrid method Tridiagonal matrix Discretization Elliptic partial differential equation Applied Mathematics MathematicsofComputing_NUMERICALANALYSIS Tridiagonal matrix algorithm Applied mathematics Inversion (discrete mathematics) Cyclic reduction Mathematics |
| Zdroj: | Journal of Computational and Applied Mathematics. 399:113706 |
| ISSN: | 0377-0427 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect