Level set and fast marching methods are new and versatile methods for analysing interface motions. In recent years these methods have found applications in a large number of fields in fluid mechanics, image processing, materials sciences, fabrication of microelectronic devices, control theory, shape optimisation and computational geometry, to mention a few.

Level set methods Level set methods rely on a paradigm shift in modelling of moving boundaries, where one goes from the geometrically intuitive Lagrangian description to an Eulerian perspective based upon partial differential equations. The idea behind level sets is to define a smooth function f(x,t) that represents the evolving interface as the set f(x,t)=0. The evolution of the function f is described by a Hamilton-Jacobi type partial differential equation, which can be discretised using standard (high-resolution) methods for hyperbolic equations. As a result, the level set method can be used to very accurately describe evolution of interfaces involving sharp fronts and changes in topology like merging and breaking. We are currently exploring the application of level-set techniques for interface tracking within multiphase flow. We also have extensive previous experience in using these techniques within material sciences, for instance to describe sputtering and depositing in production of semiconductor devices. Recent publications: P. L. O'Sullivan, F. H. Baumann, and G. H. Gilmer. Simulations of physical vapor deposition into trenches and vias: validation and comparison with experiment. J. of Applied Physics, v. 88, no. 7, pp. 4061-4068, 2000.

Simulation of a Rayleigh-Taylor instability in two fluids by a level-set method..

Fast marching methods Fast marching, on the other hand, is an optimal numerical method for computing solutions to boundary value problems for the eikonal equation (a static, nonlinear Hamilton-Jacobi equation from geometrical optics). The method was originally invented by Tsitsiklis to study optimal path planning and resembles Dijkstra's algorithm for finding shortest paths. The method uses a heap sorting algorithm to find an optimal ordering of the unknowns in the discretised nonlinear boundary problem so that iterations can be avoided. The fast marching approach can be used whenever the interface propagation is "one-way" so that the front can be marched outwards. Applications of the method includes simulation of photolithography development and inversion of seismic travel times. We are currently using the fast marching method to develop efficient methods for porous media flow. Amongst our results are a fast method for computing time-of-flight, drainage and swept volumes, and an alternative streamline-like method for solving saturation equations. Recent publications: K. Hvistendahl Karlsen, K.-A. Lie, and N. H. Risebro. A fast marching method for reservoir simulation. Computational Geosciences, Vol. 4, No. 2, pp. 185-206, 2000. K. Hvistendahl Karlsen, K.-A. Lie, J. R. Natvig, and N. H. Risebro. A fast marching method for 3D reservoir simulation. In "Proceedings of the 13th Nordic Seminar on Computational Mechanics (NSCM-13)". Eds., J. Hellesland, H. Osnes, and G. Skeie, pp. 147-150, Mechanics and Applied Mathematics Series, No. 7, University of Oslo, Norway, October 2000. I. Berre, H. K. Dahle, K. Hvistendahl Karlsen, K.-A. Lie, and J. R. Natvig. Time-of-flight + fast marching + transport collapse: an alternative to streamlines for two-phase porous media flow with capillary forces?  in  Proceedings of the XIVth International Conference on Computational Methods in Water Resources (CMWR XIV) , June 23-28 2002, Delft, The Netherlands,  Eds., S.M. Hassanizadeh, R.J. Schotting, W.G. Gray, and G.F. Pinder, Developments in Water Science, vol 47, pages 995-1002, Elsevier, 2002.,  Eds., S.M. Hassanizadeh, R.J. Schotting, W.G. Gray, and G.F. Pinder, Developments in Water Science, vol 47, pages 995-1002, Elsevier, 2002.

Fast marching solution of 2D quarter-five spot (academic test-case in reservoir simulation).