Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Adaptive methods for boundary integral equations: Complexity and convergence estimates

Authors: Wolfgang Dahmen, Helmut Harbrecht and Reinhold Schneider
Journal: Math. Comp. 76 (2007), 1243-1274
MSC (2000): Primary 47A20, 65F10, 65N38, 65R20, 41A55, 41A25
Published electronically: February 21, 2007
MathSciNet review: 2299773
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. A. Barinka, Fast computation tools for adaptive wavelet methods, Doctoral Dissertation, RWTH Aachen, 2005.
  • 2. G. Beylkin, R. R. Coifman, V. Rokhlin, Fast wavelet transforms and numerical algorithms I, Comm. Pure and Appl. Math., 44 (1991), 141-183. MR 1085827 (92c:65061)
  • 3. P. Binev and R. DeVore, Fast computation in adaptive tree approximation, Num. Math. 97 (2004), 193-217. MR 2050076 (2005e:65223)
  • 4. A. Canuto, A. Tabacco, K. Urban, The wavelet element method, part I: Construction and analysis, Appl. Comp. Harm. Anal., 6(1999), 1-52. MR 1664902 (99k:42055)
  • 5. A. Canuto, A. Tabacco, K. Urban, The wavelet element method, part II: Realization and additional features, Appl. Comp. Harm. Anal. 8 (2000), 123-165. MR 1743533 (2001e:42044)
  • 6. A. Cohen, W. Dahmen, R. DeVore, Adaptive wavelet methods for elliptic operator equations: Convergence rates, Math. Comp. 70 (2001), 27-75. MR 1803124 (2002h:65201)
  • 7. A. Cohen, W. Dahmen, R. DeVore, Adaptive wavelet methods II: Beyond the elliptic case, Foundations of Computational Mathematics, 2 (2002), 203-245. MR 1907380 (2003f:65212)
  • 8. A. Cohen, W. Dahmen, R. DeVore, Adaptive Wavelet Schemes for Nonlinear Variational Problems, SIAM J. Numer. Anal., (5) 41 (2003), 1785-1823. MR 2035007 (2005a:65055)
  • 9. A. Cohen, W. Dahmen, R. DeVore, Sparse evaluation of compositions of functions using multiscale expansions, SIAM J. Math. Anal., 35 (2003), 279-303. MR 2001102 (2004f:41036)
  • 10. Cohen, A., W. Dahmen, I. Daubechies and R. DeVore (2001) Tree-structured approximation and optimal encoding, App. Comp. Harm. Anal. 11, 192-226. MR 1848303 (2002g:42048)
  • 11. A. Cohen, R. Masson, Wavelet adaptive method for second order elliptic problems: boundary conditions and domain decomposition, Numer. Math., 86 (2000), 193-238. MR 1777487 (2001j:65185)
  • 12. S. Dahlke, W. Dahmen, R. DeVore, Nonlinear approximation and adaptive techniques for solving elliptic operator equations, in: Multiscale Wavelet Methods for PDEs, W. Dahmen, A. Kurdila, P. Oswald (eds.), Academic Press, London, 237-283, 1997. MR 1475001 (99a:65001)
  • 13. S. Dahlke, W. Dahmen, K. Urban, Adaptive wavelet methods for saddle point problems - optimal convergence rates, SIAM J. Numer. Anal., 40 (No. 4) (2002), 1230-1262. MR 1951893 (2004g:42039)
  • 14. W. Dahmen, Wavelet and Multiscale Methods for Operator Equations, (invited contribution) Acta Numerica, Cambridge University Press, 6 (1997), 55-228. MR 1489256 (98m:65102)
  • 15. W. Dahmen, H. Harbrecht, R. Schneider, Compression Techniques for Boundary Integral Equations - Asymptotically Optimal Complexity Estimates, SIAM J. Numer. Anal., 43:2251-2271 (2006). MR 2206435 (2006j:65377)
  • 16. W. Dahmen, S. Prößdorf, R. Schneider, Multiscale methods for pseudo-differential equations on smooth manifolds, in: Proceedings of the International Conference on Wavelets: Theory, Algorithms, and Applications, C.K. Chui, L. Montefusco, L. Puccio (eds.), Academic Press, 1994, 385-424. MR 1321437 (96c:65208)
  • 17. W. Dahmen and R. Schneider, Composite wavelet bases for operator equations, Math. Comp., 68 (1999), 1533-1567. MR 1648379 (99m:65122)
  • 18. DeVore, R. (1998) Nonlinear approximation, Acta Numerica 7, 51-150. MR 1689432 (2001a:41034)
  • 19. B. Faermann, Localization of the Aronszajn-Slobodeckij norm and application to adaptive boundary element methods, Part II. The three-dimensional case, Numer. Math., 92(3) (2002), 467-499. MR 1930387 (2003i:65120)
  • 20. T. Gantumur, H. Harbrecht, R. Stevenson, An optimal adaptive wavelet method for elliptic equations without coarsening. Math. Comp., 76 (2007), 615-629.
  • 21. T. Gantumur and R. Stevenson, Computation of singular integral operators in wavelet coordinates. Computing, 76 (2006), 77-107. MR 2174673 (2006e:65051)
  • 22. L. Greengard and V. Rokhlin, A fast algorithm for particle simulation, J. Comput. Phys., 73 (1987), 325-348. MR 918448 (88k:82007)
  • 23. W. Hackbusch, A sparse matrix arithmetic based on $ \mathcal{H}$-matrices. Part I: Introduction to $ \mathcal{H}$-matrices, Computing, 64 (1999), 89-108. MR 1694265 (2000c:65039)
  • 24. W. Hackbusch and Z.P. Nowak, On the fast matrix multiplication in the boundary element method by panel clustering, Numer. Math., 54 (1989), 463-491. MR 972420 (89k:65162)
  • 25. H. Harbrecht, Wavelet Galerkin schemes for the boundary element method in three dimensions, Ph.D. Thesis, Technische Universität Chemnitz, Germany, 2001.
  • 26. H. Harbrecht, R. Schneider, Wavelet Galerkin schemes for boundary integral equations - implementation and quadrature, SIAM J. Sci. Comput., 27 (2006), 1347-1370. MR 2199752 (2006j:65379)
  • 27. T. von Petersdorff, C. Schwab, Wavelet approximation for first kind integral equations on polygons, Numer. Math., 74 (1996), 479-519. MR 1414419 (97m:65223)
  • 28. T. von Petersdorff, C. Schwab, Fully discrete multiscale Galerkin BEM, in: Multiscale Wavelet Methods for PDEs, W. Dahmen, A. Kurdila, P. Oswald (eds.), Academic Press, San Diego, 1997, 287-346. MR 1475002 (99a:65158)
  • 29. S. Sauter, Über die effiziente Verwendung des Galerkin Verfahrens zur Lösung Fredholmscher Integralgleichungen. Ph.D. Thesis, Christian-Albrecht-Universität Kiel, Germany, 1992.
  • 30. S. Sauter and C. Schwab. Quadrature for the $ hp$-Galerkin BEM in $ \mathbb{R}^3$. Numer. Math., 78 1997, 211-258. MR 1485998 (99f:65207)
  • 31. S. Sauter, C. Schwab, Randelementmethoden: Analyse, Numerik und Implementierung schneller Algorithmen, B.G. Teubner, Stuttgart, 2005.
  • 32. 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.
  • 33. R. Schneider, Multiskalen- und Wavelet-Matrixkompression: Analysisbasierte Methoden zur effizienten Lösung großer vollbesetzter Gleichungssysteme, B.G. Teubner, Stuttgart, 1998. MR 1623209 (99f:65067)
  • 34. R. Stevenson, On the compressibility of operators in wavelet coordinates, SIAM J. Math. Anal. 35(5) (2004), 1110-1132. MR 2050194 (2005e:42128)
  • 35. 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.
  • 36. G. Verchota, Layer potentials and regularity for the Dirichlet problem for Laplace's equation in Lipschitz domains, J. Funct. Anal., 59 (1984), 572-611. MR 0769382 (86e:35038)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 47A20, 65F10, 65N38, 65R20, 41A55, 41A25

Retrieve articles in all journals with MSC (2000): 47A20, 65F10, 65N38, 65R20, 41A55, 41A25

Additional Information

Wolfgang Dahmen
Affiliation: Institut für Geometrie und Praktische Mathematik, RWTH Aachen, Templergraben 55, 52056 Aachen, Germany

Helmut Harbrecht
Affiliation: Lehrstuhl für Scientific Computing, Christian-Albrechts-Platz 4, D-24098 Kiel, Germany

Reinhold Schneider
Affiliation: Lehrstuhl für Scientific Computing, Christian-Albrechts-Platz 4, D-24098 Kiel, Germany

Keywords: Boundary integral equations, adaptive wavelet scheme, best $N$-term approximation, compressible matrices, adaptive hp-quadrature, complexity and convergence estimates.
Received by editor(s): March 24, 2005
Received by editor(s) in revised form: April 1, 2006
Published electronically: February 21, 2007
Additional Notes: This research was supported in part by the EEC Human Potential Programme under contract HPRN-CT-2002-00286, “Breaking Complexity”, and the SFB 401, “Flow Modulation and Fluid-Structure Interaction at Airplane Wings”, and by the Leibniz program funded by the German Research Foundation
Article copyright: © Copyright 2007 American Mathematical Society

American Mathematical Society