The Relative Computational Cost

The computational costs of the proposed method and of standard migration (and therefore the relative computational cost) will be derived as follows, assuming the observed CSG's are already in the frequency domain. Since ultimately it is the ratio between the computational costs of different methods that is of interest, I restrict the attention to one frequency and to the $S$ sources encompassed by one supergather.

First, spatial FFT's, repeatedly invoked in Figure B.1(a-c), dominate the computational cost of split-step migration. Element-wise product and dot product between two vectors of length $n_x$ (the grid size along $x$ ) incur a cost $C_p$ that is a small multiple of $n_x$ , and the number of times such computation is invoked is comparable to that of FFT_x. On the other hand, the cost of each FFT_x in terms of nflop $\cong \frac{34}{9} n_x \log_2(n_x)$ (Johnson and Frigo, 2006), which $\gtrsim 37 n_x$ because $n_x$ is on the order of a thousand or more for typical reflectivity models. This cost far exceeds that of $C_p$ . Since every flowchart in Figure B.1 contains equal number of FFT_x's, from now on take the computational cost for each of these flowcharts as of unit 1.

Next, the computational costs for forward modeling and for migration, in cases of whether the source field is available, are given by the following items:

1. Forward modeling
   1. The source field, $P(x,z,\omega)$ as depicted in Figure B.1(a), is not available. Therefore $P(x,z,\omega)$ needs to be computed before the reflected field $R(x,z,\omega)$ , as depicted in Figure B.1(b), can be obtained. The computational cost is thus 2.
   2. The source field is available. Then the only task is to compute $R(x,z,\omega)$ , with a computational cost of 1.
2. Migration
   1. The source field is not available. Then both the source field and the downward continued data field $D(x,z,\omega)$ , as depicted in Figure B.1(c), need to be computed. The computational cost is 2. Note: This applies to standard migration.
   2. The source field is available. Then only the downward continued data field needs to be computed, before forming the final migration image. This computational cost is 1.

With these results in mind, I study the computational cost incurred in a CG algorithm, as listed in Algorithm 1. For standard migration, there are $S$ sources covered by the supergather in question and therefore the computational cost as remarked at the end of item 2(a) needs a factor $S$ . Let $\kappa_0$ be this cost, expressed as

$$\kappa_0 = 2 S,$$ (8.1)

and let $\kappa_{LS}$ be the cost for LSM, given in the comment besides line alg:CGalg:CG_end as

$$\kappa_{LS} = K_{it}\frac{3 + 2K_{CGit}}{K_{CGit}} - 1.$$ (8.2)

Therefore the relative computational cost is given by

$$\rho = \frac{\kappa_{LS}} {\kappa_0} = \frac{K_{it}}{S}\frac{3 + 2K_{CGit}}{2K_{CGit}} - \frac{1}{2S}$$ (8.3)

$$= \frac{3 K_{it}-1}{2S}, \textrm{~~when~} K_{CGit}=3.$$ (8.4)

In the case of steepest descent, the relative computational cost is given by

$$\bar{\rho} = \frac{4K_{it} - 1}{2S},$$ (8.5)

which follows from the comment regarding line alg:CGalg:CG_GD and equation C.1.

In the case of IS with encoded supergathers, the computational cost per iteration is equal to that of standard migration, except without the $S$ factor. For $J_{it}$ stackings, the cost is thus

$$\kappa_{IS} = 2 J_{it}.$$ (8.6)

Equating equation C.2 and C.6 leads to

$$J_{it} = K_{it} \frac{3 + 2K_{CGit}}{2K_{CGit}} - \frac{1}{2}$$ (8.7)

$$= \frac{3 K_{it}-1}{2}, \textrm{~~when~} K_{CGit}=3.$$ (8.8)

Equation C.7 relates $J_{it}$ , the number of iterations of IS, to $K_{it}$ , the number of iterations of LSM, on the condition that the computational costs incurred by these two methods are equal. This allows us to compare two criterion functions for LSM and for IS, respectively, on the basis of the same computational cost. Let $f_{LSM}(K_{it})$ and $f_{IS}(J_{it})$ be criterion functions of iteration step $K_{it}$ and $J_{it}$ , for LSM and for IS, respectively. Using equation C.7, I write $f_{IS}(J_{it}) = f_{IS}(J_{it}(K_{it}))$ . Plotted on the abscissa of $K_{it}$ , the two curves of $f_{LSM}(K_{it})$ and $f_{IS}(J_{it}(K_{it}))$ are thus put on equal footing of computational cost. Examples of such plots are provided in Figure 2.3(b).