zbMATH — the first resource for mathematics

Computation of differential operators in wavelet coordinates. (English) Zbl 1158.65355
Summary: In Found. Comput. Math. 2, No. 3, 203–245 (2002; Zbl 1025.65056) A. Cohen, W. Dahmen and R. DeVore proposed an adaptive wavelet algorithm for solving general operator equations. Assuming that the operator defines a boundedly invertible mapping between a Hilbert space and its dual, and that a Riesz basis of wavelet type for this Hilbert space is available, the operator equation is transformed into an equivalent well-posed infinite matrix-vector system. This system is solved by an iterative method, where each application of the infinite stiffness matrix is replaced by an adaptive approximation. It was shown that if the errors of the best linear combinations from the wavelet basis with \( N\) terms are \( \mathcal{O}(N^{-s})\) for some \(s>0\), which is determined by the Besov regularity of the solution and the order of the wavelet basis, then approximations yielded by the adaptive method with \( N\) terms also have errors of \( \mathcal{O}(N^{-s})\). Moreover, their computation takes only \( \mathcal{O}(N)\) operations, provided \(s<s^*\), with \(s^*\) being a measure of how well the infinite stiffness matrix with respect to the wavelet basis can be approximated by computable sparse matrices. Under appropriate conditions on the wavelet basis, for both differential and singular integral operators and for the relevant range of \( s\), in [SIAM J. Math. Anal., 35, No. 5, 1110–1132 (2004; Zbl 1087.47012)] the second author showed that \(s^{\ast}>s\), assuming that each entry of the stiffness matrix is exactly available at unit cost.
Generally these entries have to be approximated using numerical quadrature. In this paper, restricting ourselves to differential operators, we develop a numerical integration scheme that computes these entries giving an additional error that is consistent with the approximation error, whereas in each column the average computational cost per entry is \({\mathcal O}(1)\). As a consequence, we can conclude that the adaptive wavelet algorithm has optimal computational complexity.

65T60 Numerical methods for wavelets
42C40 Nontrigonometric harmonic analysis involving wavelets and other special systems
65Y20 Complexity and performance of numerical algorithms
Full Text: DOI
[1] Victor I. Burenkov, Sobolev spaces on domains, Teubner-Texte zur Mathematik [Teubner Texts in Mathematics], vol. 137, B. G. Teubner Verlagsgesellschaft mbH, Stuttgart, 1998. · Zbl 0893.46024
[2] A. Cohen, W. Dahmen, and R. DeVore, Adaptive wavelet methods. II. Beyond the elliptic case, Found. Comput. Math. 2 (2002), no. 3, 203 – 245. · Zbl 1025.65056 · doi:10.1007/s102080010027 · doi.org
[3] Albert Cohen, Wavelet methods in numerical analysis, Handbook of numerical analysis, Vol. VII, Handb. Numer. Anal., VII, North-Holland, Amsterdam, 2000, pp. 417 – 711. · Zbl 0976.65124
[4] 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. · Zbl 0961.65106 · doi:10.1007/PL00005404 · doi.org
[5] 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. · Zbl 0949.42024 · doi:10.1006/acha.1997.0242 · doi.org
[6] Wolfgang Dahmen, Stability of multiscale transformations, J. Fourier Anal. Appl. 2 (1996), no. 4, 341 – 361. · Zbl 0919.46006
[7] Ronald A. DeVore, Nonlinear approximation, Acta numerica, 1998, Acta Numer., vol. 7, Cambridge Univ. Press, Cambridge, 1998, pp. 51 – 150. · Zbl 0931.65007 · doi:10.1017/S0962492900002816 · doi.org
[8] S. Dekel and D. Leviatan, The Bramble-Hilbert lemma for convex domains, SIAM J. Math. Anal. 35 (2004), no. 5, 1203 – 1212. · Zbl 1078.41006 · doi:10.1137/S0036141002417589 · doi.org
[9] Wolfgang Dahmen and Reinhold Schneider, Wavelets with complementary boundary conditions — function spaces on the cube, Results Math. 34 (1998), no. 3-4, 255 – 293. · Zbl 0931.46006 · doi:10.1007/BF03322055 · doi.org
[10] Wolfgang Dahmen and Reinhold Schneider, Composite wavelet bases for operator equations, Math. Comp. 68 (1999), no. 228, 1533 – 1567. · Zbl 0932.65148
[11] Wolfgang Dahmen and Reinhold Schneider, Wavelets on manifolds. I. Construction and domain decomposition, SIAM J. Math. Anal. 31 (1999), no. 1, 184 – 230. · Zbl 0955.42025 · doi:10.1137/S0036141098333451 · doi.org
[12] Wolfgang Dahmen and Rob Stevenson, Element-by-element construction of wavelets satisfying stability and moment conditions, SIAM J. Numer. Anal. 37 (1999), no. 1, 319 – 352. · Zbl 0942.65130 · doi:10.1137/S0036142997330949 · doi.org
[13] T. Gantumur and R.P. Stevenson. Computation of singular integral operators in wavelet coordinates. Computing, 76:77-107, 2006. · Zbl 1087.65120
[14] Rob Stevenson, Adaptive solution of operator equations using wavelet frames, SIAM J. Numer. Anal. 41 (2003), no. 3, 1074 – 1100. · Zbl 1057.41010 · doi:10.1137/S0036142902407988 · doi.org
[15] Rob Stevenson, On the compressibility operators in wavelet coordinates, SIAM J. Math. Anal. 35 (2004), no. 5, 1110 – 1132. · Zbl 1087.47012 · doi:10.1137/S0036141002411520 · doi.org
[16] R.P. Stevenson. Composite wavelet bases with extended stability and cancellation properties. Preprint 1304, Department of Mathematics, Utrecht University, 2004. Submitted. · Zbl 1141.46007
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.