Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 30 of 33
Full-Text Articles in Physical Sciences and Mathematics
Comparing Monte Carlo Methods For Finding Ground States Of Ising Spin Glasses: Population Annealing, Simulated Annealing And Parallel Tempering, Wenlong Wang, Jonathan Machta, Helmut G. Katzgraber
Comparing Monte Carlo Methods For Finding Ground States Of Ising Spin Glasses: Population Annealing, Simulated Annealing And Parallel Tempering, Wenlong Wang, Jonathan Machta, Helmut G. Katzgraber
Jonathan Machta
Population annealing is a Monte Carlo algorithm that marries features from simulated annealing and parallel tempering Monte Carlo. As such, it is ideal to overcome large energy barriers in the free-energy landscape while minimizing a Hamiltonian. Thus, population annealing Monte Carlo can be used as a heuristic to solve combinatorial optimization problems. We illustrate the capabilities of population annealing Monte Carlo by computing ground states of the three-dimensional Ising spin glass with Gaussian disorder, whilst comparing to simulated annealing and parallel tempering Monte Carlo. Our results suggest that population annealing Monte Carlo is significantly more effiicient than simulated annealing but …
Evidence Against A Mean-Field Description Of Short-Range Spin Glasses Revealed Through Thermal Boundary Conditions, Wenlong Wang, Jonathan Machta, Helmut G. Katzgraber
Evidence Against A Mean-Field Description Of Short-Range Spin Glasses Revealed Through Thermal Boundary Conditions, Wenlong Wang, Jonathan Machta, Helmut G. Katzgraber
Jonathan Machta
A theoretical description of the low-temperature phase of short-range spin glasses has remained elusive for decades. In particular, it is unclear if theories that assert a single pair of pure states, or theories that are based on infinitely many pure states—such as replica symmetry breaking—best describe realistic short-range systems. To resolve this controversy, the three-dimensional Edwards-Anderson Ising spin glass in thermal boundary conditions is studied numerically using population annealing Monte Carlo. In thermal boundary conditions all eight combinations of periodic vs antiperiodic boundary conditions in the three spatial directions appear in the ensemble with their respective Boltzmann weights, thus minimizing …
Low-Temperature Behavior Of The Statistics Of The Overlap Distribution In Ising Spin-Glass Models, Matthew Wittmann, B. Yucesoy, Helmut G. Katzgraber, Jonathan Machta, A. P. Young
Low-Temperature Behavior Of The Statistics Of The Overlap Distribution In Ising Spin-Glass Models, Matthew Wittmann, B. Yucesoy, Helmut G. Katzgraber, Jonathan Machta, A. P. Young
Jonathan Machta
Using Monte Carlo simulations, we study in detail the overlap distribution for individual samples for several spin-glass models including the infinite-range Sherrington-Kirkpatrick model, short-range Edwards-Anderson models in three and four space dimensions, and one-dimensional long-range models with diluted power-law interactions. We study three long-range models with different powers as follows: The first is approximately equivalent to a short-range model in three dimensions, the second to a short-range model in four dimensions, and the third to a short-range model in the mean-field regime. We study an observable proposed earlier by some of us which aims to distinguish the “replica symmetry breaking” …
Erratum: Glassy Chimeras Could Be Blind To Quantum Speedup: Designing Better Benchmarks For Quantum Annealing Machines, Martin Weigel, Helmut G. Katzgraber, Jonathan Machta, Firas Hamze, Ruben S. Andrist
Erratum: Glassy Chimeras Could Be Blind To Quantum Speedup: Designing Better Benchmarks For Quantum Annealing Machines, Martin Weigel, Helmut G. Katzgraber, Jonathan Machta, Firas Hamze, Ruben S. Andrist
Jonathan Machta
No abstract provided.
Correlations Between The Dynamics Of Parallel Tempering And The Free Energy Landscape In Spin Glasses, Burcu Yucesoy, Jonathan Machta, Helmut G. Katzgraber
Correlations Between The Dynamics Of Parallel Tempering And The Free Energy Landscape In Spin Glasses, Burcu Yucesoy, Jonathan Machta, Helmut G. Katzgraber
Jonathan Machta
We present the results of a large-scale numerical study of the equilibrium three-dimensional Edwards-Anderson Ising spin glass with Gaussian disorder. Using parallel tempering (replica exchange) Monte Carlo we measure various static, as well as dynamical quantities, such as the autocorrelation times and round-trip times for the parallel tempering Monte Carlo method. The correlation between static and dynamic observables for 5000 disorder realizations and up to 1000 spins down to temperatures at 20% of the critical temperature is examined. Our results show that autocorrelation times are directly correlated with the roughness of the free-energy landscape.
Nature Vs. Nurture: Predictability In Low-Temperature Ising Dynamics, J. Ye, Jonathan Machta, C. M. Newman, D. L. Stein
Nature Vs. Nurture: Predictability In Low-Temperature Ising Dynamics, J. Ye, Jonathan Machta, C. M. Newman, D. L. Stein
Jonathan Machta
Consider a dynamical many-body system with a random initial state subsequently evolving through stochastic dynamics. What is the relative importance of the initial state (“nature”) versus the realization of the stochastic dynamics (“nurture”) in predicting the final state? We examined this question for the two-dimensional Ising ferromagnet following an initial deep quench from T=∞ to T=0. We performed Monte Carlo studies on the overlap between “identical twins” raised in independent dynamical environments, up to size L=500. Our results suggest an overlap decaying with time as t−θh with θh=0.22±0.02; the same exponent holds for a quench to low but nonzero temperature. …
Evidence Of Non-Mean-Field-Like Low-Temperature Behavior In The Edwards-Anderson Spin-Glass Model, B. Yucesoy, Helmut G. Katzgraber, Jonathan Machta
Evidence Of Non-Mean-Field-Like Low-Temperature Behavior In The Edwards-Anderson Spin-Glass Model, B. Yucesoy, Helmut G. Katzgraber, Jonathan Machta
Jonathan Machta
The three-dimensional Edwards-Anderson and mean-field Sherrington-Kirkpatrick Ising spin glasses are studied via large-scale Monte Carlo simulations at low temperatures, deep within the spin-glass phase. Performing a careful statistical analysis of several thousand independent disorder realizations and using an observable that detects peaks in the overlap distribution, we show that the Sherrington-Kirkpatrick and Edwards-Anderson models have a distinctly different low-temperature behavior. The structure of the spin-glass overlap distribution for the Edwards-Anderson model suggests that its low-temperature phase has only a single pair of pure states.
Computational Study Of A Multistep Height Model, Matthew Drake, Jonathan Machta, Youjin Deng, Douglas Abraham, Charles Newman
Computational Study Of A Multistep Height Model, Matthew Drake, Jonathan Machta, Youjin Deng, Douglas Abraham, Charles Newman
Jonathan Machta
An equilibrium random surface multistep height model proposed in [Abraham and Newman, EPL, 86, 16002 (2009)] is studied using a variant of the worm algorithm. In one limit, the model reduces to the two-dimensional Ising model in the height representation. When the Ising model constraint of single height steps is relaxed, the critical temperature and critical exponents are continuously varying functions of the parameter controlling height steps larger than one. Numerical estimates of the critical exponents can be mapped via a single parameter-- the Coulomb gas coupling-- to the exponents of the O(n) loop model on the honeycomb lattice with …
Packing Squares In A Torus, D. W. Blair, C. Santangelo, Jonathan Machta
Packing Squares In A Torus, D. W. Blair, C. Santangelo, Jonathan Machta
Jonathan Machta
The densest packings of N unit squares in a torus are studied using analytical methods as well as simulated annealing. A rich array of dense packing solutions are found: density-one packings when N is the sum of two square integers; a family of 'gapped bricklayer' Bravais lattice solutions with density N/(N + 1); and some surprising non-Bravais lattice configurations, including lattices of holes as well as a configuration for N = 23 in which not all squares share the same orientation. The entropy of some of these configurations and the frequency and orientation of density-one solutions as N -> Infinity …
Natural Complexity, Computational Complexity And Depth, Jonathan Machta
Natural Complexity, Computational Complexity And Depth, Jonathan Machta
Jonathan Machta
Depth is a complexity measure for natural systems of the kind studied in statistical physics and is defined in terms of computational complexity. Depth quantifies the length of the shortest parallel computation required to construct a typical system state or history starting from simple initial conditions. The properties of depth are discussed and it is compared with other complexity measures. Depth can only be large for systems with embedded computation.
Parallel Complexity Of Random Boolean Circuits, Jonathan Machta, S. Dedeo, S. Mertens, C. Moore
Parallel Complexity Of Random Boolean Circuits, Jonathan Machta, S. Dedeo, S. Mertens, C. Moore
Jonathan Machta
Random instances of feedforward Boolean circuits are studied both analytically and numerically. Evaluating these circuits is known to be a P-complete problem and thus, in the worst case, believed to be impossible to perform, even given a massively parallel computer, in a time much less than the depth of the circuit. Nonetheless, it is found that, for some ensembles of random circuits, saturation to a fixed truth value occurs rapidly so that evaluation of the circuit can be accomplished in much less parallel time than the depth of the circuit. For other ensembles saturation does not occur and circuit evaluation …
Monte Carlo Methods For Rough Free Energy Landscapes: Population Annealing And Parallel Tempering, Jonathan Machta, Richard S. Ellis
Monte Carlo Methods For Rough Free Energy Landscapes: Population Annealing And Parallel Tempering, Jonathan Machta, Richard S. Ellis
Jonathan Machta
Parallel tempering and population annealing are both effective methods for simulating equilibrium systems with rough free energy landscapes. Parallel tempering, also known as replica exchange Monte Carlo, is a Markov chain Monte Carlo method while population annealing is a sequential Monte Carlo method. Both methods overcome the exponential slowing associated with high free energy barriers. The convergence properties and efficiencies of the two methods are compared. For large systems, population annealing is closer to equilibrium than parallel tempering for short simulations. However, with respect to the amount of computation, parallel tempering converges exponentially while population annealing converges only inversely. As …
Granular Gases Under Extreme Driving, W. Kang, Jonathan Machta, E. Ben-Namin
Granular Gases Under Extreme Driving, W. Kang, Jonathan Machta, E. Ben-Namin
Jonathan Machta
We study inelastic gases in two dimensions using event-driven molecular-dynamics simulations. Our focus is the nature of the stationary state attained by rare injection of large amounts of energy to balance the dissipation due to collisions. We find that under such extreme driving, with the injection rate much smaller than the collision rate, the velocity distribution has a power-law high-energy tail. The numerically measured exponent characterizing this tail is in excellent agreement with predictions of kinetic theory over a wide range of system parameters. We conclude that driving by rare but powerful energy injection leads to a well-mixed gas and …
Population Annealing With Weighted Averages: A Monte Carlo Method For Rough Free-Energy Landscapes, Jonathan Machta
Population Annealing With Weighted Averages: A Monte Carlo Method For Rough Free-Energy Landscapes, Jonathan Machta
Jonathan Machta
The population annealing algorithm introduced by Hukushima and Iba is described. Population annealing combines simulated annealing and Boltzmann weighted differential reproduction within a population of replicas to sample equilibrium states. Population annealing gives direct access to the free energy. It is shown that unbiased measurements of observables can be obtained by weighted averages over many runs with weight factors related to the free-energy estimate from the run. Population annealing is well suited to parallelization and may be a useful alternative to parallel tempering for systems with rough free-energy landscapes such as spin glasses. The method is demonstrated for spin glasses.
A Percolation-Theoretic Approach To Spin Glass Phase Transitions, Jonathan Machta, C. M. Newman, D. L. Stein
A Percolation-Theoretic Approach To Spin Glass Phase Transitions, Jonathan Machta, C. M. Newman, D. L. Stein
Jonathan Machta
The magnetically ordered, low temperature phase of Ising ferromagnets is manifested within the associated Fortuin—Kasteleyn (FK) random cluster representation by the occurrence of a single positive density percolating cluster. In this paper, we review our recent work on the percolation signature for Ising spin glass ordering — both in the short-range Edwards—Anderson (EA) and infinite-range Sherrington—Kirkpatrick (SK) models — within a tworeplica FK representation and also in the different Chayes—Machta—Redner two-replica graphical representation. Numerical studies of the ±J EA model in dimension three and rigorous results for the SK model are consistent in supporting the conclusion that the signature of …
Strengths And Weaknesses Of Parallel Tempering, Jonathan Machta
Strengths And Weaknesses Of Parallel Tempering, Jonathan Machta
Jonathan Machta
Parallel tempering, also known as replica exchange Monte Carlo, is studied in the context of two simple free-energy landscapes. The first is a double-well potential defined by two macrostates separated by a barrier. The second is a “golf course” potential defined by microstates having two possible energies with exponentially more high-energy states than low-energy states. The equilibration time for replica exchange is analyzed for both systems. For the double-well system, parallel tempering with a number of replicas that scales as the square root of the barrier height yields exponential speedup of the equilibration time. On the other hand, replica exchange …
The Percolation Signature Of The Spin Glass Transition, Jonathan Machta, C. M. Newman, D. L. Stein
The Percolation Signature Of The Spin Glass Transition, Jonathan Machta, C. M. Newman, D. L. Stein
Jonathan Machta
Magnetic ordering at low temperature for Ising ferromagnets manifests itself within the associated Fortuin–Kasteleyn (FK) random cluster representation as the occurrence of a single positive density percolating network. In this paper we investigate the percolation signature for Ising spin glass ordering—both in short-range (EA) and infinite-range (SK) models—within a two-replica FK representation and also within the different Chayes–Machta–Redner two-replica graphical representation. Based on numerical studies of the ±J EA model in three dimensions and on rigorous results for the SK model, we conclude that the spin glass transition corresponds to the appearance of two percolating clusters of unequal densities.
Percolation In The Sherrington-Kirkpatrick Spin Glass, Jonathan Machta, C. M. Newman, D. L. Stein
Percolation In The Sherrington-Kirkpatrick Spin Glass, Jonathan Machta, C. M. Newman, D. L. Stein
Jonathan Machta
We present extended versions and give detailed proofs of results about percolation (using various sets of two-replica bond occupation variables) in Sherrington-Kirkpatrick spin glasses (with zero external field) that were first given in an earlier paper by the same authors. We also explain how ultrametricity is manifested by the densities of large percolating clusters. Our main theorems concern the connection between these densities and the usual spin overlap distribution. Their corollaries are that the ordered spin glass phase is characterized by a unique percolating cluster of maximal density (normally coexisting with a second cluster of nonzero but lower density). The …
Dynamic Critical Behavior Of The Chayes-Machta-Swendsen-Wang Algorithm, Youjin Deng, Timothy M. Garoni, Jonathan Machta, Giovanni Ossola, Marco Polin, Alan D. Sokal
Dynamic Critical Behavior Of The Chayes-Machta-Swendsen-Wang Algorithm, Youjin Deng, Timothy M. Garoni, Jonathan Machta, Giovanni Ossola, Marco Polin, Alan D. Sokal
Jonathan Machta
We study the dynamic critical behavior of the Chayes-Machta dynamics for the Fortuin-Kasteleyn random-cluster model, which generalizes the Swendsen-Wang dynamics for the q-state Potts model to noninteger q, in two and three spatial dimensions, by Monte Carlo simulation. We show that the Li-Sokal bound z≥α/ν is close to but probably not sharp in d=2 and is far from sharp in d=3, for all q. The conjecture z≥β/ν is false (for some values of q) in both d=2 and d=3.
High Precision Measurement Of The Thermal Exponent For The Three-Dimensional Xy Universality Class, Evgeni Burovski, Jonathan Machta, Nikolay Prokof'ev, Boris Svitunov
High Precision Measurement Of The Thermal Exponent For The Three-Dimensional Xy Universality Class, Evgeni Burovski, Jonathan Machta, Nikolay Prokof'ev, Boris Svitunov
Jonathan Machta
Simulation results are reported for the critical point of the two-component ϕ4 field theory. The correlation-length exponent is measured to high precision with the result ν=0.6717(3). This value is in agreement with recent simulation results [Campostrini et al., Phys. Rev. B 63, 214503 (2001)] and marginally agrees with the most recent space-based measurements of the superfluid transition in He4 [Lipa et al., Phys. Rev. B 68, 174518 (2003)].
Complexity, Parallel Computation And Statistical Physics, Jonathan Machta
Complexity, Parallel Computation And Statistical Physics, Jonathan Machta
Jonathan Machta
The intuition that a long history is required for the emergence of complexity in natural systems is formalized using the notion of depth. The depth of a system is defined in terms of the number of parallel computational steps needed to simulate it. Depth provides an objective, irreducible measure of history that is applicable to systems of the kind studied in statistical physics. It is argued that physical complexity cannot occur in the absence of substantial depth and that depth is a useful proxy for physical complexity. The ideas are illustrated for a variety of systems in statistical physics
Numerical Study Of The Random Field Ising Model At Zero And Positive Temperature, Yong Wu, Jonathan Machta
Numerical Study Of The Random Field Ising Model At Zero And Positive Temperature, Yong Wu, Jonathan Machta
Jonathan Machta
In this paper the three-dimensional random-field Ising model is studied at both zero temperature and positive temperature. Critical exponents are extracted at zero temperature by finite size scaling analysis of large discontinuities in the bond energy. The heat capacity exponent α is found to be near zero. The ground states are determined for a range of external field and disorder strength near the zero temperature critical point and the scaling of ground state tilings of the field-disorder plane is discussed. At positive temperature the specific heat and the susceptibility are obtained using the Wang-Landau algorithm. It is found that sharp …
Stationary States And Energy Cascades In Inelastic Gases, E. Ben-Naim, Jonathan Machta
Stationary States And Energy Cascades In Inelastic Gases, E. Ben-Naim, Jonathan Machta
Jonathan Machta
We find a general class of nontrivial stationary states in inelastic gases where, due to dissipation, energy is transferred from large velocity scales to small velocity scales. These steady states exist for arbitrary collision rules and arbitrary dimension. Their signature is a stationary velocity distribution f(v) with an algebraic high-energy tail, f(v)∼v−σ. The exponent σ is obtained analytically and it varies continuously with the spatial dimension, the homogeneity index characterizing the collision rate, and the restitution coefficient. We observe these stationary states in numerical simulations in which energy is injected into the system by infrequently boosting particles to high velocities. …
Parallel Dynamics And Computational Complexity Of Network Growth Models, Benjamin Machta, Jonathan Machta
Parallel Dynamics And Computational Complexity Of Network Growth Models, Benjamin Machta, Jonathan Machta
Jonathan Machta
The parallel computational complexity or depth of growing network models is investigated. The networks considered are generated by preferential attachment rules where the probability of attaching a new node to an existing node is given by a power α of the connectivity of the existing node. Algorithms for generating growing networks very quickly in parallel are described and studied. The sublinear and superlinear cases require distinct algorithms. As a result, there is a discontinuous transition in the parallel complexity of sampling these networks corresponding to the discontinuous structural transition at α=1, where the networks become scale-free. For α>1, networks …
Power-Law Velocity Distributions In Granular Gases, E. Ben-Naim, B. Machta, Jonathan Machta
Power-Law Velocity Distributions In Granular Gases, E. Ben-Naim, B. Machta, Jonathan Machta
Jonathan Machta
The kinetic theory of granular gases is studied for spatially homogeneous systems. At large velocities, the equation governing the velocity distribution becomes linear, and it admits stationary solutions with a power-law tail, f(v)∼v−σ. This behavior holds in arbitrary dimension for arbitrary collision rates including both hard spheres and Maxwell molecules. Numerical simulations show that driven steady states with the same power-law tail can be realized by injecting energy into the system at very high energies. In one dimension, we also obtain self-similar time-dependent solutions where the velocities collapse to zero. At small velocities there is a steady state and a …
Ground States And Thermal States Of The Random Field Ising Model, Yong Wu, Jonathan Machta
Ground States And Thermal States Of The Random Field Ising Model, Yong Wu, Jonathan Machta
Jonathan Machta
The random field Ising model is studied numerically at both zero and positive temperature. Ground states are mapped out in a region of random field and external field strength. Thermal states and thermodynamic properties are obtained for all temperatures using the Wang-Landau algorithm. The specific heat and susceptibility typically display sharp peaks in the critical region for large systems and strong disorder. These sharp peaks result from large domains flipping. For a given realization of disorder, ground states and thermal states near the critical line are found to be strongly correlated—a concrete manifestation of the zero temperature fixed point scenario.
Structural And Computational Depth Of Diffusion Limited Aggregation, D. Tillberg, Jonathan Machta
Structural And Computational Depth Of Diffusion Limited Aggregation, D. Tillberg, Jonathan Machta
Jonathan Machta
Diffusion-limited aggregation (DLA) is studied from the perspective of computational complexity. A parallel algorithm is exhibited that requires a number of steps that scales as the depth of the tree defined by the cluster. The existence of this algorithm suggests a connection between a fundamental computational and structural property of DLA.
Ground State Numerical Study Of The Three-Dimensional Random Field Ising Model, I. Dukovski, Jonathan Machta
Ground State Numerical Study Of The Three-Dimensional Random Field Ising Model, I. Dukovski, Jonathan Machta
Jonathan Machta
The random field Ising model in three dimensions with Gaussian random fields is studied at zero temperature for system sizes up to 603. For each realization of the normalized random fields, the strength of the random field, Δ and a uniform external, H is adjusted to find the finite-size critical point. The finite-size critical point is identified as the point in the H−Δ plane where three degenerate ground states have the largest discontinuities in the magnetization. The discontinuities in the magnetization and bond energy between these ground states are used to calculate the magnetization and specific heat critical exponents and …
Invaded Cluster Simulations Of The Xy Model In Two And Three, I. Dukovski, Jonathan Machta, L. V. Chayes
Invaded Cluster Simulations Of The Xy Model In Two And Three, I. Dukovski, Jonathan Machta, L. V. Chayes
Jonathan Machta
The invaded cluster algorithm is used to study the XY model in two and three dimensions up to sizes 20002 and 1203, respectively. A soft spin O(2) model, in the same universality class as the three-dimensional XY model, is also studied. The static critical properties of the model and the dynamical properties of the algorithm are reported. The results are Kc=0.45412(2) for the three-dimensional XY model and η=0.037(2) for the three-dimensional XY universality class. For the two-dimensional XY model the results are Kc=1.120(1) and η=0.251(5). The invaded cluster algorithm does not show any critical slowing for the magnetization or critical …
Parallel Dynamics And Computational Complexity Of The Bak-Sneppen Model, Jonathan Machta, X. N. Li
Parallel Dynamics And Computational Complexity Of The Bak-Sneppen Model, Jonathan Machta, X. N. Li
Jonathan Machta
No abstract provided.