Polynomial algorithm for exact calculation of partition function for binary spin model on planar graphs

被引：0
作者：
Karandashev Y.M. [1 ]
Malsagov M.Y. [1 ]
机构：
[1] Center of Optical Neural Technologies Scientific Research Institute for System Analysis RAS, Moscow
来源：
Optical Memory and Neural Networks | 2017年 / 26卷 / 2期
关键词：
binary model; Ising model; partition function; Planar graph; polynomial algorithm;
D O I：
10.3103/S1060992X17020035
中图分类号：
学科分类号：
摘要：
In this paper we propose and realize an algorithm for exact calculation of partition function for planar graph models with binary variables. The complexity of the algorithm is O(N2) Experiments show good agreement with Onsager’s analytical solution for the two-dimensional Ising model of infinite size. © 2017, Allerton Press, Inc.
引用
收藏
页码：87 / 95
页数：8
相关论文
共 21 条
  • [1] Dixon J.M., Tuszynski J.A., Carpenter E.J., Analytical expressions for energies, degeneracies and critical temperatures of the 2D square and 3D cubic Ising models, Phys. A, 349, pp. 487-510, (2005)
  • [2] Martin O.C., Monasson R., Zecchina R., Statistical mechanics methods and phase transitions in optimization problems, Theor. Comput. Sci., 265, (2001)
  • [3] Hinton G.E., Osindero S., Teh Y.W., A fast learning algorithm for deep belief nets, Neural Comput., 18, (2006)
  • [4] Wainwright M.J., Jaakkola T., Willsky A.S., A new class of upper bounds on the log partition function, IEEE Trans. Inf. Theory, 51, pp. 2313-2335, (2005)
  • [5] Yedidia J.S., Freeman W.T., Weiss Y., Constructing free-energy approximations and generalized belief propagation approximations, IEEE Trans. Inf. Theory, 51, pp. 2282-2312, (2005)
  • [6] Wainwright M.J., Jordan M.I., Graphical, exponential families, and variational inference, Technical Report, UC, Berkeley Dept. of Statistics, (2003)
  • [7] Wainwright M.J., Jaakkola T., Willsky A.S., Tree-based reparameterization framework for analysis of sum-product and related algorithms, IEEE Trans. Inform. Theory, 49, 5, pp. 1120-1146, (2003)
  • [8] Kryzhanovsky B., Litinskii L., Approximate method of free energy calculation for spin system with arbitrary connection matrix, J. Phys. Conf. Ser., (2015)
  • [9] Kryzhanovsky B., Litinskii L., Generalized approach to energy distribution of spin system, Opt. Mem. Neural Networks, 24, (2015)
  • [10] Applicability of n-vicinity method for calculation of free energy of Ising model, Phys.
123