The design of a parallel dense linear algebra software library: Reduction to Hessenberg, tridiagonal, and bidiagonal form

Jaeyoung Choi, Jack J. Dongarra, David W. Walker

Research output: Contribution to journalArticlepeer-review

24 Scopus citations

Abstract

This paper discusses issues in the design of ScaLAPACK, a software library for performing dense linear algebra computations on distributed memory concurrent computers. These issues are illustrated using the ScaLAPACK routines for reducing matrices to Hessenberg, tridiagonal, and bidiagonal forms. These routines are important in the solution of eigenproblems. The paper focuses on how building blocks are used to create higher-level library routines. Results are presented that demonstrate the scalability of the reduction routines. The most commonly-used building blocks used in ScaLAPACK are the sequencing BLAS, the parallel BLAS (PBLAS) and the Basic Linear Algebra Communication Subprograms (BLACS). Each of the matrix reduction algorithms consists of a series of steps in each of which one block column (or panel), and/or block row, of the matrix is reduced, followed by an update of the portion of the matrix that has not been factorized so far. This latter phase is performed using Level 3 PBLAS operations and contains the bulk of the computation. However, the panel reduction phase involves a significant amount of communication, and is important in determining the scalability of the algorithm. The simplest way to parallelize the panel reduction phase is to replace the BLAS routines appearing in the LAPACK routine (mostly matrix-vector and matrix-matrix multiplications) with the corresponding PBLAS routines. However, in some cases it is possible to reduce communication startup costs by performing the communication necessary for consecutive BLAS operations in a single communication using a BLACS call. Thus, there is a tradeoff between efficiency and software engineering considerations, such as ease of programming and simplicity of code.

Original languageEnglish
Pages (from-to)379-399
Number of pages21
JournalNumerical Algorithms
Volume10
Issue number2
DOIs
StatePublished - Sep 1995

Fingerprint

Dive into the research topics of 'The design of a parallel dense linear algebra software library: Reduction to Hessenberg, tridiagonal, and bidiagonal form'. Together they form a unique fingerprint.

Cite this