- 1.
- Transform the regular grid in
*t*to Gauss-Lobato collocation points, required for the fast Chebyshev transform. First, a new variable is introduced by the shift transform:(10) - 2.
- Transform the initial image
*P*(_{0}*x*,*t*) into the Chebyshev space in and Fourier transform in*x*, using the FFT algorithm. The Chebyshev-Fourier representation of*P*(_{0}*x*,*t*) is(11) *T*_{j}denotes the Chebyshev polynomial of degree*j*. - 3.
- Apply equation (1) to advance the image in velocity
*v*. It is convenient to rewrite this equation in the form(12) *x*is performed by multiplying the Fourier transform of*P*by -*k*, and integration in is performed as a direct operations on the Chebyshev coefficients. In particular, if is the Chebyshev representation of the function , then the coefficients^{2}*b*_{j}of are defined by the relation(13) *c*= 2,_{0}*c*_{j}= 0 for*j*< 0, and*c*_{j}= 1 for*j*> 0. The constant of integration (and, correspondingly, the coefficient*b*) can be found at each velocity step from the boundary conditions (2), which are transformed to the form_{0}(14) For the velocity advancement I used an implicit Crank-Nicolson scheme, which is unconditionally stable independent of the velocity step size. By writing equation (12) in the matrix form

(15) (16) - 4.
- Transform the result of the velocity advancement back to the physical domain.
- 5.
- Transform the grid back to being regularly space in
*t*.

Figure 6

Figure 7

The first advantage of the Chebyshev approach comes from the better conditioning of the grid transform. Figure 6 shows the synthetic data before and after the grid transform. Figure 7 shows a reconstruction of the original data after transforming back from the Chebyshev grid (Gauss-Lobato collocation points). The difference with the original image is negligibly small.

Figure 8

The second advantage is the compactness of the Chebyshev
representation. Figure 8 shows the data after the
decomposition into Chebyshev polynomials in and Fourier
transform in *x*. We observe a very rapid convergence of the Chebyshev
representation: a relatively small number of polynomials suffices to
represent the data.

Figure 9

The third advantage is the proper handling of the non-periodic boundary conditions. Figure 9 shows the velocity continuation impulse responses, computed by the Chebyshev method. As expected, no wraparound artifacts occur on the time axis, and the accuracy of the result is noticeably higher than in the case of finite differences (Figure 1).

7/5/1998