Communication-Avoiding Symmetric-Indefinite Factorization
Lists
Only you see this
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=PLTL^{T}P^{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
@article{ballard2014communication,
author = {Grey Ballard and Dulceneia Becker and James Demmel and Jack J. Dongarra and Alex Druinsky and Inon Peled and Oded Schwartz and Sivan Toledo and Ichitaro Yamazaki},
title = {{Communication-Avoiding Symmetric-Indefinite Factorization}},
journal = {SIAM J. Matrix Anal. Appl.},
year = {2014},
url = {https://openreview.net/forum?id=NGnhQskbGR},
}Loading related content...