FiEstAS sampling—a Monte Carlo algorithm for multidimensional numerical integration

This paper describes a new algorithm for Monte Carlo integration, based on the Field Estimator for Arbitrary Spaces (FiEstAS). The algorithm is discussed in detail, and its performance is evaluated in the context of Bayesian analysis, with emphasis on multimodal distributions with strong parameter degeneracies. Source code is available upon request.     

Error in Monte Carlo, quasi-error in Quasi-Monte Carlo

While the Quasi-Monte Carlo method of numerical integration achieves smaller integration error than standard Monte Carlo, its use in particle physics phenomenology has been hindered by the absence of a reliable way to estimate that error. The standard Monte Carlo error estimator relies on the assumption that the points are generated independently of each other and, therefore, fails to account for the error improvement advertised by the Quasi-Monte Carlo method. We advocate the construction of an estimator of stochastic nature, based on the ensemble of pointsets with a particular discrepancy value. We investigate the consequences of this choice and give some first empirical results on the suggested estimators.     

Importance sampling in rigid body diffusion Monte Carlo

We present an algorithm for rigid body diffusion Monte Carlo with importance sampling, which is based on a rigorous short-time expansion of the Green's function for rotational motion in three dimensions. We show that this short-time approximation provides correct sampling of the angular degrees of freedom, and provides a general way to incorporate importance sampling for all degrees of freedom. The full importance sampling algorithm significantly improves both calculational efficiency and accuracy of ground state properties, and allows rotational and bending excitations in molecular van der Waals clusters to be studied directly.     

A Mathematica program for the two-step twelfth-order method with multi-derivative for the numerical solution of a one-dimensional Schrödinger equation

In this paper, we present the detailed Mathematica symbolic derivation and the program which is used to integrate a one-dimensional Schrödinger equation by a new two-step numerical method. We add the fourth- and sixth-order derivatives to raise the precision of the traditional Numerov's method from fourth order to twelfth order, and to expand the interval of periodicity from (0,6) to the one of (0,9.7954) and (9.94792,55.6062). In the program we use an efficient algorithm to calculate the first-order derivative and avoid unnecessarily repeated calculation resulting from the multi-derivatives. We use the well-known Woods-Saxon's potential to test our method. The numerical test shows that the new method is not only superior to the previous lower order ones in accuracy, but also in the efficiency. This program is specially applied to the problem where a high accuracy or a larger step size is required.

Program summary

Title of program: ShdEq.nbCatalogue number: ADTTProgram summary URL:http://cpc.cs.qub.ac.uk/summaries/ADTTProgram obtainable from: CPC Program Library, Queen's University of Belfast, N. IrelandLicensing provisions: noneComputer for which the program is designed and others on which it has been tested: The program has been designed for the microcomputer and been tested on the microcomputer.Computers: IBM PCOperating systems under which the program has been tested: Windows XPProgramming language used: Mathematica 4.2Memory required to execute with typical data: 51 712 bytesNo. of bytes in distributed program, including test data, etc.: 45 381No. of lines in distributed program, including test data, etc.: 7311Distribution format: tar gzip fileCPC Program Library subprograms used: noNature of physical problem: Numerical integration of one-dimensional or radial Schrödinger equation to find the eigenvalues for a bound states and phase shift for a continuum state.Method of solution: Using a two-step method twelfth-order method to integrate a Schrödinger equation numerically from both two ends and the connecting conditions at the matching point, an eigenvalue for a bound state or a resonant state with a given phase shift can be found.Restrictions on the complexity of the problem: The analytic form of the potential function and its high-order derivatives must be known.Typical running time: Less than one second.Unusual features of the program: Take advantage of the high-order derivatives of the potential function and efficient algorithm, the program can provide all the numerical solution of a given Schrödinger equation, either a bound or a resonant state, with a very high precision and within a very short CPU time. The program can apply to a very broad range of problems because the method has a very large interval of periodicity.References: [1] T.E. Simos, Proc. Roy. Soc. London A 441 (1993) 283.[2] Z. Wang, Y. Dai, An eighth-order two-step formula for the numerical integration of the one-dimensional Schrödinger equation, Numer. Math. J. Chinese Univ. 12 (2003) 146.[3] Z. Wang, Y. Dai, An twelfth-order four-step formula for the numerical integration of the one-dimensional Schrödinger equation, Internat. J. Modern Phys. C 14 (2003) 1087.     

Quantum Monte Carlo on graphical processing units

Quantum Monte Carlo (QMC) is among the most accurate methods for solving the time independent Schrödinger equation. Unfortunately, the method is very expensive and requires a vast array of computing resources in order to obtain results of a reasonable convergence level. On the other hand, the method is not only easily parallelizable across CPU clusters, but as we report here, it also has a high degree of data parallelism. This facilitates the use of recent technological advances in Graphical Processing Units (GPUs), a powerful type of processor well known to computer gamers. In this paper we report on an end-to-end QMC application with core elements of the algorithm running on a GPU. With individual kernels achieving as much as 30× speed up, the overall application performs at up to 6× faster relative to an optimized CPU implementation, yet requires only a modest increase in hardware cost. This demonstrates the speedup improvements possible for QMC in running on advanced hardware, thus exploring a path toward providing QMC level accuracy as a more standard tool. The major current challenge in running codes of this type on the GPU arises from the lack of fully compliant IEEE floating point implementations. To achieve better accuracy we propose the use of the Kahan summation formula in matrix multiplications. While this drops overall performance, we demonstrate that the proposed new algorithm can match CPU single precision.     

Computation of the eigenvalues of the Schrödinger equation by exponentially-fitted Runge-Kutta-Nyström methods

In this work we consider exponentially fitted and trigonometrically fitted Runge-Kutta-Nyström methods. These methods integrate exactly differential systems whose solutions can be expressed as linear combinations of the set of functions exp(wx), exp(−wx), or sin(wx), cos(wx), w∈ℜ. We modify existing RKN methods of fifth and sixth order. We apply these methods to the computation of the eigenvalues of the Schrödinger equation with different potentials as the harmonic oscillator, the doubly anharmonic oscillator and the exponential potential.     

Trigonometrically-fitted method with the Fourier frequency spectrum for undamped Duffing equation

With non-linearities, the frequency spectrum of an undamped Duffing oscillator should be composed of odd multiples of the driving frequency which can be interpreted as resonance driving terms. It is expected that the frequency spectrum of the corresponding numerical solution with high accurateness should contain nearly the same components. Hence, to contain these Fourier components and to calculate the amplitudes of these components in a more accurate and efficient way is the key to develop a new numerical method with high stability, accuracy and efficiency for the Duffing equation. To explore the possibility of using trigonometrically-fitting technique to build a numerical method with resonance spectrum, we design four types of Numerov methods, in which the first one is the traditional Numerov method, which contains no Fourier component, the second one contains only the first resonance term, the third one contains the first two resonance terms, and the last one contains the first three resonance terms, and apply them to the well-known undamped Duffing equation with Dooren's parameters. The numerical results demonstrate that the Numerov method fitted with the Fourier components is much more stable, accurate and efficient than the one with no Fourier component. The accuracy of the fitted method with the first three Fourier components can attain 10⁻⁹ for a remarkable range of step sizes, including nearly infinite, except individual small range of instability, which is much higher than the one of the traditional Numerov method, with eight orders for step size of π/2.011.     

On the performance of SPAI and ADI-like preconditioners for core collapse supernova simulations in one spatial dimension

The simulation of core collapse supernovæ calls for the time accurate solution of the (Euler) equations for inviscid hydrodynamics coupled with the equations for neutrino transport. The time evolution is carried out by evolving the Euler equations explicitly and the neutrino transport equations implicitly. Neutrino transport is modeled by the multi-group Boltzmann transport (MGBT) and the multi-group flux limited diffusion (MGFLD) equations. An implicit time stepping scheme for the MGBT and MGFLD equations yields Jacobian systems that necessitate scaling and preconditioning. Two types of preconditioners, namely, a sparse approximate inverse (SPAI) preconditioner and a preconditioner based on the alternating direction implicit iteration (ADI-like) have been found to be effective for the MGFLD and MGBT formulations. This paper compares these two preconditioners. The ADI-like preconditioner performs well with both MGBT and MGFLD systems. For the MGBT system tested, the SPAI preconditioner did not give competitive results. However, since the MGBT system in our experiments had a high condition number before scaling and since we used a sequential platform, care must be taken in evaluating these results.     

A new kind of high-efficient and high-accurate P-stable Obrechkoff three-step method for periodic initial-value problems

In order to improve the efficiency and accuracy of the previous Obrechkoff method, in this paper we put forward a new kind of P-stable three-step Obrechkoff method of O(h¹⁰) for periodic initial-value problems. By using a new structure and an embedded high accurate first-order derivative formula, we can avoid time-consuming iterative calculation to obtain the high-order derivatives. By taking advantage of new trigonometrically-fitting scheme we can make both the main structure and the first-order derivative formula to be P-stable. We apply our new method to three periodic problems and compare it with the previous three Obrechkoff methods. Numerical results demonstrate that our new method is superior over the previous ones in accuracy, efficiency and stability.     

Parallel Monte Carlo Driver (PMCD)—a software package for Monte Carlo simulations in parallel

Thanks to the dramatic decrease of computer costs and the no less dramatic increase in those same computer's capabilities and also thanks to the availability of specific free software and libraries that allow the set up of small parallel computation installations the scientific community is now in a position where parallel computation is within easy reach even to moderately budgeted research groups. The software package PMCD (Parallel Monte Carlo Driver) was developed to drive the Monte Carlo simulation of a wide range of user supplied models in parallel computation environments. The typical Monte Carlo simulation involves using a software implementation of a function to repeatedly generate function values. Typically these software implementations were developed for sequential runs. Our driver was developed to enable the run in parallel of the Monte Carlo simulation, with minimum changes to the original code that implements the function of interest to the researcher. In this communication we present the main goals and characteristics of our software, together with a simple study its expected performance. Monte Carlo simulations are informally classified as “embarrassingly parallel”, meaning that the gains in parallelizing a Monte Carlo run should be close to ideal, i.e. with speed ups close to linear. In this paper our simple study shows that without compromising the easiness of use and implementation, one can get performances very close to the ideal.     

CANM, a program for numerical solution of a system of nonlinear equations using the continuous analog of Newton's method

A FORTRAN program is presented which solves a system of nonlinear simultaneous equations using the continuous analog of Newton's method (CANM). The user has the option of either to provide a subroutine which calculates the Jacobian matrix or allow the program to calculate it by a forward-difference approximation. Five iterative schemes using different algorithms of determining adaptive step size of the CANM process are implemented in the program.

Program summary

Title of program: CANMCatalogue number: ADSNProgram summary URL:http://cpc.cs.qub.ac.uk/summaries/ADSNProgram available from: CPC Program Library, Queen's University of Belfast, Northern IrelandLicensing provisions: noneComputer for which the program is designed and others on which it has been tested:Computers: IBM RS/6000 Model 320H, SGI Origin2000, SGI Octane, HP 9000/755, Intel Pentium IV PCInstallation: Department of Chemistry, University of Toronto, Toronto, CanadaOperating systems under which the program has been tested: IRIX64 6.1, 6.4 and 6.5, AIX 3.4, HP-UX 9.01, Linux 2.4.7Programming language used: FORTRAN 90Memory required to execute with typical data: depends on the number of nonlinear equations in a system. Test run requires 80 KBNo. of bits in distributed program including test data, etc.: 15283Distribution format: tar gz formatNo. of lines in distributed program, including test data, etc.: 1794Peripherals used: line printer, scratch disc storeExternal subprograms used: DGECO and DGESL [1]Keywords: nonlinear equations, Newton's method, continuous analog of Newton's method, continuous parameter, evolutionary differential equation, Euler's methodNature of physical problem: System of nonlinear simultaneous equations

     

An optimized algorithm for ionized impurity scattering in Monte Carlo simulations

We present a new optimized model of Brookes-Herring ionized impurity scattering for use in Monte Carlo simulations of semiconductors. When implemented, it greatly decreases the execution time needed for simulations (typically by a factor of the order of 100), and also properly incorporates the great proportion of small angle scatterings that are neglected in the standard algorithm. It achieves this performance by using an anisotropic choice of scattering angle which accurately mimics the true angular distribution of ionized impurity scattering.     

Arbitrarily precise numerical solutions of the one-dimensional Schrödinger equation

In this paper, how to overcome the barrier for a finite difference method to obtain the numerical solutions of a one-dimensional Schrödinger equation defined on the infinite integration interval accurate than the computer precision is discussed. Five numerical examples of solutions with the error less than 10⁻⁵⁰ and 10⁻³⁰ for the bound and resonant state, respectively, obtained by the Obrechkoff one-step method implemented in the multi precision mode, which include the harmonic oscillator, the Pöschl-Teller potential, the Morse potential and the Woods-Saxon potential, demonstrate that the finite difference method can yield the eigenvalues of a complex potential with an arbitrarily desired precision within a reasonable efficiency.     

Computing zeros of analytic functions in the complex plane without using derivatives

We present a package in Fortran 90 which solves f(z)=0, where z∈W⊂C without requiring the evaluation of derivatives, f^′(z). W is bounded by a simple closed curve and f(z) must be holomorphic within W.We have developed and tested the package to support our work in the modeling of high frequency and optical wave guiding and resonant structures. The respective eigenvalue problems are particularly challenging because they require the high precision computation of all multiple complex roots of f(z) confined to the specified finite domain. Generally f(z), despite being holomorphic, does not have explicit analytical form thereby inhibiting evaluation of its derivatives.

Program summary

Title of program:EZEROCatalogue identifier:ADXY_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/ADXY_v1_0Program obtainable from:CPC Program Library, Queen's University of Belfast, N. IrelandComputer:IBM compatible desktop PCOperating system:Fedora Core 2 Linux (with 2.6.5 kernel)Programming languages used:Fortran 90No. of bits in a word:32No. of processors used:oneHas the code been vectorized:noNo. of lines in distributed program, including test data, etc.:21045Number of bytes in distributed program including test data, etc.:223 756Distribution format:tar.gzPeripherals used:noneMethod of solution:Our package uses the principle of the argument to count the number of zeros encompassed by a contour and then computes estimates for the zeros. Refined results for each zero are obtained by application of the derivative-free Halley method with or without Aitken acceleration, as the user wishes.     

ExHuME 1.3: A Monte Carlo event generator for exclusive diffraction

We have written the Exclusive Hadronic Monte Carlo Event (ExHuME) generator. ExHuME is based around the perturbative QCD calculation of Khoze, Martin and Ryskin of the process pp→p+X+p, where X is a centrally produced colour singlet system.

Program summary

Title of program:ExHuMECatalogue identifier:ADYA_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/ADYA_v1_0Program obtainable from:CPC Program Library, Queen's University of Belfast, N. IrelandLicensing provisions:NoneProgramming language used:C++, some FORTRANComputer:Any computer with UNIX capability. Users should refer to the README file distributed with the source code for further detailsOperating system:Linux, Mac OS XNo. of lines in distributed program, including test data, etc.:111 145No. of bytes in distributed program, including test data, etc.: 791 085Distribution format:tar.gzRAM:60 MBExternal routines/libraries:LHAPDF [http://durpdg.dur.ac.uk/lhapdf/], CLHEP v1.8 or v1.9 [L. Lönnblad, Comput. Phys. Comm. 84 (1994) 307; http://wwwinfo.cern.ch/asd/lhc++/clhep/]Subprograms used:Pythia [T. Sjostrand et al., Comput. Phys. Comm. 135 (2001) 238], HDECAY [A. Djouadi, J. Kalinowski, M. Spira, HDECAY: A program for Higgs boson decays in the standard model and its supersymmetric extension, Comput. Phys. Comm. 108 (1998) 56, hep-ph/9704448]. Both are distributed with the source codeNature of problem:Central exclusive production offers the opportunity to study particle production in a uniquely clean environment for a hadron collider. This program implements the KMR model [V.A. Khoze, A.D. Martin, M.G. Ryskin, Prospects for New Physics observations in diffractive processes at the LHC and Tevatron, Eur. Phys. J. C 23 (2002) 311, hep-ph/0111078], which is the only fully perturbative model of exclusive production.Solution method:Monte Carlo techniques are used to produce the central exclusive parton level system. Pythia routines are then used to develop a realistic hadronic system.Restrictions:The program is, at present, limited to Higgs, di-gluon and di-quark production. However, in principle it is not difficult to include more.Running time:Approximately 10 minutes for 10000 Higgs events on an Apple 1 GHz G4 PowerPC.     

On the numerical treatment of an ordinary differential equation arising in one-dimensional non-Fickian diffusion problems

In a recent study, Chen and Liu [Comput. Phys. Comm. 150 (2003) 31] considered a one-dimensional, linear non-Fickian diffusion problem with a potential field, which, upon application of the Laplace transform, resulted in a second-order linear ordinary differential equation which was solved by means of a control-volume finite difference method that employs exponential shape functions. It is first shown that this formulation does not properly account for the spatial dependence of the drift forces and results in oscillatory solutions near the left boundary when these forces are large. A piecewise linearized method that provides piecewise analytical solutions, is exact in exact arithmetic for constant coefficients, homogeneous, second-order linear ordinary differential equations and results in three-point finite difference equations is then proposed. Numerical simulations indicate that the piecewise linearized method is free from unphysical oscillations and more accurate than that of Chen and Liu, especially for large drift forces. The method is then applied to non-Fickian diffusion problems with non-constant drift forces in order to determine the effects of the potential field on the concentration distribution.     

Parallel Monte Carlo simulations by asynchronous domain decomposition

A simple general method for performing Metropolis Monte Carlo condensed matter simulations on parallel processors is examined. The method is based on the cyclic generation of temporary discrete domains within the system, which are separated by distances greater than the inter-particle interaction range. Particle configurations within each domain are then sampled independently by an assigned processor, whilst particles outside these domains are held fixed. Results for a simulated Lennard-Jones fluid confirm that the method rigorously satisfies the detailed balance condition, and that the efficiency of configurational sampling scales almost linearly with the number of processors. Furthermore, the number of iterations performed on a given processor can be essentially arbitrary, with very low levels of inter-process communication. Provided the CPU time per step is not state-dependent, the method can then be used to perform large calculations as unsupervised background tasks on heterogeneous networks.     

?-SHAKE: An extension to SHAKE for the explicit treatment of angular constraints

This paper presents ?-SHAKE, an extension to SHAKE, an algorithm for the resolution of holonomic constraints in molecular dynamics simulations, which allows for the explicit treatment of angular constraints. We show that this treatment is more efficient than the use of fictitious bonds, significantly reducing the overlap between the individual constraints and thus accelerating convergence. The new algorithm is compared with SHAKE, M-SHAKE, the matrix-based approach described by Ciccotti and Ryckaert and P-SHAKE for rigid water and octane.     

An out-of-core high-resolution FFT algorithm for determining large-scale imperfections of surface potentials in crystals

We present a simple out-of-core algorithm for computing the Fast-Fourier Transform (FFT) needed to determine the two-dimensional potential of surface crystals with large-scale features, like faults, at ultra-high resolution, with around 10⁹ grid points. This algorithm represents a proof of concept that a simple and easy-to-code, out-of-core algorithm can be easily implemented and used to solve large-scale problems on low-cost hardware. The main novelties of our algorithm are: (1) elapsed and I/O times decrease with the number of single records (lines) being read; (2) only basic reading and writing routines is necessary for making the out-of-core access. Our method can be easily extended to 3D and be applied to many grand-challenge problems in science and engineering, such as fluid dynamics.