Wave atoms and time upscaling of wave equations

algorithm complexity Courant-Friedrichs-Lewy condition numerical examples numerical implementation reflection seismology upscaled timestepping wave atoms wave equation

Mathematics Subject Classification ID

Wave equation (35L05) Spectral, collocation and related methods for initial value and initial-boundary value problems involving PDEs (65M70) Complexity and performance of numerical algorithms (65Y20)

Review text

This is by far the most voluminous paper including the longest abstract I have ever seen in Numer. Math. Additionally, for a full understanding of the paper the article [Appl. Comput. Harmon. Anal. 23, No. 3, 368--387 (2007; Zbl 1132.68068)] by the authors and the article by \textit{E.-J.\ Candès} and \textit{L.\ Demanet} [Commun. Pure Appl. Math.\ 58, No.\ 11, 1472--1528 (2005; Zbl 1078.35007)] should be visited. The paper is concerned with the numerical solution of the wave equation \[ p_{tt}-c^2(x)\Delta p=0, \quad p(x,0)=p_0, \quad p_t(x,0)=p_1 \] in the square \([0,1]^2\) with periodic boundary conditions. The problem is rewritten as a first order system and is then discretized in space using a \(N \times N-\)mesh on \([0,1]^2\). The resulting system is \(u_t=Au\). The basic idea of the numerical method is to provide a new approximation of the semigroup \(\exp(tA)\), which can be used for larger time-steps than the discretizations based on an expansion of \(\exp(tA)\) near \(t=0\), where restrictions like the Courant-Friedrichs-Lewy condition must be imposed. Moreover, the new approximation is universally sparse which means that sparsity can be maintained after its repeated application in the time-stepping process by suitable truncation. The proposed method is expensive regarding the calculation of the semi-group approximation consuming between \(O(N^3 \log N)\) and \(O(N^4 \log N)\) steps. But the time-stepping needs only \(O(N^{2+\delta})\) operations which beats the complexity of pseudospectral methods. The quantity \(\delta>0\) can be chosen arbitrarily small but there is a corresponding increase in the \(O\)-constant which leads the authors to choose \(\delta \in [0.5,1]\). The wave atom solver becomes competitive in regimes where the wave equation is to be solved for hundreds of times with different initial value conditions, as in reflection seismology. The approximation is obtained with the aid of wave atoms \(\varphi_\mu\). Here \(\mu:=(j,\mathbf{m},\mathbf{n})\) with \(\mathbf{m}, \mathbf{n} \in {\mathbb Z^2}\), where \(|{\mathbf{m}}|=O(2^j)\). The wave atom \(\varphi_\mu\) is localized around the space-phase point \((x_\mu,\xi_\mu)\), where \(x_\mu:=2^{-j}\mathbf{n}\) and \(\xi_\mu:=\pi 2^j\mathbf{m}\). The quantity \(j\) indexes the scale. There exists a fast wave atom transform described in the above cited article by the authors. Apart from the transform the authors present the main algorithm in detail and provide the analysis with emphasis on complexity, rank estimates and repeated square algorithm. A number of interesting numerical examples is given.

Recommendations

Cites work

Cited in

(16)

This page was built for publication: Wave atoms and time upscaling of wave equations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2391129)