Reconstruction of independent sub-domains for a class of Hamilton–Jacobi equations and application to parallel computing
ESAIM: Mathematical Modelling and Numerical Analysis , Volume 50 (2016) no. 4, pp. 1223-1240.

A previous knowledge of the domains of dependence of a Hamilton–Jacobi equation can be useful in its study and approximation. Information of this nature is, in general, difficult to obtain directly from the data of the problem. In this paper we formally introduce the concept of an independent sub-domain, discuss its main properties and provide a constructive implicit representation formula. Through these results, we propose an algorithm for the approximation of these sets that is shown to be relevant in the numerical resolution, via parallel computing.

Received:
Accepted:
DOI: 10.1051/m2an/2015070
Classification: 49L25, 65N55, 49M27
Keywords: Hamilton–Jacobi equations, viscosity solutions, numerical approximation, parallel computing, domain decomposition
Festa, Adriano 1

1 RICAM – Johann Radon Institute for Computational and Applied Mathematics, Austrian Academy of Sciences (ÖAW) Altenberger Straße 4040 Linz, Austria.
@article{M2AN_2016__50_4_1223_0,
     author = {Festa, Adriano},
     title = {Reconstruction of independent sub-domains for a class of {Hamilton{\textendash}Jacobi} equations and application to parallel computing},
     journal = {ESAIM: Mathematical Modelling and Numerical Analysis },
     pages = {1223--1240},
     publisher = {EDP-Sciences},
     volume = {50},
     number = {4},
     year = {2016},
     doi = {10.1051/m2an/2015070},
     mrnumber = {3535237},
     zbl = {1347.49044},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/m2an/2015070/}
}
TY  - JOUR
AU  - Festa, Adriano
TI  - Reconstruction of independent sub-domains for a class of Hamilton–Jacobi equations and application to parallel computing
JO  - ESAIM: Mathematical Modelling and Numerical Analysis 
PY  - 2016
SP  - 1223
EP  - 1240
VL  - 50
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/m2an/2015070/
DO  - 10.1051/m2an/2015070
LA  - en
ID  - M2AN_2016__50_4_1223_0
ER  - 
%0 Journal Article
%A Festa, Adriano
%T Reconstruction of independent sub-domains for a class of Hamilton–Jacobi equations and application to parallel computing
%J ESAIM: Mathematical Modelling and Numerical Analysis 
%D 2016
%P 1223-1240
%V 50
%N 4
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/m2an/2015070/
%R 10.1051/m2an/2015070
%G en
%F M2AN_2016__50_4_1223_0
Festa, Adriano. Reconstruction of independent sub-domains for a class of Hamilton–Jacobi equations and application to parallel computing. ESAIM: Mathematical Modelling and Numerical Analysis , Volume 50 (2016) no. 4, pp. 1223-1240. doi : 10.1051/m2an/2015070. http://www.numdam.org/articles/10.1051/m2an/2015070/

F. Ancona and A. Bressan, Patchy vector fields and asymptotic stabilization. ESAIM: COCV 4 (1999) 445–471. | Numdam | MR | Zbl

M. Bardi and M. Falcone, An approximation scheme for the minimum time function. SIAM J. Control Optim. 28 (1990) 950–965. | DOI | MR | Zbl

M. Bardi and I.C.-Dolcetta, Optimal control and viscosity solutions of Hamilton–Jacobi–Bellman equations. Systems and Control: Foundations and Applications. Birkhäuser, Boston (1997). | MR | Zbl

M. Bardi, M. Falcone and P. Soravia, Numerical methods for pursuit-evasion games via viscosity solutions. In Stochastic and differential games. Birkhauser, Boston (1999) 105–175. | MR | Zbl

G. Barles, Solutions de viscosité des équations de Hamilton-Jacobi. Vol. 17 of Math. Appl. Springer, Paris (1994). | MR | Zbl

S. Cacace, E. Cristiani and M. Falcone, A local ordered upwind method for Hamilton–Jacobi and Isaacs equations. In Proc. of 18th IFAC World Congress (2011) 6800–6805.

S. Cacace, E. Cristiani, M. Falcone and A. Picarelli, A patchy dynamic programming scheme for a class of Hamilton–Jacobi–Bellman equations. SIAM J. Sci. Comput. 34 (2012) A2625–A2649. | DOI | MR | Zbl

F. Camilli, M. Falcone, P. Lanucara and A. Seghini, A domain decomposition method for bellman equations. In Vol. 180, Domain Decomposition methods in Scientific and Engineering Computing. Contemp. Math. (1994) 477–483. | MR | Zbl

P. Cannarsa and C. Sinestrari, Semiconcave functions, Hamilton–Jacobi equations, and optimal control. In Vol. 58 Progress Nonlin. Differ. Eq. Appl. Birkhäuser, Boston, MA (2004). | MR | Zbl

E. Carlini, M. Falcone, N. Forcadel and R. Monneau, Convergence of a generalized fast-marching method for an eikonal equation with a velocity-changing sign. SIAM J. Numer. Anal. 46 (2008) 2920–2952. | DOI | MR | Zbl

M. Detrixhe, F. Gibou and C. Min, A parallel fast sweeping method for the eikonal equation. J. Comput. Phys. 237 (2013) 46–55. | DOI | MR

I. Capuzzo Dolcetta and H. Ishii, Approximate solutions of the Bellman equation of deterministic control theory. Appl. Math. Optim. 11 (1984) 161–181. | DOI | MR | Zbl

R.J. Elliott and N.J. Kalton, The existence of value in differential games, Bull. Amer. Math. Soc. 78 (1972) 427–431. | DOI | MR | Zbl

M. Falcone, A numerical approach to the infinite horizon problem of deterministic control theory. Appl. Math. Optim. 15 (1987) 1–13. | DOI | MR | Zbl

M. Falcone and R. Ferretti, Convergence analysis for a class of high-order semi-Lagrangian advection schemes. SIAM J. Numer. Anal. 35 (1998) 909–940. | DOI | MR | Zbl

M. Falcone and R. Ferretti, Semi-Lagrangian Approximation Schemes for Linear and Hamilton–Jacobi Equations. Appl. Math. SIAM, Philadelphia (2014). | MR

A. Festa and R.B. Vinter, A decomposition technique for pursuit evasion games with many pursuers. 52nd IEEE Control and Decision Conference CDC (2013) 5797–5802.

A. Festa and R.B. Vinter, Decomposition of differential games with multiple targets. J. Optim. Theory Appl. 169 (2016) 848–875. | DOI | MR | Zbl

C. Navasca and A.J. Krener, Patchy solutions of Hamilton–Jacobi-Bellman partial differential equations. In Vol. 364 of Modeling, Estimation and Control. Lect. Notes Control Inform. Sci., edited by A. Chiuso, A. Ferrante, and S. Pinzoni. Springer, Berlin (2007) 251–270. | MR | Zbl

P. Soravia, Estimates of convergence of fully discrete schemes for the Isaacs equation of pursuit-evasion differential games via maximum principle. SIAM J. Control Optim. 36 (1998) 1–11. | DOI | MR | Zbl

M. Sun, Domain decomposition algorithms for solving hamilton–jacobi–bellman equations. Numer. Func. Anal. Optim. 14 (1993) 145–166. | DOI | MR | Zbl

A. Valli and A. Quarteroni, Domain decomposition methods for partial differential equations. Oxford University Press, Oxford (1999). | MR | Zbl

R.B. Vinter, Optimal Control Theory. Birkhäuser, Boston Heidelberg (2000). | MR

H. Zhao, Parallel implementations of the fast sweeping method. J. Comput. Math. 25 (2007) 421–429. | MR

S. Zhou and W. Zhan, A new domain decomposition method for an hjb equation. J. Comput. Appl. Math. 159 (2003) 195–204. | DOI | MR | Zbl

Cited by Sources: