Report Number: CS-TR-91-1377
Institution: Stanford University, Department of Computer Science
Title: An evaluation of left-lookikng, right-looking and
multifrontal approaches to sparse Cholesky factorization on
hierarchical memory machines
Author: Rothberg, Edward
Author: Gupta, Anoop
Date: August 1991
Abstract: In this paper we present a comprehensive analysis of the
performance of a variety of sparse Cholesky factorization
methods on hierarchical-memory machines. We investigate
methods that vary along two different axes. Along the first
axis, we consider three different high-level approaches to
sparse factorization: left-looking, right-looking, and
multifrontal. Along the second axis, we consider the
implementation of each of these high-level approaches using
different sets of primitives. The primitives vary based on
the structures they manipulate. One important structure in
sparse Cholesky factorization is a single column of the
matrix. We first consider primitives that manipulate single
columns. These are the most commonly used primitives for
expressing the sparse Cholesky computation. Another important
structure is the supernode, a set of columns with identical
non-zero structures. We consider sets of primitives that
exploit the supemodal structure of the matrix to varying
degrees. We find that primitives that manipulate larger
structures greatly increase the amount of exploitable data
reuse, thus leading to dramatically higher perfommance on
hierarchical-memory machines. We observe performance
increases of two to three times when comparing methods based
on primitives that make extensive use of the supernodal
structure to methods based on primitives that manipulate
columns. We also find that the overall approach
(left-looking, right-looking, or multifrontal) is less
important for performance than the particular set of
primitives used to implement the approach.
http://i.stanford.edu/pub/cstr/reports/cs/tr/91/1377/CS-TR-91-1377.pdf