# Junction Tree Algorithms for Solving Sparse Linear Systems

### Mark A. Paskin and Gregory D. Lawrence

###
EECS Department

University of California, Berkeley

Technical Report No. UCB/CSD-03-1271

November 2003

### http://www.eecs.berkeley.edu/Pubs/TechRpts/2003/CSD-03-1271.pdf

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

BibTeX citation:

@techreport{Paskin:CSD-03-1271, Author = {Paskin, Mark A. and Lawrence, Gregory D.}, Title = {Junction Tree Algorithms for Solving Sparse Linear Systems}, Institution = {EECS Department, University of California, Berkeley}, Year = {2003}, Month = {Nov}, URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2003/5808.html}, Number = {UCB/CSD-03-1271}, 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 <i>Ax</i> = <i>b</i> where <i>A</i> is a sparse <i>n</i> x <i>n</i> matrix, these methods require <i>O</i>(<i>n</i> x <i>w</i>^3) time and <i>O</i>(<i>n</i> x <i>w</i>^2) space, where <i>w</i> is the treewidth of <i>A</i>'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.)} }

EndNote citation:

%0 Report %A Paskin, Mark A. %A Lawrence, Gregory D. %T Junction Tree Algorithms for Solving Sparse Linear Systems %I EECS Department, University of California, Berkeley %D 2003 %@ UCB/CSD-03-1271 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/2003/5808.html %F Paskin:CSD-03-1271