American Institute of Mathematical Sciences

Advanced
February  2016, 9(1): 109-123. doi: 10.3934/dcdss.2016.9.109

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, Italy, Italy

Received  September 2014 Revised  February 2015 Published  December 2015

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: Hamilton-Jacobi equations, eikonal-diffusion equation, semi-Lagrangian schemes, Domain decomposition, stochastic optimal control..
Mathematics Subject Classification: Primary: 65N99, 65N55; Secondary: 49L2.
Citation: Simone Cacace, Maurizio Falcone. A dynamic domain decomposition for the eikonal-diffusion equation. Discrete & Continuous Dynamical Systems - S, 2016, 9 (1) : 109-123. doi: 10.3934/dcdss.2016.9.109
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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[6]

S. Cacace and M. Falcone, A dynamic domain decomposition for a class of second order semi-linear equations,, in preparation, ().   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[9]

M. Falcone and R. Ferretti, Semi-Lagrangian Approximation Schemes for Linear and Hamilton-Jacobi Equations, SIAM, 2014.  Google Scholar

[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.  Google Scholar

[11]

A. Quarteroni and A. Valli, Numerical Approximation of Partial Differential Equations, Oxford University Press, 1999.  Google Scholar

[12]

A. Quarteroni and A. Valli, Domain Decomposition Methods for Partial Differential Equations, Springer, 2008. Google Scholar

[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.  Google Scholar

[14]

J. A. Sethian, Level Set Methods and Fast Marching Methods, Cambridge University Press, 1999.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[17]

J. N. Tsitsiklis, Efficient algorithms for globally optimal trajectories, IEEE Trans. Autom. Control, 40 (1995), 1528-1538. doi: 10.1109/9.412624.  Google Scholar

[18]

H. Zhao, A fast sweeping method for Eikonal equations, Math. Comp., 74 (2005), 603-627. doi: 10.1090/S0025-5718-04-01678-3.  Google Scholar

show all references

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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[6]

S. Cacace and M. Falcone, A dynamic domain decomposition for a class of second order semi-linear equations,, in preparation, ().   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[9]

M. Falcone and R. Ferretti, Semi-Lagrangian Approximation Schemes for Linear and Hamilton-Jacobi Equations, SIAM, 2014.  Google Scholar

[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.  Google Scholar

[11]

A. Quarteroni and A. Valli, Numerical Approximation of Partial Differential Equations, Oxford University Press, 1999.  Google Scholar

[12]

A. Quarteroni and A. Valli, Domain Decomposition Methods for Partial Differential Equations, Springer, 2008. Google Scholar

[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.  Google Scholar

[14]

J. A. Sethian, Level Set Methods and Fast Marching Methods, Cambridge University Press, 1999.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[17]

J. N. Tsitsiklis, Efficient algorithms for globally optimal trajectories, IEEE Trans. Autom. Control, 40 (1995), 1528-1538. doi: 10.1109/9.412624.  Google Scholar

[18]

H. Zhao, A fast sweeping method for Eikonal equations, Math. Comp., 74 (2005), 603-627. doi: 10.1090/S0025-5718-04-01678-3.  Google Scholar

[1]

Joan-Andreu Lázaro-Camí, Juan-Pablo Ortega. The stochastic Hamilton-Jacobi equation. Journal of Geometric Mechanics, 2009, 1 (3) : 295-315. doi: 10.3934/jgm.2009.1.295
[2]

Olivier Bokanowski, Maurizio Falcone, Roberto Ferretti, Lars Grüne, Dante Kalise, Hasnaa Zidani. Value iteration convergence of $\epsilon$-monotone schemes for stationary Hamilton-Jacobi equations. Discrete & Continuous Dynamical Systems, 2015, 35 (9) : 4041-4070. doi: 10.3934/dcds.2015.35.4041
[3]

Tomoki Ohsawa, Anthony M. Bloch. Nonholonomic Hamilton-Jacobi equation and integrability. Journal of Geometric Mechanics, 2009, 1 (4) : 461-481. doi: 10.3934/jgm.2009.1.461
[4]

Nalini Anantharaman, Renato Iturriaga, Pablo Padilla, Héctor Sánchez-Morgado. Physical solutions of the Hamilton-Jacobi equation. Discrete & Continuous Dynamical Systems - B, 2005, 5 (3) : 513-528. doi: 10.3934/dcdsb.2005.5.513
[5]

María Barbero-Liñán, Manuel de León, David Martín de Diego, Juan C. Marrero, Miguel C. Muñoz-Lecanda. Kinematic reduction and the Hamilton-Jacobi equation. Journal of Geometric Mechanics, 2012, 4 (3) : 207-237. doi: 10.3934/jgm.2012.4.207
[6]

Larry M. Bates, Francesco Fassò, Nicola Sansonetto. The Hamilton-Jacobi equation, integrability, and nonholonomic systems. Journal of Geometric Mechanics, 2014, 6 (4) : 441-449. doi: 10.3934/jgm.2014.6.441
[7]

Melvin Leok, Diana Sosa. Dirac structures and Hamilton-Jacobi theory for Lagrangian mechanics on Lie algebroids. Journal of Geometric Mechanics, 2012, 4 (4) : 421-442. doi: 10.3934/jgm.2012.4.421
[8]

Claudio Marchi. On the convergence of singular perturbations of Hamilton-Jacobi equations. Communications on Pure & Applied Analysis, 2010, 9 (5) : 1363-1377. doi: 10.3934/cpaa.2010.9.1363
[9]

Isabeau Birindelli, J. Wigniolle. Homogenization of Hamilton-Jacobi equations in the Heisenberg group. Communications on Pure & Applied Analysis, 2003, 2 (4) : 461-479. doi: 10.3934/cpaa.2003.2.461
[10]

Holger Heumann, Ralf Hiptmair. Eulerian and semi-Lagrangian methods for convection-diffusion for differential forms. Discrete & Continuous Dynamical Systems, 2011, 29 (4) : 1471-1495. doi: 10.3934/dcds.2011.29.1471
[11]

Daniel Guo, John Drake. A global semi-Lagrangian spectral model for the reformulated shallow water equations. Conference Publications, 2003, 2003 (Special) : 375-385. doi: 10.3934/proc.2003.2003.375
[12]

Yoshikazu Giga, Przemysław Górka, Piotr Rybka. Nonlocal spatially inhomogeneous Hamilton-Jacobi equation with unusual free boundary. Discrete & Continuous Dynamical Systems, 2010, 26 (2) : 493-519. doi: 10.3934/dcds.2010.26.493
[13]

Nicolas Forcadel, Mamdouh Zaydan. A comparison principle for Hamilton-Jacobi equation with moving in time boundary. Evolution Equations & Control Theory, 2019, 8 (3) : 543-565. doi: 10.3934/eect.2019026
[14]

Yuxiang Li. Stabilization towards the steady state for a viscous Hamilton-Jacobi equation. Communications on Pure & Applied Analysis, 2009, 8 (6) : 1917-1924. doi: 10.3934/cpaa.2009.8.1917
[15]

Alexander Quaas, Andrei Rodríguez. Analysis of the attainment of boundary conditions for a nonlocal diffusive Hamilton-Jacobi equation. Discrete & Continuous Dynamical Systems, 2018, 38 (10) : 5221-5243. doi: 10.3934/dcds.2018231
[16]

Renato Iturriaga, Héctor Sánchez-Morgado. Limit of the infinite horizon discounted Hamilton-Jacobi equation. Discrete & Continuous Dynamical Systems - B, 2011, 15 (3) : 623-635. doi: 10.3934/dcdsb.2011.15.623
[17]

Laura Caravenna, Annalisa Cesaroni, Hung Vinh Tran. Preface: Recent developments related to conservation laws and Hamilton-Jacobi equations. Discrete & Continuous Dynamical Systems - S, 2018, 11 (5) : i-iii. doi: 10.3934/dcdss.201805i
[18]

Fabio Camilli, Paola Loreti, Naoki Yamada. Systems of convex Hamilton-Jacobi equations with implicit obstacles and the obstacle problem. Communications on Pure & Applied Analysis, 2009, 8 (4) : 1291-1302. doi: 10.3934/cpaa.2009.8.1291
[19]

Yasuhiro Fujita, Katsushi Ohmori. Inequalities and the Aubry-Mather theory of Hamilton-Jacobi equations. Communications on Pure & Applied Analysis, 2009, 8 (2) : 683-688. doi: 10.3934/cpaa.2009.8.683
[20]

Olga Bernardi, Franco Cardin. On $C^0$-variational solutions for Hamilton-Jacobi equations. Discrete & Continuous Dynamical Systems, 2011, 31 (2) : 385-406. doi: 10.3934/dcds.2011.31.385

2020 Impact Factor: 2.425

Tools

Metrics

  • PDF downloads (111)
  • HTML views (1)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences