A dynamic domain decomposition for the eikonal-diffusion equation

Simone  Cacace; Maurizio  Falcone

doi:10.3934/dcdss.2016.9.109

Article Contents

2016, Volume 9, Issue 1: 109-123. Doi: 10.3934/dcdss.2016.9.109

This issue Previous Article Discrete models for fluid-structure interactions: The finite element Immersed Boundary Method Next Article Hyperbolic equations of Von Karman type

A dynamic domain decomposition for the eikonal-diffusion equation

Simone Cacace^1, and
Maurizio Falcone^1,

1.
Dipartimento di Matematica, Sapienza Università di Roma, Piazzale Aldo Moro 5, 00185 Roma

Received: August 31, 2014

Revised: January 31, 2015

Published: January 2016

Abstract Related Papers Cited by

Abstract

We propose a parallel algorithm for the numerical solution of the eikonal-diffusion equation, by means of a dynamic domain decomposition technique. The new method is an extension of the patchy domain decomposition method presented in [5] for first order Hamilton-Jacobi-Bellman equations. Using the connection with stochastic optimal control theory, the semi-Lagrangian scheme underlying the original method is modified in order to deal with (possibly degenerate) diffusion. We show that under suitable relations between the discretization parameters and the diffusion coefficient, the parallel computation on the proposed dynamic decomposition can be faster than that on a static decomposition. Some numerical tests in dimension two are presented, in order to show the features of the proposed method.

Keywords:

Mathematics Subject Classification: Primary: 65N99, 65N55; Secondary: 49L20.

Citation:

Related Papers

Cited by

References

[1]	M. Bardi and I. Capuzzo Dolcetta, Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations, Birkhäuser, 1997.doi: 10.1007/978-0-8176-4755-1.
[2]	M. Bardi and M. Falcone, An approximation scheme for the minimum time function, SIAM Journal of Control and Optimization, 28 (1990), 950-965.doi: 10.1137/0328053.
[3]	M. Bardi and M. Falcone, Discrete approximation of the minimal time function for systems with regular optimal trajectories, in Analysis and Optimization of Systems (eds. A. Bensoussan, J.-L. Lions), Lecture Notes in Control and Information Sciences, 144, Springer-Verlag, 1990, 103-112.doi: 10.1007/BFb0120033.
[4]	S. Cacace, E. Cristiani and M. Falcone, Two semi-lagrangian fast methods for Hamilton-Jacobi-Bellman equations, in System Modeling and Optimization (eds. C. Pötzsche, et al.), 443, Springer, 2014, 74-84.doi: 10.1007/978-3-662-45504-3_7.
[5]	S. Cacace, E. Cristiani, M. Falcone and A. Picarelli, A patchy dynamic programming scheme for a class of Hamilton-Jacobi-Bellman equations, SIAM Journal on Scientific Computing, 34 (2012), 2625-2649.doi: 10.1137/110841576.
[6]	S. Cacace and M. Falcone, A dynamic domain decomposition for a class of second order semi-linear equations, in preparation, arXiv:1502.01629.
[7]	F. Camilli and M. Falcone, An approximation scheme for the optimal control of diffusion processes, Mathematical Modelling and Numerical Analysis, 29 (1995), 97-122.
[8]	F. Camilli, M. Falcone, P. Lanucara and A. Seghini, A domain decomposition method for Bellman equations, in Domain Decomposition methods in Scientific and Engineering Computing (eds. D. E. Keyes and J. Xu), Contemporary Mathematics, 180, AMS, 1994, 477-483.doi: 10.1090/conm/180/02008.
[9]	M. Falcone and R. Ferretti, Semi-Lagrangian Approximation Schemes for Linear and Hamilton-Jacobi Equations, SIAM, 2014.
[10]	M. Falcone, P. Lanucara and A. Seghini, A splitting algorithm for Hamilton-Jacobi-Bellman equations, Applied Numerical Mathematics, 15 (1994), 207-218.doi: 10.1016/0168-9274(94)00017-4.
[11]	A. Quarteroni and A. Valli, Numerical Approximation of Partial Differential Equations, Oxford University Press, 1999.
[12]	A. Quarteroni and A. Valli, Domain Decomposition Methods for Partial Differential Equations, Springer, 2008.
[13]	J. A. Sethian, A fast marching level set method for monotonically advancing fronts, Proc. Natl. Acad. Sci. USA, 93 (1996), 1591-1595.doi: 10.1073/pnas.93.4.1591.
[14]	J. A. Sethian, Level Set Methods and Fast Marching Methods, Cambridge University Press, 1999.
[15]	J. A. Sethian and A. Vladimirsky, Ordered upwind methods for static Hamilton-Jacobi equations: Theory and algorithms, SIAM J. Numer. Anal., 41 (2003), 325-363.doi: 10.1137/S0036142901392742.
[16]	Y. Tsai, L. Cheng, S. Osher and H. Zhao, Fast sweeping algorithms for a class of Hamilton-Jacobi equations, SIAM J. Numer. Anal., 41 (2003), 673-694.doi: 10.1137/S0036142901396533.
[17]	J. N. Tsitsiklis, Efficient algorithms for globally optimal trajectories, IEEE Trans. Autom. Control, 40 (1995), 1528-1538.doi: 10.1109/9.412624.
[18]	H. Zhao, A fast sweeping method for Eikonal equations, Math. Comp., 74 (2005), 603-627.doi: 10.1090/S0025-5718-04-01678-3.