Junction tree algorithms for solving sparse linear systems
Mark A. Paskin, Gregory Lawrence · UC Berkeley · 2003
In this technical report we present a self-contained introduction to algorithms that solve sparse linear systems by message passing on a junction tree (a.k.a. clique tree). When solving the system Ax = b where A is a sparse n x n matrix, these methods require O(n x w^3) time and O(n x w^2) space, where w is the treewidth of A's sparsity graph. These algorithms are useful for parallel or distributed solutions to linear systems, or to efficiently solve sets of similar linear systems. (Originally published on September 8, 2003; this is a revised version.)