Finite Differences on Sparse Grids for Continuous-Time Heterogeneous Agent Models
We present a finite difference method working on sparse grids to solve higher dimensional heterogeneous agent models. If one wants to solve the arising Hamilton–Jacobi–Bellman equation on a standard full grid, one faces the problem that the number of grid points grows exponentially with the number o...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-01-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/18/1/40 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832589418516447232 |
|---|---|
| author | Jochen Garcke Steffen Ruttscheidt |
| author_facet | Jochen Garcke Steffen Ruttscheidt |
| author_sort | Jochen Garcke |
| collection | DOAJ |
| description | We present a finite difference method working on sparse grids to solve higher dimensional heterogeneous agent models. If one wants to solve the arising Hamilton–Jacobi–Bellman equation on a standard full grid, one faces the problem that the number of grid points grows exponentially with the number of dimensions. Discretizations on sparse grids only involve <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi mathvariant="script">O</mi><mo>(</mo><mi>N</mi><msup><mrow><mo>(</mo><mo form="prefix">log</mo><mi>N</mi><mo>)</mo></mrow><mrow><mi>d</mi><mo>−</mo><mn>1</mn></mrow></msup><mo>)</mo></mrow></semantics></math></inline-formula> degrees of freedom in comparison to the <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi mathvariant="script">O</mi><mo>(</mo><msup><mi>N</mi><mi>d</mi></msup><mo>)</mo></mrow></semantics></math></inline-formula> degrees of freedom of conventional methods, where <i>N</i> denotes the number of grid points in one coordinate direction and <i>d</i> is the dimension of the problem. While one can show convergence for the used finite difference method on full grids by using the theory introduced by Barles and Souganidis, we explain why one cannot simply use their results for sparse grids. Our numerical studies show that our method converges to the full grid solution for a two-dimensional model. We analyze the convergence behavior for higher dimensional models and experiment with different sparse grid adaptivity types. |
| format | Article |
| id | doaj-art-9ec5d6f936e54968ac07703cc98d4875 |
| institution | Kabale University |
| issn | 1999-4893 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj-art-9ec5d6f936e54968ac07703cc98d48752025-01-24T13:17:34ZengMDPI AGAlgorithms1999-48932025-01-011814010.3390/a18010040Finite Differences on Sparse Grids for Continuous-Time Heterogeneous Agent ModelsJochen Garcke0Steffen Ruttscheidt1Institut für Numerische Simulation, Universität Bonn, 53111 Bonn, GermanyInstitut für Numerische Simulation, Universität Bonn, 53111 Bonn, GermanyWe present a finite difference method working on sparse grids to solve higher dimensional heterogeneous agent models. If one wants to solve the arising Hamilton–Jacobi–Bellman equation on a standard full grid, one faces the problem that the number of grid points grows exponentially with the number of dimensions. Discretizations on sparse grids only involve <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi mathvariant="script">O</mi><mo>(</mo><mi>N</mi><msup><mrow><mo>(</mo><mo form="prefix">log</mo><mi>N</mi><mo>)</mo></mrow><mrow><mi>d</mi><mo>−</mo><mn>1</mn></mrow></msup><mo>)</mo></mrow></semantics></math></inline-formula> degrees of freedom in comparison to the <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi mathvariant="script">O</mi><mo>(</mo><msup><mi>N</mi><mi>d</mi></msup><mo>)</mo></mrow></semantics></math></inline-formula> degrees of freedom of conventional methods, where <i>N</i> denotes the number of grid points in one coordinate direction and <i>d</i> is the dimension of the problem. While one can show convergence for the used finite difference method on full grids by using the theory introduced by Barles and Souganidis, we explain why one cannot simply use their results for sparse grids. Our numerical studies show that our method converges to the full grid solution for a two-dimensional model. We analyze the convergence behavior for higher dimensional models and experiment with different sparse grid adaptivity types.https://www.mdpi.com/1999-4893/18/1/40sparse gridsHamilton–Jacobi–Bellman equationhigh-dimensional approximation |
| spellingShingle | Jochen Garcke Steffen Ruttscheidt Finite Differences on Sparse Grids for Continuous-Time Heterogeneous Agent Models Algorithms sparse grids Hamilton–Jacobi–Bellman equation high-dimensional approximation |
| title | Finite Differences on Sparse Grids for Continuous-Time Heterogeneous Agent Models |
| title_full | Finite Differences on Sparse Grids for Continuous-Time Heterogeneous Agent Models |
| title_fullStr | Finite Differences on Sparse Grids for Continuous-Time Heterogeneous Agent Models |
| title_full_unstemmed | Finite Differences on Sparse Grids for Continuous-Time Heterogeneous Agent Models |
| title_short | Finite Differences on Sparse Grids for Continuous-Time Heterogeneous Agent Models |
| title_sort | finite differences on sparse grids for continuous time heterogeneous agent models |
| topic | sparse grids Hamilton–Jacobi–Bellman equation high-dimensional approximation |
| url | https://www.mdpi.com/1999-4893/18/1/40 |
| work_keys_str_mv | AT jochengarcke finitedifferencesonsparsegridsforcontinuoustimeheterogeneousagentmodels AT steffenruttscheidt finitedifferencesonsparsegridsforcontinuoustimeheterogeneousagentmodels |