We examine several models in statistical physics from the perspective of parallel computational complexity theory. In each case, we describe a parallel method of simulation that is faster than current sequential methods. We find that parallel complexity results are in accord with intuitive notions of physical complexity for the models studied. First, we investigate the parallel complexity of sampling Lorentz lattice gas (LLG) trajectories. We show that the single-particle LLG can be simulated in highly parallel fashion, in contrast to multi-particle lattice gases which most likely cannot. In the case of diffusion-limited aggregation (DLA), we show that a polynomial speedup is feasible even though a highly parallel algorithm probably is not. In particular, we present a polynomial-processor algorithm for generating DLA clusters that runs in a time sub-linear in the cluster mass. We relate the dynamic exponent of our parallel DLA algorithm to static scaling exponents of DLA and give numerical estimates. We investigate the parallel complexity of the invaded cluster (IC) algorithm and find that a single sweep can be carried out in highly parallel fashion but that a polynomial number of sweeps most likely cannot be compressed into a polylogarithmic number of parallel steps. We argue that quantities measured for a sub-system of size l, using the IC algorithm, should exhibit a crossover to Swendsen-Wang behavior for l sufficiently smaller than the system size L, and we propose a scaling form to describe this phenomenon. By studying sub-systems, we observe critical slowing for the $2d$ Ising and 3-state Potts models. We define the dynamic exponent of the IC algorithm according to $\tau\sb{\varepsilon,\max} \sim L\sp{z{\rm IC}}$, where $\tau\sb{\varepsilon,\max}$ is the maximum value of the energy autocorrelation time attained over all sub-system sizes for a given L. We give numerical estimates for $z\sp{\rm IC}$ for the $2d$ Ising and 3-state Potts models which result in improved upper bounds on the parallel complexity of sampling the critical points of these systems.
| Identifer | oai:union.ndltd.org:UMASS/oai:scholarworks.umass.edu:dissertations-3112 |
| Date | 01 January 1998 |
| Creators | Moriarty, Kenneth J |
| Publisher | ScholarWorks@UMass Amherst |
| Source Sets | University of Massachusetts, Amherst |
| Language | English |
| Detected Language | English |
| Type | text |
| Source | Doctoral Dissertations Available from Proquest |
Page generated in 0.0016 seconds