Adaptive methods for boundary integral equations: Complexity and convergence estimates

Dahmen, Wolfgang; Harbrecht, Helmut; Schneider, Reinhold

doi:10.1090/S0025-5718-07-01970-9

Adaptive methods for boundary integral equations: Complexity and convergence estimates
HTML articles powered by AMS MathViewer

by Wolfgang Dahmen, Helmut Harbrecht and Reinhold Schneider PDF

Math. Comp. 76 (2007), 1243-1274 Request permission

Abstract:

This paper is concerned with developing numerical techniques for the adaptive application of global operators of potential type in wavelet coordinates. This is a core ingredient for a new type of adaptive solvers that has so far been explored primarily for PDEs. We shall show how to realize asymptotically optimal complexity in the present context of global operators. “Asymptotically optimal” means here that any target accuracy can be achieved at a computational expense that stays proportional to the number of degrees of freedom (within the setting determined by an underlying wavelet basis) that would ideally be necessary for realizing that target accuracy if full knowledge about the unknown solution were given. The theoretical findings are supported and quantified by the first numerical experiments.

References

A. Barinka, Fast computation tools for adaptive wavelet methods, Doctoral Dissertation, RWTH Aachen, 2005.
G. Beylkin, R. Coifman, and V. Rokhlin, Fast wavelet transforms and numerical algorithms. I, Comm. Pure Appl. Math. 44 (1991), no. 2, 141–183. MR 1085827, DOI 10.1002/cpa.3160440202
Peter Binev and Ronald DeVore, Fast computation in adaptive tree approximation, Numer. Math. 97 (2004), no. 2, 193–217. MR 2050076, DOI 10.1007/s00211-003-0493-6
Claudio Canuto, Anita Tabacco, and Karsten Urban, The wavelet element method. I. Construction and analysis, Appl. Comput. Harmon. Anal. 6 (1999), no. 1, 1–52. MR 1664902, DOI 10.1006/acha.1997.0242
Claudio Canuto, Anita Tabacco, and Karsten Urban, The wavelet element method. II. Realization and additional features in 2D and 3D, Appl. Comput. Harmon. Anal. 8 (2000), no. 2, 123–165. MR 1743533, DOI 10.1006/acha.2000.0282
Albert Cohen, Wolfgang Dahmen, and Ronald DeVore, Adaptive wavelet methods for elliptic operator equations: convergence rates, Math. Comp. 70 (2001), no. 233, 27–75. MR 1803124, DOI 10.1090/S0025-5718-00-01252-7
A. Cohen, W. Dahmen, and R. DeVore, Adaptive wavelet methods. II. Beyond the elliptic case, Found. Comput. Math. 2 (2002), no. 3, 203–245. MR 1907380, DOI 10.1007/s102080010027
Albert Cohen, Wolfgang Dahmen, and Ronald Devore, Adaptive wavelet schemes for nonlinear variational problems, SIAM J. Numer. Anal. 41 (2003), no. 5, 1785–1823. MR 2035007, DOI 10.1137/S0036142902412269
Albert Cohen, Wolfgang Dahmen, and Ronald Devore, Sparse evaluation of compositions of functions using multiscale expansions, SIAM J. Math. Anal. 35 (2003), no. 2, 279–303. MR 2001102, DOI 10.1137/S0036141002412070
Albert Cohen, Wolfgang Dahmen, Ingrid Daubechies, and Ronald DeVore, Tree approximation and optimal encoding, Appl. Comput. Harmon. Anal. 11 (2001), no. 2, 192–226. MR 1848303, DOI 10.1006/acha.2001.0336
A. Cohen and R. Masson, Wavelet adaptive method for second order elliptic problems: boundary conditions and domain decomposition, Numer. Math. 86 (2000), no. 2, 193–238. MR 1777487, DOI 10.1007/PL00005404
Stephan Dahlke, Wolfgang Dahmen, and Ronald A. DeVore, Nonlinear approximation and adaptive techniques for solving elliptic operator equations, Multiscale wavelet methods for partial differential equations, Wavelet Anal. Appl., vol. 6, Academic Press, San Diego, CA, 1997, pp. 237–283. MR 1475001, DOI 10.1016/S1874-608X(97)80008-8
Stephan Dahlke, Wolfgang Dahmen, and Karsten Urban, Adaptive wavelet methods for saddle point problems—optimal convergence rates, SIAM J. Numer. Anal. 40 (2002), no. 4, 1230–1262. MR 1951893, DOI 10.1137/S003614290139233X
Wolfgang Dahmen, Wavelet and multiscale methods for operator equations, Acta numerica, 1997, Acta Numer., vol. 6, Cambridge Univ. Press, Cambridge, 1997, pp. 55–228. MR 1489256, DOI 10.1017/S0962492900002713
Wolfgang Dahmen, Helmut Harbrecht, and Reinhold Schneider, Compression techniques for boundary integral equations—asymptotically optimal complexity estimates, SIAM J. Numer. Anal. 43 (2006), no. 6, 2251–2271. MR 2206435, DOI 10.1137/S0036142903428852
Wolfgang Dahmen, Siegfried Prössdorf, and Reinhold Schneider, Multiscale methods for pseudo-differential equations on smooth closed manifolds, Wavelets: theory, algorithms, and applications (Taormina, 1993) Wavelet Anal. Appl., vol. 5, Academic Press, San Diego, CA, 1994, pp. 385–424. MR 1321437, DOI 10.1016/B978-0-08-052084-1.50023-5
Wolfgang Dahmen and Reinhold Schneider, Composite wavelet bases for operator equations, Math. Comp. 68 (1999), no. 228, 1533–1567. MR 1648379, DOI 10.1090/S0025-5718-99-01092-3
Ronald A. DeVore, Nonlinear approximation, Acta numerica, 1998, Acta Numer., vol. 7, Cambridge Univ. Press, Cambridge, 1998, pp. 51–150. MR 1689432, DOI 10.1017/S0962492900002816
Birgit Faermann, Localization of the Aronszajn-Slobodeckij norm and application to adaptive boundary element methods. II. The three-dimensional case, Numer. Math. 92 (2002), no. 3, 467–499. MR 1930387, DOI 10.1007/s002110100319
T. Gantumur, H. Harbrecht, R. Stevenson, An optimal adaptive wavelet method for elliptic equations without coarsening. Math. Comp., 76 (2007), 615–629.
T. Gantumur and R. P. Stevenson, Computation of singular integral operators in wavelet coordinates, Computing 76 (2006), no. 1-2, 77–107. MR 2174673, DOI 10.1007/s00607-005-0135-1
L. Greengard and V. Rokhlin, A fast algorithm for particle simulations, J. Comput. Phys. 73 (1987), no. 2, 325–348. MR 918448, DOI 10.1016/0021-9991(87)90140-9
W. Hackbusch, A sparse matrix arithmetic based on $\scr H$-matrices. I. Introduction to $\scr H$-matrices, Computing 62 (1999), no. 2, 89–108. MR 1694265, DOI 10.1007/s006070050015
W. Hackbusch and Z. P. Nowak, On the fast matrix multiplication in the boundary element method by panel clustering, Numer. Math. 54 (1989), no. 4, 463–491. MR 972420, DOI 10.1007/BF01396324
H. Harbrecht, Wavelet Galerkin schemes for the boundary element method in three dimensions, Ph.D. Thesis, Technische Universität Chemnitz, Germany, 2001.
Helmut Harbrecht and Reinhold Schneider, Wavelet Galerkin schemes for boundary integral equations—implementation and quadrature, SIAM J. Sci. Comput. 27 (2006), no. 4, 1347–1370. MR 2199752, DOI 10.1137/S1064827503429387
Tobias von Petersdorff and Christoph Schwab, Wavelet approximations for first kind boundary integral equations on polygons, Numer. Math. 74 (1996), no. 4, 479–516. MR 1414419, DOI 10.1007/s002110050226
Tobias von Petersdorff and Christoph Schwab, Fully discrete multiscale Galerkin BEM, Multiscale wavelet methods for partial differential equations, Wavelet Anal. Appl., vol. 6, Academic Press, San Diego, CA, 1997, pp. 287–346. MR 1475002, DOI 10.1016/S1874-608X(97)80009-X
S. Sauter, Über die effiziente Verwendung des Galerkin Verfahrens zur Lösung Fredholmscher Integralgleichungen. Ph.D. Thesis, Christian–Albrecht–Universität Kiel, Germany, 1992.
Stefan A. Sauter and Christoph Schwab, Quadrature for $hp$-Galerkin BEM in $\textbf {R}^3$, Numer. Math. 78 (1997), no. 2, 211–258. MR 1485998, DOI 10.1007/s002110050311
S. Sauter, C. Schwab, Randelementmethoden: Analyse, Numerik und Implementierung schneller Algorithmen, B.G. Teubner, Stuttgart, 2005.
G. Schmidlin, C. Lage, C. Schwab, Rapid solution of first kind boundary integral equations in $\mathbb {R}^3$, Research Report No. 2002-07, Seminar für Angewandte Mathematik, ETH Zürich.
Reinhold Schneider, Multiskalen- und Wavelet-Matrixkompression, Advances in Numerical Mathematics, B. G. Teubner, Stuttgart, 1998 (German, with German summary). Analysisbasierte Methoden zur effizienten Lösung großer vollbesetzter Gleichungssysteme. [Analysis-based methods for the efficient solution of large nonsparse systems of equations]. MR 1623209, DOI 10.1007/978-3-663-10851-1
Rob Stevenson, On the compressibility operators in wavelet coordinates, SIAM J. Math. Anal. 35 (2004), no. 5, 1110–1132. MR 2050194, DOI 10.1137/S0036141002411520
P. Tchamitchian, Wavelets, Functions, and Operators, in: Wavelets: Theory and Applications, G. Erlebacher, M.Y. Hussaini, and L. Jameson (eds.), ICASE/LaRC Series in Computational Science and Engineering, Oxford University Press, 1996, 83–181.
Gregory Verchota, Layer potentials and regularity for the Dirichlet problem for Laplace’s equation in Lipschitz domains, J. Funct. Anal. 59 (1984), no. 3, 572–611. MR 769382, DOI 10.1016/0022-1236(84)90066-1