Parallel computational complexity in statistical physics.

摘要

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 {dollar}2d{dollar} Ising and 3-state Potts models. We define the dynamic exponent of the IC algorithm according to {dollar}tausb{lcub}varepsilon,max{rcub} sim Lsp{lcub}z{lcub}rm IC{rcub}{rcub}{dollar}, where {dollar}tausb{lcub}varepsilon,max{rcub}{dollar} is the maximum value of the energy autocorrelation time attained over all sub-system sizes for a given L. We give numerical estimates for {dollar}zsp{lcub}rm IC{rcub}{dollar} for the {dollar}2d{dollar} Ising and 3-state Potts models which result in improved upper bounds on the parallel complexity of sampling the critical points of these systems.