External Memory Sparse Direct Solvers
Collaborators:
Florin Dobrian
Objective:
We are developing external memory algorithms and software
for solving large, sparse systems of equations by means of
direct solvers. Such methods will enable sparse direct solvers to
make effective use of the Terabytes of storage available
on serial computers; parallel algorithms running on
PC-clusters like Coral and Teraflop parallel computers with
multiple levels of memory hierarchy will also benefit.
Approach:
We formalize two problems for
external memory sparse matrix factorizations:
minimizing the core memory required
in a read-once/write-once model, and minimizing the data movement
needed in a read-many/write-many model.
We compute bounds on these quantities
for sparse problems whose computational graphs have
good separators.
We show that a data structure
called the elimination tree determines the core memory requirements
and the data movement costs of
a sparse factorization algorithm.
The relative performance
of the three commonly used variants of the factorization algorithm, viz.
left-looking, right-looking, and multifrontal, can vary a great deal
for unbalanced elimination trees that occur in mathematical programming
and related applications.
We have designed
fast simulators that compute the data movement costs of
these algorithms in time proportional to the
size of the factors rather than the flops required to compute them.
Florin Dobrian's PhD thesis contains a detailed discussion of
the issues in designing efficient external memory sparse factorization
algorithms.
We also propose to
extend OBLIO, our object-oriented sparse direct solver library,
with serial and parallel implementations of external memory solvers.
back to
highlights page