Newton-type Gauss-Seidel Lax-Friedrichs high-order fast sweeping methods for solving generalized eikonal equations at large-scale discretization

摘要

We propose a Newton-type Gauss-Seidel Lax-Friedrichs sweeping method to solve the generalized eikonal equation arising from wave propagation in a moving fluid. The Lax-Friedrichs numerical Hamiltonian is used in discretization of the generalized eikonal equation. Different from traditional Lax-Friedrichs sweeping algorithms, we design a novel approach with a line-wise sweeping strategy. In the local solver, the values of traveltime on an entire line are updated simultaneously by Newton's method. The global solution is then obtained by Gauss-Seidel iterations with line-wise sweepings. We first develop the Newton-based first-order scheme, and on top of that we further develop high-order schemes by applying weighted essentially non-oscillatory (WEND) approximations to derivatives. Extensive 2-D and 3-D numerical examples demonstrate the efficiency and accuracy of the new algorithm. The combination of Newton's method and Gauss-Seidel iterations improves upon the convergence speed of the original Lax-Friedrichs sweeping algorithm. In addition, the Newton-type sweeping method manipulates data in a vectorized manner so that it can be efficiently implemented in modern programming languages that feature array programming, and the resulting advantages are extremely significant for large-scale 3-D computations. (C) 2019 Elsevier Ltd. All rights reserved.