### Junction Tree Algorithms for Solving Sparse Linear Systems

**Authors:**

Paskin, Mark A.

Lawrence, Gregory D.
**Technical Report Identifier:** CSD-03-1271
**November 7, 2003**

CSD-03-1271.pdf

CSD-03-1271.ps

**Abstract:** 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.).