Abstract
The numerical solution of linear stationary variational problems involving elliptic partial differential operators usually requires iterative solvers on account of their problem size. Our guiding principle is to devise theoretically and practically efficient iterative solution schemes which are optimal in the number of arithmetic operations, i.e., of linear complexity in the total number of unknowns. For these algorithms, asymptotically optimal preconditioners are indispensable. This article collects the main ingredients for multilevel preconditioners based on wavelets for certain systems of elliptic PDEs with smooth solutions. Specifically, we consider problems from optimal control with distributed or Dirichlet boundary control constrained by elliptic PDEs. Moreover, the wavelet characterization of function space norms will also be used in modelling the control functional, thereby extending the range of applicability over conventional methods. The wavelet preconditioners are optimized for these PDE systems to exhibit small absolute condition numbers and consequently entail absolute low iteration numbers, as numerical experiments show.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
- Conjugate Gradient
- Saddle Point Problem
- Biorthogonal Wavelet
- Essential Boundary Condition
- Cancellation Property
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
I. Babuška, The finite element method with Lagrange multipliers, Numer. Math. 20 (1973), 179–192.
D. Braess, Finite Elements: Theory, Fast Solvers and Applications in Solid Mechanics, 2nd ed., Cambridge University Press, Cambridge, 2001.
D. Braess, W. Hackbusch, A new convergence proof for the multigrid method including the V-cycle, SIAM J. Numer. Anal. 20 (1983), 967–975.
J.H. Bramble, J.E. Pasciak, J. Xu, Parallel multilevel preconditioners, Math. Comp. 55 (1990), 1–22.
F. Brezzi, M. Fortin, Mixed and Hybrid Finite Element Methods, Springer, 1991.
C. Burstedde, Fast Optimised Wavelet Methods for Control Problems Constrained by Elliptic PDEs, PhD Dissertation, Mathematisch-Naturwissenschaftliche Fakultät, Universität Bonn, Germany, 2005.
C. Burstedde, On the numerical evaluation of fractional Sobolev norms, Comm. Pure Appl. Anal. 6(3) (2007), 587–605.
C. Burstedde, A. Kunoth, Fast iterative solution of elliptic control problems in wavelet discretizations, J. Comp. Appl. Math. 196(1) (2006), 299–319.
C. Canuto, A. Tabacco, K. Urban, The wavelet element method, part I: Construction and analysis, Appl. Comput. Harm. Anal. 6 (1999), 1–52.
J.M. Carnicer, W. Dahmen, J.M. Peña, Local decomposition of refinable spaces, Appl. Comp. Harm. Anal. 3 (1996), 127–153.
Z. Ciesielski, T. Figiel, Spline bases in classical function spaces on compact C ∞ manifolds: Part I and II, Studia Mathematica (1983), 1–58 and 95–136.
A. Cohen, Numerical Analysis of Wavelet Methods, Studies in Mathematics and its Applications 32, Elsevier, 2003.
A. Cohen, I. Daubechies, J.-C. Feauveau, Biorthogonal bases of compactly supported wavelets, Comm. Pure Appl. Math. 45 (1992), 485–560.
S. Dahlke, W. Dahmen, K. Urban, Adaptive wavelet methods for saddle point problems — Optimal convergence rates, SIAM J. Numer. Anal. 40 (2002), 1230–1262.
W. Dahmen, Stability of multiscale transformations, J. Four. Anal. Appl. 2 (1996), 341–361.
W. Dahmen, Wavelet and multiscale methods for operator equations, Acta Numerica (1997), 55–228.
W. Dahmen, Wavelet methods for PDEs – Some recent developments, J. Comput. Appl. Math. 128 (2001), 133–185.
W. Dahmen, Multiscale and wavelet methods for operator equations, in: Multiscale Problems and Methods in Numerical Simulation, C. Canuto (ed.), C.I.M.E. Lecture Notes in Mathematics 1825, Springer Heidelberg (2003), 31–96.
W. Dahmen, A. Kunoth, Multilevel preconditioning, Numer. Math. 63 (1992), 315–344.
W. Dahmen, A. Kunoth, Appending boundary conditions by Lagrange multipliers: Analysis of the LBB condition, Numer. Math. 88 (2001), 9–42.
W. Dahmen, A. Kunoth, Adaptive wavelet methods for linear–quadratic elliptic control problems: Convergence Rates, SIAM J. Contr. Optim. 43(5) (2005), 1640–1675.
W. Dahmen, A. Kunoth, R. Schneider, Wavelet least squares methods for boundary value problems, SIAM J. Numer. Anal. 39 (2002), 1985–2013.
W. Dahmen, A. Kunoth, K. Urban, Biorthogonal spline wavelets on the interval – Stability and moment conditions, Appl. Comput. Harm. Anal. 6 (1999), 132–196.
W. Dahmen, R. Schneider, Wavelets with complementary boundary conditions — Function spaces on the cube, Results in Mathematics 34 (1998), 255–293.
W. Dahmen, R. Schneider, Composite wavelet bases for operator equations, Math. Comp. 68 (1999), 1533–1567.
W. Dahmen, R. Schneider, Wavelets on manifolds I: Construction and domain decomposition, SIAM J. Math. Anal. 31 (1999), 184–230.
W. Dahmen, R. Stevenson, Element–by–element construction of wavelets satisfying stability and moment conditions, SIAM J. Numer. Anal. 37 (1999), 319–325.
I. Daubechies, Orthonormal bases of compactly supported wavelets, Comm. Pure Appl. Math. 41 (1988), 909–996.
P. Grisvard, Elliptic Problems in Nonsmooth Domains, Pitman, 1985.
S. Jaffard, Wavelet methods for fast resolution of elliptic problems, Siam J. Numer. Anal. 29 (1992), 965–986.
P. Kantartzis, A. Kunoth, A wavelet approach for a problem in electrical impedance tomography formulated by means of a domain embedding method, Manuscript, in preparation.
J. Krumsdorf, Finite Element Wavelets for the Numerical Solution of Elliptic Partial Differential Equations on Polygonal Domains, Diploma Thesis, Universität Bonn, 2004.
A. Kunoth, Wavelet Methods — Elliptic Boundary Value Problems and Control Problems, Advances in Numerical Mathematics, Teubner, 2001.
A. Kunoth, Wavelet techniques for the fictitious domain—Lagrange multiplier approach, Numer. Algor. 27 (2001), 291–316.
A. Kunoth, Fast iterative solution of saddle point problems in optimal control based on wavelets, Comput. Optim. Appl. 22 (2002), 225–259.
A. Kunoth, Adaptive wavelet schemes for an elliptic control problem with Dirichlet boundary control, Numer. Algor. 39(1-3) (2005), 199–220.
A. Kunoth, J. Sahner, Wavelets on manifolds: An optimized construction, Math. Comp. 75 (2006), 1319–1349.
J.L. Lions, Optimal Control of Systems Governed by Partial Differential Equations, Springer, Berlin, 1971.
J. Maes, A. Bultheel, A hierarchical basis preconditioner for the biharmonic equation on the sphere, IMA J. Numer. Anal. 26(3) (2006), 563–583.
J. Maes, A. Kunoth, A. Bultheel, BPX-type preconditioners for 2nd and 4th order elliptic problems on the sphere, SIAM J. Numer. Anal. 45(1) (2007), 206–222.
P. Oswald, On discrete norm estimates related to multilevel preconditioners in the finite element method, in: Constructive Theory of Functions, K.G. Ivanov, P. Petrushev, B. Sendov, (eds.), Proc. Int. Conf. Varna 1991, Bulg. Acad. Sci., Sofia (1992), 203–214.
R. Pabel, Wavelet Methods for PDE Constrained Elliptic Control Problems with Dirichlet Boundary Control, Diploma Thesis, Universität Bonn, 2006. doi: 10.2370/236_232
R. Stevenson, Locally supported, piecewise polynomial biorthogonal wavelets on non-uniform meshes, Constr. Approx. 19 (2003), 477–508.
K. Urban, Wavelet Methods for Elliptic Partial Differential Equations, Oxford University Press, 2009.
J. Xu, Theory of multilevel methods, Report AM 48, Department of Mathematics, Pennsylvania State University, 1989.
J. Xu, Iterative methods by space decomposition and subspace correction, SIAM Review 34(4) (1992), 581–613.
H. Yserentant, On the multilevel splitting of finite element spaces, Numer. Math. 49 (1986), 379–412.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kunoth, A. (2009). Optimized wavelet preconditioning. In: DeVore, R., Kunoth, A. (eds) Multiscale, Nonlinear and Adaptive Approximation. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-03413-8_10
Download citation
DOI: https://doi.org/10.1007/978-3-642-03413-8_10
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-03412-1
Online ISBN: 978-3-642-03413-8
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)