Abstract. Since the cost of communication (moving data) greatly exceeds the cost of doing arithmetic on current and future computing platforms, we are motivated to devise algorithms that communicate as little as possible, even if they do slightly more arithmetic, and as long as they still get the right answer. This paper is about getting the right answer for such an algorithm. It discusses CALU, a communication avoiding LU factorization algorithm based on a new pivoting strategy, that we refer to as tournament pivoting. The reason to consider CALU is that it does an optimal amount of communication, and asymptotically less than Gaussian elimination with partial pivoting (GEPP), and so will be much faster on platforms where communication is expensive, as shown in previous work. We show that the Schur complement obtained after each step of performing CALU on a matrix A is the same as the Schur complement obtained after performing GEPP on a larger matrix whose entries are the same as the entries of A (sometimes slightly perturbed) and zeros. More generally, the entire CALU process is equivalent to GEPP on a large, but very sparse matrix, formed by entries of A and zeros. Hence we expect that CALU will behave as GEPP and it will be also very stable in practice. In addition, extensive experiments on random matrices and a set of special matrices show that CALU is stable in practice. The upper bound on the growth factor of CALU is worse than of GEPP. However, there are Wilkinson like-matrices for which GEPP has exponential growth factor, but not CALU, and vice-versa. Key words. LU factorization, communication optimal algorithm, numerical stability AMS subject classifications. 65F50, 65F05, 68R10 1. Introduction. In this paper we discuss CALU, a communication avoiding LU factorization algorithm. The main part of the paper focuses on showing that CALU is stable in practice. We also show that CALU minimizes communication. For this, we use lower bounds on communication for dense LU factorization that were introduced in [5] . These bounds were obtained by showing through reduction that lower bounds on dense matrix multiplication [15, 16] represent lower bounds for dense LU factorization as well. These bounds show that a sequential algorithm that computes the LU factorization of a dense n×n matrix transfers between slow and fast memory at least Ω(n 3 /W 1/2 ) words and Ω(n 3 /W 3/2 ) messages, where W denotes the fast memory size and we assume a message consists of at most W words in consecutive memory locations. On a parallel machine with P processors, if we consider that the local memory size used on each processor is on the order of n 2 /P , it results from the previous bounds that a lower bound on the number of words is Ω(n 2 / √ P ) and a lower
It uses tournament pivoting which has been proven to be stable in practice REF .
CALU: A Communication Optimal LU Factorization Algorithm
Mathematics Computer Science