James Demmel and Laura Grigori and Hua Xiang

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2010-29

March 15, 2010

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2010/EECS-2010-29.pdf

Since the cost of communication (moving data) greating exceeds the cost of doing arithmetic on current and future computing platforms, we are motivated to devise algorithms that communication 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 ca-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. 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 for GEPP. However, we present examples showing that neither GEPP nor CALU is uniformly more stable than the other.

---

BibTeX citation:

@techreport{Demmel:EECS-2010-29,
    Author= {Demmel, James and Grigori, Laura and Xiang, Hua},
    Title= {CALU: A Communication Optimal LU Factorization Algorithm},
    Year= {2010},
    Month= {Mar},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2010/EECS-2010-29.html},
    Number= {UCB/EECS-2010-29},
    Abstract= {Since the cost of communication (moving data) greating exceeds the cost of doing arithmetic on current and future computing platforms, we are motivated to devise algorithms that communication 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 ca-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. 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 for GEPP. However, we present examples showing that neither GEPP nor CALU is uniformly more stable than the other.},
}

EndNote citation:

%0 Report
%A Demmel, James 
%A Grigori, Laura 
%A Xiang, Hua 
%T CALU: A Communication Optimal LU Factorization Algorithm
%I EECS Department, University of California, Berkeley
%D 2010
%8 March 15
%@ UCB/EECS-2010-29
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2010/EECS-2010-29.html
%F Demmel:EECS-2010-29