Parallel family trees for transfer matrices in the Potts model

Abstract

The computational cost of transfer matrix methods for the Potts model is directly related to the problem of \textit{into how many ways can two adjacent blocks of a lattice be connected}. Answering this question leads to the generation of a combinatorial set of lattice configurations. This set defines the \textit{configuration space} of the problem, and the smaller it is, the faster the transfer matrix method can be. The configuration space of generic transfer matrix methods for strip lattices in the Potts model is in the order of the Catalan numbers, leading to an asymptotic cost of $O(4^m)$ with $m$ being the width of the strip. Transfer matrix methods with a smaller configuration space indeed exist but they make assumptions on the temperature, number of spin states, or restrict the topology of the lattice in order to work. In this paper we propose a general and parallel transfer matrix method, based on family trees, that uses a sub-Catalan configuration space of size $O(3^m)$. The improvement is achieved by grouping the original set of Catalan configurations into a forest of family trees, in such a way that the solution to the problem is now computed by just solving the root node of each family. As a result, the algorithm becomes exponentially faster and highly parallel. An additional advantage is that the final matrix ends up being compressed, not only saving space but also making numerical evaluation on $(q,v)$ faster than in a non-compressed scenario. Experimental results for different sizes of strip lattices show that the \textit{Parallel family trees (PFT)} strategy indeed runs exponentially faster than the \textit{Catalan Parallel Method (CPM)}, specially when dealing with dense transfer matrices. We can confirm that a parallel implementation of the PFT algorithm is highly effective and efficient for large problem sizes...

arXiv commentAccepted in October 10, 2014 for publication in Computer Physics Communications Journal

References in corpus (19)

• The multivariate Tutte polynomial (alias Potts model) for graphs and matroids
• Transfer Matrices and Partition-Function Zeros for Antiferromagnetic Potts Models I. General Theory and Square-Lattice Chromatic Polynomial
• Exact Potts Model Partition Functions on Ladder Graphs
• Exact Potts Model Partition Functions on Wider Arbitrary-Length Strips of the Square Lattice
• Partition function of two- and three-dimensional Potts ferromagnets for arbitrary values of q>0
• Exact Potts Model Partition Function for Strips of the Square Lattice
• Transfer Matrices and Partition-Function Zeros for Antiferromagnetic Potts Models II. Extended Results for Square-Lattice Chromatic Polynomial
• Phase diagram of the chromatic polynomial on a torus
• Transfer Matrices and Partition-Function Zeros for Antiferromagnetic Potts Models III. Triangular-Lattice Chromatic Polynomial
• q-State Potts model metastability study using optimized GPU-based Monte Carlo algorithms
• Transfer Matrices and Partition-Function Zeros for Antiferromagnetic Potts Models. IV. Chromatic polynomial with cyclic boundary conditions
• Transfer Matrices and Partition-Function Zeros for Antiferromagnetic Potts Models. V. Further Results for the Square-Lattice Chromatic Polynomial
• Bulk, surface and corner free energy series for the chromatic polynomial on the square and triangular lattices
• Transfer matrices and partition-function zeros for antiferromagnetic Potts models. VI. Square lattice with special boundary conditions
• Potts model on recursive lattices: some new exact results
• A tree-decomposed transfer matrix for computing exact Potts model partition functions for arbitrary graphs, with applications to planar graph colourings
• Structure of the Partition Function and Transfer Matrices for the Potts Model in a Magnetic Field on Lattice Strips
• Size Reduction of The Transfer Matrix of Two-Dimensional Ising and Potts Models
• Multi-core computation of transfer matrices for strip lattices in the Potts model

Cited by in corpus (1)

• Opinion percolation in structured population