An Efficient Data Structure and Accurate Scheme to Solve Front Propagation Problems

作者：Bokanowski O^*; Cristiani E; Zidani H

来源：Journal of Scientific Computing, 2010, 42(2): 251-273.

DOI：10.1007/s10915-009-9329-6

• Ultra Bee scheme
• Narrow band method
• Sparse matrices
• Data storage
• Hamilton-Jacobi-Bellman equations
• Front propagation
• Level set methods

In this paper, we are interested in some front propagation problems coming from control problems in d-dimensional spaces, with da parts per thousand yen2. As opposed to the usual level set method, we localize the front as a discontinuity of a characteristic function. The evolution of the front is computed by solving an Hamilton-Jacobi-Bellman equation with discontinuous data, discretized by means of the antidissipative Ultra Bee scheme.
We develop an efficient dynamic storage technique suitable for handling front evolutions in large dimension. Then we propose a fast algorithm, showing its relevance on several challenging tests in dimension d=2,3,4. We also compare our method with the techniques usually used in level set methods. Our approach leads to a computational cost as well as a memory allocation scaling as O(N (nb) ) in most situations, where N (nb) is the number of grid nodes around the front. Moreover, we show on several examples the accuracy of our approach when compared with level set methods.

• 出版日期2010-2
• 单位INRIA