The serial and parallel belief propagation algorithms

被引：0
|
作者：
Tan, PH [1 ]
Rasmussen, LK [1 ]
机构：
[1] Chalmers Univ Technol, Dept Comp Engn, S-41296 Gothenburg, Sweden
来源：
2005 IEEE International Symposium on Information Theory (ISIT), Vols 1 and 2 | 2005年
关键词：
D O I：
暂无
中图分类号：
TN [电子技术、通信技术];
学科分类号：
0809 ;
摘要：
It has been shown that the stable fixed points of belief propagation (BP) algorithms correspond to extrema of the Bethe free energy. In this paper, we describe the dual problem for the minimization of the Bethe free energy and solve it using simple nonlinear block Gauss-Seidel and Jacobi algorithms. The use of the nonlinear block Gauss-Seidel algorithm corresponds to serial scheduling for the BP algorithm. In addition, it is shown that applying the nonlinear block Jacobi algorithm on the dual of the Bethe free energy corresponds to the parallel BP algorithm.
引用
收藏
页码：729 / 733
页数：5
相关论文
共 50 条
  • [1] A Comparison of Serial and Parallel LLR Updates for LDPC Coded Massive MIMO Detection with Belief Propagation
    Tanno, Shuhei
    Nishimura, Toshihiko
    Ohgane, Takeo
    Ogawa, Yasutaka
    PROCEEDINGS OF 2016 INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY AND ITS APPLICATIONS (ISITA 2016), 2016, : 473 - 477
  • [2] Belief Propagation Algorithms on Noisy Hardware
    Huang, Chu-Hsiang
    Li, Yao
    Dolecek, Lara
    IEEE TRANSACTIONS ON COMMUNICATIONS, 2015, 63 (01) : 11 - 24
  • [3] Parallel belief propagation in factor graphs
    Carnegie Mellon University, Pittsburgh, PA, United States
    Scaling up Machine Learning: Parallel and Distributed Approaches, (190-216):
  • [4] APPLYING PARALLEL COMPUTATION ALGORITHMS IN THE DESIGN OF SERIAL ALGORITHMS
    MEGIDDO, N
    JOURNAL OF THE ACM, 1983, 30 (04) : 852 - 865
  • [5] Factorization in molecular modeling and belief propagation algorithms
    Du, Bochuan
    Tian, Pu
    MATHEMATICAL BIOSCIENCES AND ENGINEERING, 2023, 20 (12) : 21147 - 21162
  • [6] Parallel Belief Propagation Optimized by Coloring on GPUs
    Hou, Junteng
    Si, Chengxiang
    Wang, Shupeng
    Wu, Guangjun
    Zhang, Lei
    ALGORITHMS AND ARCHITECTURES FOR PARALLEL PROCESSING, ICA3PP 2020, PT I, 2020, 12452 : 645 - 660
  • [7] Serial and Parallel LLR Updates Using Damped LLR for LDPC Coded Massive MIMO Detection with Belief Propagation
    Tanno, Shuhei
    Nishimura, Toshihiko
    Ohgane, Takeo
    Ogawa, Yasutaka
    IEICE TRANSACTIONS ON COMMUNICATIONS, 2017, E100B (08) : 1277 - 1284
  • [8] Can parallel algorithms enhance serial implementation?
    Vishkin, U
    COMMUNICATIONS OF THE ACM, 1996, 39 (09) : 88 - 91
  • [9] EFFICIENT SERIAL AND PARALLEL ALGORITHMS FOR MEDIAN FILTERING
    RANKA, S
    SAHNI, S
    PROCEEDINGS OF THE 1989 INTERNATIONAL CONFERENCE ON PARALLEL PROCESSING, VOL 3: ALGORITHMS AND APPLICATIONS, 1989, : 56 - 62
  • [10] EFFICIENT SERIAL AND PARALLEL ALGORITHMS FOR MEDIAN FILTERING
    RANKA, S
    SAHNI, S
    IEEE TRANSACTIONS ON SIGNAL PROCESSING, 1991, 39 (06) : 1462 - 1466
12345