Comparison of two Eulerian solvers for the four-dimensional Vlasov equation: Part I

This paper presents two methods for solving the four-dimensional Vlasov equation on a grid of the phase space. The two methods are based on the semi-Lagrangian method which consists in computing the distribution function at each grid point by following the characteristic curves ending there. The first method reconstructs the distribution function using local splines which are well suited for a parallel implementation. The second method is adaptive using wavelets interpolation: only a subset of the grid points are conserved to manage data locality. Numerical results are presented in the second part.     

Comparison of two Eulerian solvers for the four-dimensional Vlasov equation: Part II

In this second part, we carry out a numerical comparison between two Vlasov solvers, which solve directly the Vlasov equation on a grid of the phase space. The two methods are based on the semi-Lagrangian method as presented in Part I: the first one (LOSS, local splines simulator) uses a uniform mesh of the phase space whereas the second one (OBI, ondelets based interpolation) is an adaptive method. The numerical comparisons are performed by solving the four-dimensional Vlasov equation for some classical problems of plasma and beam physics. We shall also investigate the speedup and the CPU time as well as the compression rate of the adaptive method which are important features because of the size of the problems.     

On using the Lagrange coefficients for a posteriori error estimation

A posteriori error estimation of the objective functional is considered by means of a differential presentation of a finite-difference scheme and adjoint equations. The local approximation error is presented as a Taylor series remainder in the Lagrangian form. The field of the Lagrange coefficients is determined by a high-accuracy finite-difference template affecting the computation results. The feasibility of using the Lagrange coefficients for refining the solution and for estimating its uncertainty is considered.     

Optimal synthesis in grid schemes for quasi-convex approximation functions

A single grid algorithm which constructs the value function and the optimal synthesis, based on a local quasi-differential approximations of the Hamilton-Jacobi equation, is considered. The optimal synthesis is generated by the method of extremal translation in the direction of generalized gradients. The quasi-convex approximation functions, for which it is possible to use a linear dependence of the space-time steps for correct interpolation of the nodal optimal control values, thus substantially reducing the amount of computation, simplifying the finite-difference formulae and permitting the use of simple operators involving constructions of the method of least squares, are investigated.     

Goal-oriented anisotropic grid adaptation

Venditti and Darmofal have introduced a grid adaptation strategy for estimating and reducing simulation errors in functional outputs of partial differential equations. The procedure is based on an adjoint formulation in which the estimated error in the functional can be directly related to the local residual errors of both the primal and adjoint solutions. In this note, we propose an extension of this method to the anisotropic case. The strategy proposed for grid adaptation is also compared with the anisotropic Hessian approach, based on the minimization of interpolation error. To cite this article: G. Rogé, L. Martin, C. R. Acad. Sci. Paris, Ser. I 346 (2008).     

Univariate Interpolation on a Regular Finite Grid by a Multiquadric Plus a Linear Polynomial

Univariate multiquadric interpolation to a twice continuouslydifferentiable function on a regular infinite grid enjoys secondorder convergence and some excellent localization properties,but numerical calculations suggest that, if the grid is finite,then usually the convergence rate deteriorates to first ordernear the grid boundaries, ibis conjecture is proved. It is alsoshown that one can recover superlinear convergence by addinga linear polynomial term to the multiquadric approximation.Making such additions is a standard technique, but we find thatthe usual way of choosing the polynomial fails to provide superlinearconvergence m general. Therefore some new procedures are giventhat pick a suitable polynomial automatically. Thus it is notunusual to reduce the maximum error of the interpolation bya factor of 10³. Further, it is straightforward to include oneof the new procedures in multiquadric interpolation to functionsof several variables when the data points are in general position.     

Cubic spline interpolation of functions with high gradients in boundary layers

The cubic spline interpolation of grid functions with high-gradient regions is considered. Uniform meshes are proved to be inefficient for this purpose. In the case of widely applied piecewise uniform Shishkin meshes, asymptotically sharp two-sided error estimates are obtained in the class of functions with an exponential boundary layer. It is proved that the error estimates of traditional spline interpolation are not uniform with respect to a small parameter, and the error can increase indefinitely as the small parameter tends to zero, while the number of nodes N is fixed. A modified cubic interpolation spline is proposed, for which O((ln N/N)⁴) error estimates that are uniform with respect to the small parameter are obtained.     

Mitigating the curse of dimensionality: sparse grid characteristics method for optimal feedback control and HJB equations

We address finding the semi-global solutions to optimal feedback control and the Hamilton–Jacobi–Bellman (HJB) equation. Using the solution of an HJB equation, a feedback optimal control law can be implemented in real-time with minimum computational load. However, except for systems with two or three state variables, using traditional techniques for numerically finding a semi-global solution to an HJB equation for general nonlinear systems is infeasible due to the curse of dimensionality. Here we present a new computational method for finding feedback optimal control and solving HJB equations which is able to mitigate the curse of dimensionality. We do not discretize the HJB equation directly, instead we introduce a sparse grid in the state space and use the Pontryagin’s maximum principle to derive a set of necessary conditions in the form of a boundary value problem, also known as the characteristic equations, for each grid point. Using this approach, the method is spatially causality free, which enjoys the advantage of perfect parallelism on a sparse grid. Compared with dense grids, a sparse grid has a significantly reduced size which is feasible for systems with relatively high dimensions, such as the 6-D system shown in the examples. Once the solution obtained at each grid point, high-order accurate polynomial interpolation is used to approximate the feedback control at arbitrary points. We prove an upper bound for the approximation error and approximate it numerically. This sparse grid characteristics method is demonstrated with three examples of rigid body attitude control using momentum wheels.     

An improved Lagrangian relaxation and dual ascent approach to facility location problems

The literature knows semi-Lagrangian relaxation as a particular way of applying Lagrangian relaxation to certain linear mixed integer programs such that no duality gap results. The resulting Lagrangian subproblem usually can substantially be reduced in size. The method may thus be more efficient in finding an optimal solution to a mixed integer program than a “solver” applied to the initial MIP formulation, provided that “small” optimal multiplier values can be found in a few iterations. Recently, a simplification of the semi-Lagrangian relaxation scheme has been suggested in the literature. This “simplified” approach is actually to apply ordinary Lagrangian relaxation to a reformulated problem and still does not show a duality gap, but the Lagrangian dual reduces to a one-dimensional optimization problem. The expense of this simplification is, however, that the Lagrangian subproblem usually can not be reduced to the same extent as in the case of ordinary semi-Lagrangian relaxation. Hence, an effective method for optimizing the Lagrangian dual function is of utmost importance for obtaining a computational advantage from the simplified Lagrangian dual function. In this paper, we suggest a new dual ascent method for optimizing both the semi-Lagrangian dual function as well as its simplified form for the case of a generic discrete facility location problem and apply the method to the uncapacitated facility location problem. Our computational results show that the method generally only requires a very few iterations for computing optimal multipliers. Moreover, we give an interesting economic interpretation of the semi-Lagrangian multiplier(s).     

Comments on algorithms for grid interfaces in simulating Euler flows

Some results concerning the algorithms for grid interfaces, which are crucial in simulating flows by zonal methods, are presented in this paper. It is indicated that the commonly used conservative interface scheme can ensure the discrete entropy condition, but it may be inconsistent and would bring a nonoverlapping solution on overlapping grids. A nonconservative interface matching obtained by interpolation can be monotonicity preserving, and it leads large conservation error when discontinuities are close to the interfaces. Methods for improvement of interface algorithms are also proposed.     

A conservative semi-Lagrangian method for multidimensional fluid dynamics applications

We describe a finite volume semi-Lagrangian method for the numerical approximation of conservation laws arising in fluid-dynamic applications. A discrete conservation relation is satisfied by using conservative interpolation for the material (or property) being conserved. The method was developed with a view to application in climate prediction. © 1995 John Wiley & Sons, Inc.     

The next generation CIP as a conservative semi-Lagrangian solver for solid,liquid and gas

We present a review of the CIP method, which is a kind of semi-Lagrangian scheme and has been extended to treat incompressible flow in the framework of compressible fluid. Since it uses primitive Euler representation, it is suitable for multi-phase analysis. The recent version of this method guarantees the exact mass conservation even in the framework of semi-Lagrangian scheme. Comprehensive review is given for the strategy of the CIP method that has a compact support and subcell resolution including front capturing algorithm with functional transformation.     

A streamline tracking algorithm for semi-Lagrangian advection schemes based on the analytic integration of the velocity field

A new scheme for the construction on an unstructured grid of the streamlines of the three-dimensional shallow water equations is presented. The qualitative advantages of the scheme, notably closed streamlines and realistic treatment of closed boundaries, are derived and the spatial accuracy is demonstrated.Semi-Lagrangian advection schemes offer the computational cost advantage of being explicit but also unconditionally stable with respect to time step. However, semi-Lagrangian methods based on the numerical integration of the discretised velocity field frequently have difficulty in meeting physically significant criteria such as the closure of streamlines and the inviolability of closed boundaries. Here a streamline tracking scheme based on the analytic integration of the discretised velocity field is presented.     

An optimization approach for the numerical approximation of differential equations

An alternative approach for the numerical approximation of ODEs is presented in this article. It is based on a variational framework recently introduced in S. Amat and P. Pedregal [A variational approach to implicit ODEs and differential inclusions, ESAIM: COCV 15 (2009), 149–172] where the solution is sought as the minimizer of an error functional tailored after the ODE in a rather straightforward way. A suitable discretization of this error functional is pursued, and it is performed using Hermite's interpolation and quadrature formulae. Notice that only Hermite's interpolation is necessary when polynomial systems of ODEs are considered (many models in practice use these types of equations). A comparison with implicit Runge–Kutta methods is analysed. With this variational strategy not only some classical collocation methods, but also new schemes that seem to have better numerical behaviour can be recovered. Although the driving idea is very simple, the strategy turns out to be very general and flexible. At the same time, it can be implemented efficiently.     

Error estimates for spline interpolants on equidistant grids

Summary For oddm, the error of them-th-degree spline interpolant of power growth on an equidistant grid is estimated. The method is based on a decomposition formula for the spline function, which locally can be represented as an interpolation polynomial of degreem which is corrected by an (m+1)-st.-order difference term.Dedicated to Prof. Dr. Karl Zeller on the occasion of his 60th birthday     

On the structure of error estimates for finite-difference methods

In this paper we study in an abstract setting the structure of estimates for the global (accumulated) error in semilinear finite-difference methods. We derive error estimates, which are the most refined ones (in a sense specified precisely in this paper) that are possible for the difference methods considered. Applications and (numerical) examples are presented in the following fields: 1. Numerical solution of ordinary as well as partial differential equations with prescribed initial or boundary values. 2. Accumulation of local round-off error as well as of local discretization error. 3. The problem of fixing which methods out of a given class of finite-difference methods are most stable. 4. The construction of finite-difference methods which are convergent but not consistent with respect to a given differential equation.     

Comparison Between the Mean-Variance Optimal and the Mean-Quadratic-Variation Optimal Trading Strategies

ABSTRACT

We compare optimal liquidation policies in continuous time in the presence of trading impact using numerical solutions of Hamilton–Jacobi–Bellman (HJB) partial differential equations (PDEs). In particular, we compare the time-consistent mean-quadratic-variation strategy with the time-inconsistent (pre-commitment) mean-variance strategy. We show that the two different risk measures lead to very different strategies and liquidation profiles. In terms of the optimal trading velocities, the mean-quadratic-variation strategy is much less sensitive to changes in asset price and varies more smoothly. In terms of the liquidation profiles, the mean-variance strategy is much more variable, although the mean liquidation profiles for the two strategies are surprisingly similar. On a numerical note, we show that using an interpolation scheme along a parametric curve in conjunction with the semi-Lagrangian method results in significantly better accuracy than standard axis-aligned linear interpolation. We also demonstrate how a scaled computational grid can improve solution accuracy.     

A simple procedure for determining order quantities under a fill rate constraint and normally distributed lead-time demand

One of the most common practical inventory control problems is considered. A single-echelon inventory system is controlled by a continuous review (R, Q) policy. The lead-time demand is normally distributed. We wish to minimize holding and ordering costs under a fill rate constraint. Although, it is not especially complicated to derive the optimal solution, it is much more common in practice to use a simple approximate two-step procedure where the order quantity is determined from a deterministic model in the first step. We provide an alternative, equally simple technique, which is based on the observation that the considered problem for each considered fill rate has a single parameter only. The optimal solution for a grid of parameter values is stored in a file. When solving the problem for an item we use interpolation, or for parameter values outside the grid special approximations. The approximation errors turn out to be negligible. As an alternative to the interpolation we also provide polynomial approximations.     

Modification of the Euler quadrature formula for functions with a boundary-layer component

The Euler quadrature formula for the numerical integration of functions with a boundary-layer component on a uniform grid is investigated. If the function under study has a rapidly growing component, the error can be significant. A uniformly accurate quadrature formula is constructed by modifying the Hermite interpolation formula so that the resulting one is exact for the boundary-layer component. An analogue of the Euler formula that is exact for the boundary-layer component is constructed. It is proved that the resulting composite quadrature formula is third-order accurate in space uniformly with respect to the boundary-layer component and its derivatives.     

MATRIX ALGORITHMS AND ERROR FORMULA FOR BIVARIATE THIELE-TYPE RECTANGULAR MATRIX VALUED RATIONAL INTERPOLATION

A new method for the construction of bivariate matrix valued rational interpolants (BGIRI) on a rectangular grid is presented in [6]. The rational interpolants are of Thiele-type continued fraction form with scalar denominator. The generalized inverse introduced by [3]is gen-eralized to rectangular matrix case in this paper. An exact error formula for interpolation is ob-tained, which is an extension in matrix form of bivariate scalar and vector valued rational interpola-tion discussed by Siemaszko[l2] and by Gu Chuangqing [7] respectively. By defining row and col-umn-transformation in the sense of the partial inverted differences for matrices, two type matrix algorithms are established to construct corresponding two different BGIRI, which hold for the vec-tor case and the scalar case.