Geodesic
Bulk-synchronous parallel Gaussian elimination
Zapiski Nauchnykh Seminarov POMI, Representation theory, dynamical systems, combinatorial and algoritmic methods. Part IV, Tome 258 (1999), pp. 115-133

Voir la notice de l'article provenant de la source Math-Net.Ru

The model of bulk-synchronous parallel (BSP) computation is an emerging paradigm of general-purpose parallel computing. We study the BSP complexity of Gaussian elimination and related problems. First, we analyze the Gaussian elimination without pivoting, which can be applied to the LU decomposition of symmetric positive definite or diagonally dominant real matrices. Then we analyze the Gaussian elimination with Schönhage's recursive local pivoting suitable for the LU decomposition of matrices over a finite field, and for the QR decomposition of real matrices by the Givens rotations. Both versions of Gaussian elimination can be performed with an optimal amount of local computation, but optimal communication and synchronization costs may not be achievable simultaneously. The algorithms presented in the paper allow one to trade off communication and synchronization costs in a certain range, achieving optimal or near-optimal cost values at the extremes. 
@article{ZNSL_1999_258_a5,
     author = {A. V. Tiskin},
     title = {Bulk-synchronous parallel {Gaussian} elimination},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {115--133},
     publisher = {mathdoc},
     volume = {258},
     year = {1999},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_1999_258_a5/}
}
TY  - JOUR
AU  - A. V. Tiskin
TI  - Bulk-synchronous parallel Gaussian elimination
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 1999
SP  - 115
EP  - 133
VL  - 258
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ZNSL_1999_258_a5/
LA  - en
ID  - ZNSL_1999_258_a5
ER  - 
%0 Journal Article
%A A. V. Tiskin
%T Bulk-synchronous parallel Gaussian elimination
%J Zapiski Nauchnykh Seminarov POMI
%D 1999
%P 115-133
%V 258
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ZNSL_1999_258_a5/
%G en
%F ZNSL_1999_258_a5
A. V. Tiskin. Bulk-synchronous parallel Gaussian elimination. Zapiski Nauchnykh Seminarov POMI, Representation theory, dynamical systems, combinatorial and algoritmic methods. Part IV, Tome 258 (1999), pp. 115-133. http://geodesic.mathdoc.fr/item/ZNSL_1999_258_a5/