LU Factorization with Communication Avoiding Pivoting Strategy

Hua Xiang

July 22, 2008, 8 a.m. HF 136

We present a low latency approach for computing the LU factorization. The scheme is based on a heuristic communication avoiding(CA) pivoting strategy, which is shown by numerical experiments to be stable in practice. With this scheme we decrease the number of messages, and hence decreasing the time spent in communication. For the sparse case, the hypergraph partition is used to reorder the matrix, and an associated separator tree is used for distributing the data. We also apply the CA-pivoting strategy to reduce the latency, and obtain a balance between numerical stability and parallelism.