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 Free Access

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 and a nested sequence of subspaces , we construct operators which are spectrally equivalent to those of the form . Here , , are positive numbers and is the orthogonal projector onto with . We first present abstract results which show when is spectrally equivalent to a similarly constructed operator defined in terms of an approximation of , for . 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 can be preconditioned uniformly independently of the parameter . 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.

**1.**James H. Bramble and Joseph E. Pasciak,*New estimates for multilevel algorithms including the 𝑉-cycle*, Math. Comp.**60**(1993), no. 202, 447–471. MR**1176705**, 10.1090/S0025-5718-1993-1176705-9**2.**James H. Bramble, Zbigniew Leyk, and Joseph E. Pasciak,*Iterative schemes for nonsymmetric and indefinite elliptic boundary value problems*, Math. Comp.**60**(1993), no. 201, 1–22. MR**1146834**, 10.1090/S0025-5718-1993-1146834-4**3.**James H. Bramble, Joseph E. Pasciak, and Jinchao Xu,*Parallel multilevel preconditioners*, Math. Comp.**55**(1990), no. 191, 1–22. MR**1023042**, 10.1090/S0025-5718-1990-1023042-6**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 decomposition of refinable spaces and wavelets*, Appl. Comput. Harmon. Anal.**3**(1996), no. 2, 127–153. MR**1385049**, 10.1006/acha.1996.0012**6.**Philippe G. Ciarlet,*The finite element method for elliptic problems*, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1978. Studies in Mathematics and its Applications, Vol. 4. MR**0520174****7.**Xavier Saint Raymond,*Non-unicité pour certains problèmes de Cauchy complexes non linéaires du premier ordre*, C. R. Acad. Sci. Paris Sér. I Math.**299**(1984), no. 18, 927–930 (French, with English summary). MR**774670****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), no. 3, 173–193. MR**1296981****9.**Uwe Kotyczka and Peter Oswald,*Piecewise linear prewavelets of small support*, Approximation theory VIII, Vol. 2 (College Station, TX, 1995) Ser. Approx. Decompos., vol. 6, World Sci. Publ., River Edge, NJ, 1995, pp. 235–242. MR**1471789****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.**Frank Natterer,*Error bounds for Tikhonov regularization in Hilbert scales*, Applicable Anal.**18**(1984), no. 1-2, 29–37. MR**762862**, 10.1080/00036818408839508**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.**Peter Oswald,*Multilevel finite element approximation*, Teubner Skripten zur Numerik. [Teubner Scripts on Numerical Mathematics], B. G. Teubner, Stuttgart, 1994. Theory and applications. MR**1312165****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.**Panayot S. Vassilevski and Junping Wang,*Stabilizing the hierarchical basis by approximate wavelets. I. Theory*, Numer. Linear Algebra Appl.**4**(1997), no. 2, 103–126. MR**1443598**, 10.1002/(SICI)1099-1506(199703/04)4:2<103::AID-NLA101>3.0.CO;2-J**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.

Retrieve articles in *Mathematics of Computation of the American Mathematical Society*
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

Email:
bramble@math.tamu.edu

**Joseph E. Pasciak**

Email:
pasciak@math.tamu.edu

**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.

Email:
panayot@iscbg.acad.bg, panayot@llnl.gov

DOI:
http://dx.doi.org/10.1090/S0025-5718-99-01106-0

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