1. H2-MG: A multigrid method for hierarchical rank structured matrices
- Author
-
Sushnikova, Daria, Turkiyyah, George, Chow, Edmond, and Keyes, David
- Subjects
Mathematics - Numerical Analysis ,65F10, 65N55, 65F30, 65F55 - Abstract
This paper presents a new fast iterative solver for large systems involving kernel matrices. Advantageous aspects of H2 matrix approximations and the multigrid method are hybridized to create the H2-MG algorithm. This combination provides the time and memory efficiency of H2 operator representation along with the rapid convergence of a multilevel method. We describe how H2MG works, show its linear complexity, and demonstrate its effectiveness on two standard kernels. The current zoo of H2 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 H2-MG a valuable addition to the collection of H2 solvers. The algorithm has potential for advancing various fields that require the solution of large, dense, symmetric positive definite matrices.
- Published
- 2025