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

, 2003

http://www2.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},
    Year= {2003},
    Month= {Nov},
    Url= {http://www2.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://www2.eecs.berkeley.edu/Pubs/TechRpts/2003/5808.html
%F Paskin:CSD-03-1271