Search

This study deals with a narrow escape problem, a well-know difficult problem of evaluating the probability for a diffusing particle to reach a small part of a boundary far away from the starting position of the particle. A direct simulation of the diffusion trajectories would take an enormous computer simulation time. Instead, we use a different approach which drastically improves the efficiency of the diffusion trajectory tracking algorithm by introducing an artificial drift velocity directed to the target position. The method can be efficiently applied to solve narrow escape problems for domains of long extension in one direction which is the case in many practical problems in biology and chemistry. The algorithm is meshless both in space and time, and is well applied to solve high-dimensional problems in complicated domains. We present in this paper a detailed numerical analysis of the method for the case of a rectangular parallelepiped. Both stationary and transient diffusion problems are handled. [ABSTRACT FROM AUTHOR]

The generation of appropriate parallel and high-quality quasirandom sequences (low-discrepancy sequences) is crucial to the success of quasi-Monte Carlo methods. The Kronecker sequence is well known to be one of the special types of low-discrepancy sequences, and one of its important advantages is that the Kronecker sequence is easy to implement due to its definition via the fractional parts of multiples of irrationals. However, the original Kronecker sequence suffers from correlations for different dimensions. These correlations result in poorly distributed two-dimensional projections. An approach to this is to find a modified Kronecker sequence via generalizing golden ratio and generate parallel sequences. This paper presents a new algorithm for finding a modified Kronecker sequence within special choices of irrationals. This modified sequence is numerically tested and shown empirically to be superior to the other widely used quasirandom sequences. In addition, based on analysis and insight into the correlations between dimensions of the Kronecker sequence, we illustrate why our algorithm is efficient for breaking these correlations. [ABSTRACT FROM AUTHOR]

The ziggurat method is a fast random variable generation method introduced by Marsaglia and Tsang in a series of papers. We discuss how the ziggurat method can be implemented for low-discrepancy sequences, and present algorithms and numerical results when the method is used to generate samples from the normal and gamma distributions. [ABSTRACT FROM AUTHOR]

Matsumoto, Saito and Matoba recently proposed the Walsh figure of merit (WAFOM), which is a computable criterion for quasi-Monte Carlo point sets using digital nets. Several algorithms have been proposed for finding low-WAFOM point sets. In the existing algorithms, the number of points is fixed in advance, but extensible point sets are preferred in some applications. In this paper, we propose a random search algorithm for extensible low-WAFOM point sets. For this, we introduce a method that uses lookup tables to compute WAFOM faster. Numerical results show that our extensible low-WAFOM point sets are comparable with Niederreiter-Xing sequences for some low-dimensional and smooth test functions. [ABSTRACT FROM AUTHOR]

In this paper, we describe a stochastic algorithm to solve sudoku puzzles. Our method consists in computing probabilities for each symbol of each cell updated at each step of the algorithm using estimation of distributions algorithms (EDA). This update is done using the empirical estimators of these probabilities for a fraction of the best puzzles according to a cost function. We develop also some partial restart techniques in the RESEDA algorithm to obtain a convergence for the most difficult puzzles. Our algorithm is tested numerically on puzzles with various levels of difficulty starting from very easy ones to very hard ones including the famous puzzle AI Escargot. The CPU times vary from few hundreds of a second for the easy ones to about one minute for the most difficult one. [ABSTRACT FROM AUTHOR]

In this paper we propose an improved quasi-Monte Carlo method for solving Linear Algebra problems. We show that by using low-discrepancy sequences both the convergence and the CPU time of the algorithm are improved. Two parallelization schemes using the Message Passing Interface with static and dynamic load balancing are proposed. The dynamic scheme is useful for computing in the GRID environment. [ABSTRACT FROM AUTHOR]

We consider a new method using genetic algorithms to obtain lower bounds for the star discrepancy for any number of points in [0, 1] s. We compute lower bounds for the star discrepancy of samples of a number of sequences in several dimensions and successfully compare with existing results from the literature. Despite statements in the quasi-Monte Carlo literature stating that computing the star discrepancy is either intractable or requires a lot of computational work for s ≥ 3, we show that it is possible to compute the star discrepancy exactly or at the very least obtain reasonable lower bounds without a huge computational burden. Our method is fast and consistent and can be easily extended to estimate lower bounds of other discrepancy measures. Our method can be used by researchers to measure the uniformity quality of point sets as given by the star discrepancy rather than having to rely on the L2 discrepancy, which is easy to compute, but is flawed (and it is well known that the L2 discrepancy is flawed). [ABSTRACT FROM AUTHOR]

New stochastic algorithms for the numerical solution of systems of ordinary differential equations (ODEs) are proposed. Furthermore, a correspondence principle is established between these algorithms, which are based on the theory of Markov jump processes, and deterministic schemes. For one of the proposed stochastic algorithms, a detailed numerical study of some of its properties is carried out using examples from high-temperature homogeneous gas-phase combustion. One deterministic method yielded by our correspondence principle is used to shed light on various aspects of the considered stochastic algorithm. In addition, we use the widespread stiff ODE-solver package DASSL for comparison. Advantages of our methods include among others their exceptional simplicity of implementation and negligible start-up costs. For a large system at moderate accuracy requirements, the proposed stochastic algorithms exhibit computational efficiency in the same order of magnitude as implicit solvers, assuming multiple runs. In view of the stiffness of the considered systems and the explicit nature of our algorithms, this is rather surprising. Limitations of our methods concerning the choice of system, initial conditions, and accuracy requirements are also addressed. [ABSTRACT FROM AUTHOR]

Integral equations with Lipschitz kernels and right-hand sides are intractable for deterministic methods, the complexity increases exponentially in the dimension d. This is true even if we only want to compute a single function value of the solution. For this latter problem we study coin tossing algorithms (or restricted Monte Carlo methods), where only random bits are allowed. We construct a restricted Monte Carlo method with error e that uses roughly ε-2 function values and only d log² ε random bits. The number of arithmetic operations is of the order ε-2 + d log² ε. Hence, the cost of our algorithm increases only mildly with the dimension d, we obtain the upper bound C ⋅ (ε-2 + d log² ε) for the complexity. In particular, the problem is tractable for coin tossing algorithms. [ABSTRACT FROM AUTHOR]

The Halton sequence is one of the standard (along with (t, s)-sequences and lattice points) low-discrepancy sequences, and thus is widely used in quasi-Monte Carlo applications. One of its important advantages is that the Halton sequence is easy to implement due to its definition via the radical inverse function. However, the original Halton sequence suffers from correlations between radical inverse functions with different bases used for different dimensions. These correlations result in poorly distributed two-dimensional projections. A standard solution to this is to use a randomized (scrambled) version of the Halton sequence. Here, we analyze the correlations in the standard Halton sequence, and based on this analysis propose a new and simpler modified scrambling algorithm. We also provide a number theoretic criterion to choose the optimal scrambling from among a large family of random scramblings. Based on this criterion, we have found the optimal scrambling for up to 60 dimensions for the Halton sequence. This derandomized Halton sequence is then numerically tested and shown empirically to be far superior to the original sequence. [ABSTRACT FROM AUTHOR]

The methods which track particles to simulate concentrations are successfully used in problems for large scale transport in groundwater, mainly when the aquifer properties are spatially heterogeneous and the process is advection dominated. These methods, sometimes called "analogical Monte Carlo methods", are not concerned with the numerical diffusion occurring in finite difference/element schemes. The limitations of classical random walk methods are due to large computation time and memory necessary to achieve statistically reliable results and accurate concentration fields. To overcome these computational limitations a "global random walk" (GRW) algorithm was developed. Unlike in the usual approach where the trajectory of each particle is simulated and stored, in GRW all the particles from a given grid node are scattered, at a given time, using a single numerical procedure, based on Bernoulli distribution, partial-deterministic, or deterministic rules. Because no restrictions are imposed for the maximum number of particles to be used in a simulation, the Monte Garlo repetitions are no longer necessary to achieve the convergence. It was proved that for simple diffusion problems GRW converges to the finite difference scheme and that for large scale transport problems in ground-water, GRW produces stable and statistically reliable simulations. A 2-dimensional transport problem was modeled by simulating local diffusion processes in realizations of a random velocity field. The behavior over 5000 days of the effective diffusion coefficients, concentration field and concentration fluctuations were investigated using 2560 realizations of the velocity field and 1010 particles in every realization. The results confirm the order of magnitude of the effective diffusion coefficients predicted by stochastic theory but the time needed to reach the asymptotic regime was found to be thousands times larger. It is also underlined that the concentration fluctuations and... [ABSTRACT FROM AUTHOR]