Improving Coarsening and Interpolation for Algebraic Multigrid

[摘要] Algebraic multigrid (AMG) is one of the most efficient algorithms for solving largesparse linear systems on unstructured grids. Classical coarsening schemes such as thestandard Ruge-Stüben method [14] can lead to adverse effects on computation timeand memory usage that affect scalability. Memory and execution time complexitygrowth is remedied for various large three-dimensional problems using the parallel modified independent set (PMIS) coarsening strategy developed by De Sterck,Yang, and Heys [18]. However, this coarsening strategy often leads to erratic gridswithout a regular structure that diminish convergence.

This thesis looks at two modifications of the PMIS algorithm that aim to improvescalability. These include a greedy implementation of PMIS and restricting PMIScoarsening to finer grid levels while Cleary-Jones-Luby-Plassman coarsening (basedon the standard Ruge-Stüben method) is performed on all other grids. It is shownthat, for a variety of problems, the greedy PMIS algorithm does little to improveconvergence, while the second modification can improve convergence. However, it isalso shown that the second modification can result in increased memory usage thatis unfavorable to scalability.

The PMIS based algorithm can be improved by redefining interpolation. As shownby De Sterck and Yang [17], PMIS coarsening combined with F-F interpolation dramatically improves convergence, but often has negative effects on computation timeper iteration and memory usage that affect scalability. A third modification is proposed that aims to remedy this problem by altering F-F interpolation. The newalgorithm is called F-F1 interpolation, and is shown to reduce computation time periteration and memory usage compared to F-F interpolation, while maintaining fastconvergence and good scalability, for a variety of problems.

[发布机构] University of Waterloo

[关键词] Mathematics