A Survey of Recent Developments in Parallel Implementations of Gaussian Elimination

TitleA Survey of Recent Developments in Parallel Implementations of Gaussian Elimination
Publication TypeJournal Article
Year of Publication2015
AuthorsDonfack, S., J. Dongarra, M. Faverge, M. Gates, J. Kurzak, P. Luszczek, and I. Yamazaki
JournalConcurrency and Computation: Practice and Experience
Volume27
Issue5
Pagination1292-1309
Date Published04-2015
KeywordsGaussian elimination, lu factorization, Multicore, parallel, shared memory
Abstract

Gaussian elimination is a canonical linear algebra procedure for solving linear systems of equations. In the last few years, the algorithm has received a lot of attention in an attempt to improve its parallel performance. This article surveys recent developments in parallel implementations of Gaussian elimination for shared memory architecture. Five different flavors are investigated. Three of them are based on different strategies for pivoting: partial pivoting, incremental pivoting, and tournament pivoting. The fourth one replaces pivoting with the Partial Random Butterfly Transformation, and finally, an implementation without pivoting is used as a performance baseline. The technique of iterative refinement is applied to recover numerical accuracy when necessary. All parallel implementations are produced using dynamic, superscalar, runtime scheduling and tile matrix layout. Results on two multisocket multicore systems are presented. Performance and numerical accuracy is analyzed.

DOI10.1002/cpe.3306