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 and 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.

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

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.

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

[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 and 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 and 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 and 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 and Applied Analysis, 2003, 2 (4) : 461-479. doi: 10.3934/cpaa.2003.2.461
[10]

Gonzalo Dávila. Comparison principles for nonlocal Hamilton-Jacobi equations. Discrete and Continuous Dynamical Systems, 2022  doi: 10.3934/dcds.2022061
[11]

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

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
[13]

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

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

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

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

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

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

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

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

2021 Impact Factor: 1.865

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy