PLEASE WAIT, LOADING...
Loading ...
ProQuest

Citation/Abstract

Cluster algorithms and computational complexity


2002 2002

Other formats: Order a copy

Abstract (summary)


Cluster algorithms for the 2D Ising model with a staggered field have been studied and a new cluster algorithm for path sampling has been worked out. The complexity properties of Bak-Seppen model and the Growing network model have been studied by using the Computational Complexity Theory.

The dynamic critical behavior of the two-replica cluster algorithm is studied. Several versions of the algorithm are applied to the two-dimensional, square lattice Ising model with a staggered field. The dynamic exponent for the full algorithm is found to be less than 0.5. It is found that odd translations of one replica with respect to the other together with global flips are essential for obtaining a small value of the dynamic exponent.

The path sampling problem for the 1D Ising model is studied using both a local algorithm and a novel cluster algorithm. The local algorithm is extremely inefficient at low temperature, where the integrated autocorrelation time is found to be proportional to the fourth power of correlation length. The dynamic exponent of the cluster algorithm is found to be zero and therefore proved to be much more efficient than the local algorithm.

The parallel computational complexity of the Bak-Sneppen evolution model is studied. It is shown that Bak-Sneppen histories can be generated by a massively parallel computer in a time that is polylog in the length of the history, which means that the logical depth of producing a Bak-Sneppen history is exponentially less than the length of the history. The parallel dynamics for generating Bak-Sneppen histories is contrasted to standard Bak-Sneppen dynamics.

The parallel computational complexity of the Growing Network model is studied. The growth of the network with linear kernels is shown to be not complex and an algorithm with polylog parallel running time is found. The growth of the network with γ ≥ 2 super-linear kernels can be realized by a randomized parallel algorithm with polylog expected running time.

Indexing (details)


Subject
Condensation
Classification
0611: Condensation
Identifier / keyword
Pure sciences, Ising model, Cluster algorithms, Computational complexity
Title
Cluster algorithms and computational complexity
Author
Li, Xuenan
Pages
99 p.
Number of pages
99
Publication year
2002
Degree date
2002
School code
0118
Source
DAI-B 63/10, p. 4733, Apr 2003
Place of publication
Ann Arbor
Country of publication
United States
ISBN
0493880585, 9780493880587
Advisor
Machta, Jonathan
University/institution
University of Massachusetts Amherst
University location
United States -- Massachusetts
Degree
Ph.D.
Source type
Dissertations & Theses
Language
English
Document type
Dissertation/Thesis
Dissertation/thesis number
3068577
ProQuest document ID
305524644
Copyright
Copyright UMI - Dissertations Publishing 2002
Document URL
http://search.proquest.com/docview/305524644