Multilevel Monte Carlo method with applications to stochastic partial differential equations

In this work, the approximation of Hilbert-space-valued random variables is combined with the approximation of the expectation by a multilevel Monte Carlo (MLMC) method. The number of samples on the different levels of the multilevel approximation are chosen such that the errors are balanced. The overall work then decreases in the optimal case to O(h ^?2) if h is the error of the approximation. The MLMC method is applied to functions of solutions of parabolic and hyperbolic stochastic partial differential equations as needed, for example, for option pricing. Simulations complete the paper.     

Discontinuous Galerkin methods for elliptic partial differential equations with random coefficients

This paper proposes and analyses two numerical methods for solving elliptic partial differential equations with random coefficients, under the finite noise assumption. First, the stochastic discontinuous Galerkin method represents the stochastic solution in a Galerkin framework. Second, the Monte Carlo discontinuous Galerkin method samples the coefficients by a Monte Carlo approach. Both methods discretize the differential operators by the class of interior penalty discontinuous Galerkin methods. Error analysis is obtained. Numerical results show the sensitivity of the expected value and variance with respect to the penalty parameter of the spatial discretization.     

An upscaling method using coefficient splitting and its applications to elliptic PDEs

In this paper, we develop an upscaling method using coefficient splitting techniques. Green’s function is constructed using the differential operator associated with the first part of the splitting. An effective upscaling coefficient is recursively calculated by Green’s function. The computation of the upscaling process involves some independent steps. Combining the proposed upscaling method with the stochastic collocation method, we present a stochastic space reduction collocation method, where the stochastic collocation method is performed on a lower dimension stochastic space than the full-dimension stochastic space. We thoroughly analyze the convergence of the proposed upscaling method for both deterministic and stochastic elliptic PDEs. Computation complexity is also addressed for the stochastic upscaling method. A number of numerical tests are presented to confirm the convergence analysis.     

Multigrid and sparse-grid schemes for elliptic control problems with random coefficients

A multigrid and sparse-grid computational approach to solving nonlinear elliptic optimal control problems with random coefficients is presented. The proposed scheme combines multigrid methods with sparse-grids collocation techniques. Within this framework the influence of randomness of problem’s coefficients on the control provided by the optimal control theory is investigated. Numerical results of computation of stochastic optimal control solutions and formulation of mean control functions are presented.     

Exploring pseudo- and chaotic random Monte Carlo simulations

Computer simulations are an increasingly important area of geoscience research and development. At the core of stochastic or Monte Carlo simulations are the random number sequences that are assumed to be distributed with specific characteristics. Computer-generated random numbers, uniformly distributed on (0, 1), can be very different depending on the selection of pseudo-random number (PRN) or chaotic random number (CRN) generators. In the evaluation of some definite integrals, the resulting error variances can even be of different orders of magnitude. Furthermore, practical techniques for variance reduction such as importance sampling and stratified sampling can be applied in most Monte Carlo simulations and significantly improve the results. A comparative analysis of these strategies has been carried out for computational applications in planar and spatial contexts. Based on these experiments, and on some practical examples of geodetic direct and inverse problems, conclusions and recommendations concerning their performance and general applicability are included.     

Application of new Monte Carlo algorithms to random spin systems

We explain the idea of the probability-changing cluster (PCC) algorithm, which is an extended version of the Swendsen-Wang algorithm. With this algorithm, we can tune the critical point automatically. We show the effectiveness of the PCC algorithm for the case of the three-dimensional (3D) Ising model. We also apply this new algorithm to the study of the 3D diluted Ising model. Since we tune the critical point of each random sample automatically with the PCC algorithm, we can investigate the sample-dependent critical temperature and the sample average of physical quantities at each critical temperature, systematically. We have also applied another newly proposed algorithm, the Wang-Landau algorithm, to the study of the spin glass problem.     

Multilevel Schwarz methods for elliptic partial differential equations

We investigate multilevel Schwarz domain decomposition preconditioners, to efficiently solve linear systems arising from numerical discretizations of elliptic partial differential equations by the finite element method. In our analysis we deal with unstructured mesh partitions and with subdomain boundaries resulting from using the mesh partitioner. We start from two-level preconditioners with either aggregative or interpolative coarse level components, then we focus on a strategy to increase the number of levels. For all preconditioners, we consider the additive residual update and its multiplicative variants within and between levels. Moreover, we compare the preconditioners behaviour, regarding scalability and rate of convergence. Numerical results are provided for elliptic boundary value problems, including a convection–diffusion problem when suitable stabilization becomes necessary.     

Error and complexity of random walk Monte Carlo radiosity

The author studies the error and complexity of the discrete random walk Monte Carlo technique for radiosity, using both the shooting and gathering methods. The author shows that the shooting method exhibits a lower complexity than the gathering one, and under some constraints, it has a linear complexity. This is an improvement over a previous result that pointed to an O(n log n) complexity. The author gives and compares three unbiased estimators for each method, and obtains closed forms and bounds for their variances. The author also bounds the expected value of the mean square error (MSE). Some of the results obtained are also shown to be valid for the nondiscrete gathering case. The author also gives bounds for the variances and MSE for the infinite path length estimators; these bounds might be useful in the study of biased estimators resulting from cutting off the infinite path     

Monte Carlo Simulation methods for slope stability

The use of the Monte Carlo Simulation method is discussed, as a sensitivity-testing tool for slope stability and also as a method of calculating P (probability of sliding failure of a given earth slope) rather than the conventional F (factor of safety against sliding failure). Probability of failure values are obtained as a result of putting the Department of Transport's program CIRCA (for slope stability) into simulation mode and are compared with values obtained analytically. The Bishop simplified formula used to determine the most critical slip circle, is the mechanical model adopted in CIRCA. Familiarity with the Bishop formula itself is assumed by the reader. Some meaning is given also to the concept of setting allowable criteria for P values, for comparison with calculated values, in order to determine whether a slope is adequately safe.     

Discrete range clustering using Monte Carlo methods

For automatic obstacle avoidance guidance during rotorcraft low altitude flight a reliable model of the nearby environment is needed. Such a model may be constructed by applying surface fitting techniques to the dense range map obtained by active sensing using radars. However, for covertness passive sensing techniques using electro-optic sensors is desirable. As opposed to the dense range map obtained via active sensing, passive sensing algorithms produce reliable range at sparse locations and, therefore, surface fitting techniques to fill the gaps in the range measurement are not directly applicable. Both, for automatic guidance and as a display for aiding the pilot, these discrete ranges need to be grouped into sets which correspond to objects in the nearby environment. The focus of this paper is on using Monte Carlo methods for clustering range points into meaningful groups. We compare three different approaches and present results of application of these algorithms to an image sequence acquired by onboard cameras during a helicopter flight. Starting with an initial grouping, these algorithms are iteratively applied with a new group creation algorithm to determine the optimal number of groups and the optimal group membership. The results indicate that the simulated annealing methods do not offer any significant advantage over the basic Monte Carlo method for this discrete optimization problem     

Monte Carlo methods in fuzzy queuing theory

In this paper, we consider an optimization problem in fuzzy queuing theory that was first used in web planning. This fuzzy optimization problem has no solution algorithm and approximate solutions were first produced by computing the fuzzy value of the objective function for only sixteen values of the fuzzy variables. We introduce our fuzzy Monte Carlo method, using a quasi-random number generator, to produce 100,000 random sequences of fuzzy vectors for the fuzzy variables, which will present a much better approximate solution.     

Monte Carlo methods for derivatives of options with discontinuous payoffs

Various Monte Carlo methods have been proposed to estimate the derivatives of contingent claims prices. The Monte Carlo approximate likelihood ratio estimator is studied. Recent convergence results are extended in order to show that the Monte Carlo approximate likelihood ratio derivative estimator is asymptotically equivalent, up to a second-order bias component, to an estimator based on a covariation approximation, the Monte Carlo Covariation estimator. Both converge slower than the Monte Carlo Malliavin derivative estimators. Theoretical convergence results are illustrated in a numerical experiment dealing with the risk management of digital options in a CEV model.     

Adaptive sparse grid multilevel methods for elliptic PDEs based on finite differences

We present a multilevel approach for the solution of partial differential equations. It is based on a multiscale basis which is constructed from a one-dimensional multiscale basis by the tensor product approach. Together with the use of hash tables as data structure, this allows in a simple way for adaptive refinement and is, due to the tensor product approach, well suited for higher dimensional problems. Also, the adaptive treatment of partial differential equations, the discretization (involving finite differences) and the solution (here by preconditioned BiCG) can be programmed easily. We describe the basic features of the method, discuss the discretization, the solution and the refinement procedures and report on the results of different numerical experiments.     

Parallel three-dimensional direct simulation Monte Carlo method and its applications

The development of a parallel three-dimensional direct simulation Monte Carlo (DSMC) method using unstructured cells is reported. Variable hard sphere molecular model and no time counter method are used for the molecular collision kinetics, while the cell-by-cell ray-tracing technique is implemented for particle movement. Developed serial code has been verified by comparing the results of a supersonic corner flow with those of Bird’s three-dimensional structured DSMC code. In addition, a benchmark test is performed for an orifice expanding flow to verify the parallel implementation of DSMC method by comparing with available experimental data. Static physical domain decomposition is used to distribute the workload among multiple processors by considering the estimated particle weighting distribution. Two-step multi-level graph partitioning technique is used to perform the required domain decomposition. Completed code is then applied to compute a hypersonic flow over a sphere (external flow) and the flow field of a spiral drag pump (internal flow), respectively. Results of the former are in good agreement with previous numerical results using axisymmetric DSMC method and experimental data. Results of the latter also agree well with previous numerical results.     

A localized RBF-MLPG method and its application to elliptic PDEs

The existing local RBF methods use the strong form equation and approximate the solution in local subdomains instead of the whole domain. In the RBF-MLPG method, the unknown solution is approximated by RBFs in the whole domain and testing is done by constructing the weak-form equations over the local subdomains. This paper proposes to approximate the unknown solution locally in the RBF-MLPG method, i.e., in the localized RBF-MLPG method, both solution approximation and testing are treated locally. As a result, the final global matrix becomes sparser and more accurate solutions can be obtained. The method is applied for the numerical solution of elliptic PDEs. The comparison of the results demonstrates the effectiveness of the method.

     

The application of Monte Carlo methods to the nonlinear filtering problem

The minimum variance estimates of state variables in a noisy, nonlinear discrete-time system are evaluated by a Monte Carlo method. The a posteriori probability density function for state variables conditioned upon measurement data sequence is expanded into a series of orthonormal Hermite functions and numerically determined in a recursive form. The numerical results indicate that the proposed method can markedly improve the accuracy by using the quasi-random numbers.     

Monte Carlo methods in fuzzy linear regression II

We apply our new fuzzy Monte Carlo method to a certain fuzzy linear regression problem to estimate the best solution. The best solution is a vector of crisp numbers, for the coefficients in the model, which minimizes one of two error measures. We use a quasi-random number generator to produce random sequences of these crisp vectors which uniformly fill the search space. We consider an example problem and show this Monte Carlo method obtains the best solution for both error measures.     

Monte Carlo方法与计算机模拟应用研究

介绍了Monte Carlo方法,提出其在模拟Buffer问题时存在的一个问题,并给出改进的方法;提出了用Monte Carlo方法产生任意分布随机变量的原理及方法,并对Beta分布和标准正态分布随机变量进行了计算机模拟和效果检验。     

Note on the Metropolis Monte Carlo method on random lattices

Efficiency of algorithms in the Metropolis Monte Carlo method is examined for the problem of random walks on random lattices. Three types of algorithms, which satisfy the detailed balance, are considered. The efficiency mainly depends on the relative ease in obtaining geometrical factors and Boltzmann factors. The most efficient algorithm for the dynamical triangulation of random surfaces is suggested.     

Reliable kinetic Monte Carlo simulation based on random set sampling

Kinetic Monte Carlo (KMC) method has been widely used in simulating rare events such as chemical reactions or phase transitions. Yet lack of complete knowledge of transitions and the associated rates is one major challenge for accurate KMC predictions. In this paper, a reliable KMC (R-KMC) mechanism is proposed in which sampling is based on random sets instead of random numbers to improve the robustness of KMC results. In R-KMC, rates or propensities are interval estimates instead of precise numbers. A multi-event algorithm based on generalized interval probability is developed. The weak convergence of the multi-event algorithm towards the traditional KMC is demonstrated with a generalized Chapman–Kolmogorov equation.