×

Jet marching methods for solving the eikonal equation. (English) Zbl 1490.65307

Summary: We develop a family of compact high-order semi-Lagrangian label-setting methods for solving the eikonal equation. These solvers march the total 1-jet of the eikonal, and use Hermite interpolation to approximate the eikonal and parametrize characteristics locally for each semi-Lagrangian update. We describe solvers on unstructured meshes in any dimension, and conduct numerical experiments on regular grids in two dimensions. Our results show that these solvers yield at least second-order convergence, and, in special cases such as a linear speed of sound, third-order convergence for both the eikonal and its gradient. We additionally show how to march the second partials of the eikonal using cell-based interpolants. Second derivative information computed this way is frequently second-order accurate, suitable for locally solving the transport equation. This provides a means of marching the prefactor coming from the WKB approximation of the Helmholtz equation. These solvers are designed specifically for computing a high-frequency approximation of the Helmholtz equation in a complicated environment with a slowly varying speed of sound, and, to the best of our knowledge, are the first solvers with these properties. We provide a link to a package providing the solvers, and from which the results of this paper can be reproduced easily.

MSC:

65N99 Numerical methods for partial differential equations, boundary value problems
65Y20 Complexity and performance of numerical algorithms
49M99 Numerical methods in optimal control

Software:

libeikonal
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] P.-A. Absil, R. Mahony, and R. Sepulchre, Optimization Algorithms on Matrix Manifolds, Princeton University Press, Princeton, NJ, 2009. · Zbl 1147.65043
[2] J. B. Allen and D. A. Berkley, Image method for efficiently simulating small-room acoustics, J. Acoust. Soc. Amer., 65 (1979), pp. 943-950.
[3] G. S. Ávila and J. B. Keller, The high-frequency asymptotic field of a point source in an inhomogeneous medium, Comm. Pure Appl. Math., 16 (1963), pp. 363-381. · Zbl 0131.21103
[4] V. M. Babich and N. Y. Kirpichnikova, The Boundary-Layer Method in Diffraction Problems, Springer Ser. Electrophys. 3, Springer, 1979. · Zbl 0411.35001
[5] J.-D. Benamou, Big ray tracing: Multivalued travel time field computation using viscosity solutions of the eikonal equation, J. Comput. Phys., 128 (1996), pp. 463-474. · Zbl 0860.65052
[6] J.-D. Benamou, Multivalued Solution and Viscosity Solutions of the Eikonal Equation, RR-3281, INRIA, 1997.
[7] J.-D. Benamou, An introduction to Eulerian geometrical optics (\textup1992-2002), J. Sci. Comput., 19 (2003), pp. 63-93. · Zbl 1042.78001
[8] J.-D. Benamou, S. Luo, and H. Zhao, A compact upwind second order scheme for the eikonal equation, J. Comput. Math., 28 (2010), pp. 489-516. · Zbl 1240.65233
[9] F. Bornemann and C. Rasch, Finite-element discretization of static Hamilton-Jacobi equations based on a local variational principle, Comput. Vis. Sci., 9 (2006), pp. 57-69. · Zbl 1511.65119
[10] P. Brunet, Increasing the smoothness of bicubic spline surfaces, Comput. Aided Geom. Design, 2 (1985), pp. 157-164. · Zbl 0585.65008
[11] M. K. Cameron, Jet Marching Method, September 2020, https://youtu.be/Ze9AeDbaDVM.
[12] A. Chacon and A. Vladimirsky, Fast two-scale methods for eikonal equations, SIAM J. Sci. Comput., 34 (2012), pp. A547-A578, https://doi.org/10.1137/10080909X. · Zbl 1244.49047
[13] A. Chandak, C. Lauterbach, M. Taylor, Z. Ren, and D. Manocha, Ad-frustum: Adaptive frustum tracing for interactive sound propagation, IEEE Trans. Vis. Comput. Graphics, 14 (2008), pp. 1707-1722.
[14] D. L. Chopp, Some improvements of the fast marching method, SIAM J. Sci. Comput., 23 (2001), pp. 230-244, https://doi.org/10.1137/S106482750037617X. · Zbl 0991.65105
[15] G. Farin, Curves and Surfaces for Computer-Aided Geometric Design: A Practical Guide, Elsevier, 2014. · Zbl 0702.68004
[16] M. S. Floater, Chordal cubic spline interpolation is fourth-order accurate, IMA J. Numer. Anal., 26 (2006), pp. 25-33. · Zbl 1095.41006
[17] S. Fomel, S. Luo, and H. Zhao, Fast sweeping method for the factored eikonal equation, J. Comput. Phys., 228 (2009), pp. 6440-6455. · Zbl 1175.65125
[18] J. V. Gómez, D. Álvarez, S. Garrido, and L. Moreno, Fast methods for eikonal equations: An experimental survey, IEEE Access, 7 (2019), pp. 39005-39029.
[19] A. Griewank and A. Walther, Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation, 2nd ed., SIAM, Philadelphia, 2008, https://doi.org/10.1137/1.9780898717761. · Zbl 1159.65026
[20] H. Hagen and G. Schulze, Automatic smoothing with geometric surface patches, Comput. Aided Geom. Design, 4 (1987), pp. 231-235. · Zbl 0635.65011
[21] J. B. Keller, Geometrical theory of diffraction, J. Opt. Soc. Amer., 52 (1962), pp. 116-130.
[22] R. Kimmel and J. A. Sethian, Computing geodesic paths on manifolds, Proc. Natl. Acad. Sci. USA, 95 (1998), pp. 8431-8435. · Zbl 0908.65049
[23] R. G. Kouyoumjian and P. H. Pathak, A uniform geometrical theory of diffraction for an edge in a perfectly conducting surface, Proc. IEEE, 62 (1974), pp. 1448-1461.
[24] S. Luo, J. Qian, and R. Burridge, High-order factorization based high-order hybrid fast sweeping methods for point-source eikonal equations, SIAM J. Numer. Anal., 52 (2014), pp. 23-44, https://doi.org/10.1137/120901696. · Zbl 1293.65130
[25] J.-C. Nave, R. R. Rosales, and B. Seibold, A gradient-augmented level set method with an optimally local, coherent advection scheme, J. Comput. Phys., 229 (2010), pp. 3802-3827. · Zbl 1189.65214
[26] R. D. Neidinger, Introduction to automatic differentiation and MATLAB object-oriented programming, SIAM Rev., 52 (2010), pp. 545-563, https://doi.org/10.1137/080743627. · Zbl 1196.65048
[27] F. E. Nicodemus, Directional reflectance and emissivity of an opaque surface, Appl. Optics, 4 (1965), pp. 767-775.
[28] M. M. Popov, Ray Theory and Gaussian Beam Method for Geophysicists, EDUFBA, Salvador, Brazil, 2002.
[29] M. M. Popov, I. Pšenčík, and V. Červenỳ, Computation of ray amplitudes in inhomogeneous media with curved interfaces, Stud. Geophys. Geod., 22 (1978), pp. 248-258.
[30] S. F. Potter and M. K. Cameron, Ordered line integral methods for solving the eikonal equation, J. Sci. Comput., 81 (2019), pp. 2010-2050. · Zbl 1434.65307
[31] D. Qi and A. Vladimirsky, Corner cases, singularities, and dynamic factoring, J. Sci. Comput., 79 (2019), pp. 1456-1476. · Zbl 1419.49034
[32] J. Qian, L. Yuan, Y. Liu, S. Luo, and R. Burridge, Babich’s expansion and high-order Eulerian asymptotics for point-source Helmholtz equations, J. Sci. Comput., 67 (2016), pp. 883-908. · Zbl 1398.65320
[33] N. Raghuvanshi and J. Snyder, Parametric wave field coding for precomputed sound propagation, ACM Trans. Graphics (TOG), 33 (2014), 38.
[34] N. Raghuvanshi and J. Snyder, Parametric directional coding for precomputed sound propagation, ACM Trans. Graphics (TOG), 37 (2018), 108.
[35] L. Savioja and U. P. Svensson, Overview of geometrical room acoustic modeling techniques, J. Acoust. Soc. Amer., 138 (2015), pp. 708-730.
[36] C. Schissler, R. Mehra, and D. Manocha, High-order diffraction and diffuse reflections for interactive sound propagation in large environments, ACM Trans. Graphics (TOG), 33 (2014), 39.
[37] B. Seibold, J.-C. Nave, and R. R. Rosales, Jet Schemes for Advection Problems, preprint, https://arxiv.org/abs/1101.5374, 2011. · Zbl 1252.65158
[38] J. A. Sethian, A fast marching level set method for monotonically advancing fronts, Proc. Natl. Acad. Sci. USA, 93 (1996), pp. 1591-1595. · Zbl 0852.65055
[39] J. A. Sethian, Fast marching methods, SIAM Rev., 41 (1999), pp. 199-235, https://doi.org/10.1137/S0036144598347059. · Zbl 0926.65106
[40] J. A. Sethian, Level Set Methods and Fast Marching Methods: Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science, Cambridge Mongr. Appl. Comput. Math. 3, Cambridge University Press, 1999. · Zbl 0973.76003
[41] J. A. Sethian and A. Vladimirsky, Fast methods for the eikonal and related Hamilton-Jacobi equations on unstructured meshes, Proc. Natl. Acad. Sci. USA, 97 (2000), pp. 5699-5703. · Zbl 0963.65076
[42] J. A. Sethian and A. Vladimirsky, Ordered upwind methods for static Hamilton-Jacobi equations: Theory and algorithms, SIAM J. Numer. Anal., 41 (2003), pp. 325-363, https://doi.org/10.1137/S0036142901392742. · Zbl 1040.65088
[43] G. E. Shilov and R. A. Silverman, Linear Algebra, Prentice-Hall, 1971. · Zbl 0212.36601
[44] M. M. Slotnick, Lessons in Seismic Computing: A Memorial to the Author, Society of Exploration Geophysicists, Tulsa, OK, 1959.
[45] J. Stoer and R. Bulirsch, Introduction to Numerical Analysis, Texts Appl. Math. 12, Springer Science & Business Media, 2013. · Zbl 0423.65002
[46] J. N. Tsitsiklis, Efficient algorithms for globally optimal trajectories, IEEE Trans. Automat. Control, 40 (1995), pp. 1528-1538. · Zbl 0831.93028
[47] R. Versteeg, The Marmousi experience: Velocity model determination on a synthetic complex data set, The Leading Edge, 13 (1994), pp. 927-936.
[48] T. Xiong, M. Zhang, Y.-T. Zhang, and C.-W. Shu, Fast sweeping fifth order WENO scheme for static Hamilton-Jacobi equations with accurate boundary treatment, J. Sci. Comput., 45 (2010), pp. 514-536. · Zbl 1203.65155
[49] S. Yang, S. F. Potter, and M. K. Cameron, Computing the quasipotential for nongradient SDEs in 3D, J. Comput. Phys., 379 (2019), pp. 325-350. · Zbl 07581575
[50] Y.-T. Zhang, H.-K. Zhao, and J. Qian, High order fast sweeping methods for static Hamilton-Jacobi equations, J. Sci. Comput., 29 (2006), pp. 25-56. · Zbl 1149.70302
[51] H. Zhao, A fast sweeping method for eikonal equations, Math. Comput., 74 (2005), pp. 603-627. · 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.