Efficient Implementation of Gaussian Belief Propagation Solver for Large Sparse Diagonally Dominant Linear Systems

Abstract

We present an implementation-oriented algorithm for the recently developed Gaussian Belief Propagation solver that demonstrates 17× speedup over the prior algorithm for diagonally dominant matrices generated by typical Finite Elements applications. Compared to the diagonally-preconditioned conjugate gradient method, our algorithm demonstrates empirical improvements up to 6× in iteration count and speedups up to 1.8× in execution time. Also we present a new flexible scheduling scheme of the algorithm that is aimed for implementation on parallel architectures by reducing the iteration count of parallel GaBP and achieving better hardware parallelism.