Wave atoms and time upscaling of wave equations (Q2391129)

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.