RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. POMI, 1999 Volume 258, Pages 115–133 (Mi znsl1019)

This article is cited in 12 papers

Bulk-synchronous parallel Gaussian elimination

A. V. Tiskin

Computing Laboratory, University of Oxford

Abstract: 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.

UDC: 517.3+512.3+517.7

Received: 12.05.1999

Language: English


 English version:
Journal of Mathematical Sciences (New York), 2002, 108:6, 977–991

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024