A fast marching algorithm for the factored eikonal equation. (English) Zbl 1360.65266
Summary: The eikonal equation is instrumental in many applications in several fields ranging from computer vision to geoscience. This equation can be efficiently solved using the iterative fast sweeping (FS) methods and the direct fast marching (FM) methods. However, when used for a point source, the original eikonal equation is known to yield inaccurate numerical solutions, because of a singularity at the source. In this case, the factored eikonal equation is often preferred, and is known to yield a more accurate numerical solution. One application that requires the solution of the eikonal equation for point sources is travel time tomography. This inverse problem may be formulated using the eikonal equation as a forward problem. While this problem has been solved using FS in the past, the more recent choice for applying it involves FM methods because of the efficiency in which sensitivities can be obtained using them. However, while several FS methods are available for solving the factored equation, the FM method is available only for the original eikonal equation. In this paper we develop a Fast Marching algorithm for the factored eikonal equation, using both first and second order finite-difference schemes. Our algorithm follows the same lines as the original FM algorithm and requires the same computational effort. In addition, we show how to obtain sensitivities using this FM method and apply travel time tomography, formulated as an inverse factored eikonal equation. Numerical results in two and three dimensions show that our algorithm solves the factored eikonal equation efficiently, and demonstrate the achieved accuracy for computing the travel time. We also demonstrate a recovery of a 2D and 3D heterogeneous medium by travel time tomography using the eikonal equation for forward modeling and inversion by Gauss-Newton.
MSC:
| 65N21 | Numerical methods for inverse problems for boundary value problems involving PDEs |
| 65N06 | Finite difference methods for boundary value problems involving PDEs |
| 65N12 | Stability and convergence of numerical methods for boundary value problems involving PDEs |
Keywords:
eikonal equation; factored eikonal equation; fast marching; first arrival; travel time tomography; Gauss-Newton; seismic imagingReferences:
| [1] | Aminzadeh, F.; Jean, B.; Kunz, T., 3-D Salt and Overthrust Models (1997), Society of Exploration Geophysicists |
| [2] | Bærentzen, J. A., On the implementation of fast marching methods for 3D lattices (2001), Technical University of Denmark, DTU, Richard Petersens Plads, Building 321, DK- 2800 Kgs. Lyngby |
| [3] | Benaichouche, A.; Noble, M.; Gesret, A., First arrival traveltime tomography using the fast marching method and the adjoint state technique, (77th EAGE Conference Proceedings (2015)) |
| [4] | Bezanzon, J.; Karpinski, S.; Shah, V.; Edelman, A., Julia: a fast dynamic language for technical computing, (Lang. NEXT (Apr. 2012)) |
| [5] | Crandall, M. G.; Lions, P.-L., Viscosity solutions of Hamilton-Jacobi equations, Trans. Am. Math. Soc., 277, 1-42 (1983) · Zbl 0599.35024 |
| [6] | Fomel, S.; Luo, S.; Zhao, H., Fast sweeping method for the factored eikonal equation, J. Comput. Phys., 228, 6440-6455 (2009) · Zbl 1175.65125 |
| [7] | Gremaud, P. A.; Kuster, C. M., Computational study of fast methods for the eikonal equation, SIAM J. Sci. Comput., 27, 1803-1816 (2006) · Zbl 1102.65107 |
| [8] | Haber, E., Computational Methods in Geophysical Electromagnetics, vol. 1 (2014), SIAM |
| [9] | Haber, E.; MacLachlan, S., A fast method for the solution of the Helmholtz equation, J. Comput. Phys., 230, 4403-4418 (2011) · Zbl 1220.65172 |
| [10] | Kao, C. Y.; Osher, S.; Qian, J., Lax-Friedrichs sweeping scheme for static Hamilton-Jacobi equations, J. Comput. Phys., 196, 367-391 (2004) · Zbl 1053.65088 |
| [11] | Kimmel, R.; Sethian, J. A., Computing geodesic paths on manifolds, Proc. Natl. Acad. Sci., 95, 8431-8435 (1998) · Zbl 0908.65049 |
| [12] | Leung, S.; Qian, J.; Burridge, R., Eulerian Gaussian beams for high-frequency wave propagation, Geophysics, 72, SM61-SM76 (2007) |
| [13] | Leung, S.; Qian, J., An adjoint state method for three-dimensional transmission traveltime tomography using first-arrivals, Commun. Math. Sci., 4, 249-266 (2006) · Zbl 1096.65062 |
| [14] | Li, S.; Vladimirsky, A.; Fomel, S., First-break traveltime tomography with the double-square-root eikonal equation, Geophysics, 78, U89-U101 (2013) |
| [15] | Luo, S.; Qian, J., Factored singularities and high-order Lax-Friedrichs sweeping schemes for point-source traveltimes and amplitudes, J. Comput. Phys., 230, 4742-4755 (2011) · Zbl 1220.78004 |
| [16] | Luo, S.; Qian, J., Fast sweeping methods for factored anisotropic eikonal equations: multiplicative and additive factors, J. Sci. Comput., 52, 360-382 (2012) · Zbl 1255.65192 |
| [17] | Luo, S.; Qian, J.; Burridge, R., Fast Huygens sweeping methods for Helmholtz equations in inhomogeneous media in the high frequency regime, J. Comput. Phys., 270, 378-401 (2014) · Zbl 1349.78051 |
| [18] | Luo, S.; Qian, J.; Burridge, R., High-order factorization based high-order hybrid fast sweeping methods for point-source eikonal equations, SIAM J. Numer. Anal., 52, 23-44 (2014) · Zbl 1293.65130 |
| [19] | Luo, S.; Qian, J.; Zhao, H., Higher-order schemes for 3d first-arrival traveltimes and amplitudes, Geophysics, 77, T47-T56 (2012) |
| [20] | Noble, M.; Gesret, A.; Belayouni, N., Accurate 3-d finite difference computation of traveltimes in strongly heterogeneous media, Geophys. J. Int., 199, 1572-1585 (2014) |
| [21] | Pica, A., Fast and accurate finite-difference solutions of the 3d eikonal equation parametrized in celerity, (67th Ann. Internat. Mtg (1997), Soc. of Expl. Geophys), 1774-1777 |
| [22] | Qian, J.; Symes, W. W., An adaptive finite-difference method for traveltimes and amplitudes, Geophysics, 67, 167-176 (2002) |
| [23] | Qian, J.; Zhang, Y.-T.; Zhao, H.-K., A fast sweeping method for static convex Hamilton-Jacobi equations, J. Sci. Comput., 31, 237-271 (2007) · Zbl 1115.70005 |
| [24] | Rawlinson, N.; Sambridge, M., Wave front evolution in strongly heterogeneous layered media using the fast marching method, Geophys. J. Int., 156, 631-647 (2004) |
| [25] | Rouy, E.; Tourin, A., A viscosity solutions approach to shape-from-shading, SIAM J. Numer. Anal., 29, 867-884 (1992) · Zbl 0754.65069 |
| [26] | Rudin, L. I.; Osher, S.; Fatemi, E., Nonlinear total variation based noise removal algorithms, Physica D, 60, 259-268 (1992) · Zbl 0780.49028 |
| [28] | Saragiotis, C.; Alkhalifah, T.; Fomel, S., Automatic traveltime picking using instantaneous traveltime, Geophysics, 78, T53-T58 (2013) |
| [29] | Sei, A.; Symes, W. W., Gradient calculation of the traveltime cost function without ray tracing, (65th Ann. Internat. Mtg., Expanded Abstracts (1994), Soc. Expl. Geophys), 1351-1354 |
| [30] | Sethian, J. A., A fast marching level set method for monotonically advancing fronts, Proc. Natl. Acad. Sci., 93, 1591-1595 (1996) · Zbl 0852.65055 |
| [31] | Sethian, J. A., Fast marching methods, SIAM Rev., 41, 199-235 (1999) · Zbl 0926.65106 |
| [32] | Somersalo, E.; Kaipio, J., Statistical and Computational Inverse Problems, Appl. Math. Sci., vol. 160 (2004) · Zbl 0927.35134 |
| [33] | Spira, A.; Kimmel, R., An efficient solution to the eikonal equation on parametric manifolds, Interfaces Free Bound., 6, 315-328 (2004) · Zbl 1054.65098 |
| [34] | Taillandier, C.; Noble, M.; Chauris, H.; Calandra, H., First-arrival traveltime tomography based on the adjoint-state method, Geophysics, 74, WCB1-WCB10 (2009) |
| [35] | Tsai, Y.-H. R.; Cheng, L.-T.; Osher, S.; Zhao, H.-K., Fast sweeping algorithms for a class of Hamilton-Jacobi equations, SIAM J. Numer. Anal., 41, 673-694 (2003) · Zbl 1049.35020 |
| [36] | Tsitsiklis, J. N., Efficient algorithms for globally optimal trajectories, IEEE Trans. Autom. Control, 40, 1528-1538 (1995) · Zbl 0831.93028 |
| [37] | Vogel, C. R., Computational Methods for Inverse Problems, Frontiers Appl. Math., vol. 23 (2002), SIAM: SIAM Philadelphia · Zbl 1008.65103 |
| [38] | Zhao, H., A fast sweeping method for eikonal equations, Math. Comput., 74, 603-627 (2005) · Zbl 1070.65113 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
