×

An adaptive wavelet method for solving high-dimensional elliptic PDEs. (English) Zbl 1205.65313

Let \(\Omega=(0,1)^n\), and let \(\Gamma_D\) be the union of one or more \((n-1)\)-dimensional faces of \(\partial \Omega\). For given \(f \in (H_{0,\Gamma_D}^1(\Omega))'\), the authors study the numerical solution of the problem of finding \(u \in H_{0,\Gamma_D}^1(\Omega)\) such that
\[ a(u,v):= \int_{\Omega} c_0 uv + \sum_{m=1}^n c_m \partial_m u \; \partial_m v = f(v), \quad v \in (H_{0,\Gamma_D}^1(\Omega))', \]
where \(c_0 \geq 0\) and \(c_m>0\), \(m=1, \ldots , n\), are constants.
The authors apply a tensor product basis \(\{\psi_{\lambda}: \lambda \in \nabla \}\) constructed by a univariate \(L^2(0,1)\)-orthonormal piecewise polynomial wavelet basis. In this case, the condition number of the stiffness matrix \(\kappa({A})\) is bounded uniformly in \(n\), and \(c_0\) and \(c_m\), \(m=1, \dots , n\). Moreover, \({A}\) is close to a sparse matrix.
The authors are interested in solutions \(u\) from the span of \(\{ \psi_{\lambda}: \lambda \in \Lambda_N \}\), where \(\Lambda_N\) is any subset with \(\#\Lambda_N=N\). They give a detailed description of an adaptive wavelet algorithm for which the resulting approximations converge in energy norm with the same rate as the best approximations from the span of the best \(N\) tensor product wavelets. Moreover, the cost for producing these approximations will be proportional to their length with a constant factor that grows only linearly with \(N\).

MSC:

65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
46B28 Spaces of operators; tensor products; approximation properties
65T60 Numerical methods for wavelets
35J25 Boundary value problems for second-order elliptic equations
65F35 Numerical computation of matrix norms, conditioning, scaling
65Y20 Complexity and performance of numerical algorithms
65N12 Stability and convergence of numerical methods for boundary value problems involving PDEs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Barinka, A.: Fast evaluation tools for adaptive wavelet schemes. PhD thesis, RTWH Aachen, March 2005
[2] Bungartz, H.J., Griebel, M.: Sparse grids. Acta Numer. 13, 147–269 (2004) · Zbl 1118.65388 · doi:10.1017/S0962492904000182
[3] Cohen, A.: Numerical Analysis of Wavelet Methods. Elsevier, Amsterdam (2003) · Zbl 1038.65151
[4] Cohen, A., Dahmen, W., DeVore, R.: Adaptive wavelet methods for elliptic operator equations–convergence rates. Math. Comput. 70, 27–75 (2001) · Zbl 0980.65130
[5] Cohen, A., Dahmen, W., DeVore, R.: Adaptive wavelet methods II–Beyond the elliptic case. Found. Comput. Math. 2(3), 203–245 (2002) · Zbl 1025.65056 · doi:10.1007/s102080010027
[6] Dahmen, W., Harbrecht, H., Schneider, R.: Compression techniques for boundary integral equations–optimal complexity estimates. SIAM J. Numer. Anal. 43(6), 2251–2271 (2006) · Zbl 1113.65114 · doi:10.1137/S0036142903428852
[7] Daubechies, I.: Orthonormal bases of compactly supported wavelets. Commun. Pure Appl. Math. 41, 909–996 (1988) · Zbl 0644.42026 · doi:10.1002/cpa.3160410705
[8] Dauge, M.: Elliptic Boundary Value Problems on Corner Domain, Smoothness and Asymptotics of Solutions. Lecture Notes in Mathematics, vol. 1341. Springer, Berlin (1988) · Zbl 0668.35001
[9] DeVore, R.: Nonlinear approximation. Acta Numer. 7, 51–150 (1998) · Zbl 0931.65007 · doi:10.1017/S0962492900002816
[10] Dijkema, T.J.: Adaptive tensor product wavelet methods for solving PDEs. PhD thesis, Utrecht University (June 2009) · Zbl 1205.65313
[11] Donovan, G.C., Geronimo, J.S., Hardin, D.P.: Intertwining multiresolution analyses and the construction of piecewise-polynomial wavelets. SIAM J. Math. Anal. 27(6), 1791–1815 (1996) · Zbl 0857.42023 · doi:10.1137/S0036141094276160
[12] Donovan, G.C., Geronimo, J.S., Hardin, D.P.: Orthogonal polynomials and the construction of piecewise polynomial smooth wavelets. SIAM J. Math. Anal. 30(5), 1029–1056 (1999) · Zbl 0932.42021 · doi:10.1137/S0036141096313112
[13] Feynman, A.R., Hibbs, A.R.: Quantum Mechanics and Path Integrals. McGraw-Hill, New York (1965) · Zbl 0176.54902
[14] Freidlin, M.: Functional Integration and Partial Differential Equations. Annals of Mathematics Studies, vol. 109. Princeton University Press, Princeton (1985) · Zbl 0568.60057
[15] Gantumur, T., Stevenson, R.P.: Computation of differential operators in wavelet coordinates. Math. Comput. 75, 697–709 (2006) · Zbl 1158.65355
[16] Gantumur, T., Harbrecht, H., Stevenson, R.P.: An optimal adaptive wavelet method without coarsening of the iterands. Math. Comput. 76, 615–629 (2007) · Zbl 1115.41023 · doi:10.1090/S0025-5718-06-01917-X
[17] Gavrilyuk, I.P., Hackbusch, W., Khoromskij, B.N.: Hierarchical tensor-product approximation to the inverse and related operators for high-dimensional elliptic problems. Computing 74(2), 131–157 (2005) · Zbl 1071.65032 · doi:10.1007/s00607-004-0086-y
[18] Grasedyck, L.: Existence and computation of low Kronecker-rank approximations for large linear systems of tensor product structure. Computing 72(3–4), 247–265 (2004) · Zbl 1058.65036 · doi:10.1007/s00607-003-0037-z
[19] Greengard, L., Rokhlin, V.: A fast algorithm for particle simulation. J. Comput. Phys. 73, 325–348 (1987) · Zbl 0629.65005 · doi:10.1016/0021-9991(87)90140-9
[20] Griebel, M., Knapek, S.: Optimized tensor-product approximation spaces. Constr. Approx. 16(4), 525–540 (2000) · Zbl 0969.65107 · doi:10.1007/s003650010010
[21] Griebel, M., Oswald, P.: Tensor product type subspace splittings and multilevel iterative methods for anisotropic problems. Adv. Comput. Math. 4(1–2), 171–206 (1995) · Zbl 0826.65099 · doi:10.1007/BF02123478
[22] Hackbusch, W.: Iterative Solution of Large Sparse Systems of Equations. Applied Mathematical Sciences, vol. 95. Springer, New York (1994) · Zbl 0789.65017
[23] Hoang, V.H., Schwab, Ch.: High-dimensional finite elements for elliptic problems with multiple scales. SIAM J. Multiscale Model. Simul. 3(1), 168–194 (2005) · Zbl 1074.65135 · doi:10.1137/030601077
[24] Metselaar, A.: Handling wavelet expansions in numerical methods. PhD thesis, University of Twente (2002)
[25] Nitsche, P.-A.: Sparse approximation of singularity functions. Constr. Approx. 21(1), 63–81 (2005) · Zbl 1073.65118
[26] Nitsche, P.-A.: Best N-term approximation spaces for tensor product wavelet bases. Constr. Approx. 24(1), 49–70 (2006) · Zbl 1101.41021 · doi:10.1007/s00365-005-0609-6
[27] Schwab, Ch., Stevenson, R.P.: Adaptive wavelet algorithms for elliptic PDEs on product domains. Math. Comput. 77, 71–92 (2008) · Zbl 1127.41009 · doi:10.1090/S0025-5718-07-02019-4
[28] Todor, R.A., Schwab, Ch.: Convergence rates for sparse chaos approximations of elliptic problems with stochastic coefficients. IMA J. Numer. Anal. 27(2), 232–261 (2007) · Zbl 1120.65004 · doi:10.1093/imanum/drl025
[29] Yserentant, H.: Sparse grid spaces for the numerical solution of the electronic Schrödinger equation. Numer. Math. 101(2), 381–389 (2005) · Zbl 1084.65125 · doi:10.1007/s00211-005-0581-x
[30] Zenger, Ch.: Sparse grids. In: Parallel Algorithms for Partial Differential Equations, Kiel, 1990. Notes Numer. Fluid Mech., vol. 31, pp. 241–251. Vieweg, Braunschweig (1991)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.