AutoAMG($θ$): An Auto-Tuned AMG Method Based on Deep Learning for Strong Threshold (Communications in Computational Physics, 2024)
Algebraic Multigrid (AMG) is one of the most widely used iterative algorithms for solving large sparse linear equations $Ax=b.$ In AMG, the coarse grid is akey component that affects the efficiency of the algorithm, the construction of whichrelies on the strong threshold parameter $θ.$ This parameter is generally chosen empirically, with a default value in many current AMG solvers of 0.25 for 2D problems and0.5 for 3D problems. However, for many practical problems, the quality of the coarsegrid and the efficiency of the AMG algorithm are sensitive to $θ;$ the default value israrely optimal, and sometimes is far from it. Therefore, how to choose a better $θ$ isan important question. In this paper, we propose a deep learning based auto-tuningmethod, AutoAMG($θ$) for multiscale sparse linear equations, which are common inpractical problems. The method uses Graph Neural Network (GNN) to extract matrix features, and a Multilayer Perceptron (MLP) to build the mapping between matrixfeatures and the optimal $θ,$ which can adaptively predict $θ$ values for different matrices. Numerical experiments show that AutoAMG($θ$) can achieve significant speedupcompared to the default $θ$ value.
Keywords: AMG; strong threshold; graph neural network; auto-tuning; multiscale matrix.