A Matrix-Free ILU Realization Based on Surrogates

Abstract

Matrix-free techniques play an increasingly important role in large-scale simulations. Schur complement techniques and massively parallel multigrid solvers for second-order elliptic partial differential equations significantly benefit from reduced memory traffic and consumption. The matrix-free approach often restricts solver components to purely local operations, for instance, to the most basic schemes like Jacobi- or Gauss–Seidel-Smoothers in multigrid methods. An incomplete LU(0)-decomposition (ILU) cannot be calculated from local information and is therefore not applicable to an on-the-fly computation typically needed for matrix-free calculations. It requires storing and factorizing a sparse matrix, contradicting the low memory requirements in large-scale scenarios. Here, we propose a matrix-free ILU realization. More precisely, we introduce a memory-efficient matrix-free ILU-Smoother component for low-order conforming finite elements on tetrahedral hybrid grids. Hybrid grids consist of an unstructured macro-mesh which is subdivided into structured micro-meshes. The ILU operates on the degrees of freedom assigned to the interior of macro-tetrahedra. This ILU-Smoother can be applied to the efficient matrix-free evaluation of the Steklov–Poincaré operator from domain-decomposition methods, as well as for the finite element tearing and interconnecting dual-primal and balancing domain decomposition by constraints methods. After introducing and formally defining our smoother, we investigate its performance on refined macro-tetrahedra. On the macro-tetrahedra the ILU-Smoother is implemented via surrogate matrix polynomials, which we combine with a fast on-the-fly evaluation scheme, resulting in an efficient matrix-free algorithm. We obtain the polynomial coefficients by solving a least-squares problem on a small part of the factorized ILU matrices to remain memory efficient. The convergence rates of this smoother in relation to the polynomial order are thoroughly studied.