Uniform estimate of the constant in the strengthened CBS inequality for anisotropic non-conforming FEM systems

Preconditioners based on various multilevel extensions of two-level finite element methods (FEM) lead to iterative methods which have an optimal order computational complexity with respect to the size of the system. Such methods were first presented in Axelsson and Padiy (SIAM. J. Sci. Stat. Cony). 1990; 20:1807) and Axelsson and Vassilevski (Numer. Math. 1989-, 56:157), and are based on (recursive) two-level splittings of the finite element space. The key role in the derivation of optimal convergence rate estimates is played by the constant in the so-called Cauchy-Bunyakowski-Schwarz (CBS) inequality, associated with the angle between the two subspaces of the splitting. It turns out that only existence of uniform estimates for this constant gamma is not enough but accurate quantitative bounds for gamma have to be found as well. More precisely, the value of the upper bound for gamma is an element of (0, 1) is part of the construction of various multilevel extensions of the related two-level methods. In this paper, an algebraic two-level preconditioning algorithm for second-order elliptic boundary value problems is constructed, where the discretization is done using Crouzeix-Raviart non-conforming linear finite elements on triangles. An important point to make is that in this case the finite element spaces corresponding to two successive levels of mesh refinements are not nested. To handle this, a proper two-level basis is considered, which enables us to fit the general framework for the construction of two-level preconditioners for conforming finite elements and to generalize the method to the multilevel case. The major contribution of this paper is the derived estimates of the related constant gamma in the strengthened CBS inequality. These estimates are uniform with respect to both coefficient and mesh anisotropy. To our knowledge, the results presented in the paper are the first such estimates for non-conforming FEM systems. Copyright (C) 2004 John Wiley Sons, Ltd.