A multigraph-based selective update method for the efficient solution of dynamic programming

We consider a class of nonlinear equations that are related to the numerical solution of the Hamilton-Jacobi-Bellman equation for dynamic programming. Equations of this class can be solved with a simple fixed-point iteration, however this method may have slow convergence. We present two main contributions for increasing the efficiency of the solution: a simple preconditioning, inspired by the Jacobi method, and a selective node update procedure that reduces the number of required elementary operations.