Properties of a Level Set Algorithm for the Visibility Problems

We study an implicit visibility formulation and show that the corresponding closed form formula satisfies a dynamic programming principle, and is the viscosity solution of a Hamilton-Jacobi type equation involving jump discontinuities in the Hamiltonian. We derive the corresponding discretization in multi-dimensions and prove convergence of the corresponding numerical approximations. Finally, we introduce a generalization of the original Hamilton-Jacobi equation and the corresponding discretization that can be solved efficiently using either the fast sweeping or the fast marching methods. Thus, the visibility of an observer in non-constant media can be computed. We also introduce a specialization of the algorithms for environments in which occluders are described by the graph of a function.     

A Fast Marching Method for Hamilton-Jacobi Equations Modeling Monotone Front Propagations

In this paper we present a generalization of the Fast Marching method introduced by J.A. Sethian in 1996 to solve numerically the eikonal equation. The new method, named Buffered Fast Marching (BFM), is based on a semi-Lagrangian discretization and is suitable for Hamilton-Jacobi equations modeling monotonically advancing fronts, including Hamilton-Jacobi-Bellman and Hamilton-Jacobi-Isaacs equations which arise in the framework of optimal control problems and differential games. We also show the convergence of the algorithm to the viscosity solution. Finally we present several numerical tests comparing the BFM method with other existing methods. This research was partially supported by the MIUR Project 2006 “Modellistica Numerica per il Calcolo Scientifico ed Applicazioni Avanzate” and by INRIA–Futurs and ENSTA, Paris, France.     

A Central Discontinuous Galerkin Method for Hamilton-Jacobi Equations

In this paper, a central discontinuous Galerkin method is proposed to solve for the viscosity solutions of Hamilton-Jacobi equations. Central discontinuous Galerkin methods were originally introduced for hyperbolic conservation laws. They combine the central scheme and the discontinuous Galerkin method and therefore carry many features of both methods. Since Hamilton-Jacobi equations in general are not in the divergence form, it is not straightforward to design a discontinuous Galerkin method to directly solve such equations. By recognizing and following a “weighted-residual” or “stabilization-based” formulation of central discontinuous Galerkin methods when applied to hyperbolic conservation laws, we design a high order numerical method for Hamilton-Jacobi equations. The L ² stability and the error estimate are established for the proposed method when the Hamiltonians are linear. The overall performance of the method in approximating the viscosity solutions of general Hamilton-Jacobi equations are demonstrated through extensive numerical experiments, which involve linear, nonlinear, smooth, nonsmooth, convex, or nonconvex Hamiltonians.     

On reachability and minimum cost optimal control

Questions of reachability for continuous and hybrid systems can be formulated as optimal control or game theory problems, whose solution can be characterized using variants of the Hamilton-Jacobi-Bellman or Isaacs partial differential equations. The formal link between the solution to the partial differential equation and the reachability problem is usually established in the framework of viscosity solutions. This paper establishes such a link between reachability, viability and invariance problems and viscosity solutions of a special form of the Hamilton-Jacobi equation. This equation is developed to address optimal control problems where the cost function is the minimum of a function of the state over a specified horizon. The main advantage of the proposed approach is that the properties of the value function (uniform continuity) and the form of the partial differential equation (standard Hamilton-Jacobi form, continuity of the Hamiltonian and simple boundary conditions) make the numerical solution of the problem much simpler than other approaches proposed in the literature. This fact is demonstrated by applying our approach to a reachability problem that arises in flight control and using numerical tools to compute the solution.     

带有运行成本函数的Hamilton-Jacobi可达性分析

水平集方法将可达集表示为Hamilton-Jacobi方程解的零水平集,保存多个不同时间范围的可达集则需要保存Hamilton-Jacobi方程在多个时刻的解,这不仅需要消耗大量的存储空间还为控制律的设计造成了困难.针对这些局限性,提出了一种改进的基于Hamilton-Jacobi方程的可达集表示方法.该方法在Hamilton-Jacobi方程中加入了一项运行成本函数,可以用同一个时刻的解的多个非零水平集表示多个不同时间范围的可达集,极大地节省了存储空间并为控制律的设计提供了便利.为了求解所构造的带有运行成本函数的Hamilton-Jacobi方程,采用了一种基于递归和插值的方法.最后,通过一些数值算例验证了所提出的方法的精确性、在存储空间方面的优越性以及设计的控制律的有效性.     

Pricing American bond options using a penalty method

We develop a novel numerical method to price American options on a discount bond under the Cox–Ingrosll–Ross (CIR) model which is governed by a partial differential complementarity problem. We first propose a penalty approach to this complementarity problem, resulting in a nonlinear partial differential equation (PDE). To numerically solve this nonlinear PDE, we develop a novel fitted finite volume method for the spatial discretization, coupled with a fully implicit time-stepping scheme. We show that this full discretization scheme is consistent, stable and monotone, and hence the convergence of the numerical solution to the viscosity solution of the continuous problem is guaranteed. To solve the discretized nonlinear system, we design an iterative method and prove that the method is convergent. Numerical results are presented to demonstrate the accuracy, efficiency and robustness of our methods.     

Three-dimensional spectral element simulations of variable density and viscosity, miscible displacements in a capillary tube

A high-accuracy numerical approach is introduced for three-dimensional, time-dependent simulations of variable density and viscosity, miscible flows in a circular tube. Towards this end, the conservation equations are treated in cylindrical coordinates. The spatial discretization is based on a mixed spectral element/Fourier spectral scheme, with careful treatment of the singularity at the axis. For the temporal discretization, an efficient semi-implicit method is applied to the variable viscosity momentum equation. This approach results in a constant coefficient Helmholtz equation, which is solved by a fast diagonalization method. Numerical validation data are presented, and simulations are conducted for the three-dimensionally evolving instability resulting from an unstable density stratification in a vertical tube. Some preliminary comparisons with corresponding experiments are undertaken.     

On numerical stabilization in the solution of Saint-Venant equations using the finite element method

Solving the Saint-Venant equations by using numerical schemes like finite difference and finite element methods leads to some unwanted oscillations in the water surface elevation. The reason for these oscillations lies in the method used for the approximation of the nonlinear terms. One of the ways of smoothing these oscillations is by adding artificial viscosity into the scheme. In this paper, by using a suitable discretization, we first solve the one-dimensional Saint-Venant equations by a finite element method and eliminate the unwanted oscillations without using an artificial viscosity. Second, our main discussion is concentrated on numerical stabilization of the solution in detail. In fact, we first convert the systems resulting from the discretization to systems relating to just water surface elevation. Then, by using M-matrix properties, the stability of the solution is shown. Finally, two numerical examples of critical and subcritical flows are given to support our results.     

A full discretisation of the time-dependent Boussinesq (buoyancy) model with nonlinear viscosity

In this article, we study the time dependent Boussinesq (buoyancy) model with nonlinear viscosity depending on the temperature. We propose and analyze first and second order numerical schemes based on finite element methods. An optimal a priori error estimate is then derived for each numerical scheme. Numerical experiments are presented that confirm the theoretical accuracy of the discretization.     

Distributed approximating functional approach to Burgers' equation in one and two space dimensions

The method of distributed approximating functionals (DAFs) is applied to Burgers' equation, as a typical nonlinear PDE, in one and two space dimensions. This equation is similar to, but simpler than, the Navier-Stokes equation in fluid dynamics. The present approach uses DAFs for spatial discretization and a Taylor expansion for time discretization. Several moderately large values of the Reynolds number are considered in the present application. The results obtained, which are in excellent agreement with the formally exact series solutions, are compared with those obtained by other authors using various different methods. It is found that a simple numerical propagation scheme based on DAFs provides highly accurate numerical solutions for Burgers' equation, while requiring very few grid points.     

Regularization and computation of a bifurcation problem with corank 2

This paper deals with a numerical approximation of a bifurcation problem with corank 2. In the neighborhood of the bifurcation point the nonlinear equation is embedded into an extended system. The regular solution of this system including bifurcation point and null space of the corresponding operator derivative allows approximate computation of the bifurcation point and the null space via general discretization and Newton-like methods. In addition, numerical examples are discussed.     

Semiconductor device simulation using a viscous-hydrodynamic model

In this article we deal with a hydrodynamic model of Navier–Stokes (NS) type for semiconductors including a physical viscosity in the momentum and energy equations. A stabilized finite difference scheme with upwinding based on the characteristic variables is used for the discretization of the NS equations, while a mixed finite element scheme is employed for the approximation of the Poisson equation. A consistency result for the method is established showing that the scheme is first-order accurate in both space and time. We also perform a stability analysis of the numerical method applied to a linearized incompletely parabolic system in two space dimensions with vanishing viscosity. A thorough numerical parametric study as a function of the heat conductivity and of the momentum viscosity is carried out in order to investigate their effect on the development of shocks in both one and two space dimensional devices.     

Optimal error analysis of spectral methods with emphasis on non-constant coefficients and deformed geometries

In this paper we present the numerical analysis of spectral methods when non-constant coefficients appear in the equation, either due to the original statement of the equations or to take into account the deformed geometry. A particular attention is devoted to the optimality of the discretization even for low values of the discretization parameter. The effect of some ‘overintegration’ is also addressed, in order to possibly improve the accuracy of the discretization.     

Numerical solutions of the one-phase classical Stefan problem using an enthalpy green element formulation

The enthalpy method is exploited in tackling a heat transfer problem involving a change of state. The resulting governing equation is then solved with a hybrid finite element - boundary element technique known as the Green element method (GEM). Two methods of approximation are employed to handle the time derivative contained in the discrete element equation. The first involves a finite difference method, while the second utilizes a Galerkin finite element approach. The performance of both methods are assessed with a known closed form solution. The finite element based time discretization, despite its greater challenge, yields less reliable numerical results. In addition a numerical stability test of both methods based on a Fourier series analysis explain the dispersive characters of both techniques, and confirms that replication of correct results is largely attributed to their ability to handle the harmonics of small wavelengths which are usually dominant in the vicinity of a front.     

Efficient algorithms for globally optimal trajectories

We present serial and parallel algorithms for solving a system of equations that arises from the discretization of the Hamilton-Jacobi equation associated to a trajectory optimization problem of the following type. A vehicle starts at a prespecified point x_o and follows a unit speed trajectory x(t) inside a region in ℛ^m until an unspecified time T that the region is exited. A trajectory minimizing a cost function of the form ∫₀^T r(x(t))dt+q(x(T)) is sought. The discretized Hamilton-Jacobi equation corresponding to this problem is usually solved using iterative methods. Nevertheless, assuming that the function r is positive, we are able to exploit the problem structure and develop one-pass algorithms for the discretized problem. The first algorithm resembles Dijkstra's shortest path algorithm and runs in time O(n log n), where n is the number of grid points. The second algorithm uses a somewhat different discretization and borrows some ideas from a variation of Dial's shortest path algorithm (1969) that we develop here; it runs in time O(n), which is the best possible, under some fairly mild assumptions. Finally, we show that the latter algorithm can be efficiently parallelized: for two-dimensional problems and with p processors, its running time becomes O(n/p), provided that p=O(√n/log n)     

An Adaptive Sparse Grid Semi-Lagrangian Scheme for First Order Hamilton-Jacobi Bellman Equations

We propose a semi-Lagrangian scheme using a spatially adaptive sparse grid to deal with non-linear time-dependent Hamilton-Jacobi Bellman equations. We focus in particular on front propagation models in higher dimensions which are related to control problems. We test the numerical efficiency of the method on several benchmark problems up to space dimension d=8, and give evidence of convergence towards the exact viscosity solution. In addition, we study how the complexity and precision scale with the dimension of the problem.     

Truncation versus mapping in the spectral approximation to the Korteweg-De Vries equation

We propose two different approaches to the numerical solution of the initial boundary value problem for the Korteweg-De Vries equation; the former is based on the truncation of the domain, the latter on the reduction of the real axis to a bounded interval by a suitable mapping technique. In both cases we consider spectral Chebyshev collocation methods for the space discretization and finite difference schemes for advancing in time. Both single and multi-domain approaches are discussed. We report numerical experiments showing the stability and convergence properties of the methods     

Aeroacoustic modeling of complex flow problems: I-Domain decomposition method for the reduced wave equation

An accurate and efficient method for solving the wave equation on multi-domains is developed for two-dimensional geometries. In this work we treat Cartesian geometries, but the method may be directly extended to more general geometries. As a first step, the one-dimensional problem is investigated. The wave equation is solved in the Fourier space. Three different numerical discretizations are tested, a Pointwise second-order accurate discretization (PT), and two fourth-order schemes: a Padè approximation (HO), and an Equation Based scheme (EB). A consistent discretization of the non reflecting boundary conditions is proposed, which preserves the overall accuracy of the corresponding interior scheme. For the solution of the linear system, it is shown that the preconditioned ILUT-GMRES method is an appropriate choice. In the multi-domain method, an optimal iterative procedure is described, specifying the correct form of the transmission conditions at the interfaces. The numerical tests confirm that the present multi-domain technique retains the same numerical properties of the single domain method. Finally the single and multi domain methods are extended to the two-dimensional case. Received: 31 January 2001 / Accepted: 30 September 2001     

On unconditional conservation of kinetic energy by finite-difference discretizations of the linear and non-linear convection equation

In the past the development of kinetic energy conserving finite-difference methods mostly focused on second-order accurate central methods defined on uniform grids. Nowadays the need for high-order accurate discretizations, to perform for instance accurate numerical simulations of turbulent flow, calls for the development of novel kinetic energy conserving discretization schemes. Instead of choosing a fixed basis discretization up front, in this paper a different, more general, approach is applied. For a Cartesian mesh, sets of conditions are presented such that all discretizations of the linear or non-linear convection equation which obey these conditions, unconditionally conserve kinetic energy.For the linear convection equation it is shown that on a uniform grid it is necessary and sufficient for a discretization to be central in order to be fully conservative, that is: such discretizations not only unconditionally conserve kinetic energy but also unconditionally conserve momentum. On non-uniform grids an algorithm is introduced that can be used to generate fully conservative discretizations that are at least first-order accurate.The derivation of the discretization conditions for the non-linear convection equation is performed in the two-dimensional (2D) linear case. Some examples on uniform grids and on non-uniform grids are presented. It is shown that on uniform grids no upper limit exists with respect to the accuracy of the kinetic energy conserving method. For the higher-dimensional linear and non-linear convection equation the same set of conditions, which ensure the unconditional conservation of kinetic energy, are found as in the 2D linear case. Other results too are found to be straightforward generalizations of the corresponding 2D linear results.It is shown that the fourth-order unconditionally kinetic energy conserving discretization on a staggered mesh introduced in this paper is well suited to simulate the initial development of an inviscid shear layer instability in a divergence-free flow.     

二维非结构网格Hamilton-Jacobi方程的一种简化的加权ENO格式

考虑标量Hamilton-Jacobi方程,对二维非结构网格给出了一种简化的三阶精度加权ENO格式.方法的主要思想是时间和空间分开处理,时间离散用三阶TVD Runge-Kutta 方法.对空间,在每一个三角形单元上构造一个三次多项式,该多项式是一些三次多项式的加权,并给出了加权因子的构造方法.最后用该格式对一些典型算例进行了数值试验,并分析了方法的精度,结果表明该格式是成功的.