First-break traveltime tomography with the double-square-root eikonal equation

Appendix C: Adjoint-state tomography with upwind finite-differences

Following Appendix A, we let $T_i^{j,k}$ in the DSR case be the traveltime at vertex $(z_i,r_j,s_k)$ and approximate $D_z$ in equation 8 by a one-sided finite-difference

$$D_z^{\pm} T_i^{j,k} = \pm \frac{T_{i \pm 1}^{j,k} - T_i^{j,k}}{\Delta}\;,$$ (41)

where the $\pm$ sign corresponds to the two neighbors of $T_i^{j,k}$ in $z$ direction. An upwind scheme (Franklin and Harris, 2001) picks the sign by

$$D_z T_i^{j,k} = \max \left( D_z^- T_i^{j,k}, -D_z^+ T_i^{j,k}, 0 \right)\;.$$ (42)

The above strategy can be applied to $D_r$ and $D_s$ straightforwardly. For the shot-indexed eikonal equation 9, we approximate $D_x$ with the same upwind method while $T$ in this case is indexed for $z$ and $x$.

For a Cartesian ordering of the discretized $T$, i.e. vector $\mathbf{t}$, the discretized operators $D_m T \cdot D_m$ with $m = z,x,r,s$ are matrices. Thanks to upwind finite-differences, these matrices are sparse and contain only two non-zero entries per row. For instance, suppose $T_i^{j,k}$ has its upwind neighbor in $z$ at $T_{i-1}^{j,k}$, then

$$D_z T \cdot D_z = \left[ \begin{array}{cccccc} \ddots & & & ... ...z & & \kappa_z & & \\ & & & & & \ddots \end{array} \right]\;,$$ (43)

where

$$\kappa_z \equiv \frac{D_z T_i^{j,k}}{\Delta} = \frac{T_i^{j,k} - T_{i-1}^{j,k}}{\Delta^2}\;.$$ (44)

Definitions of $\kappa_r$, $\kappa_s$ and $\kappa_x$ follow their upwind approximations, respectively. In equation C-3, $\pm \kappa_z$ are located in the same row as that of $T_i^{j,k}$ in $\mathbf{t}$. While $\kappa_z$ sits on the diagonal, $- \kappa_z$ has a column index equals to the row of $T_{i-1}^{j,k}$ in $\mathbf{t}$. At $T = 0$, there is no upwind neighbor and the corresponding row contains all zeros.

We can sort entries of $\mathbf{t}$ by their values in an increasing order, which equivalently performs column-wise permutations to $D_m T \cdot D_m$. The results are lower triangular matrices. In fact, during FMM forward modeling, such an upwind ordering is maintained and updated by the priority queue and thus can be conveniently imported for usage here.

Note that the summation and subtraction of two (or more) $D_m T \cdot D_m$ matrices are still lower triangular. These matrices are also invertible, except for a singularity at $T = 0$ where we may set the entries to be zero. Naturally, the inverted matrices are also lower triangular. One example is the linearized eikonal equation that gives rise to equation 10. Following notation C-4 and assuming the upwind neighbors of $T_i^j$ are $T_{i-1}^j$ and $T_i^{j-1}$, the linearized equation 9 reads

$$2 \kappa_z (\delta T_i^j - \delta T_{i-1}^j) + 2 \kappa_x (\delta T_i^j - \delta T_i^{j-1}) = \delta w_i^j\;.$$ (45)

After regrouping the terms, we get

$$\delta T_i^j = \frac{2 \kappa_z \delta T_{i-1}^j + 2 \kappa_x \delta T_i^{j-1} + \delta w_i^j}{2\,(\kappa_z + \kappa_x)}\;.$$ (46)

Equation C-6 means the inverse of the operator $D_z T \cdot D_z + D_x T \cdot D_x$ does not need to be computed by an explicit matrix inversion. Instead, we can perform its application to a vector by a single sweep based on causal upwind ordering. The same conclusion can be drawn for operator B-4.

Lastly, the adjoint-state calculations implied by equations 12 and 16 multiply the transpose of these inverse matrices with the data residual. The matrix transposition leads to upper triangular matrices. Accordingly, we solve the linear system with anti-causal downwind ordering that follows a decrease in values of $\mathbf{t}$.

First-break traveltime tomography with the double-square-root eikonal equation