Narrow Results

We present the results in embedding a multigrid solver for Poisson's equation into the parallel 3D Monte Carlo device simulator, PMC-3D. First we have implemented the sequential multigrid solver, and embedded it into the Monte Carlo code which previously was using the sequential successive overrelaxation (SOR) solver. Depending on the convergence threshold, we have obtained significant speedups ranging from 5 to 15 on a single HP 712/80 workstation. We have also implemented the parallel multigrid solver by extending the partitioning algorithm and the interprocessor communication routines of the SOR solver in order to service multiple grids. The Monte Carlo code with the parallel multigrid Poisson solver is 3 to 9 times faster than the Monte Carlo code with the parallel SOR code, based on timing results on a 32-node nCUBE multiprocessor.

In this work, a general Monte Carlo framework is proposed for applying numerical knot invariants in simulations of systems containing knotted one-dimensional ring-shaped objects like polymers and vortex lines in fluids, superfluids or other quantum liquids. A general prescription for smoothing the sharp corners appearing in discrete knots consisting of segments joined together is provided. Smoothing is very important for the correct evaluation of numerical knot invariants.

A discrete version of framing is adopted in order to eliminate singularities that are possibly arising when computing the invariants. The presented algorithms for smoothing, eliminating potentially dangerous singularities and speeding up the calculations are quite general and can be applied to any discrete knot defined off- or on-lattice.

This is one of the first attempts to use numerical knot invariants in order to avoid potential topology breakings during the sampling process taking place in computer simulations, in which millions of knot conformations are randomly generated. As an application, the energy domain of knotted polymer rings subjected to short-range interactions is studied using the so-called Vassiliev knot invariant of degree 2.

We apply a newly-developed computational method, Geometric Random Inner Products (GRIP), to quantify the randomness of number sequences obtained from the decimal digits of π. Several members from the GRIP family of tests are used, and the results from π are compared to those calculated from other random number generators. These include a recent hardware generator based on an actual physical process, turbulent electroconvection. We find that the decimal digits of π are in fact good candidates for random number generators and can be used for practical scientific and engineering computations.

The rural-urban migration phenomenon is analyzed by using an agent-based computational model. Agents are placed on lattices which dimensions varying from d =2 up to d =7. The localization of the agents in the lattice defines that their social neighborhood (rural or urban) is not related to their spatial distribution. The effect of the dimension of lattice is studied by analyzing the variation of the main parameters that characterizes the migratory process. The dynamics displays strong effects even for around one million of sites, in higher dimensions (d =6, 7).

The norm game described by Axelrod in 1985 was recently treated with the master equation formalism. Here we discuss the equations, where (i) those who break the norm cannot punish and those who punish cannot break the norm, (ii) the tendency to punish is suppressed if the majority breaks the norm. The second mechanism is new. For some values of the parameters the solution shows the saddle-point bifurcation. Then, two stable solutions are possible, where the majority breaks the norm or the majority punishes. This means, that the norm breaking can be discontinuous, when measured in the social scale. The bistable character is reproduced also with new computer simulations on the Erdös–Rényi directed network.

The uniform sampling of convex regions in high dimension is an important computational issue, both from theoretical and applied point of view. The hit-and-run Monte Carlo algorithms are the most efficient methods known to perform it and one of their bottlenecks relies in the difficulty of escaping from tight corners in high dimension. Inspired by optimized Monte Carlo methods used in statistical mechanics, we define a new algorithm by over-relaxing the hit-and-run dynamics. We made numerical simulations on high-dimensional simplexes and hypercubes in order to test its performances, pointing out its improved ability to escape from angles and finally apply it to an inference problem in the steady state dynamics of metabolic networks.

For a homogeneous system divisible into identical, weakly interacting subsystems, the multicanonical procedure can be accelerated if it is first applied to determine the density of states for a single subsystem. This result is then employed to approximate the state density of a subsystem with twice the size that forms the starting point of a new multicanonical iteration. Since this compound subsystem interacts less on average with its environment, iterating this sequence of steps rapidly generates the state density of the full system.

A sampling procedure for the transition matrix Monte Carlo method is introduced that generates the density of states function over a wide parameter range with minimal coding effort.

In this work, the Gardner problem of inferring interactions and fields for an Ising neural network from given patterns under a local stability hypothesis is addressed under a dual perspective. By means of duality arguments, an integer linear system is defined whose solution space is the dual of the Gardner space and whose solutions represent mutually unstable patterns. We propose and discuss Monte Carlo methods in order to find and remove unstable patterns and uniformly sample the space of interactions thereafter. We illustrate the problem on a set of real data and perform ensemble calculation that shows how the emergence of phase dominated by unstable patterns can be triggered in a nonlinear discontinuous way.

Minesweeper is a famous computer game consisting usually in a two-dimensional lattice, where cells can be empty or mined and gamers are required to locate the mines without dying. Even if minesweeper seems to be a very simple system, it has some complex and interesting properties as NP-completeness. In this paper and for the one-dimensional case, given a lattice of n cells and m mines, we calculate the winning probability. By numerical simulations this probability is also estimated. We also find out by mean of these simulations that there exists a critical density of mines that minimize the probability of winning the game. Analytical results and simulations are compared showing a very good agreement.

We analyze the structure of the periodic trajectories of the K-system generator of pseudorandom numbers on a rational sublattice which coincides with the Galois field GF[p]. The period of the trajectories increases as a function of the lattice size p and the dimension of the K-matrixd. We emphasize the connection of this approach with the one which is based on primitive matrices over Galois fields.

There are 880 magic squares of size 4 by 4, and 275 305 224 of size 5 by 5. It seems very difficult if not impossible to count exactly the number of higher order magic squares. We propose a method to estimate these numbers by Monte Carlo simulating magic squares at finite temperature. One is led to perform low temperature simulations of a system with many ground states that are separated by energy barriers. The Parallel Tempering Monte Carlo method turns out to be of great help here. Our estimate for the number of 6 by 6 magic squares is (0.17745± 0.00016)×10²⁰.

The random deposition model must be enhanced to reflect the variety of surface roughness due to some material characteristics of the film growing by vacuum deposition or sputtering. The essence of the computer simulation in this case is to account for possible surface migration of atoms just after the deposition, in connection with the binding energy between atoms (as the mechanism provoking the diffusion) and/or diffusion energy barrier. The interplay of these two factors leads to different morphologies of the growing surfaces, from flat and smooth ones to rough and spiky ones. In this paper, we extended our earlier calculation by applying an extra diffusion barrier at the edges of terrace-like structures, known as the Ehrlich–Schwoebel barrier. It is experimentally observed that atoms avoid descending when the terrace edge is approached, and these barriers mimic this tendency. Results of our Monte Carlo computer simulations are discussed in terms of surface roughness, and compared with other model calculations and some experiments from literature. The power law of the surface roughness σ against film thickness t was confirmed. The nonzero minimum value of the growth exponent β near 0.2 was obtained which is due to the limited range of the surface diffusion and the Ehrlich–Schwoebel barrier. Observations for different diffusion ranges are also discussed. The results are also confirimed with some deterministic growth models.

In this paper we present a generalization of a simple solid-on-solid epitaxial model of thin film growth, when surface morphology anisotropy is provoked by anisotropy in the model control parameters of binding energy and/or diffusion barrier. The anisotropy is discussed in terms of the height–height correlation function. It was experimentally confirmed that the difference in diffusion barriers yields anisotropy in morphology of the surface. We obtained antisymmetric correlations in the two in-plane directions for antisymmetric binding.

Neutron oscillation into mirror neutron, a sterile state exactly degenerate in mass with the neutron, could be a very rapid process, even faster than the neutron decay itself. It can be observed by comparing the neutron lose rates in an ultracold neutron trapping experiment for different experimental magnetic fields. We developed a Monte Carlo code that simulates many of the features of this kind of experiment with nonuniform magnetic fields. The aim of the simulation is to provide all necessary tools, needed for analyzing experimental results for neutron traps with different geometry and different configurations of magnetic fields. This work contains technical details on the Monte Carlo simulation used for the analysis in Ref. 46 not presented in it.

The deconvolution method has received much attention recently, and is becoming one of the major tools for well test and production data analysis in oil and gas industry. Here, we present a new deconvolution approach, which we believe is relevant and can be an important addition to the existing efforts made in this field. We show that the solution of the deconvolution problem can be successfully represented as a linear combination of non-orthogonal exponential functions. Also, we present three deconvolution algorithms. The first two algorithms are based on regularization concepts borrowed from the well-known Tikhonov and Krylov methods, while the third algorithm is based on the stochastic Monte Carlo method.

Within the framework of the extended Hubbard model on a hexagonal lattice, the effect of sublattice symmetry breaking on the position of the semimetal-antiferromagnet phase transition is studied. The study is carried out using the Quantum Monte Carlo method with five auxiliary Hubbard fields. It is shown that the difference in the intensity of the on-site interaction of electrons on the sublattices leads to a shift of the phase transition point towards lower values of the interaction parameter. An antiferromagnetic condensate is considered.

The Diffusion Monte Carlo (DMC) method is a powerful strategy to estimate the ground state energy E₀ of an N-body Schrödinger Hamiltonian H = -½Δ + V with high accuracy. It consists of writing E₀ as the long-time limit of an expectation value of a drift-diffusion process with a source term, and numerically simulating this process by means of a collection of random walkers. As for a number of stochastic methods, a DMC calculation makes use of an importance sampling function ψ_I which hopefully approximates some ground state ψ₀ of H. In the fermionic case, it has been observed that the DMC method is biased, except in the special case when the nodal surfaces of ψ_I coincide with those of a ground state of H. The approximation due to the fact that, in practice, the nodal surfaces of ψ_I differ from those of the ground states of H, is referred to as the Fixed Node Approximation (FNA). Our purpose in this paper is to provide a mathematical analysis of the FNA. We prove that, under convenient hypotheses, a DMC calculation performed with the importance sampling function ψ_I, provides an estimation of the infimum of the energy 〈ψ, Hψ〉 on the set of the fermionic test functions ψ that exactly vanish on the nodal surfaces of ψ_I.

This paper develops bridge sampling path integral algorithms for pricing path-dependent options under a new class of nonlinear state dependent volatility models. Path-dependent option pricing is considered within a new (dual) Bessel family of semimartingale diffusion models, as well as the constant elasticity of variance (CEV) diffusion model, arising as a particular case of these models. The transition p.d.f.s or pricing kernels are mapped onto an underlying simpler squared Bessel process and are expressed analytically in terms of modified Bessel functions. We establish precise links between pricing kernels of such models and the randomized gamma distributions, and thereby demonstrate how a squared Bessel bridge process can be used for exact sampling of the Bessel family of paths. A Bessel bridge algorithm is presented which is based on explicit conditional distributions for the Bessel family of volatility models and is similar in spirit to the Brownian bridge algorithm. A special rearrangement and splitting of the path integral variables allows us to combine the Bessel bridge sampling algorithm with either adaptive Monte Carlo algorithms, or quasi-Monte Carlo techniques for significant numerical efficiency improvement. The algorithms are illustrated by pricing Asian-style and lookback options under the Bessel family of volatility models as well as the CEV diffusion model.

This paper investigates the use of multiple directions of stratification as a variance reduction technique for Monte Carlo simulations of path-dependent options driven by Gaussian vectors. The precision of the method depends on the choice of the directions of stratification and the allocation rule within each strata. Several choices have been proposed but, even if they provide variance reduction, their implementation is computationally intensive and not applicable to realistic payoffs, in particular not to Asian options with barrier. Moreover, all these previously published methods employ orthogonal directions for multiple stratification. In this work we investigate the use of algorithms producing convenient directions, generally non-orthogonal, combining a lower computational cost with a comparable variance reduction. In addition, we study the accuracy of optimal allocation in terms of variance reduction compared to the Latin Hypercube Sampling. We consider the directions obtained by the Linear Transformation and the Principal Component Analysis. We introduce a new procedure based on the Linear Approximation of the explained variance of the payoff using the law of total variance. In addition, we exhibit a novel algorithm that permits to correctly generate normal vectors stratified along non-orthogonal directions. Finally, we illustrate the efficiency of these algorithms in the computation of the price of different path-dependent options with and without barriers in the Black-Scholes and in the Cox-Ingersoll-Ross markets.