An Efficient Approximate Residual Evaluation in the Adaptive Tensor Product Wavelet Method
- PDF / 585,379 Bytes
- 25 Pages / 439.37 x 666.142 pts Page_size
- 57 Downloads / 196 Views
An Efficient Approximate Residual Evaluation in the Adaptive Tensor Product Wavelet Method Sebastian Kestler · Rob Stevenson
Received: 1 August 2012 / Revised: 23 February 2013 / Accepted: 30 March 2013 © Springer Science+Business Media New York 2013
Abstract A wide class of well-posed operator equations can be solved in optimal computational complexity by adaptive wavelet methods. A quantitative bottleneck is the approximate evaluation of the arising residuals that steer the adaptive refinements. In this paper, we consider multi-tree approximations from tensor product wavelet bases for solving linear PDE’s. In this setting, we develop a new efficient approximate residual evaluation. Other than the commonly applied method, that uses the so-called APPLY routine, our approximate residual depends affinely on the current approximation of the solution. Our findings are illustrated by numerical results that show a considerable speed-up. Keywords Adaptive wavelet method · Multi-tree tensor product approximation · Optimal computational complexity Mathematics Subject Classification (2000)
41A30 · 41A63 · 65N30 · 65Y20
S.K. was supported by the Deutsche Forschungsgemeinschaft within the Research Training Group (Graduiertenkolleg) GrK 1100 Modellierung, Analyse und Simulation in der Wirtschaftsmathematik at the University of Ulm. S. Kestler (B) Institute for Numerical Mathematics, University of Ulm, Helmholtzstrasse 20, 89069 Ulm, Germany e-mail: [email protected] R. Stevenson Korteweg-de Vries Institute for Mathematics, University of Amsterdam, P.O. Box 94248, 1090 GE Amsterdam, The Netherlands e-mail: [email protected]
123
J Sci Comput
1 Introduction: Adaptive Wavelet Galerkin Methods For some countable set ∇, f ∈ 2 (∇), and an A ∈ L(2 (∇), 2 (∇)) that is symmetric and coercive, i.e., Av, v2 (∇) v22 (∇) (v ∈ 2 (∇)), consider the problem of finding the solution u ∈ 2 (∇) of Au = f. Such a problem arises from the equivalent formulation of an elliptic operator equation as a well-posed bi-infinite matrix-vector problem. Indeed, for some real Hilbert space H , let A ∈ L(H, H ) be such that (Av)(v) v2H (v ∈ H ), let f ∈ H , and let = {ψλ : λ ∈ ∇} be a Riesz basis for H , where we have in mind to be a wavelet basis. Then Au = f is equivalently formulated as Au = f, where A = (A)(), u = u and f = f (). Recall that being a Riesz basis for H means that H → 2 (∇) : g → [g(ψλ )]λ∈∇ , or equivalently, its adjoint 2 (∇) → H : v → v , is boundedly invertible. The (idealized) adaptive wavelet-Galerkin method for solving Au = f reads as follows. , f := R f, For ⊂ ∇, let I ∈ L(2 (), 2 (∇)) be the extension with zeros, R := I and A := R AI . Let μ ∈ (0, 1) be some constant, and 0 ⊂ ∇. for k = 0, 1, . . . do solve Ak uk = fk find the smallest k+1 ⊃ k such that Rk+1 (f − AIk uk )2 (k+1 ) ≥ μf − AIk uk 2 (∇) enddo This algorithm, with an additional recurrent coarsening step, was introduced in [9], where in [17] it was demonstrated that this coarsening
Data Loading...
