×

Sparse-grid implementation of fixed-point fast sweeping WENO schemes for eikonal equations. (English) Zbl 07846910

Summary: Fixed-point fast sweeping methods are a class of explicit iterative methods developed in the literature to efficiently solve steady-state solutions of hyperbolic partial differential equations (PDEs). As other types of fast sweeping schemes, fixed-point fast sweeping methods use the Gauss-Seidel iterations and alternating sweeping strategy to cover characteristics of hyperbolic PDEs in a certain direction simultaneously in each sweeping order. The resulting iterative schemes have a fast convergence rate to steady-state solutions. Moreover, an advantage of fixed-point fast sweeping methods over other types of fast sweeping methods is that they are explicit and do not involve the inverse operation of any nonlinear local system. Hence, they are robust and flexible, and have been combined with high-order accurate weighted essentially non-oscillatory (WENO) schemes to solve various hyperbolic PDEs in the literature. For multidimensional nonlinear problems, high-order fixed-point fast sweeping WENO methods still require quite a large amount of computational costs. In this technical note, we apply sparse-grid techniques, an effective approximation tool for multidimensional problems, to fixed-point fast sweeping WENO methods for reducing their computational costs. Here, we focus on fixed-point fast sweeping WENO schemes with third-order accuracy [Y.-T. Zhang et al., Methods Appl. Anal. 13, No. 3, 299–320 (2006; Zbl 1134.65076)], for solving Eikonal equations, an important class of static Hamilton-Jacobi (H-J) equations. Numerical experiments on solving multidimensional Eikonal equations and a more general static H-J equation are performed to show that the sparse-grid computations of the fixed-point fast sweeping WENO schemes achieve large savings of CPU times on refined meshes, and at the same time maintain comparable accuracy and resolution with those on corresponding regular single grids.

MSC:

65N06 Finite difference methods for boundary value problems involving PDEs
65N22 Numerical solution of discretized equations for boundary value problems involving PDEs
35L99 Hyperbolic equations and hyperbolic systems

Citations:

Zbl 1134.65076

References:

[1] Alves, MA; Cruz, P.; Mendes, A.; Magalhães, FD; Pinho, FT; Oliveira, PJ, Adaptive multiresolution approach for solution of hyperbolic PDEs, Comput. Methods Appl. Mech. Eng., 191, 3909-3928, (2002) · Zbl 1010.65042 · doi:10.1016/S0045-7825(02)00334-1
[2] Aurenhammer, F., Voronoi diagrams - a survey of a fundamental geometric data structure, ACM Comput. Surv., 23, 345-405, (1991) · doi:10.1145/116873.116880
[3] Bungartz, H-J; Griebel, M., Sparse grids, Acta Numer, 13, 147-269, (2004) · Zbl 1118.65388 · doi:10.1017/S0962492904000182
[4] Chen, W.; Chou, C-S; Kao, C-Y, Lax-Friedrichs fast sweeping methods for steady state problems for hyperbolic conservation laws, J. Comput. Phys., 234, 452-471, (2012) · Zbl 1284.35275 · doi:10.1016/j.jcp.2012.10.008
[5] Chew, L.P., Drysdale, R.L.: Voronoi diagrams based on convex distance functions. In: SCG ’85: Proceedings of the First Annual Symposium and Computational Geometry, New York, NY, Association for Computing Machinery, pp. 235-244 (1985)
[6] Chou, C-S; Shu, C-W, High order residual distribution conservative finite difference WENO schemes for steady state problems on non-smooth meshes, J. Comput. Phys., 214, 698-724, (2006) · Zbl 1093.65102 · doi:10.1016/j.jcp.2005.10.007
[7] 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
[8] Dijkstra, EW, A note on two problems in connection with graphs, Numer. Math., 1, 269-271, (1959) · Zbl 0092.16002 · doi:10.1007/BF01386390
[9] 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
[10] Garcke, J.: Sparse grids in a nutshell. In: Garcke, J., Griebel, M. (eds) Sparse Grids and Applications, Lecture Notes in Computational Science and Engineering, vol. 88, pp. 57-80. Springer, New York (2013)
[11] Gerstner, T.; Griebel, M., Dimension-adaptive tensor-product quadrature, Computing, 71, 65-87, (2003) · Zbl 1030.65015 · doi:10.1007/s00607-003-0015-5
[12] Griebel, M., Adaptive sparse grid multilevel methods for elliptic PDEs based on finite differences, Computing, 61, 151-179, (1998) · Zbl 0918.65078 · doi:10.1007/BF02684411
[13] Griebel, M.; Schneider, M.; Zenger, C.; Beauwens, R.; de Groen, P., A combination technique for the solution of sparse grid problems, Iterative methods in linear algebra, 263-281, (1992), Amsterdam: North-Holland, Amsterdam · Zbl 0785.65101
[14] Guo, W.; Cheng, Y., An adaptive multiresolution discontinuous Galerkin method for time-dependent transport equations in multidimensions, SIAM J. Sci. Comput., 39, A2962-A2992, (2017) · Zbl 1379.65077 · doi:10.1137/16M1083190
[15] Hegland, M., Adaptive sparse grids, ANZIAM J., 44, C335-C353, (2002) · Zbl 1078.65520 · doi:10.21914/anziamj.v44i0.685
[16] Kao, CY; Osher, S.; Qian, J., Lax-Friedrichs sweeping schemes for static Hamilton-Jacobi equations, J. Comput. Phys., 196, 367-391, (2004) · Zbl 1053.65088 · doi:10.1016/j.jcp.2003.11.007
[17] Lastdrager, B.; Koren, B.; Verwer, J., Solution of time-dependent advection-diffusion problems with the sparse-grid combination technique and a Rosenbrock solver, Comput. Methods Appl. Math., 1, 86-99, (2001) · Zbl 1029.76038 · doi:10.2478/cmam-2001-0006
[18] Lastdrager, B.; Koren, B.; Verwer, J., The sparse-grid combination technique applied to time-dependent advection problems, Appl. Numer. Math., 38, 377-401, (2001) · Zbl 0984.65087 · doi:10.1016/S0168-9274(01)00030-7
[19] 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
[20] 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., 43, 1-24, (2021) · Zbl 07515416
[21] Lu, D.; Chen, S.; Zhang, Y-T, Third order WENO scheme on sparse grids for hyperbolic equations, Pure Appl. Math. Q., 14, 57-86, (2018) · Zbl 1422.65148 · doi:10.4310/PAMQ.2018.v14.n1.a3
[22] Lu, D.; Zhang, Y-T, Krylov integration factor method on sparse grids for high spatial dimension convection-diffusion equations, J. Sci. Comput., 69, 736-763, (2016) · Zbl 1370.65045 · doi:10.1007/s10915-016-0216-7
[23] Nishida, T., Sugihara, K.: Voronoi diagram in a flow field. In: Ibaraki, T., Katoh, N., Ono, H. (eds) Algorithms and Computation, ISAAC 2003 Lecture Notes in Computer Science, vol. 2906, pp. 26-35. Berlin, Springer (2003) · Zbl 1205.68469
[24] Nishida, T.; Sugihara, K., Boat-sail Voronoi diagram on a curved surface, Jpn. J. Ind. Appl. Math., 22, 267-278, (2005) · Zbl 1104.68125 · doi:10.1007/BF03167442
[25] Noordmans, J.; Hemker, PW, Application of an adaptive sparse-grid technique to a model singular perturbation problem, Computing, 65, 357-378, (2000) · Zbl 0986.65118 · doi:10.1007/s006070070005
[26] Obersteiner, M.; Bungartz, H-J, A generalized spatially adaptive sparse grid combination technique with dimension-wise refinement, SIAM J. Sci. Comput., 43, A2381-A2403, (2021) · Zbl 07378157 · doi:10.1137/20M1325885
[27] Okabe, A.; Boots, B.; Sugihara, K.; Chu, SN, Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, (2000), Wiley, Hoboken, NJ: Wiley Series in Probability and Statistics, Wiley, Hoboken, NJ · Zbl 0946.68144 · doi:10.1002/9780470317013
[28] 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
[29] 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
[30] 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
[31] 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
[32] 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
[33] Sethian, JA; Vladimirsky, A., Ordered upwind methods for static Hamilton-Jacobi equations, Proc. Natl. Acad. Sci. U.S.A., 98, 11069-11074, (2001) · Zbl 1002.65112 · doi:10.1073/pnas.201222998
[34] 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
[35] Shu, C.-W.: Essentially non-oscillatory and weighted essentially non-oscillatory schemes for hyperbolic conservation laws. In: Quarteroni, A. (ed) Advanced Numerical Approximation of Nonlinear Hyperbolic Equations, Lecture Notes in Mathematics, vol. 1697, pp. 325-432. Springer-Verlag, New York (1998) · Zbl 0927.65111
[36] 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
[37] 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
[38] Xiong, T.; Zhang, M.; Zhang, Y-T; Shu, C-W, Fifth order fast sweeping 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
[39] Zenger, C.: Sparse grids. In: Hackbusch, W. (ed) Notes on Numerical Fluid Mechanics, vol. 31, pp. 241-251. Vieweg, Braunschweig (1991) · Zbl 0763.65091
[40] 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
[41] 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
[42] 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
[43] 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
[44] 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
[45] Zhu, X.; Zhang, Y-T, Fast sparse grid simulations of fifth order WENO scheme for high dimensional hyperbolic PDEs, J. Sci. Comput., 87, 1-38, (2021) · Zbl 1473.65131 · doi:10.1007/s10915-021-01444-9
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.