Mark A. Paskin and Gregory D. Lawrence

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-03-1271
November 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},
    Institution = {EECS Department, University of California, Berkeley},
    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