An odyssey into local refinement and multilevel preconditioning I: Optimality of the BPX preconditioner

In this paper we give a systematic presentation of a number of modern approximation theory tools which are useful for the analysis of multilevel preconditioners. We then use these tools to establish a number of new (and old) results for the Bramble-Pasciak-Xu (BPX) preconditioner in two and three spatial dimensions, on quasiuniform and locally re ned meshes, for both red-green (conforming) and red (non-conforming) mesh refinement algorithms. For example, under the assumption of Hˢ-stability of L₂-projection for s ≥ 1 we give a very simple optimality proof of the BPX preconditioner on quasiuniform meshes through the use of K-functionals. While the existing literature on the optimality of the BPX preconditioner is primarily restricted to uniformly refined meshes, there are some notable exceptions for two dimensions such as the original Dahmen-Kunoth paper. One of the main results of this paper is the extension of these types of optimality results to locally re ned two- and three-dimensional meshes constructed using standard red-green as well as red-only refinement algorithms. We establish a number of geometrical relationships between neighboring simplices produced by these classes of refinement algorithms, and these results are then used to show that the resulting locally enriched  nite element subspace supports the construction of a scaled basis which is formally Riesz stable. The proof techniques we use are quite general; in particular, the results in this paper require no smoothness assumptions on the differential equation coefficients, and the refinement procedures may produce nonconforming meshes. Moreover, the theoretical framework supports arbitrary spatial dimension d ≥ 1; only the geometrical relationships must be re-established for spatial dimension d ≥ 4.