  In this paper, we argue for the utility of deterministic inference in the
classical problem of numerical linear algebra, that of solving a linear system.
We show how the Gaussian belief propagation solver, known to work for symmetric
matrices can be modified to handle nonsymmetric matrices. Furthermore, we
introduce a new algorithm for matrix inversion that corresponds to the
generalized belief propagation derived from the cluster variation method (or
Kikuchi approximation). We relate these algorithms to LU and block LU
decompositions and provide certain guarantees based on theorems from the theory
of belief propagation. All proposed algorithms are compared with classical
solvers (e.g., Gauss-Seidel, BiCGSTAB) with application to linear elliptic
equations. We also show how the Gaussian belief propagation can be used as
multigrid smoother, resulting in a substantially more robust solver than the
one based on the Gauss-Seidel iterative method.
