Optimality of multilevel preconditioning for nonconforming P1 finite elements

We prove the optimality of hierarchical and BPX-type preconditioners for finite element discretizations with nonconforming P1 finite elements. Such preconditioners were proposed about 15 years ago, and until now only suboptimal estimates of their preconditioning properties have been available. The main new tool is an improved Bernstein type inequality for an associated subdivision process generated by the prolongations which allows us to give an asymptotically optimal upper bound for the spectrum of the preconditioned systems.