期刊
SIAM JOURNAL ON SCIENTIFIC COMPUTING
卷 43, 期 5, 页码 S392-S419出版社
SIAM PUBLICATIONS
DOI: 10.1137/20M1348571
关键词
mixed precision; multigrid; rounding-error analysis; progressive precision
This paper establishes the first theoretical framework for analyzing the rounding-error effects on multigrid methods using mixed-precision iterative-refinement solvers, providing normwise forward error analysis and introducing the notion of progressive precision for multigrid solvers. The theoretical results show that rounding an exact result to finite precision causes an error in the energy norm proportional to the square root of the matrix condition number K, indicating that the limiting accuracy for both V-cycles and full multigrid is proportional to k(1/2) in energy. Additionally, the loss of convergence rate due to rounding grows in proportion to k(1/2), but is argued to be insignificant in practice.
This paper establishes the first theoretical framework for analyzing the rounding-error effects on multigrid methods using mixed-precision iterative-refinement solvers. While motivated by the sparse symmetric positive definite (SPD) matrix equations that arise from discretizing linear elliptic PDEs, the framework is purely algebraic such that it applies to matrices that do not necessarily come from the continuum. Based on the so-called energy or A norm, which is the natural norm for many problems involving SPD matrices, we provide a normwise forward error analysis and introduce the notion of progressive precision for multigrid solvers. Each level of the multigrid hierarchy uses three different precisions that each increase with the fineness of the level, but at different rates, thereby ensuring that the bulk of the computation uses the lowest possible precision. The theoretical results developed here in the energy norm differ notably from previous theory based on the Euclidean norm in important ways. In particular, we show that simply rounding an exact result to finite precision causes an error in the energy norm that is proportional to the square root of K, the associated matrix condition number. (By contrast, this error is of order 1 when measured in the Euclidean norm.) Given this observation, we show that the limiting accuracy for both V-cycles and full multigrid is optimal in the sense that it is also proportional to k(1/2) in energy. Additionally, we show that the loss of convergence rate due to rounding grows in proportion to k(1/2) , but argue that this loss is insignificant in practice. The theory presented here is the first forward error analysis in the energy norm of iterative refinement and the first rounding error analysis of multigrid in general.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据