High order edge sensors with \(\ell^1\) regularization for enhanced discontinuous Galerkin methods. (English) Zbl 1416.65377
Summary: This paper investigates the use of \(\ell^1\) regularization for solving hyperbolic conservation laws based on high order discontinuous Galerkin (DG) approximations. We first use the polynomial annihilation method to construct a high order edge sensor which enables us to flag “troubled” elements. The DG approximation is enhanced in these troubled regions by activating \(\ell^1\) regularization to promote sparsity in the corresponding jump function of the numerical solution. The resulting \(\ell^1\) optimization problem is efficiently implemented using the alternating direction method of multipliers. By enacting \(\ell^1\) regularization only in troubled cells, our method remains accurate and efficient, as no additional regularization or expensive iterative procedures are needed in smooth regions. We present results for the inviscid Burgers’ equation as well as a nonlinear system of conservation laws using a nodal collocation-type DG method as a solver.
MSC:
| 65M70 | Spectral, collocation and related methods for initial value and initial-boundary value problems involving PDEs |
| 65M12 | Stability and convergence of numerical methods for initial value and initial-boundary value problems involving PDEs |
| 65K10 | Numerical optimization and variational techniques |
| 76L05 | Shock waves and blast waves in fluid mechanics |
| 65M60 | Finite element, Rayleigh-Ritz and Galerkin methods for initial value and initial-boundary value problems involving PDEs |
| 35L65 | Hyperbolic conservation laws |
Keywords:
discontinuous Galerkin; \(\ell^1\) regularization; polynomial annihilation; shock capturing; discontinuity sensor; hyperbolic conservation lawsReferences:
| [1] | Y. Allaneau and A. Jameson, Connections between the filtered discontinuous Galerkin method and the flux reconstruction approach to high order discretizations, Comput. Methods Appl. Mech. Engrg., 200 (2011), pp. 3628-3636. · Zbl 1239.65061 |
| [2] | R. Archibald, A. Gelb, and R. B. Platte, Image reconstruction from undersampled Fourier data using the polynomial annihilation transform, J. Sci. Comput., 67 (2016), pp. 432-452. · Zbl 1339.65026 |
| [3] | R. Archibald, A. Gelb, R. Saxena, and D. Xiu, Discontinuity detection in multivariate space for stochastic simulations, J. Comput. Phys., 228 (2009), pp. 2676-2689. · Zbl 1161.65307 |
| [4] | R. Archibald, A. Gelb, and J. Yoon, Polynomial fitting for edge detection in irregularly sampled signals and images, SIAM J. Numer. Anal., 43 (2005), pp. 259-279. · Zbl 1093.41009 |
| [5] | R. Archibald, A. Gelb, and J. Yoon, Determining the locations and discontinuities in the derivatives of functions, Appl. Numer. Math., 58 (2008), pp. 577-592. · Zbl 1141.65011 |
| [6] | G. E. Barter and D. L. Darmofal, Shock capturing with PDE-based artificial viscosity for DGFEM: Part I. Formulation, J. Comput. Phys., 229 (2010), pp. 1810-1827. · Zbl 1329.76153 |
| [7] | F. Bassi and S. Rebay, Accurate 2D Euler computations by means of a high order discontinuous finite element method, in Fourteenth International Conference on Numerical Methods in Fluid Dynamics, Springer, New York, 1995, pp. 234-240. · Zbl 0850.76344 |
| [8] | E. J. Candes, M. B. Wakin, and S. P. Boyd, Enhancing sparsity by reweighted \(\ell_1\) minimization, J. Fourier Anal. Appl., 14 (2008), pp. 877-905. · Zbl 1176.94014 |
| [9] | B. Cockburn and C.-W. Shu, TVB Runge-Kutta local projection discontinuous Galerkin finite element method for conservation laws. II. General framework, Math. Comp., 52 (1989), pp. 411-435. · Zbl 0662.65083 |
| [10] | P. J. Davis and P. Rabinowitz, Methods of Numerical Integration, Courier Corporation, Chelmsford, MA, 2007. · Zbl 1139.65016 |
| [11] | D. De Grazia, G. Mengaldo, D. Moxey, P. Vincent, and S. Sherwin, Connections between the discontinuous Galerkin method and high-order flux reconstruction schemes, Internat. J. Numer. Methods Fluids, 75 (2014), pp. 860-877. · Zbl 1455.65161 |
| [12] | A. Dervieux, D. Leservoisier, P.-L. George, and Y. Coudière, About theoretical and practical impact of mesh adaptation on approximation of functions and PDE solutions, Internat. J. Numer. Methods Fluids, 43 (2003), pp. 507-516. · Zbl 1032.76666 |
| [13] | W.-S. Don, Z. Gao, P. Li, and X. Wen, Hybrid compact-WENO finite difference scheme with conjugate Fourier shock detection algorithm for hyperbolic conservation laws, SIAM J. Sci. Comput., 38 (2016), pp. A691-A711. · Zbl 1382.65241 |
| [14] | J. Eckstein and D. P. Bertsekas, On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program., 55 (1992), pp. 293-318. · Zbl 0765.90073 |
| [15] | M. Feistauer and V. Kučera, On a robust discontinuous Galerkin technique for the solution of compressible flow, J. Comput. Phys., 224 (2007), pp. 208-221. · Zbl 1114.76042 |
| [16] | D. Gabay and B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite element approximation, Comput. Math. Appl., 2 (1976), pp. 17-40. · Zbl 0352.65034 |
| [17] | G. J. Gassner, A skew-symmetric discontinuous galerkin spectral element discretization and its relation to SBP-SAT finite difference methods, SIAM J. Sci. Comput., 35 (2013), pp. A1233-A1253. · Zbl 1275.65065 |
| [18] | G. J. Gassner, A kinetic energy preserving nodal discontinuous galerkin spectral element method, Internat. J. Numer. Methods Fluids, 76 (2014), pp. 28-50. · Zbl 1455.76142 |
| [19] | A. Gelb and D. Cates, Detection of edges in spectral data III. Refinement of the concentration method, J. Sci. Comput., 36 (2008), pp. 1-43. · Zbl 1203.94009 |
| [20] | A. Gelb and T. Scarnati, Reducing effects of bad data using variance based joint sparsity recovery, in preparation. · Zbl 1410.65120 |
| [21] | A. Gelb and E. Tadmor, Detection of edges in spectral data, Appl. Comput. Harmon. Anal., 7 (1999), pp. 101-135. · Zbl 0952.42001 |
| [22] | A. Gelb and E. Tadmor, Detection of edges in spectral data II. Nonlinear enhancement, SIAM J. Numer. Anal., 38 (2000), pp. 1389-1408. · Zbl 0990.42025 |
| [23] | A. Gelb and E. Tadmor, Adaptive edge detectors for piecewise smooth data based on the minmod limiter, J. Sci. Comput., 28 (2006), pp. 279-306. · Zbl 1103.65143 |
| [24] | J. Glaubitz, A. Nogueira, J. Almeida, R. Canta͂o, and C. Silva, Smooth and compactly supported viscous sub-cell shock capturing for discontinuous Galerkin methods, J. Sci. Comput., 79 (2019), pp. 249-272. · Zbl 1464.65120 |
| [25] | J. Glaubitz, P. Öffner, and T. Sonar, Application of modal filtering to a spectral difference method, Math. Comp., 87 (2018), pp. 175-207. · Zbl 1376.65133 |
| [26] | R. Glowinski and P. Le Tallec, Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics, Stud. Appl. Numer. Math. 9, SIAM, Philadelphia, PA, 1989. · Zbl 0698.73001 |
| [27] | R. Glowinski and A. Marroco, Sur l’approximation, par éléments finis d’ordre un, et la résolution, par pénalisation-dualité d’une classe de problèmes de Dirichlet non linéaires, Rev. Française Automat., Inform., Recherche Opér. Anal. Numér., 9 (1975), pp. 41-76. · Zbl 0368.65053 |
| [28] | T. Goldstein and S. Osher, The split Bregman method for l1-regularized problems, SIAM J. Imaging Sci., 2 (2009), pp. 323-343. · Zbl 1177.65088 |
| [29] | S. Gottlieb and C.-W. Shu, Total variation diminishing Runge-Kutta schemes, Math. Comp., 67 (1998), pp. 73-85. · Zbl 0897.65058 |
| [30] | J.-L. Guermond, F. Marpeau, and B. Popov, A fast algorithm for solving first-order PDEs by \(L1\)-minimization, Commun. Math. Sci., 6 (2008), pp. 199-216. · Zbl 1143.65060 |
| [31] | J.-L. Guermond and R. Pasquetti, Entropy-based nonlinear viscosity for Fourier approximations of conservation laws, C. R. Math., 346 (2008), pp. 801-806. · Zbl 1145.65079 |
| [32] | R. Hartmann, Adaptive discontinuous Galerkin methods with shock-capturing for the compressible Navier-Stokes equations, Internat. J. Numer. Methods Fluids, 51 (2006), pp. 1131-1156. · Zbl 1106.76041 |
| [33] | J. Hesthaven and R. Kirby, Filtering in Legendre spectral methods, Math. Comp., 77 (2008), pp. 1425-1452. · Zbl 1195.65138 |
| [34] | J. S. Hesthaven and T. Warburton, Nodal Discontinuous Galerkin Methods: Algorithms, Analysis, and Applications, Springer, New York, 2007. · Zbl 1134.65068 |
| [35] | E. Hewitt and R. E. Hewitt, The Gibbs-Wilbraham phenomenon: An episode in Fourier analysis, Arch. History Exact Sci., 21 (1979), pp. 129-160. · Zbl 0424.42002 |
| [36] | T. Y. Hou, Q. Li, and H. Schaeffer, Sparse+ low-energy decomposition for viscous conservation laws, J. Comput. Phys., 288 (2015), pp. 150-166. · Zbl 1352.65413 |
| [37] | A. Huerta, E. Casoni, and J. Peraire, A simple shock-capturing technique for high-order discontinuous Galerkin methods, Internat. J. Numer. Methods Fluids, 69 (2012), pp. 1614-1632. · Zbl 1253.76058 |
| [38] | H. T. Huynh, A Flux Reconstruction Approach to High-Order Schemes Including Discontinuous Galerkin Methods, AIAA paper 4079, AIAA, Reston, VA, 2007. |
| [39] | J. Jaffre, C. Johnson, and A. Szepessy, Convergence of the discontinuous Galerkin finite element method for hyperbolic conservation laws, Math. Models Methods Appl. Sci., 5 (1995), pp. 367-386. · Zbl 0834.65089 |
| [40] | J. D. Jakeman, R. Archibald, and D. Xiu, Characterization of discontinuities in high-dimensional stochastic problems on adaptive sparse grids, J. Comput. Phys., 230 (2011), pp. 3977-3997. · Zbl 1218.65010 |
| [41] | A. Jameson, W. Schmidt, and E. Turkel, Numerical solution of the Euler equations by finite volume methods using Runge Kutta time stepping schemes, in Proceedings of the 14th Fluid and Plasma Dynamics Conference, 1981, p. 1259. |
| [42] | A. Klöckner, T. Warburton, and J. S. Hesthaven, Viscous shock capturing in a time-explicit discontinuous Galerkin method, Math. Model. Nat. Phenom., 6 (2011), pp. 57-83. · Zbl 1220.65165 |
| [43] | D. A. Kopriva, Implementing Spectral Methods for Partial Differential Equations: Algorithms for Scientists and Engineers, Springer, New York, 2009. · Zbl 1172.65001 |
| [44] | D. A. Kopriva and G. J. Gassner, An energy stable discontinuous Galerkin spectral element discretization for variable coefficient advection problems, SIAM J. Sci. Comput., 36 (2014), pp. A2076-A2099. · Zbl 1303.65086 |
| [45] | L. Krivodonova, J. Xin, J.-F. Remacle, N. Chevaugeon, and J. E. Flaherty, Shock detection and limiting with discontinuous Galerkin methods for hyperbolic conservation laws, Appl. Numer. Math., 48 (2004), pp. 323-338. · Zbl 1038.65096 |
| [46] | J. Lavery, Solution of steady-state one-dimensional conservation laws by mathematical programming, SIAM J. Numer. Anal., 26 (1989), pp. 1081-1089. · Zbl 0679.65063 |
| [47] | J. E. Lavery, Solution of steady-state, two-dimensional conservation laws by mathematical programming, SIAM J. Numer. Anal., 28 (1991), pp. 141-155. · Zbl 0743.65084 |
| [48] | C. Li, W. Yin, H. Jiang, and Y. Zhang, An efficient augmented Lagrangian method with applications to total variation minimization, Comput. Optim. Appl., 56 (2013), pp. 507-530. · Zbl 1287.90066 |
| [49] | Y. Liu, M. Vinokur, and Z. Wang, Spectral difference method for unstructured grids I: Basic formulation, J. Comput. Phys., 216 (2006), pp. 780-801. · Zbl 1097.65089 |
| [50] | J. Nordström, Conservative finite difference formulations, variable coefficients, energy estimates and artificial dissipation, J. Sci. Comput., 29 (2006), pp. 375-404. · Zbl 1109.65076 |
| [51] | P. Öffner, J. Glaubitz, and H. Ranocha, Stability of correction procedure via reconstruction with summation-by-parts operators for burgers’ equation using a polynomial chaos approach, ESAIM Math. Model. Numer. Anal., 52 (2018), pp. 2215-2245. · Zbl 1420.65094 |
| [52] | P. Öffner, T. Sonar, and M. Wirz, Detecting strength and location of jump discontinuities in numerical data, Appl. Math., 4 (2013), pp. 1-14. |
| [53] | P.-O. Persson and J. Peraire, Sub-cell shock capturing for discontinuous Galerkin methods, in Proceedings of the 44th AIAA Aerospace Sciences Meeting and Exhibit, 2006. |
| [54] | M. P. Pettersson, G. Iaccarino, and J. Nordström, Polynomial Chaos Methods for Hyperbolic Partial Differential Equations: Numerical Techniques for Fluid Dynamics Problems in the Presence of Uncertainties, Springer, New York, 2015. · Zbl 1325.76004 |
| [55] | P. Pettersson, G. Iaccarino, and J. Nordström, Numerical analysis of the Burgersâ equation in the presence of uncertainty, J. Comput. Phys., 228 (2009), pp. 8394-8412. · Zbl 1177.65017 |
| [56] | J. Qiu and C.-W. Shu, A comparison of troubled-cell indicators for Runge-Kutta discontinuous Galerkin methods using weighted essentially nonoscillatory limiters, SIAM J. Sci. Comput., 27 (2005), pp. 995-1013. · Zbl 1092.65084 |
| [57] | J. L. Randall, Numerical Methods for Conservation Laws, Lectures in Math. ETH Zürich, Springer, New York, 1992. · Zbl 0847.65053 |
| [58] | H. Ranocha, J. Glaubitz, P. Öffner, and T. Sonar, Stability of artificial dissipation and modal filtering for flux reconstruction schemes using summation-by-parts operators, Appl. Numer. Math., 128 (2018), pp. 1-23. · Zbl 1404.65201 |
| [59] | T. Sanders, MATLAB Imaging Algorithms: Image Reconstruction, Restoration, and Alignment, with a Focus in Tomography, 2016, . |
| [60] | T. Sanders, A. Gelb, and R. B. Platte, Composite SAR imaging using sequential joint sparsity, J. Comput. Phys., 338 (2017), pp. 357-370. · Zbl 1415.65050 |
| [61] | T. Scarnati, A. Gelb, and R. B. Platte, Using \(\ell_1\) regularization to improve numerical partial differential equation solvers, J. Sci. Comput., 75 (2018), pp. 225-252. · Zbl 1395.65032 |
| [62] | H. Schaeffer, R. Caflisch, C. D. Hauck, and S. Osher, Sparse dynamics for partial differential equations, Proc. Nat. Acad. Sci., 110 (2013), pp. 6634-6639. · Zbl 1292.35012 |
| [63] | C.-W. Shu and S. Osher, Efficient implementation of essentially non-oscillatory shock-capturing schemes, J. Comput. Phys., 77 (1988), pp. 439-471. · Zbl 0653.65072 |
| [64] | C.-W. Shu and S. Osher, Efficient implementation of essentially‘ non-oscillatory shock-capturing schemes, II, J. Comput. Phys., 83 (1989), pp. 32-78. · Zbl 0674.65061 |
| [65] | W. Stefan, R. A. Renaut, and A. Gelb, Improved total variation-type regularization using higher order edge detectors, SIAM J. Imaging Sci., 3 (2010), pp. 232-251. · Zbl 1195.41007 |
| [66] | E. Tadmor, Shock capturing by the spectral viscosity method, Comput. Methods Appl. Mech. Engrg., 80 (1990), pp. 197-208. · Zbl 0729.65073 |
| [67] | E. Tadmor, M. Baines, and K. Morton, Super viscosity and spectral approximations of nonlinear conservation laws, in Numerical Methods for Fluid Dynamics IV, Clarendon Press, Oxford, UK, 1993, pp. 69-82. · Zbl 0805.76057 |
| [68] | E. Tadmor and K. Waagan, Adaptive spectral viscosity for hyperbolic conservation laws, SIAM J. Sci. Comput., 34 (2012), pp. A993-A1009. · Zbl 1250.65113 |
| [69] | E. F. Toro, Riemann Solvers and Numerical Methods for Fluid Dynamics: A Practical Introduction, Springer, New York, 2013. |
| [70] | J. von Neumann and R. D. Richtmyer, A method for the numerical calculation of hydrodynamic shocks, J. Appl. Phys., 21 (1950), pp. 232-237. · Zbl 0037.12002 |
| [71] | Z. Wang, Y. Liu, G. May, and A. Jameson, Spectral difference method for unstructured grids II: Extension to the Euler equations, J. Sci. Comput., 32 (2007), pp. 45-71. · Zbl 1151.76543 |
| [72] | G. Wasserman, R. Archibald, and A. Gelb, Image reconstruction from Fourier data using sparsity of edges, J. Sci. Comput., 65 (2015), pp. 533-552. · Zbl 1355.94010 |
| [73] | M. Yu and Z. Wang, On the connection between the correction and weighting functions in the correction procedure via reconstruction method, J. Sci. Comput., 54 (2013), pp. 227-244. · Zbl 1259.65154 |
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.
