×

Ordered line integral methods for solving the eikonal equation. (English) Zbl 1434.65307

Summary: We present a family of fast and accurate Dijkstra-like solvers for the eikonal equation and factored eikonal equation which compute solutions on a regular grid by solving local variational minimization problems. Our methods converge linearly but compute significantly more accurate solutions than competing first order methods. In 3D, we present two different families of algorithms which significantly reduce the number of FLOPs needed to obtain an accurate solution to the eikonal equation. One method employs a fast search using local characteristic directions to prune unnecessary updates, and the other uses the theory of constrained optimization to achieve the same end. The proposed solvers are more efficient than the standard fast marching method in terms of the relationship between error and CPU time. We also modify our method for use with the additively factored eikonal equation, which can be solved locally around point sources to maintain linear convergence. We conduct extensive numerical simulations and provide theoretical justification for our approach. A library that implements the proposed solvers is available on GitHub.

MSC:

65N99 Numerical methods for partial differential equations, boundary value problems
65Y20 Complexity and performance of numerical algorithms
65K10 Numerical optimization and variational techniques
65N12 Stability and convergence of numerical methods for boundary value problems involving PDEs
65D32 Numerical quadrature and cubature formulas
49L20 Dynamic programming in optimal control and differential games
49L25 Viscosity solutions to Hamilton-Jacobi equations in optimal control and differential games
35L70 Second-order nonlinear hyperbolic equations
76Q05 Hydro- and aero-acoustics
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alexandrescu, A.: Modern C++ Design: Generic Programming and Design Patterns Applied. Addison-Wesley, Boston (2001)
[2] Arndt, J.: Matters Computational: Ideas, Algorithms, Source Code. Springer, Berlin (2010) · Zbl 1210.68128
[3] Bertsekas, D.P.: Network Optimization: Continuous and Discrete Models. Princeton, Citeseer (1998) · Zbl 0997.90505
[4] Bertsekas, D.P.: Nonlinear Programming. Athena Scientific, Belmont (1999) · Zbl 1015.90077
[5] Bornemann, F.; Rasch, C., Finite-element discretization of static Hamilton-Jacobi equations based on a local variational principle, Comput. Vis. Sci., 9, 57-69 (2006) · Zbl 1511.65119
[6] Bronstein, A.M., Bronstein, M.M., Kimmel, R.: Numerical Geometry of Non-rigid Shapes. Springer, Berlin (2008) · Zbl 1178.68608
[7] Chacon, A.; Vladimirsky, A., Fast two-scale methods for eikonal equations, SIAM J. Sci. Comput., 34, a547-a578 (2012) · Zbl 1244.49047
[8] Chacon, A.; Vladimirsky, A., A parallel two-scale method for eikonal equations, SIAM J. Sci. Comput., 37, a156-a180 (2015) · Zbl 1348.49025
[9] Chopp, DL, Some Improvements of the Fast Marching Method, SIAM J. Sci. Comput., 23, 230-244 (2001) · Zbl 0991.65105
[10] Crandall, MG; Lions, P-L, Viscosity solutions of Hamilton-Jacobi equations, Trans. Am. Math. Soc., 277, 1-42 (1983) · Zbl 0599.35024
[11] Dahiya, D., Cameron, M.: An ordered line integral method for computing the quasi-potential in the case of variable anisotropic diffusion (2018). arXiv preprint arXiv:1806.05321 · Zbl 1415.65017
[12] Dahiya, D.; Cameron, M., Ordered line integral methods for computing the quasi-potential, J. Sci. Comput., 75, 1351-1384 (2018) · Zbl 1395.65150
[13] Dial, RB, Algorithm 360: shortest-path forest with topological ordering, Commun. ACM, 12, 632-633 (1969)
[14] Dijkstra, EW, A note on two problems in connexion with graphs, Numer Math, 1, 269-271 (1959) · Zbl 0092.16002
[15] Durou, J-D; Falcone, M.; Sagona, M., Numerical methods for shape-from-shading: a new survey with benchmarks, Comput. Vis. Image Underst., 109, 22-43 (2008)
[16] Engquist, B.; Runborg, O., Computational high frequency wave propagation, Acta Numer., 12, 181-266 (2003) · Zbl 1049.65098
[17] Fomel, S.; Luo, S.; Zhao, H., Fast sweeping method for the factored eikonal equation, J. Comput. Phys., 228, 6440-6455 (2009) · Zbl 1175.65125
[18] Fomel, S.; Sethian, JA, Fast-phase space computation of multiple arrivals, Proc. Natl. Acad. Sci., 99, 7329-7334 (2002) · Zbl 1002.65113
[19] Gómez, J.V., Alvarez, D., Garrido, S., Moreno, L.: Fast methods for eikonal equations: an experimental survey. IEEE Access (2019)
[20] https://github.com/sampotter/olim/tree/sisc19. Project page for libolim on GitHub
[21] https://github.com/sampotter/olim/tree/sisc19/plotting. Link to section of libolim project page containing Python plotting scripts and instructions
[22] Ihrke, I.; Ziegler, G.; Tevs, A.; Theobalt, C.; Magnor, M.; Seidel, H-P, Eikonal rendering: efficient light transport in refractive objects, ACM Trans. Graph. (TOG), 26, 59 (2007)
[23] Jeong, W-K; Whitaker, RT, A fast iterative method for eikonal equations, SIAM J. Sci. Comput., 30, 2512-2534 (2008) · Zbl 1246.70003
[24] Kao, C-Y; Osher, S.; Qian, J., Legendre-transform-based fast sweeping methods for static Hamilton-Jacobi equations on triangulated meshes, J. Comput. Phys., 227, 10209-10225 (2008) · Zbl 1152.65102
[25] Kim, S., An \(O(N)\) level set method for eikonal equations, SIAM J. Sci. Comput., 22, 2178-2193 (2001) · Zbl 0994.76080
[26] Kim, S., 3-D eikonal solvers: first-arrival traveltimes, Geophysics, 67, 1225-1231 (2002)
[27] Kimmel, R.; Sethian, JA, Computing geodesic paths on manifolds, Proc. Natl. Acad. Sci., 95, 8431-8435 (1998) · Zbl 0908.65049
[28] Kimmel, R.; Sethian, JA, Optimal algorithm for shape from shading and path planning, J. Math. Imaging Vis., 14, 237-244 (2001) · Zbl 0995.68101
[29] Lewiner, T.; Lopes, H.; Vieira, AW; Tavares, G., Efficient implementation of marching cubes’ cases with topological guarantees, J. Graph. Tools, 8, 1-15 (2003)
[30] 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
[31] Luo, S.; Zhao, H., Convergence analysis of the fast sweeping method for static convex Hamilton-Jacobi equations, Res. Math. Sci., 3, 35 (2016) · Zbl 1356.35094
[32] Mirebeau, J-M, Anisotropic fast-marching on cartesian grids using lattice basis reduction, SIAM J. Numer. Anal., 52, 1573-1599 (2014) · Zbl 1312.65172
[33] Mirebeau, J-M, Efficient fast marching with Finsler metrics, Numer. Math., 126, 515-557 (2014) · Zbl 1297.65074
[34] Mitchell, JSB; Mount, DM; Papadimitriou, CH, The discrete geodesic problem, SIAM J. Comput., 16, 647-668 (1987) · Zbl 0625.68051
[35] Nethercote, N., Seward, J.: Valgrind: a framework for heavyweight dynamic binary instrumentation. In: ACM Sigplan Notices, pp. 89-100. ACM (2007)
[36] Nocedal, J., Wright, S.: Numerical Optimization. Springer, Berlin (2006) · Zbl 1104.65059
[37] Osher, S., Fedkiw, R.: Level Set Methods and Dynamic Implicit Surfaces, vol. 153. Springer, Berlin (2006) · Zbl 1026.76001
[38] Popovici, AM; Sethian, JA, 3-D imaging using higher order fast marching traveltimes, Geophysics, 67, 604-609 (2002)
[39] Potter, S.F.: http://umiacs.umd.edu/ sfp. Author’s personal webpage
[40] Potter, S.F., Cameron, M.K.: https://github.com/sampotter/olim-plots/blob/master/marmousi_2d.ipynb. Supplemental numerical experiments in 2D for the original Marmousi model
[41] Prados, E., Faugeras, O.: Shape from shading. In: Handbook of Mathematical Models in Computer Vision, pp. 375-388. Springer (2006) · Zbl 1112.49025
[42] Prislan, R.; Veble, G.; Svenšek, D., Ray-trace modeling of acoustic Green’s function based on the semiclassical (eikonal) approximation, J. Acoust. Soc. Am., 140, 2695-2702 (2016)
[43] Qi, D., Vladimirsky A.: Corner cases, singularities, and dynamic factoring (2018). arXiv preprint arXiv:1801.04322 · Zbl 1419.49034
[44] Raghuvanshi, N.; Snyder, J., Parametric wave field coding for precomputed sound propagation, ACM Trans. Graph. (TOG), 33, 38 (2014)
[45] Raghuvanshi, N.; Snyder, J., Parametric directional coding for precomputed sound propagation, ACM Trans. Graph. (TOG), 37, 108 (2018)
[46] Sedgewick, R., Wayne, K.: Algorithms. Addison-Wesley Professional, Reading (2011) · Zbl 07105648
[47] Sethian, JA, A fast marching level set method for monotonically advancing fronts, Proc. Natl. Acad. Sci., 93, 1591-1595 (1996) · Zbl 0852.65055
[48] Sethian, J.A.: Level Set Methods and Fast Marching Methods: Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science, vol. 3. Cambridge University Press, Cambridge (1999) · Zbl 0973.76003
[49] Sethian, JA; Popovici, AM, 3-D traveltime computation using the fast marching method, Geophysics, 64, 516-523 (1999)
[50] Sethian, JA; Vladimirsky, A., Fast methods for the Eikonal and related Hamilton-Jacobi equations on unstructured meshes, Proc. Natl. Acad. Sci., 97, 5699-5703 (2000) · Zbl 0963.65076
[51] Sethian, JA; Vladimirsky, A., Ordered upwind methods for static Hamilton-Jacobi equations: theory and algorithms, SIAM J. Numer. Anal., 41, 325-363 (2003) · Zbl 1040.65088
[52] Slotnick, M.: Lessons in seismic computing. Soc. Expl. Geophys, p. 268 (1959)
[53] Stoer, J., Bulirsch, R.: Introduction to Numerical Analysis, vol. 12. Springer, Berlin (2013) · Zbl 0423.65002
[54] Stroustrup, B.: The C++ Programming Language. Pearson Education, London (2013) · Zbl 0825.68056
[55] Treister, E.; Haber, E., A fast marching algorithm for the factored eikonal equation, J. Comput. Phys., 324, 210-225 (2016) · Zbl 1360.65266
[56] Tsai, Y-HR; 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
[57] Tsitsiklis, JN, Efficient algorithms for globally optimal trajectories, IEEE Trans. Autom. Control, 40, 1528-1538 (1995) · Zbl 0831.93028
[58] Walt, S.; Schönberger, JL; Nunez-Iglesias, J.; Boulogne, F.; Warner, JD; Yager, N.; Gouillart, E.; Yu, T., scikit-image: image processing in python, PeerJ, 2, 453 (2014)
[59] Trier, J.; Symes, WW, Upwind finite-difference calculation of traveltimes, Geophysics, 56, 812-821 (1991)
[60] Versteeg, R., The marmousi experience: velocity model determination on a synthetic complex data set, Lead. Edge, 13, 927-936 (1994)
[61] Vidale, JE, Finite-difference calculation of traveltimes in three dimensions, Geophysics, 55, 521-526 (1990)
[62] Yang, S.; Potter, SF; Cameron, MK, Computing the quasipotential for nongradient SDEs in 3D, J. Comput. Phys., 379, 325-350 (2019) · Zbl 07581575
[63] Yatziv, L.; Bartesaghi, A.; Sapiro, G., \(O(N)\) implementation of the fast marching algorithm, J. Comput. Phys., 212, 393-399 (2006) · Zbl 1083.65083
[64] Zhang, Y-T; Zhao, H-K; Qian, J., High order fast sweeping methods for static Hamilton-Jacobi equations, J. Sci. Comput., 29, 25-56 (2006) · Zbl 1149.70302
[65] Zhao, H-K, 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.