High order absolutely convergent fast sweeping methods with multi-resolution WENO local solvers for Eikonal and factored Eikonal equations. (English) Zbl 07845609
Summary: Fast sweeping methods are a class of efficient iterative methods developed in the literature to solve steady-state solutions of hyperbolic partial differential equations (PDEs). In [Y.-T. Zhang et al., J. Sci. Comput. 29, No. 1, 25–56 (2006; Zbl 1149.70302)] and [T. Xiong et al., J. Sci. Comput. 45, No. 1–3, 514–536 (2010; Zbl 1203.65155)], high order accuracy fast sweeping schemes based on classical weighted essentially non-oscillatory (WENO) local solvers were developed for solving static Hamilton-Jacobi equations. However, since high order classical WENO methods (e.g., fifth order and above) often suffer from difficulties in their convergence to steady-state solutions, iteration residues of high order fast sweeping schemes with these local solvers may hang at a level far above round-off errors even after many iterations. This issue makes it difficult to determine the convergence criterion for the high order fast sweeping methods and challenging to apply the methods to complex problems. Motivated by the recent work on absolutely convergent fast sweeping method for steady-state solutions of hyperbolic conservation laws in [L. Li et al., J. Comput. Phys. 443, Article ID 110516, 24 p. (2021; Zbl 07515416)], in this paper we develop high order fast sweeping methods with multi-resolution WENO local solvers for solving Eikonal equations, an important class of static Hamilton-Jacobi equations. Based on such kind of multi-resolution WENO local solvers with unequal-sized sub-stencils, iteration residues of the designed high order fast sweeping methods can settle down to round-off errors and achieve the absolute convergence. In order to obtain high order accuracy for problems with singular source-point, we apply the factored Eikonal approach developed in the literature and solve the resulting factored Eikonal equations by the new high order WENO fast sweeping methods. Extensive numerical experiments are performed to show the accuracy, computational efficiency, and advantages of the new high order fast sweeping schemes for solving static Hamilton-Jacobi equations.
MSC:
| 65N06 | Finite difference methods for boundary value problems involving PDEs |
| 65N12 | Stability and convergence of numerical methods for boundary value problems involving PDEs |
| 65N99 | Numerical methods for partial differential equations, boundary value problems |
| 35F21 | Hamilton-Jacobi equations |
| 35L65 | Hyperbolic conservation laws |
| 35D40 | Viscosity solutions to PDEs |
Keywords:
high order accuracy fast sweeping methods; weighted essentially non-oscillatory (WENO) schemes; multi-resolution WENO schemes; static homotopy method equations; factored Eikonal equationsReferences:
| [1] | Borges, R.; Carmona, M.; Costa, B.; Don, WS, An improved weighted essentially non-oscillatory scheme for hyperbolic conservation laws, J. Comput. Phys., 227, 3191-3211, 2008 · Zbl 1136.65076 · doi:10.1016/j.jcp.2007.11.038 |
| [2] | Crandall, MG; Lions, PL, Viscosity solutions of Hamilton-Jacobi equations, Trans. Am. Math. Soc., 277, 1-42, 1983 · Zbl 0599.35024 · doi:10.1090/S0002-9947-1983-0690039-8 |
| [3] | Dijkstra, EW, A note on two problems in connection with graphs, Numer. Math., 1, 269-271, 1959 · Zbl 0092.16002 · doi:10.1007/BF01386390 |
| [4] | Fomel, S.; Luo, S.; Zhao, H., Fast sweeping method for the factored eikonal equation, J. Comput. Phys., 228, 6440-6455, 2009 · Zbl 1175.65125 · doi:10.1016/j.jcp.2009.05.029 |
| [5] | Huang, G., Luo, S.: Hybrid fast sweeping methods for anisotropic Eikonal equation in two-dimensional tilted transversely isotropic media. J. Sci. Comput. 84, Article 32 (2020) · Zbl 1450.65122 |
| [6] | Huang, L.; Shu, C-W; Zhang, M., Numerical boundary conditions for the fast sweeping high order WENO methods for solving the Eikonal equation, J. Comput. Math., 26, 1-11, 2008 · Zbl 1149.91033 · doi:10.1016/j.cam.2007.06.009 |
| [7] | Jiang, G.; Shu, C-W, Efficient implementation of weighted ENO schemes, J. Comput. Phys., 126, 202-228, 1996 · Zbl 0877.65065 · doi:10.1006/jcph.1996.0130 |
| [8] | Kao, CY; Osher, S.; Qian, J., Lax-Friedrichs sweeping scheme for static Hamilton-Jacobi equations, J. Comput. Phys., 196, 367-391, 2004 · Zbl 1053.65088 · doi:10.1016/j.jcp.2003.11.007 |
| [9] | Li, F.; Shu, C-W; Zhang, Y-T; Zhao, H-K, A second order discontinuous Galerkin fast sweeping method for Eikonal equations, J. Comput. Phys., 227, 8191-8208, 2008 · Zbl 1151.65092 · doi:10.1016/j.jcp.2008.05.018 |
| [10] | Li, L.; Zhu, J.; Shu, C-W; Zhang, Y-T, A fixed-point fast sweeping WENO method with inverse Lax-Wendroff boundary treatment for steady state of hyperbolic conservation laws, Commun. Appl. Math. Comput., 5, 403-427, 2023 · Zbl 1524.65365 · doi:10.1007/s42967-021-00179-6 |
| [11] | Li, L., Zhu, J., Zhang, Y.-T.: Absolutely convergent fixed-point fast sweeping WENO methods for steady state of hyperbolic conservation laws. J. Comput. Phys. 443, Article 110516 (2021) · Zbl 07515416 |
| [12] | Li, W.; Qian, J., Newton-type Gauss-Seidel Lax-Friedrichs high-order fast sweeping methods for solving generalized eikonal equations at large-scale discretization, Comput. Math. Appl., 79, 1222-1239, 2020 · Zbl 1443.65284 · doi:10.1016/j.camwa.2019.08.031 |
| [13] | Li, Y.; Cheng, J.; Xia, Y.; Shu, C-W, High order arbitrary Lagrangian-Eulerian finite difference WENO scheme for Hamilton-Jacobi equations, Commun. Comput. Phys., 26, 1530-1574, 2019 · Zbl 1473.65114 · doi:10.4208/cicp.2019.js60.15 |
| [14] | 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 · doi:10.1016/j.jcp.2011.02.043 |
| [15] | 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 · doi:10.1007/s10915-011-9550-y |
| [16] | 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 · doi:10.1137/120901696 |
| [17] | Miksis, ZM; Zhang, Y-T, Sparse-grid implementation of fixed-point fast sweeping WENO schemes for Eikonal equations, Commun. Appl. Math. Comput., 6, 3-29, 2024 · Zbl 07846910 · doi:10.1007/s42967-022-00209-x |
| [18] | Osher, S.; Shu, C-W, High-order essentially nonoscillatory schemes for Hamilton-Jacobi equations, SIAM J. Numer. Anal., 28, 907-922, 1991 · Zbl 0736.65066 · doi:10.1137/0728049 |
| [19] | Qian, J.; Zhang, Y-T; Zhao, H-K, Fast sweeping methods for Eikonal equations on triangular meshes, SIAM J. Numer. Anal., 45, 83-107, 2007 · Zbl 1149.65087 · doi:10.1137/050627083 |
| [20] | 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 · doi:10.1007/s10915-006-9124-6 |
| [21] | Ren, Y., Xiong, T., Qiu, J.: A hybrid finite difference WENO-ZQ fast sweeping method for static Hamilton-Jacobi equations. J. Sci. Comput. 83, Article 54 (2020) · Zbl 1440.65099 |
| [22] | Rouy, E.; Tourin, A., A viscosity solutions approach to shape-from-shading, SIAM J. Numer. Anal., 29, 867-884, 1992 · Zbl 0754.65069 · doi:10.1137/0729053 |
| [23] | Sethian, JA, A fast marching level set method for monotonically advancing fronts, Proc. Natl. Acad. Sci. USA, 93, 1591-1595, 1996 · Zbl 0852.65055 · doi:10.1073/pnas.93.4.1591 |
| [24] | Sethian, JA; Vladimirsky, A., Ordered upwind methods for static Hamilton-Jacobi equations, Proc. Natl. Acad. Sci. USA, 98, 11069-11074, 2001 · Zbl 1002.65112 · doi:10.1073/pnas.201222998 |
| [25] | 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 · doi:10.1137/S0036142901392742 |
| [26] | Shu, C-W; Osher, S., Efficient Implementation of essentially non-oscillatory shock-capturing schemes, J. Comput. Phys., 77, 439-471, 1988 · Zbl 0653.65072 · doi:10.1016/0021-9991(88)90177-5 |
| [27] | Tro, S., Evans, T.M., Aslam, T.D., Lozano, E., Culp, D.B.: A second-order distributed memory parallel fast sweeping method for the Eikonal equation. J. Comput. Phys. 474, Article 111785 (2023) · Zbl 07640544 |
| [28] | Versteeg, R., The Marmousi experience: velocity model determination on a synthetic complex data set, Lead. Edge, 13, 927-936, 1994 · doi:10.1190/1.1437051 |
| [29] | Wu, L.; Zhang, Y-T, A third order fast sweeping method with linear computational complexity for Eikonal equations, J. Sci. Comput., 62, 198-229, 2015 · Zbl 1312.65198 · doi:10.1007/s10915-014-9856-7 |
| [30] | Wu, L.; Zhang, Y-T; Zhang, S.; Shu, C-W, High order fixed-point sweeping WENO methods for steady state of hyperbolic conservation laws and its convergence study, Commun. Comput. Phys., 20, 835-869, 2016 · Zbl 1388.65068 · doi:10.4208/cicp.130715.010216a |
| [31] | Xiong, T.; Zhang, M.; Zhang, Y-T; Shu, C-W, Fast sweeping fifth order WENO scheme for static Hamilton-Jacobi equations with accurate boundary treatment, J. Sci. Comput., 45, 514-536, 2010 · Zbl 1203.65155 · doi:10.1007/s10915-010-9345-6 |
| [32] | Zhang, Y-T; Chen, S.; Li, F.; Zhao, H.; Shu, C-W, Uniformly accurate discontinuous Galerkin fast sweeping methods for Eikonal equations, SIAM J. Sci. Comput., 33, 1873-1896, 2011 · Zbl 1255.65215 · doi:10.1137/090770291 |
| [33] | Zhang, Y-T; Shu, C-W, High order WENO schemes for Hamilton-Jacobi equations on triangular meshes, SIAM J. Sci. Comput., 24, 1005-1030, 2003 · Zbl 1034.65051 · doi:10.1137/S1064827501396798 |
| [34] | Zhang, Y-T; Zhao, H-K; Chen, S., Fixed-point iterative sweeping methods for static Hamilton-Jacobi equations, Methods Appl. Anal., 13, 299-320, 2006 · Zbl 1134.65076 · doi:10.1039/D0AY02022B |
| [35] | 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 · doi:10.1007/s10915-005-9014-3 |
| [36] | Zhao, H-K, A fast sweeping method for Eikonal equations, Math. Comput., 74, 603-627, 2005 · Zbl 1070.65113 · doi:10.1090/S0025-5718-04-01678-3 |
| [37] | Zhao, H.; Osher, S.; Merriman, B.; Kang, M., Implicit and non-parametric shape reconstruction from unorganized points using variational level set method, Comput. Vis. Image Underst., 80, 295-319, 2000 · Zbl 1011.68538 · doi:10.1006/cviu.2000.0875 |
| [38] | Zhu, J.; Shu, C-W, Numerical study on the convergence to steady state solutions of a new class of high order WENO schemes, J. Comput. Phys., 349, 80-96, 2017 · Zbl 1380.76074 · doi:10.1016/j.jcp.2017.08.012 |
| [39] | Zhu, J.; Shu, C-W, A new type of multi-resolution WENO schemes with increasingly higher order of accuracy, J. Comput. Phys., 375, 659-683, 2018 · Zbl 1416.65286 · doi:10.1016/j.jcp.2018.09.003 |
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.
