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

摘要

We present an implementation-oriented algorithm for the recently developed Gaussian Belief Propagation solver that demonstrates $17times$ 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 $6times$ in iteration count and speedups up to $1.8times$ 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.