Scalable Sparse LU Decomposition with Static Pivoting
Sherry Li(National Energy Research Scientific Computing (NERSC))
Division Lawrence Berkeley National Laboratory
Monday March 1st, 11.00 a.m. Parallel Algorithms Seminar CERFACS Conference Room
Abstract :
Although Gaussian elimination with partial pivoting is a robust algorithm to solve unsymmetric sparse linear systems of equations, it is hard to implement efficiently on distributed memory machines, because of its dynamic and somewhat unpredictable way of generating fine-grained work and intermediate results at run time. We have been investigating the possibility of replacing (dynamic) partial pivoting by some other techniques to control the element growth during the elimination. These include static pre-pivoting large elements to the diagonal, use extra precision if needed, and allow low rank modifications with corrections in the end. We will show the promise of the new method from numeric experiments.
In the second part, we present an MPI implementation of the distributed LU and triangular solve algorithms. Both algorithms are governed by an elaborate 2-D (nonuniform) block-cyclic data distribution. This layout is not natural for sparse matrices, but proves to be more scalable. Initial results on the Cray T3E are very encouraging.
Joint work with Jim Demmel.
Cerfacs' Conferences 1999-2001 Home Page
