Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Computational scales of Sobolev norms
with application to preconditioning

Authors: James H. Bramble, Joseph E. Pasciak and Panayot S. Vassilevski
Journal: Math. Comp. 69 (2000), 463-480
MSC (1991): Primary 65F10, 65N20, 65N30
Published electronically: May 19, 1999
MathSciNet review: 1651742
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: 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.

References [Enhancements On Off] (What's this?)

  • 1. J. H. Bramble and J. E. Pasciak New estimates for multigrid algorithms including the V-cycle Math. Comp. 60(1993),447-471. MR 94a:65064
  • 2. J.H. Bramble, Z. Leyk, and J.E. Pasciak, Iterative schemes for non-symmetric and indefinite elliptic boundary value problems, Math. Comp. 60 (1993) 1-22. MR 93d:65034
  • 3. J. H. Bramble, J. E. Pasciak and J. Xu, Parallel multilevel preconditioners, Math. Comp. 55(1990), 1-22. MR 90k:65170
  • 4. J. H. Bramble and P. S. Vassilevski, Wavelet-like extension operators in interface domain decomposition methods, (unpublished manuscript) 1997.
  • 5. J. M. Carnicer, W. Dahmen, and J. M. Peña, Local decompositions of refinable spaces and wavelets, Appl. Comp. Harm. Anal. 3(1996), 127-153. MR 97f:42050
  • 6. P.G. Ciarlet, The Finite Element Method for Elliptic Problems, North-Holland,New York, 1978. MR 58:25001
  • 7. P. Grisvard, Elliptic Problems in Nonsmooth Domains, Pitman, Boston, 1985. MR 86m:35004
  • 8. G. Haase, U. Langer, A. Meyer, and S. V. Nepomnyaschikh, Hierarchical extension operators and local multigrid methods in domain decomposition preconditioners, East-West J. Numer. Math. 2(1994), 173-193. MR 95g:65171
  • 9. U. Kotyczka and P. Oswald, Piecewise linear prewavelets of small support, in: Approximation Theory VIII, vol. 2 (wavelets and multilevel approximation), C. Chui, L.L. Schumaker, eds., World Scientific, Singapore, 1995, 235-242. MR 98e:42035
  • 10. R. Lorentz and P. Oswald, Constructing economical Riesz bases for Sobolev spaces, Proceedings of the Domain Decomposition Conference held in Bergen, Norway, June 3-8, 1996.
  • 11. F. Natterer, Error bounds for Tikhonov regularization in Hilbert scales, Appl. Anal. 18(1984), 29-37. MR 86e:65081
  • 12. S. V. Nepomnyaschikh, Optimal multilevel extension operators, Report SPC 95-3, Jan, 1995, Technische Universität Chemnitz-Zwickau, Germany.
  • 13. P. Oswald, On discrete norm estimates related to multilevel preconditioners in the finite element method, Constructive Theory of Functions, Proc. Int. Conf. Varna 1992, Bulg. Acad. Sci., Sofia, 1992, 203-214.
  • 14. P. Oswald, Multilevel Finite Element Approximation, Theory and Applications B.G. Teubner Stuttgart, Germany 1994. MR 95k:65110
  • 15. R. Stevenson, A robust hierarchical basis preconditioner on general meshes, Numer. Math. 78 (1997), 269-303. CMP 98:05
  • 16. R. Stevenson, Piecewise linear (pre-) wavelets on non-uniform meshes, Report # 9701, Department of Mathematics, University of Nijmegen, Nijmegen, The Netherlands, 1997.
  • 17. U. Tautenhahn, Error estimates for regularization methods in Hilbert scales, SIAM J. Numer. Anal. 33(1996), 2120-2130.
  • 18. P. S. Vassilevski and J. Wang, Stabilizing the hierarchical basis by approximate wavelets, I: Theory, Numer. Linear Alg. Appl. 4(1997), 103-126. MR 98c:65197
  • 19. P. S. Vassilevski and J. Wang, Stabilizing the hierarchical basis by approximate wavelets, II: Implementation and numerical experiments, SIAM J. Sci. Comput. 20 (1999), 490-514. CMP 98:17
  • 20. X. Zhang, Multi-level Additive Schwarz Methods, Courant Inst. Math. Sci., Dept. Comp. Sci. Rep. 1991.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (1991): 65F10, 65N20, 65N30

Retrieve articles in all journals with MSC (1991): 65F10, 65N20, 65N30

Additional Information

James H. Bramble
Affiliation: Department of Mathematics, Texas A & M University, College Station, Texas 77843

Joseph E. Pasciak

Panayot S. Vassilevski
Affiliation: Central Laboratory of Parallel Processing, Bulgarian Academy of Sciences, “Acad. G. Bontchev” Street, Block 25 A, 1113 Sofia, Bulgaria
Address at time of publication: Center for Applied Scientific Computing, Lawrence Livermore National Laboratory, P. O. Box 808, L-560, Livermore, CA 94551, U.S.A.

Keywords: Interpolation spaces, equivalent norms, finite elements, preconditioning
Received by editor(s): January 14, 1998
Received by editor(s) in revised form: June 23, 1998
Published electronically: May 19, 1999
Additional Notes: The first two authors were partially supported under National Science Foundation grant number DMS-9626567. The third author was partially supported by the Bulgarian Ministry for Education, Science and Technology under grant I–504, 1995.
Article copyright: © Copyright 2000 American Mathematical Society

American Mathematical Society