A penalty-regularization-operator splitting method for the numerical solution of a scalar Eikonal equation

Abstract

In this article, we discuss a numerical method for the computation of the minimal and maximal solutions of a steady scalar Eikonal equation. This method relies on a penalty treatment of the nonlinearity, a biharmonic regularization of the resulting variational problem, and the time discretization by operator-splitting of an initial value problem associated with the Euler-Lagrange equations of the regularized variational problem. A low-order finite element discretization is advocated since it is well-suited to the low regularity of the solutions. Numerical experiments show that the method sketched above can capture efficiently the extremal solutions of various two-dimensional test problems and that it has also the ability of handling easily domains with curved boundaries.

Keywords

Eikonal equation / Minimal and maximal solutions / Regularization methods / Penalization of equality constraints / Dynamical flow / Operator splitting / Finite element methods

References

[1] Aronsson G., Evans L. C., Wu Y.. Fast/slow diffusion and growing sandpiles. Journal of Differential Equations, 1996, 131: 304-335

[2] Barth T. J., Sethian J. A.. Numerical schemes for the Hamilton-Jacobi and level set equations on triangulated domains. J. Comput. Phys., 1998, 145(1): 1-40

[3] Caboussat A., Glowinski R.. A numerical method for a non-smooth advection-diffusion problem arising in sand mechanics. Commun. Pure Appl. Anal, 2008, 8(1): 161-178

[4] Caboussat A., Glowinski R.. Regularization methods for the divergence equation ▽ · u = f. J. Comput. Math, 2012, 30(4): 354-380.

[5] Caboussat A., Glowinski R., Pan T. W.. On the numerical solution of some Eikonal equations: An elliptic solver approach, to appear of Contemporary Applied Mathematics, 2013, Beijing and World Scientific, Singapore: Higher Education Press

[6] Caboussat A., Glowinski R., Sorensen D. C.. A least-squares method for the numerical solution of the Dirichlet problem for the elliptic Monge-Ampère equation in dimension two. ESIAM: Control, Optimization and Calculus of Variations, 2013, 19(3): 780-810

[7] Caffarelli L., Crandall M. G.. Distance functions and almost global solutions of Eikonal equations. Comm. Partial Differential Equations, 2010, 3: 391-414

[8] Caffarelli, L. A. and Cabré, X., Fully Nonlinear Elliptic Equations, American Mathematical Society Colloquium Publications, 43, Providence, RI,1995.

[9] Caffarelli L. A., Glowinski R.. Numerical solution of the Dirichlet problem for a Pucci equation in dimension two. Application to homogenization. J. Numer. Math., 2008, 16(3): 185-216

[10] Chan T., Shen J.. Image Processing and Analysis: Variational, PDE, Wavelet, and Stochastic Methods, 2005

[11] Crandall M., Evans L., Lions P. L.. Some properties of viscosity solutions of Hamilton-Jacobi equations. Trans. Amer. Math. Soc., 1984, 282: 487-502

[12] Dacorogna B., Glowinski R., Kuznetzov Y., Pan T. W.. Křížek M., Neittaanmäki P., Glowinski R., Korotov S.. On a conjuguate gradient/Newton/penalty method for the solution of obstacle problems. application to the solution of an Eikonal system with Dirichlet boundary conditions. Conjugate Gradient Algorithms and Finite Element Methods, 2004, Berlin, Heidelberg: Springer-Verlag 263-283

[13] Dacorogna B., Glowinski R., Pan T. W.. Numerical methods for the solution of a system of Eikonal equations with Dirichlet boundary conditions. C. R. Acad. Sci. Paris, Sér. I, 2003, 336: 511-518

[14] Dacorogna B., Marcellini P.. Implicit Partial Differential Equations, 1999

[15] Dacorogna B., Marcellini P., Paolini E.. An explicit solution to a system of implicit differential equations. Ann. Inst. Henri Poincaré, Analyse Non Linéaire, 2008, 25: 163-171

[16] Dacorogna B., Marcellini P., Paolini E.. Lipschitz-continuous local isometric immersions: Rigid maps and origami. Journal Math. Pures Appl., 2008, 90: 66-81

[17] Dacorogna B., Marcellini P., Paolini E.. Origami and partial differential equations. Notices of the American Math. Soc., 2010, 57: 598-606

[18] Dean E. J., Glowinski R.. Numerical methods for fully nonlinear elliptic equations of the Monge-Ampère type. Comp. Meth. Appl. Mech. Engrg., 2006, 195: 1344-1386

[19] Dean E. J., Glowinski R.. On the numerical solution of the elliptic Monge-Ampère equation in dimension two: A least-squares approach. Partial Differential Equations: Modeling and Numerical Simulation, 2008, 16: 43-63

[20] Dean E. J., Glowinski R., Guidoboni G.. On the numerical simulation of Bingham visco-plastic flow: Old and new results. Journal of Non Newtonian Fluid Mechanics, 2007, 142: 36-62

[21] Delbos F., Gilbert J. C., Glowinski R., Sinoquet D.. Constrained optimization in seismic reflection tomography: A Gauss-Newton augmented Lagrangian approach. Geophysical Journal International, 2006, 164: 670-684

[22] Evans L. C.. Partial Differential Equations, 19, Graduate Texts in Mathematics. American Mathematical Society, 1998

[23] Flück M., Hofer T., Picasso M. Scientific computing for aluminum production. Int. J. Numer. Anal. and Modeling, 2009, 6(3): 489-504

[24] Glowinski, R., Finite Element Method for Incompressible Viscous Flow, IX, Handbook of Numerical Analysis (Ciarlet, P. G., Lions, J. L., eds), Elsevier, Amsterdam, 2003, 3–1176.

[25] Glowinski R.. Numerical Methods for Nonlinear Variational Problems, 2008, New York, NY: Springer-Verlag

[26] Glowinski R.. Numerical methods for fully nonlinear elliptic equations, Invited Lectures. Congress on Industrial and Applied Mathematics, 2009 155-192

[27] Glowinski R., Kuznetzov Y., Pan T. W.. A penalty/Newton/conjugate gradient method for the solution of obstacle problems. C. R. Acad. Sci. Paris, Sér. I, 2003, 336: 435-440

[28] Glowinski R., Lions J. L., Trémolières R.. Numerical Analysis of Variational Inequalities. Studies in Mathematics and Its Applications, 1981, Amsterdam, New York: North-Holland Publishing Co.

[29] Gremaud P. A., Ide N. R.. Computation of nonclassical solutions to Hamilton-Jacobi problems. SIAM J. Sci. Comput., 1999, 21: 502-521

[30] Gremaud P. A., Kuster C. M.. Computational study of fast methods for the Eikonal equation. SIAM J. Sci. Comp., 2006, 27: 1803-1816

[31] Hysing S. R., Turek S.. The Eikonal equation: Numerical efficiency vs algorithmic complexity on quadrilateral grids. Proceedings of Algorithmy, 2005 22-31

[32] Kimmel R., Sethian J. A.. Computing geodesic paths on manifolds. Proceedings of National Academy of Sciences, 1998, 95(15): 8431-8435

[33] Majava K., Glowinski R., Kärkkäinen T.. Solving a non-smooth eigenvalue problem using operatorsplitting methods. International Journal of Computer Mathematics, 2007, 84(6): 825-84

[34] Nečas J.. Introduction to the Theory of Nonlinear Elliptic Equations, 1986, Chichester: JohnWiley & Sons, Ltd.

[35] Prigozhin L.. Sandpiles and rivers networks: Extended systems with nonlocal interactions. Phys. Rev. E, 1994, 49(2): 1161-1167

[36] Prigozhin L.. Variational model of sandpile growth. Euro. Journal of Applied Mathematics, 1996, 7: 225-235

[37] Qin F., Luo Y., Olsen K. Finite-difference solution of the Eikonal equation along expanding wavefronts. Geophysics, 1992, 57(3): 478-487

[38] Rockafellar R. T.. Convex Analysis, 1997, Princeton, NJ: Princeton University Press

[39] Schlichting H., Gersten K.. Boundary Layer Theory, McGraw and Hill, 2000, Berlin: Springer-Verlag

[40] Sethian J. A.. Fast marching methods. SIAM Rev., 1999, 41(2): 199-235

[41] Sethian J. A., Vladimirsky A.. Fast methods for the Eikonal and related Hamilton-Jacobi equations on unstructured meshes. Proceedings of National Academy of Sciences, 2000, 11: 5699-5703

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