UC BERKELEY
EECS technical reports
TECHNICAL REPORTS


CSD-03-1271.pdf
CSD-03-1271.ps
Conditions of Use

Archive Home Page

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.).