A Multigrid Algorithm for Hybrid Joint PDF Simulations in Complex Geometries

In hybrid joint probability density function (joint PDF) algorithms for turbulent reactive flows the equations for the mean flow discretized with a classical grid based method (e.g. finite volume methods (FVM)) are solved together with a Monte Carlo (particle) method for the joint velocity composition PDF. When applied for complex geometries, the solution strategy for such methods which aims at obtaining a converged solution of the coupled problem on a sufficiently fine grid becomes very important. This paper describes one important aspect of this solution strategy, i.e. multigrid computing, which is well known to be very efficient for computing numerical solutions on fine grids. Two sets of grid based variables are involved: cell-centered variables from the FVM and node-centered variables, which denote the moments of the PDF extracted from the particle fields. Starting from a given multiblock grid environment first a new (refined or coarsened) grid is defined retaining the grid quality. The projection and prolongation operators are defined for the two sets of variables. In this new grid environment the particles are redistributed. The effectiveness of the multigrid algorithm is demonstrated. Compared to solely solving on the finest grid, convergence can be reached about one order of magnitude faster when using the multigrid algorithm in three stages. Computation time used for projection or prolongation is negligible. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

The analytical solution of two interesting hyperbolic problems as a test case for a finite volume method with a new grid refinement technique

A finite volume method with grid adaption is applied to two hyperbolic problems: the ultra-relativistic Euler equations, and a scalar conservation law. Both problems are considered in two space dimensions and share the common feature of moving shock waves. In contrast to the classical Euler equations, the derivation of appropriate initial conditions for the ultra-relativistic Euler equations is a non-trivial problem that is solved using one-dimensional shock conditions and the Lorentz invariance of the system. The discretization of both problems is based on a finite volume method of second order in both space and time on a triangular grid. We introduce a variant of the min-mod limiter that avoids unphysical states for the Euler system. The grid is adapted during the integration process. The frequency of grid adaption is controlled automatically in order to guarantee a fine resolution of the moving shock fronts. We introduce the concept of “width refinement” which enlarges the width of strongly refined regions around the shock fronts; the optimal width is found by a numerical study. As a result we are able to improve efficiency by decreasing the number of adaption steps. The performance of the finite volume scheme is compared with several lower order methods.     

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.     

Contour integral method for European options with jumps

We develop an efficient method for pricing European options with jump on a single asset. Our approach is based on the combination of two powerful numerical methods, the spectral domain decomposition method and the Laplace transform method. The domain decomposition method divides the original domain into sub-domains where the solution is approximated by using piecewise high order rational interpolants on a Chebyshev grid points. This set of points are suitable for the approximation of the convolution integral using Gauss–Legendre quadrature method. The resulting discrete problem is solved by the numerical inverse Laplace transform using the Bromwich contour integral approach. Through rigorous error analysis, we determine the optimal contour on which the integral is evaluated. The numerical results obtained are compared with those obtained from conventional methods such as Crank–Nicholson and finite difference. The new approach exhibits spectrally accurate results for the evaluation of options and associated Greeks. The proposed method is very efficient in the sense that we can achieve higher order accuracy on a coarse grid, whereas traditional methods would required significantly more time-steps and large number of grid points.     

Order h4 difference methods for a class of singular two space elliptic boundary value problems

In this article, we derive difference methods of O(h⁴) for solving the system of two space nonlinear elliptic partial differential equations with variable coefficients having mixed derivatives on a uniform square grid using nine grid points. We obtain two sets of fouth-order difference methods; one in the absence of mixed derivatives, second when the coefficients of u_xy are not equal to zero and the coefficients of u_xx and u_yy are equal. There do not exist fourth-order schemes involving nine grid points for the general case. The method having two variables has been tested on two-dimensional viscous, incompressible steady-state Navier-Stokes' model equations in polar coordinates. The proposed difference method for scalar equation is also applied to the Poisson's equation in polar coordinates. Some numerical examples are provided to illustrate the fourth-order convergence of the proposed methods.     

Wavelets collocation methods for the numerical solution of elliptic BV problems

Based on collocation with Haar and Legendre wavelets, two efficient and new numerical methods are being proposed for the numerical solution of elliptic partial differential equations having oscillatory and non-oscillatory behavior. The present methods are developed in two stages. In the initial stage, they are developed for Haar wavelets. In order to obtain higher accuracy, Haar wavelets are replaced by Legendre wavelets at the second stage. A comparative analysis of the performance of Haar wavelets collocation method and Legendre wavelets collocation method is carried out. In addition to this, comparative studies of performance of Legendre wavelets collocation method and quadratic spline collocation method, and meshless methods and Sinc–Galerkin method are also done. The analysis indicates that there is a higher accuracy obtained by Legendre wavelets decomposition, which is in the form of a multi-resolution analysis of the function. The solution is first found on the coarse grid points, and then it is refined by obtaining higher accuracy with help of increasing the level of wavelets. The accurate implementation of the classical numerical methods on Neumann’s boundary conditions has been found to involve some difficulty. It has been shown here that the present methods can be easily implemented on Neumann’s boundary conditions and the results obtained are accurate; the present methods, thus, have a clear advantage over the classical numerical methods. A distinct feature of the proposed methods is their simple applicability for a variety of boundary conditions. Numerical order of convergence of the proposed methods is calculated. The results of numerical tests show better accuracy of the proposed method based on Legendre wavelets for a variety of benchmark problems.     

Quadrature discretization method in tethered satellite control

A pseudospectral method for solving the tethered satellite retrieval problem based on nonclassical orthogonal and weighted interpolating polynomials is presented. Traditional pseudospectral methods expand the state and control trajectories using global Lagrange interpolating polynomials based on a specific class of orthogonal polynomials from the Jacobi family, such as Legendre or Chebyshev polynomials, which are orthogonal with respect to a specific weight function over a fixed interval. Although these methods have many advantages, the location of the collocation points are more or less fixed. The method presented in this paper generalizes the existing methods and allows a much more flexible selection of grid points by the arbitrary selection of the orthogonal weight function and interval. The trajectory optimization problem is converted to set of algebraic equations by discretization of the necessary conditions using a nonclassical pseudospectral method.     

Pareto set approximation by the method of adjustable weights and successive lexicographic goal programming

A nonlinear multiobjective optimization problem is considered. Two methods are proposed to generate solutions with an approximately uniform distribution in a Pareto set. The first method is supposed to find the solutions as minimizers of weighted sums of objective functions where the weights are properly selected using a branch and bound type algorithm. The second method is based on lexicographic goal programming. The proposed methods are compared with several metaheuristic methods using two and three-criteria tests and applied problems.     

Integration of barotropic vorticity equation over spherical geodesic grid using multilevel adaptive wavelet collocation method

In this paper, we present the multilevel adaptive wavelet collocation method for solving non-divergent barotropic vorticity equation over spherical geodesic grid. This method is based on multi-dimensional second generation wavelet over a spherical geodesic grid. The method is more useful in capturing, identifying, and analyzing local structure [1] than any other traditional methods (i.e. finite difference, spectral method), because those methods are either full or partial miss important phenomena such as trends, breakdown points, discontinuities in higher derivatives of the solution. Wavelet decomposition is used for interpolation and adaptive grid refinement on different levels.     

A two-dimensional minimum-derivative spline

We consider the construction of a C ^(1,1) interpolation parabolic spline function of two variables on a uniform rectangular grid, i.e., a function continuous in a given region together with its first partial derivatives which on every partial grid rectangle is a polynomial of second degree in x and second degree in y. The spline function is constructed as a minimum-derivative one-dimensional quadratic spline in one of the variables, and the spline coefficients themselves are minimum-derivative quadratic spline functions of the other variable.     

A computational framework of kinematic accuracy reliability analysis for industrial robots

A new computational method to evaluate comprehensively the positional accuracy reliability for single coordinate, single point, multipoint and trajectory accuracy of industrial robots is proposed using the sparse grid numerical integration method and the saddlepoint approximation method. A kinematic error model of end-effector is constructed in three coordinate directions using the sparse grid numerical integration method considering uncertain parameters. The first-four order moments and the covariance matrix for three coordinates of the end-effector are calculated by extended Gauss–Hermite integration nodes and corresponding weights. The eigen-decomposition is conducted to transform the interdependent coordinates into independent standard normal variables. An equivalent extreme value distribution of response is applied to assess the reliability of kinematic accuracy. The probability density function and probability of failure for extreme value distribution are then derived through the saddlepoint approximation method. Four examples are given to demonstrate the effectiveness of the proposed method.     

A cooperative strategy for solving dynamic optimization problems

Optimization in dynamic environments is a very active and important area which tackles problems that change with time (as most real-world problems do). In this paper we present a new centralized cooperative strategy based on trajectory methods (tabu search) for solving Dynamic Optimization Problems (DOPs). Two additional methods are included for comparison purposes. The first method is a Particle Swarm Optimization variant with multiple swarms and different types of particles where there exists an implicit cooperation within each swarm and competition among different swarms. The second method is an explicit decentralized cooperation scheme where multiple agents cooperate to improve a grid of solutions. The main goals are: firstly, to assess the possibilities of trajectory methods in the context of DOPs, where populational methods have traditionally been the recommended option; and secondly, to draw attention on explicitly including cooperation schemes in methods for DOPs. The results show how the proposed strategy can consistently outperform the results of the two other methods.     

Multigrid solution of high order discretisation for three-dimensional biharmonic equation with Dirichlet boundary conditions of second kind

In this paper, we propose two compact finite difference approximations for three-dimensional biharmonic equation with Dirichlet boundary conditions of second kind. In these methods there is no need to define special formulas near the boundaries and boundary conditions are incorporated with these techniques. The unknown solution and its second derivatives are carried as unknowns at grid points. We derive second-order and fourth-order approximations on a 27 point compact stencil. Classical iteration methods such as Gauss–Seidel and SOR for solving the linear system arising from the second-order and fourth-order discretisation suffer from slow convergence. In order to overcome this problem we use multigrid method which exhibit grid-independent convergence and solve the linear system of equations in small amount of computer time. The fourth-order finite difference approximations are used to solve several test problems and produce high accurate numerical solutions.     

Numerical solution of systems of partial integral differential equations with application to pricing options

We introduce and analyze a strongly stable numerical method designed to yield good performance under challenging conditions of irregular or mismatched initial data for solving systems of coupled partial integral differential equations (PIDEs). Spatial derivatives are approximated using second order central difference approximations by treating the mixed derivative terms in a special way. The integral operators are approximated using one and two–dimensional trapezoidal rule on an equidistant grid. Computational complexity of the method for solving large systems of PIDEs is discussed. A detailed treatment for the consistency, stability, and convergence of the proposed method is provided. Two asset American option under regime–switching with jump–diffusion model when solved using a penalty term, leads to a system of two dimensional PIDEs with mixed derivatives. This model involves double probability density function which brings more challenges to the numerical solution in already a complicated partial integral differential equation. The complexity of the dense jump probability generator, the nonlinear penalty term and the regime–switching terms are treated efficiently, while maintaining the stability and convergence of the method. The impact of the jump intensity and other parameters is shown in the graphs. Numerical experiments are performed to demonstrated efficiency, accuracy, and reliability of the proposed approach.     

High-order accurate bicompact schemes for solving the multidimensional inhomogeneous transport equation and their efficient parallel implementation

The method of lines is used to obtain semidiscrete equations for a bicompact scheme in operator form for the inhomogeneous linear transport equation in two and three dimensions. In each spatial direction, the scheme has a two-point stencil, on which the spatial derivatives are approximated to fourth-order accuracy due to expanding the list of unknown grid functions. This order of accuracy is preserved on an arbitrary nonuniform grid. The equations of the method of lines are integrated in time using diagonally implicit multistage Runge–Kutta methods of the third up fifth orders of accuracy. Test computations on refined meshes are presented. It is shown that the high-order accurate bicompact schemes can be efficiently parallelized on multicore and multiprocessor computers.     

A Cartesian‐grid collocation method based on radial‐basis‐function networks for solving PDEs in irregular domains

This paper reports a new Cartesian‐grid collocation method based on radial‐basis‐function networks (RBFNs) for numerically solving elliptic partial differential equations in irregular domains. The domain of interest is embedded in a Cartesian grid, and the governing equation is discretized by using a collocation approach. The new features here are (a) one‐dimensional integrated RBFNs are employed to represent the variable along each line of the grid, resulting in a significant improvement of computational efficiency, (b) the present method does not require complicated interpolation techniques for the treatment of Dirichlet boundary conditions in order to achieve a high level of accuracy, and (c) normal derivative boundary conditions are imposed by means of integration constants. The method is verified through the solution of second‐ and fourth‐order PDEs; accurate results and fast convergence rates are obtained. © 2007 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2007     

Method for solving the Boltzmann kinetic equation for polyatomic gases

A method is proposed for computing the collision operator of a generalized Boltzmann kinetic equation with allowance for energy transfer from translational to vibrational or rotational degrees of freedom. The collision operator is computed using a projection method on a uniform velocity grid. The operator satisfies the mass, momentum, and energy conservation laws and vanishes for an equilibrium velocity distribution function. Approximate models are suggested that provide savings on the computation of rotational-translational relaxation. Numerical examples are presented.     

有限元法中大单元的构造

在通常的有限元法中,单元内的插值多项式的阶数固定不变,通过加密剖分网格来提高精度.大单元法则剖分的网格固定不变而通过增加单元内逼近级数的项数来提高精度. 本文提出采用两套变量的办法来构造大单元,即单元内采用一套变量,单元的边界上采用另一套变量,然后用杂交罚函数法把两者联系起来.这种方法能适用于任何椭圆型方程,任意几何形状区域以及任何复杂的边界条件.本文用严密的数学方法证明了:在一般情况下,这种方法的精度比通常的有限元法和文[7]的大单元法高得多.即在达到相同的精度时,本文方法所需要的自由度(即未知数数目)比上述两种方法少得多.     

First and second order numerical differentiation with Tikhonov regularization

This work deals with the numerical differentiation for an unknown smooth function whose data on a given set are available. The numerical differentiation is an ill-posed problem. In this work, the first and second derivatives of the smooth function are approximated by using the Tikhonov regularization method. It is proved that the approximate function can be chosen as a minimizer to a cost functional. The existence and uniqueness theory of the minimizer is established. Errors in the derivatives between the smooth unknown function and the approximate function are obtained, which depend on the mesh size of the grid and the noise level in the data. The numerical results are provided to support the theoretical analysis of this work. Selected from Numerical Mathematics (A Journal of Chinese Universities), 2004, 26(1):62–74     

双障碍问题的多重网格法

本文研究双障碍问题的多重网格法,提出了两类算法,证明了其收敛性及对贴合分量的有限步收敛性,同时对其中一种算法的特款提出了一个 k无关收敛性定理。