Sparse-Grid Implementation of Fixed-Point Fast Sweeping WENO Schemes for Eikonal Equations

Abstract

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 (Zhang et al. 2006 [41]), 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.

Keywords

Fixed-point fast sweeping methods / Weighted essentially non-oscillatory (WENO) schemes / Sparse grids / Static Hamilton-Jacobi (H - J) equations / Eikonal equations

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., 2002, 191: 3909-3928,

[2.] Aurenhammer F. Voronoi diagrams - a survey of a fundamental geometric data structure. ACM Comput. Surv., 1991, 23: 345-405,

[3.] Bungartz H-J, Griebel M. Sparse grids. Acta Numer, 2004, 13: 147-269,

[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., 2012, 234: 452-471,

[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., 2006, 214: 698-724,

[7.] Crandall MG, Lions PL. Viscosity solutions of Hamilton–Jacobi equations. Trans. Am. Math. Soc., 1983, 277: 1-42,

[8.] Dijkstra EW. A note on two problems in connection with graphs. Numer. Math., 1959, 1: 269-271,

[9.] Fomel S, Luo S, Zhao H. Fast sweeping method for the factored eikonal equation. J. Comput. Phys., 2009, 228: 6440-6455,

[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, 2003, 71: 65-87,

[12.] Griebel M. Adaptive sparse grid multilevel methods for elliptic PDEs based on finite differences. Computing, 1998, 61: 151-179,

[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, 1992 Amsterdam North-Holland 263-281

[14.] Guo W, Cheng Y. An adaptive multiresolution discontinuous Galerkin method for time-dependent transport equations in multidimensions. SIAM J. Sci. Comput., 2017, 39: A2962-A2992,

[15.] Hegland M. Adaptive sparse grids. ANZIAM J., 2002, 44: C335-C353,

[16.] Kao CY, Osher S, Qian J. Lax-Friedrichs sweeping schemes for static Hamilton-Jacobi equations. J. Comput. Phys., 2004, 196: 367-391,

[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., 2001, 1: 86-99,

[18.] Lastdrager B, Koren B, Verwer J. The sparse-grid combination technique applied to time-dependent advection problems. Appl. Numer. Math., 2001, 38: 377-401,

[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., 2008, 227: 8191-8208,

[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., 2021, 43: 1-24 Article 110516

[21.] Lu D, Chen S, Zhang Y-T. Third order WENO scheme on sparse grids for hyperbolic equations. Pure Appl. Math. Q., 2018, 14: 57-86,

[22.] Lu D, Zhang Y-T. Krylov integration factor method on sparse grids for high spatial dimension convection-diffusion equations. J. Sci. Comput., 2016, 69: 736-763,

[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)

[24.] Nishida T, Sugihara K. Boat-sail Voronoi diagram on a curved surface. Jpn. J. Ind. Appl. Math., 2005, 22: 267-278,

[25.] Noordmans J, Hemker PW. Application of an adaptive sparse-grid technique to a model singular perturbation problem. Computing, 2000, 65: 357-378,

[26.] Obersteiner M, Bungartz H-J. A generalized spatially adaptive sparse grid combination technique with dimension-wise refinement. SIAM J. Sci. Comput., 2021, 43: A2381-A2403,

[27.] Okabe A, Boots B, Sugihara K, Chu SN. . Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, 2000 2 Wiley, Hoboken, NJ Wiley Series in Probability and Statistics,

[28.] Osher S, Shu C-W. High-order essentially nonoscillatory schemes for Hamilton-Jacobi equations. SIAM J. Numer. Anal., 1991, 28: 907-922,

[29.] Qian J, Zhang Y-T, Zhao H-K. Fast sweeping methods for Eikonal equations on triangular meshes. SIAM J. Numer. Anal., 2007, 45: 83-107,

[30.] Qian J, Zhang Y-T, Zhao H-K. A fast sweeping method for static convex Hamilton-Jacobi equations. J. Sci. Comput., 2007, 31: 237-271,

[31.] Rouy E, Tourin A. A viscosity solutions approach to shape-from-shading. SIAM J. Numer. Anal., 1992, 29: 867-884,

[32.] Sethian JA. A fast marching level set method for monotonically advancing fronts. Proc. Natl. Acad. Sci. USA, 1996, 93: 1591-1595,

[33.] Sethian JA, Vladimirsky A. Ordered upwind methods for static Hamilton-Jacobi equations. Proc. Natl. Acad. Sci. U.S.A., 2001, 98: 11069-11074,

[34.] Sethian JA, Vladimirsky A. Ordered upwind methods for static Hamilton-Jacobi equations: theory and algorithms. SIAM J. Numer. Anal., 2003, 41: 325-363,

[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)

[36.] Wu L, Zhang Y-T. A third order fast sweeping method with linear computational complexity for Eikonal equations. J. Sci. Comput., 2015, 62: 198-229,

[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., 2016, 20: 835-869,

[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., 2010, 45: 514-536,

[39.] Zenger, C.: Sparse grids. In: Hackbusch, W. (ed) Notes on Numerical Fluid Mechanics, vol. 31, pp. 241–251. Vieweg, Braunschweig (1991)

[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., 2011, 33: 1873-1896,

[41.] Zhang Y-T, Zhao H-K, Chen S. Fixed-point iterative sweeping methods for static Hamilton-Jacobi equations. Methods Appl. Anal., 2006, 13: 299-320,

[42.] Zhang Y-T, Zhao H-K, Qian J. High order fast sweeping methods for static Hamilton-Jacobi equations. J. Sci. Comput., 2006, 29: 25-56,

[43.] Zhao H-K. A fast sweeping method for Eikonal equations. Math. Comput., 2005, 74: 603-627,

[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., 2000, 80: 295-319,

[45.] Zhu X, Zhang Y-T. Fast sparse grid simulations of fifth order WENO scheme for high dimensional hyperbolic PDEs. J. Sci. Comput., 2021, 87: 1-38,

Funding

National Science Foundation(DMS-1620108)