Fast computations with the harmonic Poincaré–Steklov operators on nested refined meshes

In this paper we develop asymptotically optimal algorithms for fast computations with the discrete harmonic Poincaré–Steklov operators (Dirichlet–Neumann mapping) for interior and exterior problems in the presence of a nested mesh refinement. Our approach is based on the multilevel interface solver applied to the Schur complement reduction onto the nested refined interface associated with a nonmatching decomposition of a polygon by rectangular substructures. This paper extends methods from Khoromskij and Prössdorf (1995), where the finite element approximations of interior problems on quasi‐uniform grids have been considered. For both interior and exterior problems, the matrix–vector multiplication with the compressed Schur complement matrix on the interface is shown to have a complexity of the order $\mathcal{O}(N_r log^3 N_u)$, where $N_r = \mathcal{O}((1 + p_r) N_u)$ is the number of degrees of freedom on the polygonal boundary under consideration, $N_u$ is the boundary dimension of a finest quasi‐uniform level and $p_r \geq 0$ defines the refinement depth. The corresponding memory needs are estimated by $\mathcal{O}(N_r log^q N_u)$, where $q = 2$ or $q = 3$ in the case of interior and exterior problems, respectively