Exploiting symmetries for exponential error reduction in path integral Monte Carlo

The path integral of a quantum system with an exact symmetry can be written as a sum of functional integrals each giving the contribution from quantum states with definite symmetry properties. We propose a strategy to compute each of them, normalized to the one with vacuum quantum numbers, by a Monte Carlo procedure whose cost increases power-like with the time extent of the lattice. This is achieved thanks to a multi-level integration scheme, inspired by the transfer matrix formalism, which exploits the symmetry and the locality in time of the underlying statistical system. As a result the cost of computing the lowest energy level in a given channel, its multiplicity and its matrix elements is exponentially reduced with respect to the standard path-integral Monte Carlo. We test the strategy with a one-dimensional harmonic oscillator, by computing the ratio of the parity odd over the parity even functional integrals and the two-point correlation function. The cost of the simulations scales as expected. In particular the effort for computing the lowest energy eigenvalue in the parity odd sector grows linearly with the time extent. At a fixed CPU time, the statistical error on the two-point correlation function is exponentially reduced with respect to the standard Monte Carlo procedure, and at large time distances it is lowered by many orders of magnitude.     

A scalable parallel algorithm for large-scale reactive force-field molecular dynamics simulations

A scalable parallel algorithm has been designed to perform multimillion-atom molecular dynamics (MD) simulations, in which first principles-based reactive force fields (ReaxFF) describe chemical reactions. Environment-dependent bond orders associated with atomic pairs and their derivatives are reused extensively with the aid of linked-list cells to minimize the computation associated with atomic n-tuple interactions (n?4 explicitly and ?6 due to chain-rule differentiation). These n-tuple computations are made modular, so that they can be reconfigured effectively with a multiple time-step integrator to further reduce the computation time. Atomic charges are updated dynamically with an electronegativity equalization method, by iteratively minimizing the electrostatic energy with the charge-neutrality constraint. The ReaxFF-MD simulation algorithm has been implemented on parallel computers based on a spatial decomposition scheme combined with distributed n-tuple data structures. The measured parallel efficiency of the parallel ReaxFF-MD algorithm is 0.998 on 131,072 IBM BlueGene/L processors for a 1.01 billion-atom RDX system.     

Linear covariant gauges on the lattice

Linear covariant gauges, such as Feynman gauge, are very useful in perturbative calculations. Their non-perturbative formulation is, however, highly non-trivial. In particular, it is a challenge to define linear covariant gauges on a lattice. We consider a class of gauges in lattice gauge theory that coincides with the perturbative definition of linear covariant gauges in the formal continuum limit. The corresponding gauge-fixing procedure is described and analyzed in detail, with an application to the pure SU(2) case. In addition, results for the gluon propagator in the two-dimensional case are given.     

A global optimization method for Landau gauge fixing in lattice QCD

An algorithm for gauge fixing to the Landau gauge in the fundamental modular region in lattice QCD is described. The method, a combination of an evolutionary algorithm with a steepest descent method, is able to solve the problem of the nonperturbative gauge fixing. The performance of the combined algorithm is investigated on 8⁴, β=5.7, and 16⁴, β=6.0, lattice SU(3) gauge configurations.     

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.     

The MATHSCOUT Mathematica package to postprocess the output of other scientific programs

mathscout is a mathematica¹ package to postprocess the output of other programs for scientific calculations. We wrote mathscout to import data from a major program for ab initio computational chemistry into mathematica, so that we could postprocess the chemical results. It can be used to import the output of many other packages that are used, e.g. in molecular dynamics, crystallography, spectroscopic analysis, metabolic and physiological modeling, meteorology and other areas of environmental science, cosmology and particle physics. mathscout assigns a name to each table and non-tabular datum that it extracts. This name is constructed mechanically from the identifier or phrase that precedes or follows or embeds the item in the output that mathscout processes. A selection of non-contiguous items, or all the items in a section of the file, or in the entire file are extracted using simple commands. So far, we have focused on our immediate needs to postprocess the output of the Gaussian² program. Calculations on several molecules that illustrate the usage of the package are presented here and in the Supplementary Information. mathscout is shortened to msct in the software.

Program summary

Program title: msct.mCatalogue identifier: ADZQ_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/ADZQ_v1_0.htmlProgram obtainable from: CPC Program Library, Queen's University, Belfast, N. IrelandLicensing provisions: Standard CPC licence, http://cpc.cs.qub.ac.uk/licence/licence.htmlNo. of lines in distributed program, including test data, etc.: 30 396No. of bytes in distributed program, including test data, etc.: 1 799 469Distribution format: tar.gzProgramming language: MathematicaComputer: Any computer running unix and MathematicaOperating system: UnixSupplementary material: The Development guideClassification: 4.14, 5, 16.1, 20Nature of problem: Import data from output files of scientific computing packages, such as Gaussian, into Mathematica for symbolic calculation and production of publication quality tables and plots.Solution method: Provision of mnemonic top-down parsing procedures, functional programming.Running time: The complete extraction of data from a small basis density functional calculation on the water molecule, and from a larger basis density functional calculation on the zinc hydrate ion, that ran to 33 iterations, took 1 second and 23 seconds, respectively, on a Dell Poweredge 1750.     

Exploring the HMC trajectory-length dependence of autocorrelation times in lattice QCD

We study autocorrelation times of physical observables in lattice QCD as a function of the molecular dynamics trajectory length in the hybrid Monte-Carlo algorithm. In an interval of trajectory lengths where energy and reversibility violations can be kept under control, we find a variation of the integrated autocorrelation times by a factor of about two in the quantities of interest. Trajectories longer than conventionally used are found to be superior both in the Nf=0 and Nf=2 examples considered here. We also provide evidence that they lead to faster thermalization of systems with light quarks.     

A fast level set framework for large three-dimensional topography simulations

We present fast methods to describe the surface evolution of large three-dimensional structures. Based on the sparse field level set method and the hierarchical run-length encoding level set data structure optimal figures for the computation time and for the memory consumption are achieved. Furthermore, we introduce a new multi-level-set technique, which is able to incorporate multiple material regions, and which can also handle material specific surface speeds accurately. We also describe an optimal algorithm for the visibility check for unidirectional etching. The presented techniques are demonstrated on various examples.     

Symmetries and exponential error reduction in Yang-Mills theories on the lattice

The partition function of a quantum field theory with an exact symmetry can be decomposed into a sum of functional integrals each giving the contribution from states with definite symmetry properties. The composition rules of the corresponding transfer matrix elements can be exploited to devise a multi-level Monte Carlo integration scheme for computing correlation functions whose numerical cost, at a fixed precision and at asymptotically large times, increases power-like with the time extent of the lattice. As a result the numerical effort is exponentially reduced with respect to the standard Monte Carlo procedure. We test this strategy in the SU(3) Yang-Mills theory by evaluating the relative contribution to the partition function of the parity odd states.     

Dynamic procedures of image reconstruction from projections (computer tomography)

A method of reconstruction of images from projections is suggested. In contrast to the static procedure conventionally used for the solution of problems of image reconstruction from projections, this method presupposes the use of a dynamic procedure. Such an approach, in combination with the use of special noise-immune algorithms of image reconstruction, permits obtaining images of the internal structure of the object under study of a high quality by irradiating it sequentially in time by the flows of photons of a small intensity. The effectiveness of the suggested method is illustrated by the example of results of a computer experiment.     

Embedded divide-and-conquer algorithm on hierarchical real-space grids: parallel molecular dynamics simulation based on linear-scaling density functional theory

A linear-scaling algorithm has been developed to perform large-scale molecular-dynamics (MD) simulations, in which interatomic forces are computed quantum mechanically in the framework of the density functional theory. A divide-and-conquer algorithm is used to compute the electronic structure, where non-additive contribution to the kinetic energy is included with an embedded cluster scheme. Electronic wave functions are represented on a real-space grid, which is augmented with coarse multigrids to accelerate the convergence of iterative solutions and adaptive fine grids around atoms to accurately calculate ionic pseudopotentials. Spatial decomposition is employed to implement the hierarchical-grid algorithm on massively parallel computers. A converged solution to the electronic-structure problem is obtained for a 32,768-atom amorphous CdSe system on 512 IBM POWER4 processors. The total energy is well conserved during MD simulations of liquid Rb, showing the applicability of this algorithm to first principles MD simulations. The parallel efficiency is 0.985 on 128 Intel Xeon processors for a 65,536-atom CdSe system.     

Automated generation of lattice QCD Feynman rules

The derivation of the Feynman rules for lattice perturbation theory from actions and operators is complicated, especially for highly improved actions such as HISQ. This task is, however, both important and particularly suitable for automation. We describe a suite of software to generate and evaluate Feynman rules for a wide range of lattice field theories with gluons and (relativistic and/or heavy) quarks. Our programs are capable of dealing with actions as complicated as (m)NRQCD and HISQ. Automated differentiation methods are used to calculate also the derivatives of Feynman diagrams.

Program summary

Program title: HiPPY, HPsrcCatalogue identifier: AEDX_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AEDX_v1_0.htmlProgram obtainable from: CPC Program Library, Queen's University, Belfast, N. IrelandLicensing provisions: GPLv2 (see Additional comments below)No. of lines in distributed program, including test data, etc.: 513 426No. of bytes in distributed program, including test data, etc.: 4 893 707Distribution format: tar.gzProgramming language: Python, Fortran95Computer: HiPPy: Single-processor workstations. HPsrc: Single-processor workstations and MPI-enabled multi-processor systemsOperating system: HiPPy: Any for which Python v2.5.x is available. HPsrc: Any for which a standards-compliant Fortran95 compiler is availableHas the code been vectorised or parallelised?: YesRAM: Problem specific, typically less than 1 GB for either codeClassification: 4.4, 11.5Nature of problem: Derivation and use of perturbative Feynman rules for complicated lattice QCD actions.Solution method: An automated expansion method implemented in Python (HiPPy) and code to use expansions to generate Feynman rules in Fortran95 (HPsrc).Restrictions: No general restrictions. Specific restrictions are discussed in the text.Additional comments: The HiPPy and HPsrc codes are released under the second version of the GNU General Public Licence (GPL v2). Therefore anyone is free to use or modify the code for their own calculations. As part of the licensing, we ask that any publications including results from the use of this code or of modifications of it cite Refs. [1,2] as well as this paper. Finally, we also ask that details of these publications, as well as of any bugs or required or useful improvements of this core code, would be communicated to us.Running time: Very problem specific, depending on the complexity of the Feynman rules and the number of integration points. Typically between a few minutes and several weeks. The installation tests provided with the program code take only a few seconds to run.References:

• [1] 

  A. Hart, G.M. von Hippel, R.R. Horgan, L.C. Storoni, Automatically generating Feynman rules for improved lattice eld theories, J. Comput. Phys. 209 (2005) 340–353, doi:10.1016/j.jcp.2005.03.010, arXiv:hep-lat/0411026.

• [2] 

  M. Lüscher, P. Weisz, Efficient Numerical Techniques for Perturbative Lattice Gauge Theory Computations, Nucl. Phys. B 266 (1986) 309, doi:10.1016/0550-3213(86)90094-5.

     

A finite-difference eigenvalue algorithm for calculating the band structure of a photonic crystal

A new method based on a finite difference of the governing differential equation for the eigenvalue problem is introduced to calculate the band structure of a two-dimensional photonic crystal. The effective medium technique is also used in the method. The problem is reduced to a standard matrix eigenvalue problem. Compared to the conventional plane wave expansion method, the present method improves the convergence of the solution and thus is a fast and accurate algorithm for calculating the band structure of a photonic crystal.     

Pathfinder: A parallel search algorithm for concerted atomistic events

An algorithm has been designed to search for the escape paths with the lowest activation barriers when starting from a local minimum-energy configuration of a many-atom system. The pathfinder algorithm combines: (1) a steered eigenvector-following method that guides a constrained escape from the convex region and subsequently climbs to a transition state tangentially to the eigenvector corresponding to the lowest negative Hessian eigenvalue; (2) discrete abstraction of the atomic configuration to systematically enumerate concerted events as linear combinations of atomistic events; (3) evolutionary control of the population dynamics of low activation-barrier events; and (4) hybrid task + spatial decompositions to implement massive search for complex events on parallel computers. The program exhibits good scalability on parallel computers and has been used to study concerted bond-breaking events in the fracture of alumina.     

A space-time-ensemble parallel nudged elastic band algorithm for molecular kinetics simulation

A scalable parallel algorithm has been designed to study long-time dynamics of many-atom systems based on the nudged elastic band method, which performs mutually constrained molecular dynamics simulations for a sequence of atomic configurations (or states) to obtain a minimum energy path between initial and final local minimum-energy states. A directionally heated nudged elastic band method is introduced to search for thermally activated events without the knowledge of final states, which is then applied to an ensemble of bands in a path ensemble method for long-time simulation in the framework of the transition state theory. The resulting molecular kinetics (MK) simulation method is parallelized with a space-time-ensemble parallel nudged elastic band (STEP-NEB) algorithm, which employs spatial decomposition within each state, while temporal parallelism across the states within each band and band-ensemble parallelism are implemented using a hierarchy of communicator constructs in the Message Passing Interface library. The STEP-NEB algorithm exhibits good scalability with respect to spatial, temporal and ensemble decompositions on massively parallel computers. The MK simulation method is used to study low strain-rate deformation of amorphous silica.