\({\mathcal{H}^{2}}\)-MG: A Multigrid Method for Hierarchical Rank Structured Matrices

Abstract. This paper presents a new fast iterative solver for large systems involving kernel matrices. Advantageous aspects of [Formula: see text] matrix approximations and the multigrid method are hybridized to create the [Formula: see text]-MG algorithm. This combination provides the time and memory efficiency of [Formula: see text] operator representation along with the rapid convergence of a multilevel method. We describe how [Formula: see text]-MG works, show its linear complexity, and demonstrate its effectiveness on two standard kernels and on a single-layer potential boundary element discretization with complex geometry. The current zoo of [Formula: see text] solvers, which includes a wide variety of iterative and direct solvers, so far lacks a method that exploits multiple levels of resolution, commonly referred to in the iterative methods literature as “multigrid” from its origins in a hierarchy of grids used to discretize differential equations. This makes [Formula: see text]-MG a valuable addition to the collection of [Formula: see text] solvers. The algorithm has the potential for advancing various fields that require the solution of large, dense, symmetric positive definite matrices. Reproducibility of computational results. This paper has been awarded the “SIAM Reproducibility Badge: Code and data available” as recognition that the authors have followed reproducibility principles valued by SISC and the scientific computing community. Code and data that allow readers to reproduce the results in this paper are available at https://github.com/dsushnikova/h2mg and in the supplementary materials ( h2mg-main.zip [269KB]). [Formula: see text]