CommunicationAvoiding Gaussian Elimination
Authors:
Laura Grigori
(INRIA)

James Demmel
(University of California, Berkeley)

Hua Xiang
(INRIA)

Papers Session
Linear Algebra

Wednesday, 10:30AM  11:00AM

Room Ballroom E

Abstract:
We present CALU, a Communication Avoiding algorithm for the LU
factorization of dense matrices distributed in a twodimensional
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 blockcolumn, 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.