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.     

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     

Random generation of monotonic functions for Monte Carlo solution of qualitative differential equations

We present improvements to the function representation and generation method used in the Monte Carlo analysis of incomplete ordinary differential equations. Our method widens the scope of the technique to cover cases in which no envelopes have been specified for the function under consideration, thereby extending the applicability of the Monte Carlo approach to the full repertoire of models developed for qualitative reasoning algorithms, and paving the ground for the integrated operation of these two highly complementary techniques. Our new representation does not entail unjustified implicit assumptions about the shape of the generated functions, and provides better coverage of the space of models defined by the input specifications. Our simulator (MOCASSIM) also has the capability of imposing additional restrictions (e.g., convexity) on function shapes, which is particularly useful when the Monte Carlo technique is applied for solving system dynamics problems.     

An incomplete nested dissection algorithm for parallel direct solution of finite element discretizations of partial differential equations

A multilevel algorithm is presented for direct, parallel factorization of the large sparse matrices that arise from finite element and spectral element discretization of elliptic partial differential equations. Incomplete nested dissection and domain decomposition are used to distribute the domain among the processors and to organize the matrix into sections in which pivoting is applied to stabilize the factorization of indefinite equation sets. The algorithm is highly parallel and memory efficient; the efficient use of sparsity in the matrix allows the solution of larger problems as the number of processors is increased, and minimizes computations as well as the number and volume of communications among the processors. The number of messages and the total volume of messages passed during factorization, which are used as measures of algorithm efficiency, are reduced significantly compared to other algorithms. Factorization times are low and speedups high for implementation on an Intel iPSC/860 hypercube computer. Furthermore, the timings for forward and back substitutions are more than an order-of-magnitude smaller than the matrix decomposition times.     

Monte Carlo parallel algorithm for long range interactions

We show the use of the homogenous architecture in the parallel processing of long range interactions. We describe the implementation of a Monte Carlo algorithm for a two-dimensional Coulomb system on a parallel processor with hypercubic geometry (the 8-node concurrent processor at Caltech).Our results indicate that long range problems can be efficiently implemented on parallel machines.     

A parallel Monte Carlo search algorithm for the conformational analysis of polypeptides

In recent years several approaches have been proposed to overcome the multiple-minima problem associated with nonlinear optimization techniques used in the analysis of molecular conformations. One such technique based on a parallel Monte Carlo search algorithm is analyzed. Experiments on the Intel iPSC/2 confirm that the attainable parallelism is limited by the underlying acceptance rate in the Monte Carlo search. It is proposed that optimal performance can be achieved in combination with vector processing. Tests on both the IBM 3090 and Intel iPSC/2-VX indicate that vector performance is related to molecule size and vector pipeline latency.     

A random walk algorithm for automatic construction of domain-oriented sentiment lexicon

In recent years, many studies have been conducted to deal with automatic construction of domain-oriented sentiment lexicon. However, most of the attempts rely on only the relationship between sentiment words, failing to uncover the mutual relationship between the words and the documents, as well as ignoring the useful knowledge of some existed domains (or “old domain”). This paper proposes a random walk algorithm to construct domain-oriented sentiment lexicon by simultaneously utilizing sentiment words and documents from both old domain and target domain (or “new domain”). The approach simulates a random walk on the graphs that reflect four kinds of relationships (the relationship between words, the relationship from words to documents, the relationship between documents, the relationship from documents to words) between documents and words. Experimental results indicate that the proposed algorithm could dramatically improve the performance of automatic construction of domain-oriented sentiment lexicon.     

A new parallel domain decomposition method for the adaptive finite element solution of elliptic partial differential equations

We present a new domain decomposition algorithm for the parallel finite element solution of elliptic partial differential equations. As with most parallel domain decomposition methods each processor is assigned one or more subdomains and an iteration is devised which allows the processors to solve their own subproblem(s) concurrently. The novel feature of this algorithm however is that each of these subproblems is defined over the entire domain—although the vast majority of the degrees of freedom for each subproblem are associated with a single subdomain (owned by the corresponding processor). This ensures that a global mechanism is contained within each of the subproblems tackled and so no separate coarse grid solve is required in order to achieve rapid convergence of the overall iteration. Furthermore, by following the paradigm introduced in 15 , it is demonstrated that this domain decomposition solver may be coupled easily with a conventional mesh refinement code, thus allowing the accuracy, reliability and efficiency of mesh adaptivity to be utilized in a well load-balanced manner. Finally, numerical evidence is presented which suggests that this technique has significant potential, both in terms of the rapid convergence properties and the efficiency of the parallel implementation. Copyright © 2001 John Wiley & Sons, Ltd.     

A parallel multistep predictor-corrector algorithm for solving ordinary differential equations

In this paper we give a generalized predictor-corrector algorithm for solving ordinary differential equations with specified initial values. The method uses multiple correction steps which can be carried out in parallel with a prediction step. The proposed method gives a larger stability interval compared to the existing parallel predictor-corrector methods. A method has been suggested to implement the algorithm in multiple processor systems with efficient utilization of all the processors.     

A family of third-order parallel splitting methods for parabolic partial differential equations

A family of numerical methods, based upon a new rational approximation to the matrix exponential function, is developed for solving parabolic partial differential equations. These methods are L-acceptable, third-order accurate in space and time, and do not require the use of complex arithmetic. In these methods second-order spatial derivatives are approximated by third-order finite-difference approximations.- Parallel algorithms are developed and tested on the one-dimensional heat equation, with constant coefficients, subject to homogeneous boundary conditions and time-dependent boundary conditions. These methods are also extended to two- and three-dimensional heat equations, with constant coefficients, subject to homogeneous boundary conditions.     

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.     

A new algorithm for numerical solution of ordinary differential equations

A numerical integration scheme which is particularly well suited to initial value problems having oscillatory or exponential solutions is proposed. The derivation of the algorithm is based on a representation of problems (that is problems having oscillatory or exponential solutions), the complex parameters have the real plane. The interpolating function has two complex parameters whose numerical estimates are obtained by using Newton-like scheme to solve three simultaneous nonlinear equations. For the above class of paoblems (that is problems having oscillatory or exponential solutions), the complex parameters have constant values throughout the interval of integration. Hence, the parameters are obtainable at the first integration step. As the approach is applicable to systems of equations, then for an initial value problem of order m, m sets of simultaneous equations have to be solved for the complex parameters.     

A comparison of numerical methods for the solution of quasilinear partial differential equations

Various methods of approximating a parabolic partial differential equation by a system of ordinary differential equations are discussed. The methods are compared using the results of numerical experiments with a highly efficient integration procedure designed for this type of problem.     

A parallel algorithm for exact solution of linear equations via congruence technique

We present a parallel algorithm for computing the exact solution of a system of linear equations via the congruence technique. The basic idea of the technique is to convert the original system of equations into a system of congruences modulo various primes, and combine the solutions by the application of the Chinese remainder theorem. The parallel congruence algorithm proposed in this paper requires only local communication among the processors and is particularly suitable for implementation on distributed-memory multiprocessors and systolic computing systems. We have implemented the parallel congruence algorithm on an Intel cube and obtained an efficiency of greater than 90%.     

A symbolic algorithm for computing recursion operators of nonlinear partial differential equations

A recursion operator is an integro-differential operator which maps a generalized symmetry of a nonlinear partial differential equation (PDE) to a new symmetry. Therefore, the existence of a recursion operator guarantees that the PDE has infinitely many higher-order symmetries, which is a key feature of complete integrability. Completely integrable nonlinear PDEs have a bi-Hamiltonian structure and a Lax pair; they can also be solved with the inverse scattering transform and admit soliton solutions of any order.

A straightforward method for the symbolic computation of polynomial recursion operators of nonlinear PDEs in (1+1) dimensions is presented. Based on conserved densities and generalized symmetries, a candidate recursion operator is built from a linear combination of scaling invariant terms with undetermined coefficients. The candidate recursion operator is substituted into its defining equation and the resulting linear system for the undetermined coefficients is solved.

The method is algorithmic and is implemented in Mathematica. The resulting symbolic package PDERecursionOperator.m can be used to test the complete integrability of polynomial PDEs that can be written as nonlinear evolution equations. With PDERecursionOperator.m, recursion operators were obtained for several well-known nonlinear PDEs from mathematical physics and soliton theory.     

面向多智能体博弈的并行蒙特卡洛树搜索算法研究

蒙特卡洛树搜索算法是一种常用的强化学习算法,博弈过程中动态空间的指数级增长是制约该算法学习效率的因素。基于并行方法对蒙特卡洛树搜索算法进行优化,提出基于胜率估值传递的并行蒙特卡洛树搜索算法。改进后的并行博弈搜索策略框架包含一个主进程和多个子进程,其中子进程用于探索,主进程根据子进程传递的胜率估值数据进行决策。结合多智能体博弈平台Pommerman进行实验验证,与传统的蒙特卡罗树搜索算法相比,并行蒙特卡罗树搜索算法有效提高了资源利用率、博弈胜率及决策效率。     

The BEM for numerical solution of partial fractional differential equations

A numerical method is presented for the solution of partial fractional differential equations (FDEs) arising in engineering applications and in general in mathematical physics. The solution procedure applies to both linear and nonlinear problems described by evolution type equations involving fractional time derivatives in bounded domains of arbitrary shape. The method is based on the concept of the analog equation, which in conjunction with the boundary element method (BEM) enables the spatial discretization and converts a partial FDE into a system of coupled ordinary multi-term FDEs. Then this system is solved using the numerical method for the solution of such equations developed recently by Katsikadelis. The method is illustrated by solving second order partial FDEs and its efficiency and accuracy is validated.