Parallel redistancing using the Hopf-Lax formula. (English) Zbl 1395.65118
Summary: We present a parallel method for solving the eikonal equation associated with level set redistancing. Fast marching and fast sweeping are the most popular redistancing methods due to their efficiency and relative simplicity. However, these methods require propagation of information from the zero-isocontour outwards, and this data dependence complicates efficient implementation on today’s multiprocessor hardware. Recently an interesting alternative view has been developed that utilizes the Hopf-Lax formulation of the solution to the eikonal equation [the third author et al., ibid. 330, 268–281 (2017; Zbl 1378.35292); J. Darbon and the last author, Res. Math. Sci. 3, Paper No. 19, 26 p. (2016; Zbl 1348.49026)]. In this approach, the signed distance at an arbitrary point is obtained without the need of distance information from neighboring points. We extend the work of the third author et al. [J. Comput. Phys. 330, 268–281 (2017; Zbl 1378.35292)] to redistance functions defined via interpolation over a regular grid. The grid-based definition is essential for practical application in level set methods. We demonstrate the effectiveness of our approach with GPU parallelism on a number of representative examples.
MSC:
| 65M99 | Numerical methods for partial differential equations, initial value and time-dependent initial-boundary value problems |
| 65K10 | Numerical optimization and variational techniques |
| 65Y05 | Parallel numerical computation |
References:
| [1] | Tsitsiklis, J. N., Efficient algorithms for globally optimal trajectories, IEEE Trans. Autom. Control, 40, 9, 1528-1538, (1995) · Zbl 0831.93028 |
| [2] | Sethian, J. A., A fast marching level set method for monotonically advancing fronts, Proc. Natl. Acad. Sci., 93, 4, 1591-1595, (1996) · Zbl 0852.65055 |
| [3] | Zhao, H., A fast sweeping method for eikonal equations, Math. Comput., 74, 250, 603-627, (2005) · Zbl 1070.65113 |
| [4] | Lee, B.; Darbon, J.; Osher, S.; Kang, M., Revisiting the redistancing problem using the Hopf-Lax formula, J. Comp. Physiol., 330, 268-281, (2017) · Zbl 1378.35292 |
| [5] | Darbon, J.; Osher, S., Algorithms for overcoming the curse of dimensionality for certain Hamilton-Jacobi equations arising in control theory and elsewhere, Res. Math. Sci., 3, 1, 19, (2016) · Zbl 1348.49026 |
| [6] | Osher, S.; Sethian, J. A., Fronts propagating with curvature-dependent speed: algorithms based on Hamilton-Jacobi formulations, J. Comp. Physiol., 79, 1, 12-49, (1988) · Zbl 0659.65132 |
| [7] | Osher, S.; Fedkiw, R. P., Level set methods and dynamic implicit surfaces, Applied Mathematical Sciences, (2003), Springer New York, N.Y. · Zbl 1026.76001 |
| [8] | Sussman, M.; Smereka, P.; Osher, S., A level set approach for computing solutions to incompressible two-phase flow, J. Comput. Phys., 114, 1, 146-159, (1994) · Zbl 0808.76077 |
| [9] | Russo, G.; Smereka, P., A remark on computing distance functions, J. Comput. Phys., 163, 1, 51-67, (2000) · Zbl 0964.65089 |
| [10] | Crandall, M. G.; Lions, P.-L., Two approximations of solutions of Hamilton-Jacobi equations, Math. Comput., 43, 167, 1-19, (1984) · Zbl 0556.65076 |
| [11] | Dijkstra, E. W., A note on two problems in connexion with graphs, Numer. Math., 1, 1, 269-271, (1959) · Zbl 0092.16002 |
| [12] | Zhao, H., Parallel implementations of the fast sweeping method, J. Comput. Math., 421-429, (2007) |
| [13] | Detrixhe, M.; Gibou, F.; Min, C., A parallel fast sweeping method for the eikonal equation, J. Comput. Phys., 237, 46-55, (2013) |
| [14] | Detrixhe, M.; Gibou, F., Hybrid massively parallel fast sweeping method for static Hamilton-Jacobi equations, J. Comput. Phys., 322, 199-223, (2016) · Zbl 1352.65624 |
| [15] | Herrmann, M., A domain decomposition parallelization of the fast marching method, (2003), Tech. rep., DTIC Document |
| [16] | Yang, J.; Stern, F., A highly scalable massively parallel fast marching method for the eikonal equation, J. Comput. Phys., 332, 333-362, (2017) · Zbl 1380.65329 |
| [17] | Jeong, W.-k.; Whitaker, R., A fast eikonal equation solver for parallel systems, (SIAM Conf. Comp. Sci. Eng., Citeseer, (2007)) |
| [18] | Breuß, M.; Cristiani, E.; Gwosdek, P.; Vogel, O., An adaptive domain-decomposition technique for parallelization of the fast marching method, Appl. Math. Comput., 218, 1, 32-44, (2011) · Zbl 1269.65132 |
| [19] | Dang, F.; Emad, N., Fast iterative method in solving eikonal equations: a multi-level parallel approach, Proc. Comput. Sci., 29, 1859-1869, (2014) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
