Parallel family trees for transfer matrices in the Potts model

DOI10.1016/J.CPC.2014.10.011MaRDI QIDQ337713zbMATH OpenOpenAlexFDO

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)

Full work available at URL https://arxiv.org/abs/1312.2664, http://hdl.handle.net/10533/147765

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)

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...

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

Cites work

• scientific article; zbMATH DE number 3856167 (Why is no real title available?)
• scientific article; zbMATH DE number 1182906 (Why is no real title available?)
• scientific article; zbMATH DE number 1953201 (Why is no real title available?)
• scientific article; zbMATH DE number 1864855 (Why is no real title available?)
• scientific article; zbMATH DE number 814821 (Why is no real title available?)
• scientific article; zbMATH DE number 3407710 (Why is no real title available?)
• scientific article; zbMATH DE number 3076589 (Why is no real title available?)
• A Contribution to the Theory of Chromatic Polynomials
• A survey on parallel computing and its applications in data-parallel problems using GPU architectures
• A tree-decomposed transfer matrix for computing exact Potts model partition functions for arbitrary graphs, with applications to planar graph colourings
• Beitrag zur Theorie des Ferromagnetismus
• Bulk, surface and corner free-energy series for the chromatic polynomial on the square and triangular lattices
• Computationally efficient bounds for the Catalan numbers
• Computing Tutte polynomials
• Exact Potts model partition function on strips of the triangular lattice
• Exact Potts model partition functions for strips of the square lattice
• High-precision percolation thresholds and Potts-model critical manifolds from graph polynomials
• Introduction to the GiNaC framework for symbolic computation within the \(\text{C}^{++}\) programming language
• Partition algebras.
• Phase diagram of the chromatic polynomial on a torus
• Structure of the partition function and transfer matrices for the Potts model in a magnetic field on lattice strips
• The Potts model and the Tutte polynomial.
• 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.
• 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. III: Triangular-lattice chromatic polynomial
• 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
• 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

Describes a project that uses

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)