next up previous [pdf]

Next: examples Up: Cheng et al.: Propagate Previous: Extrapolating the decoupled elastic

Fast algorithm using low-rank decomposition

As proposed by Cheng and Fomel (2014), low-rank decomposition of the mixed-domain matrix $ d(\mathbf{x},\mathbf{k})$ in equation 18 yields very efficient algorithm for mode decoupling in heterogeneous anisotropic media. We find that the same strategy works for numerical implementations of above pseudo-spectral operators for elastic wave propagation.

For example, the mixed-domain matrix, i.e., $ w(\mathbf{x},\mathbf{k})$ or $ \overline{w}(\mathbf{x},\mathbf{k})$ in the FIOs, can be approximated by the following separated representation (Fomel et al., 2013):

\begin{displaymath}\begin{array}{lcl}
 
 W(\mathbf{x},\mathbf{k})\approx
 \sum_{...
...\mathbf{k}_{m})A_{mn}C(\mathbf{x}_{n},\mathbf{k}),
 \end{array}\end{displaymath} (23)

in which $ B(\mathbf{x},\mathbf{k}_{m})$ is a mixed-domain matrix with reduced wavenumber dimension $ M$ , $ C(\mathbf{x}_{n},\mathbf{k})$ is a mixed-domain matrix with reduced spatial dimension $ N$ , $ A_{mn}$ is a $ {M}\times{N}$ matrix with $ N$ and $ M$ representing the rank of this decomposition. Physically, a separable low-rank approximation amounts to selecting a set of $ N$ ( $ N\ll{N_{x}}$ ) representative spatial locations and $ M$ ( $ M\ll{N_{x}}$ ) representative wavenumbers. Construction of the separated representation follows the method of Engquist and Ying (2009). The ranks $ {M}$ and $ {N}$ are dependent on the complexities (heterogeneity and anisotropy) of the medium and the estimate of the approximation accuracy to the mixed-domain matrices (In the numerical examples, we aim for the relative single-precision accuracy of $ 10^{-6}$ ). More explainations on low-rank decomposition is available in Fomel et al. (2013) and Cheng and Fomel (2014). As we observe, the ranks are generally very small for our applications. For homogeneous media, the ranks naturally reduce to $ 1$ . If there is heterogeneity, the ranks increase to $ 2$ for isotropic media but exceed $ 2$ for anisotropic media. The $ k$ -space adjustment may slightly increase the ranks for the heterogeneous media.

Thus the above low-rank approximation speeds up computation of the FIOs since

\begin{displaymath}\begin{array}{lcl}
 
 \int{e^{i\mathbf{k}\mathbf{x}}W(\mathbf...
...(\mathbf{k})\,\mathrm{d}\mathbf{k}}\right)\right).
 \end{array}\end{displaymath} (24)

Evaluation of the last formula is effectively equivalent to applying $ N$ inverse FFTs each time-step. Accordingly, the computation complexity reduces to $ O(NN_x\log{N_x})$ . In multiple-core implementations, the matrix operations in equation 24 are easy to parallelize.


next up previous [pdf]

Next: examples Up: Cheng et al.: Propagate Previous: Extrapolating the decoupled elastic

2016-11-21