Computational scales of Sobolev norms with application to preconditioning

This paper provides a framework for developing computationally efficient multilevel preconditioners and representations for Sobolev norms. Specifically, given a Hilbert space $V$ and a nested sequence of subspaces $V_1 \subset V_2 \subset \ldots \subset V$, we construct operators which are spectrally equivalent to those of the form $\mathcal{A}= \sum _k \mu _k (Q_k-Q_{k-1})$. Here $\mu _k$, $k=1,2,\ldots$, are positive numbers and $Q_k$ is the orthogonal projector onto $V_k$ with $Q_0=0$. We first present abstract results which show when $\mathcal{A}$ is spectrally equivalent to a similarly constructed operator $\widetilde{\mathcal{A}}$ defined in terms of an approximation $\widetilde Q_k$ of $Q_k$ , for $k=1,2, \ldots$ . We show that these results lead to efficient preconditioners for discretizations of differential and pseudo-differential operators of positive and negative order. These results extend to sums of operators. For example, singularly perturbed problems such as $I-\epsilon \Delta$ can be preconditioned uniformly independently of the parameter $\epsilon$. We also show how to precondition an operator which results from Tikhonov regularization of a problem with noisy data. Finally, we describe how the technique provides computationally efficient bounded discrete extensions which have applications to domain decomposition.