Parallel family trees for transfer matrices in the Potts model

DOI10.1016/J.CPC.2014.10.011zbMATH Open1348.82044arXiv1312.2664OpenAlexW2103059474MaRDI QIDQ337713FDOQ337713

Authors: Cristobal A. Navarro, Fabrizio Canfora, Nancy Hitschfeld, Gonzalo Navarro 

Publication date: 10 November 2016

Published in: Computer Physics Communications (Search for Journal in Brave)

Abstract: The computational cost of transfer matrix methods for the Potts model is directly related to the problem of extit{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 extit{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 extit{Parallel family trees (PFT)} strategy indeed runs exponentially faster than the extit{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...

Full work available at URL: https://arxiv.org/abs/1312.2664

Recommendations

• Transfer matrix computation of critical polynomials for two-dimensional Potts models
• A tree-decomposed transfer matrix for computing exact Potts model partition functions for arbitrary graphs, with applications to planar graph colourings
• Transfer matrix algorithm for computing the exact partition function of a square lattice polymer
• Parallel Processing and Applied Mathematics
• Compression of transfer matrices

zbMATH Keywords

parallel computingPotts modeltransfer matrixdeletion-contractionstrip lattices

Mathematics Subject Classification ID

Parallel numerical computation (65Y05) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

Cites Work

• Introduction to the GiNaC framework for symbolic computation within the \(\text{C}^{++}\) programming language
• A Contribution to the Theory of Chromatic Polynomials
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The multivariate Tutte polynomial (alias Potts model) for graphs and matroids
• Beitrag zur Theorie des Ferromagnetismus
• Exact Potts model partition functions for strips of the square lattice
• The Potts model and the Tutte polynomial.
• Computing Tutte polynomials
• Partition algebras.
• Title not available (Why is that?)
• Transfer matrices and partition-function zeros for antiferromagnetic Potts models. V. Further results for the square-lattice chromatic polynomial
• Title not available (Why is that?)
• Computationally efficient bounds for the Catalan numbers
• Transfer matrices and partition-function zeros for antiferromagnetic Potts models. III: Triangular-lattice chromatic polynomial
• Exact Potts model partition function on strips of the triangular lattice
• Structure of the partition function and transfer matrices for the Potts model in a magnetic field on lattice strips
• Phase diagram of the chromatic polynomial on a torus
• Transfer matrices and partition-function zeros for antiferromagnetic Potts models. IV. Chromatic polynomial with cyclic boundary conditions
• A tree-decomposed transfer matrix for computing exact Potts model partition functions for arbitrary graphs, with applications to planar graph colourings
• Bulk, surface and corner free-energy series for the chromatic polynomial on the square and triangular lattices
• Title not available (Why is that?)
• A survey on parallel computing and its applications in data-parallel problems using GPU architectures
• High-precision percolation thresholds and Potts-model critical manifolds from graph polynomials
• Title not available (Why is that?)
• Transfer matrices and partition-function zeros for antiferromagnetic Potts models. I: General theory and square-lattice chromatic polynomial.
• Transfer matrices and partition-function zeros for antiferromagnetic Potts models. II: Extended results for square-lattice chromatic polynomial.
• Transfer matrices and partition-function zeros for antiferromagnetic Potts models. VI. Square lattice with extra-vertex boundary conditions

Cited In (1)

• Parallel Processing and Applied Mathematics

Uses Software

• GiNaC
• tutte_bhkk
• tutte

This page was built for publication: Parallel family trees for transfer matrices in the Potts model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q337713)