Kernel Multi-Grid on Manifolds

Kernel methods for solving partial differential equations on surfaces have the advantage that those methods work intrinsically on the surface and yield high approximation rates if the solution to the partial differential equation is smooth enough. Naive implementations of kernel based methods suffer, however, from the cubic complexity in the degrees of freedom. Localized Lagrange bases have proven to overcome this computational complexity to some extend. In this article we present a rigorous proof for a geometric multigrid method with $\tau\ge 2$-cycle for elliptic partial differential equations on surfaces which is based on precomputed Lagrange basis functions. Our new multigrid provably works on quasi-uniform point clouds on the surface and hence does not require a grid-structure. Moreover, the computational cost scales log-linear in the degrees of freedom.