# Communication-Avoiding Symmetric-Indefinite Factorization

### Grey Ballard, Dulceneia Becker, James Demmel, Jack Dongarra, Alex Druinsky, Inon Peled, Oded Schwartz, Sivan Toledo and Ichitaro Yamazaki

###
EECS Department

University of California, Berkeley

Technical Report No. UCB/EECS-2013-127

July 5, 2013

### http://www.eecs.berkeley.edu/Pubs/TechRpts/2013/EECS-2013-127.pdf

We describe and analyze a novel symmetric triangular factorization algorithm. The algorithm is essentially a block version of Aasen’s triangular tridiagonalization. It factors a dense symmetric matrix A as the product A = PL^TLTP^T where P is a permutation matrix, L is lower triangular, and T is block tridiagonal and banded. The algorithm is the first symmetric-indefinite communication-avoiding factorization: it performs an asymptotically optimal amount of communication in a two-level memory hierarchy for almost any cache-line size. Adaptations of the algorithm to parallel computers are likely to be communication efficient as well; one such adaptation has been recently published. The current paper describes the algorithm, proves that it is numerically stable, and proves that it is communication optimal.

BibTeX citation:

@techreport{Ballard:EECS-2013-127, Author = {Ballard, Grey and Becker, Dulceneia and Demmel, James and Dongarra, Jack and Druinsky, Alex and Peled, Inon and Schwartz, Oded and Toledo, Sivan and Yamazaki, Ichitaro}, Title = {Communication-Avoiding Symmetric-Indefinite Factorization}, Institution = {EECS Department, University of California, Berkeley}, Year = {2013}, Month = {Jul}, URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2013/EECS-2013-127.html}, Number = {UCB/EECS-2013-127}, Abstract = {We describe and analyze a novel symmetric triangular factorization algorithm. The algorithm is essentially a block version of Aasen’s triangular tridiagonalization. It factors a dense symmetric matrix A as the product A = PL^TLTP^T where P is a permutation matrix, L is lower triangular, and T is block tridiagonal and banded. The algorithm is the first symmetric-indefinite communication-avoiding factorization: it performs an asymptotically optimal amount of communication in a two-level memory hierarchy for almost any cache-line size. Adaptations of the algorithm to parallel computers are likely to be communication efficient as well; one such adaptation has been recently published. The current paper describes the algorithm, proves that it is numerically stable, and proves that it is communication optimal.} }

EndNote citation:

%0 Report %A Ballard, Grey %A Becker, Dulceneia %A Demmel, James %A Dongarra, Jack %A Druinsky, Alex %A Peled, Inon %A Schwartz, Oded %A Toledo, Sivan %A Yamazaki, Ichitaro %T Communication-Avoiding Symmetric-Indefinite Factorization %I EECS Department, University of California, Berkeley %D 2013 %8 July 5 %@ UCB/EECS-2013-127 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/2013/EECS-2013-127.html %F Ballard:EECS-2013-127