SC Conference - Activity Details
Communication-Avoiding Gaussian Elimination
Authors:| Laura Grigori (INRIA) |
| James Demmel (University of California, Berkeley) |
| Hua Xiang (INRIA) |
| Linear Algebra |
| Wednesday, 10:30AM - 11:00AM |
| Room Ballroom E |
We present CALU, a Communication Avoiding algorithm for the LU
factorization of dense matrices distributed in a two-dimensional
cyclic layout. The algorithm is based on a new pivoting strategy,
which is stable in practice. The new algorithm is optimal (up to
polylogarithmic factors) in the amount of communication it performs.
Our experiments show that CALU leads to a reduction in the parallel
time, in particular when the latency time is an important factor of
the overall time. The factorization of a block-column, a subroutine
of CALU, outperforms the corresponding routine PDGETF2 from ScaLAPACK
up to a factor of 4.37 on an IBM POWER 5 system and up to a factor
of 5.58 on a Cray XT4 system. On square matrices of order 10000,
CALU outperforms the corresponding routine PDGETRF from ScaLAPACK by a
factor of 1.24 on IBM POWER 5 and by a factor of 1.31 on Cray XT4.
The full paper can be found in the
IEEE Xplore Digital Library
and
ACM Digital Library
| IEEE Computer Society / ACM | 2 0 Y E A R S - U N L E A S H I N G T H E P O W E R O F H P C |