Numerical analysis for conservation laws using \(l_1\) minimization. (English) Zbl 1433.65176

The authors develop and analyze a new numerical scheme for solving hyperbolic conservation laws that combines the Lax Wendroff method with \(l_1\) regularization. The method developed here adds a new critical conservation constraint. The resulting method is proved to be equivalent to the well known lasso problem, guaranteeing both existence and uniqueness of the numerical solution. Consistency, convergence, and conservation of the suggested scheme are proved. It is shown that the scheme is TVD (Total Variation Diminishing) and it satisfies the weak entropy condition for conservation laws. Some numerical tests are presented to support the theoretical results.


65M08 Finite volume methods for initial value and initial-boundary value problems involving PDEs
65M15 Error bounds for initial value and initial-boundary value problems involving PDEs
65K10 Numerical optimization and variational techniques
35Q31 Euler equations


SPGL1; glmnet
Full Text: DOI


[1] Archibald, R.; Gelb, A.; Platte, RB, Image reconstruction from undersampled Fourier data using the polynomial annihilation transform, J. Sci. Comput., 67, 432-452 (2016) · Zbl 1339.65026
[2] Archibald, R.; Gelb, A.; Yoon, J., Polynomial fitting for edge detection in irregularly sampled signals and images, SIAM J. Numer. Anal., 43, 259-279 (2005) · Zbl 1093.41009
[3] Arvanitis, C.; Makridakis, C.; Sfakianakis, NI, Entropy conservative schemes and adaptive mesh selection for hyperbolic conservation laws, J. Hyperb. Differ. Equ., 07, 383-404 (2010) · Zbl 1204.65118
[4] Candes, EJ; Wakin, MB; Boyd, SP, Enhancing sparsity by reweighted \(\ell_1\) minimization, J. Fourier Anal. Appl., 14, 877-905 (2008) · Zbl 1176.94014
[5] Don, W-S; Gao, Z.; Li, P.; Wen, X., Hybrid compact-WENO finite difference scheme with conjugate Fourier shock detection algorithm for hyperbolic conservation laws, SIAM J. Sci. Comput., 38, a691-a711 (2016) · Zbl 1382.65241
[6] Friedman, J.; Hastie, T.; Tibshirani, R., Regularization paths for generalized linear models via coordinate descent, J. Stat. Softw., 33, 1-22 (2010)
[7] Gottlieb, D.; Shu, C-W, On the Gibbs phenomenon and its resolution, SIAM Rev., 39, 644-668 (1997) · Zbl 0885.42003
[8] Guermond, J-L; Marpeau, F.; Popov, B., A fast algorithm for solving first-order PDEs by l1-minimization, Commun. Math. Sci., 6, 199-216 (2008) · Zbl 1143.65060
[9] Gustafsson, B., Kreiss, H.-O., Oliger, J.: Time-Dependent Problems and Difference. Wiley, London (2013) · Zbl 1275.65048
[10] Hou, TY; Li, Q.; Schaeffer, H., Sparse + low-energy decomposition for viscous conservation laws, J. Comput. Phys., 288, 150-166 (2015) · Zbl 1352.65413
[11] Lavery, JE, Solution of steady-state one-dimensional conservation laws by mathematical programming, SIAM J. Numer. Anal., 26, 1081-1089 (1989) · Zbl 0679.65063
[12] Lavery, JE, Solution of steady-state, two-dimensional conservation laws by mathematical programming, SIAM J. Numer. Anal., 28, 141-155 (1991) · Zbl 0743.65084
[13] LeVeque, R.J.: Numerical Methods for Conservation Laws. Springer, Berlin (1992) · Zbl 0847.65053
[14] LeVeque, R.J.: Finite Volume Methods for Hyperbolic Problems. Cambridge Texts in Applied Mathematics. Cambridge University Press, Cambridge (2002)
[15] LeVeque, R.J.: Finite Difference Methods for Ordinary and Partial Differential Equations: Steady-State and Time-Dependent Problems. Society for Industrial and Applied Mathematics, Philadelphia (2007) · Zbl 1127.65080
[16] Liska, R.; Wendroff, B., Composite schemes for conservation laws, SIAM J. Numer. Anal., 35, 2250-2271 (1998) · Zbl 0920.65054
[17] Scarnati, T.; Gelb, A.; Platte, RB, Using \(l1\) regularization to improve numerical partial differential equation solvers, J. Sci. Comput., 75, 225-252 (2018) · Zbl 1395.65032
[18] Schaeffer, H.; Caflisch, R.; Hauck, CD; Osher, S., Sparse dynamics for partial differential equations, Proc. Nat. Acad. Sci., 110, 6634-6639 (2013) · Zbl 1292.35012
[19] Shu, C-W; Wong, PS, A note on the accuracy of spectral method applied to nonlinear conservation laws, J. Sci. Comput., 10, 357-369 (1995) · Zbl 0840.65103
[20] Tadmor, E., Convergence of spectral methods for nonlinear conservation laws, SIAM J. Numer. Anal., 26, 30-44 (1989) · Zbl 0667.65079
[21] Tadmor, E., Shock capturing by the spectral viscosity method, Comput. Methods Appl. Mech. Eng., 80, 197-208 (1990) · Zbl 0729.65073
[22] Tadmor, E.; Waagan, K., Adaptive spectral viscosity for hyperbolic conservation laws, SIAM J. Sci. Comput., 34, a993-a1009 (2012) · Zbl 1250.65113
[23] Tibshirani, RJ, The lasso problem and uniqueness, Electron. J. Stat., 7, 1456-1490 (2013) · Zbl 1337.62173
[24] van den Berg, E., Friedlander, M. P.: SPGL1: a solver for large-scale sparse reconstruction (2007, June). http://www.cs.ubc.ca/labs/scl/spgl1
[25] Berg, E.; Friedlander, MP, Probing the pareto frontier for basis pursuit solutions, SIAM J. Sci. Comput., 31, 890-912 (2008) · Zbl 1193.49033
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.