Search

We present a new algorithm, the efficient jet marching method (EJM), for computing the quasipotential and its gradient for two-dimensional SDEs. The quasipotential is a potential-like function for nongradient SDEs that gives asymptotic estimates for the invariant probability measure, expected escape times from basins of attractors, and maximum likelihood escape paths. The quasipotential is a solution to an optimal control problem with an anisotropic cost function which can be solved for numerically via Dijkstra-like label-setting methods. Previous Dijkstra-like quasipotential solvers have displayed in general 1st order accuracy in the mesh spacing. However, by utilizing higher order interpolations of the quasipotential as well as more accurate approximations of the minimum action paths (MAPs), EJM achieves second-order accuracy for the quasipotential and nearly second-order for its gradient. Moreover, by using targeted search neighborhoods for the fastest characteristics following the ideas of Mirebeau, EJM also enjoys a reduction in computation time. This highly accurate solver enables us to compute the prefactor for the WKB approximation for the invariant probability measure and the Bouchet-Reygner sharp estimate for the expected escape time for the Maier-Stein SDE. Our codes are available on GitHub., Comment: 21 figures, 3 tables

We present a family of fast and accurate Dijkstra-like solvers for the eikonal equation and factored eikonal equation which compute solutions on a regular grid by solving local variational minimization problems. Our methods converge linearly but compute significantly more accurate solutions than competing first order methods. In 3D, we present two different families of algorithms which significantly reduce the number of FLOPs needed to obtain an accurate solution to the eikonal equation. One method employs a fast search using local characteristic directions to prune unnecessary updates, and the other uses the theory of constrained optimization to achieve the same end. The proposed solvers are more efficient than the standard fast marching method in terms of the relationship between error and CPU time. We also modify our method for use with the additively factored eikonal equation, which can be solved locally around point sources to maintain linear convergence. We conduct extensive numerical simulations and provide theoretical justification for our approach. A library that implements the proposed solvers is available on GitHub., Comment: 43 pages, 21 figures. Submitted to Springer Journal of Scientific Computing