Scalable Linear Algebra Package (ScaLAPACK)

• Kurzbeschreibung und Übersicht
• Hinweise zur Benutzung von LAPACK/ScaLAPACK auf den HPC-Systemen des SCC
• Der ScaLAPACK Users' Guide (von www.netlib.org)
• Das ScaLAPACK Verzeichnis der NETLIB
• Informationen zu den BLACS von der NETLIB

Linear Algebra Package (LAPACK)

• Externe Informationen
  • LAPACK Users' Guide von der netlib (USA)
  • LAPACK Homepage von der netlib (USA)

Scalable Linear Algebra Package (ScaLAPACK) ist eine Fortran-Bibliothek mit Unterprogrammen zur Lösung von linearen Gleichungssystemen und Eigenwertaufgaben auf Distributed-Memory-Parallelrechnern oder Workstationclustern. Es werden Routinen unterschiedlicher Matrixtypen (u.a. beliebige rechteckige Matrix, Bandmatrix, Tridiagonalmatrix, symmetrische bzw. hermitesche Matrix) unterstützt und sowohl einfach zu benutzende Driver-Routinen als auch nur für Experten vorgesehene Unterprogrammaufrufe bereitgestellt, die eine Feinsteuerung der Algorithmen zulassen. Alle Programme sind i.a. für die vier Datentypen REAL, DOUBLE PRECISION, COMPLEX und COMPLEX*16 implementiert.

Um eine einfache Portierung von ScaLAPACK auf verschiedenste Rechnerarchitekturen und Kommunikationsbibliotheken zu ermöglichen, wurden verschiedene interne Schnittstellen definiert, die auch für andere Projekte interessant sein können. Es sind diese die PBLAS und die BLACS.

PBLAS steht für Parallel Basic Linear Algebra Subprograms und stellt eine Erweiterung der bekannten BLAS für Parallelrechner mit verteiltem Speicher dar. In den PBLAS sind also z.B. Funktionen für Matrix-Matrix- und Matrix-Vektor-Operationen enthalten, wobei die Matrizen und Vektoren auf die lokalen Speicher der einzelnen Prozessoren verteilt sind. Um eine möglichst effiziente Nutzung der Einzelprozessoren zu gewährleisten, werden für die lokalen Rechenoperationen, soweit möglich, BLAS-Routinen eingesetzt, die in der Regel in einer optimierten Version vorliegen.

Für die Kommunikation werden die Basic Linear Algebra Communication Subprograms (BLACS) verwendet, die einfache Schnittstellen zum Versenden und Empfangen von rechteckigen oder trapezförmigen Matrizen und Teilmatrizen enthalten. Die BLACS setzen wiederum auf eine Message Passing Library wie MPI oder PVM auf.

ScaLAPACK setzt auf die PBLAS-, BLACS-, LAPACK- und BLAS-Libraries auf.

Auf dem Xeon-basierten KIT-Parallelrechner HP XC3000 ist sowohl die LAPACK- als auch die ScaLAPACK-Bibliothek in die MKL von Intel integriert. Wie man die beiden Bibliotheken in eigene Software integriert, findet man im Kapitel 10 des HP XC3000 User Guide.

Auf dem Xeon-basierten InstitutsCluster II ist sowohl die LAPACK- als auch die ScaLAPACK-Bibliothek in die MKL von Intel integriert. Wie man die beiden Bibliotheken in eigene Software integriert, findet man im Kapitel 10 des InstitutsCluster II User Guide.

LAPACK Introduction

LAPACK is intended to be the successor to LINPACK and EISPACK.
It extends the functionality of these packages by including
equilibration, iterative refinement, error bounds, and driver routines
for linear systems, routines for computing and re-ordering the Schur
factorization, and condition estimation routines for eigenvalue
problems.  LAPACK improves on the accuracy of the standard algorithms
in EISPACK by including high accuracy algorithms for finding singular
values and eigenvalues of bidiagonal and tridiagonal matrices
respectively that arise in SVD and symmetric eigenvalue problems.
The algorithms and software have been restructured to achieve high
efficiency on vector processors, high-performance ``superscalar''
workstations, and shared-memory multi-processors.
                  LAPACK, Public Release 1.0
LAPACK is a transportable library of Fortran 77 subroutines for
solving the most common problems in numerical linear algebra:
systems of linear equations, linear least squares problems,
eigenvalue problems, and singular value problems. It has been
designed to be efficient on a wide range of modern high-performance
computers.
Developed by Ed Anderson, Z. Bai, Chris Bischof, Jim Demmel, Jack
Dongarra, Jeremy Du Croz, Anne Greenbaum, Sven Hammarling, Alan
McKenney, Susan Ostrouchov, and Danny Sorensen. 2/29/91.

LAPACK Routines
===============
Each subroutine name in LAPACK is a coded specification of the
computation done by the subroutine. All names consist of six characters
in the form TXXYYY. The first letter, T, indicates the matrix data type
as follows:
S    |  REAL
D    |  DOUBLE PRECISION
C    |  COMPLEX
Z    |  COMPLEX*16

The next two letters, XX, indicate the type of matrix. Most of these
two-letter codes apply to both real and complex routines; a few apply
specifically to one or the other, as indicated below:
BD   |  bidiagonal
GB   |  general band
GE   |  general (i.e. unsymmetric, in some cases rectangular)
GG   |  general matrices, generalized problem (i.e. a pair of general
     |     matrices) (not used in Release 1.0)
GT   |  general tridiagonal
HB   |  (complex) Hermitian band
HE   |  (complex) Hermitian
HG   |  upper Hessenberg matrix, generalized problem (i.e., a Hessenberg and a
     |     triangular matrix) (not used in Release 1.0)
HP   |  (complex) Hermitian, packed storage
HS   |  upper Hessenberg
OP   |  (real) orthogonal, packed storage
OR   |  (real) orthogonal
PB   |  symmetric or Hermitian positive definite band
PO   |  symmetric or Hermitian positive definite
PP   |  symmetric or Hermitian positive definite, packed storage
PT   |  symmetric or Hermitian positive definite tridiagonal
SB   |  (real) symmetric band
SP   |  symmetric, packed storage
ST   |  symmetric tridiagonal
SY   |  symmetric
TB   |  triangular band
TG   |  triangular matrices, generalized problem (i.e., a pair of
     |     triangular matrices)
TP   |  triangular, packed storage
TR   |  triangular (or in some cases quasi-triangular)
TZ   |  trapezoidal
UN   |  (complex) unitary
UP   |  (complex) unitary, packed storage

The last three characters, YYY, indicate the computation done by a
particular subroutine. Included in this release are subroutines to
perform the following computations:
BAK  |  back transformation of eigenvectors after balancing
BAL  |  permute and/or balance to isolate eigenvalues
BRD  |  reduce to bidiagonal form by orthogonal transformations
CON  |  estimate condition number
EBZ  |  compute selected eigenvalues by bisection
EIN  |  compute selected eigenvectors by inverse iteration
EQR  |  compute eigenvalues and/or the Schur form using the QR algorithm
EQU  |  equilibrate a matrix to reduce its condition number
ERF  |  compute eigenvectors using the Pal-Walker-Kahan variant of the
     |     QL or QR algorithm
EVC  |  compute eigenvectors from Schur factorization
EXC  |  swap adjacent diagonal blocks in a quasi-upper triangular matrix
GBR  |  generate the orthogonal/unitary matrix from xGEBRD
GHR  |  generate the orthogonal/unitary matrix from xGEHRD
GLQ  |  generate the orthogonal/unitary matrix from xGELQF
GQL  |  generate the orthogonal/unitary matrix from xGEQLF
GQR  |  generate the orthogonal/unitary matrix from xGEQRF
GRQ  |  generate the orthogonal/unitary matrix from xGERQF
GST  |  reduce a symmetric-definite generalized eigenvalue problem to
     |     standard form
GTR  |  generate the orthogonal/unitary matrix from xxxTRD
HRD  |  reduce to upper Hessenberg form by orthogonal transformations
LQF  |  compute an LQ factorization without pivoting
MBR  |  multiply by the orthogonal/unitary matrix from xGEBRD
MHR  |  multiply by the orthogonal/unitary matrix from xGEHRD
MLQ  |  multiply by the orthogonal/unitary matrix from xGELQF
MQL  |  multiply by the orthogonal/unitary matrix from xGEQLF
MQR  |  multiply by the orthogonal/unitary matrix from xGEQRF
MRQ  |  multiply by the orthogonal/unitary matrix from xGERQF
MTR  |  multiply by the orthogonal/unitary matrix from xxxTRD
QLF  |  compute a QL factorization without pivoting
QPF  |  compute a QR factorization with column pivoting
QRF  |  compute a QR factorization without pivoting
RFS  |  refine initial solution returned by TRS routines
RQF  |  compute an RQ factorization without pivoting
SEN  |  compute a basis and/or reciprocal condition number (sensitivity)
     |     of an invariant subspace
SNA  |  estimate reciprocal condition numbers of eigenval./-vector pairs
SQR  |  compute singular values and/or singular vectors using the QR
     |     algorithm
SYL  |  solve the Sylvester matrix equation
TRD  |  reduce a symmetric matrix to real symmetric tridiagonal form
TRF  |  compute a triangular factorization (LU, Cholesky, etc.)
TRI  |  compute inverse (based on triangular factorization)
TRS  |  solve systems of linear equations (based on triangular
     |     factorization)

Given these definitions, the following table indicates the LAPACK
subroutines for the solution of systems of linear equations:
                                        | HE | HP |              | UN |
     | GE | GB | GT | PO | PP | PB | PT | SY | SP | TR | TP | TB | OR |
     ------------------------------------------------------------------
TRF  |  x |  x |  x |  x |  x |  x |  x |  x |  x |    |    |    |    |
TRS  |  x |  x |  x |  x |  x |  x |  x |  x |  x |  x |  x |  x |    |
RFS  |  x |  x |  x |  x |  x |  x |  x |  x |  x |  x |  x |  x |    |
TRI  |  x |    |    |  x |  x |    |    |  x |  x |  x |  x |    |    |
CON  |  x |  x |  x |  x |  x |  x |  x |  x |  x |  x |  x |  x |    |
EQU  |  x |  x |    |  x |  x |  x |    |    |    |    |    |    |    |
QPF  |  x |    |    |    |    |    |    |    |    |    |    |    |    |
QRF* |  x |    |    |    |    |    |    |    |    |    |    |    |    |
GQR* |    |    |    |    |    |    |    |    |    |    |    |    |  x |
MQR* |    |    |    |    |    |    |    |    |    |    |    |    |  x |
   * - also RQ, QL, and LQ}

The following table indicates the LAPACK subroutines for finding
eigenvalues and eigenvectors or singular values and singular vectors:
                              | HE | HP | HB |
     | GE | HS | HG | TR | TG | SY | SP | SB | ST | PT | BD |
     --------------------------------------------------------
HRD  |  x |    |    |    |    |    |    |    |    |    |    |
TRD  |    |    |    |    |    |  x |  x |  x |    |    |    |
BRD  |  x |    |    |    |    |    |    |    |    |    |    |
EQR  |    |  x |    |    |    |    |    |    |  x |  x |    |
EIN  |    |  x |    |    |    |    |    |    |  x |    |    |
EVC  |    |    |    |  x |  x |    |    |    |    |    |    |
EBZ  |    |    |    |    |    |    |    |    |  x |    |    |
ERF  |    |    |    |    |    |    |    |    |  x |    |    |
SQR  |    |    |    |    |    |    |    |    |    |    |  x |
SEN  |    |    |    |  x |    |    |    |    |    |    |    |
SNA  |    |    |    |  x |    |    |    |    |    |    |    |
SYL  |    |    |    |  x |    |    |    |    |    |    |    |
EXC  |    |    |    |  x |    |    |    |    |    |    |    |
BAL  |  x |    |    |    |    |    |    |    |    |    |    |
BAK  |  x |    |    |    |    |    |    |    |    |    |    |
GST  |    |    |    |    |    |  x |  x |    |    |    |    |

Orthogonal/unitary transformation routines have also been provided for
the reductions that use elementary transformations.
     | UN  | UP  |
     | OR  | OP  |
     -------------
GHR  |  x  |     |
GTR  |  x  |  x  |
GBR  |  x  |     |
MHR  |  x  |     |
MTR  |  x  |  x  |
MBR  |  x  |     |

In addition, a number of driver routines are provided with this release.
The naming convention for the driver routines is the same as for the
LAPACK routines, but the last 3 characters YYY have the following
meanings (note an `X' in the last character position indicates a more
expert driver):
SV   |  factor the matrix and solve a system of equations
SVX  |  equilibrate, factor, solve, compute error bounds and do
     |     iterative refinement, and estimate the condition number
LS   |  solve over- or underdetermined linear system using orthogonal
     |     factorizations
LSX  |  compute a minimum-norm solution using a complete orthogonal
     |     factorization (using QR with column pivoting)
LSS  |  solve least squares problem using the SVD
EV   |  compute all eigenvalues and/or eigenvectors
EVX  |  compute selected eigenvalues and eigenvectors
ES   |  compute all eigenvalues, Schur form, and/or Schur vectors
ESX  |  compute all eigenvalues, Schur form, and/or Schur vectors and
     |     the conditioning of selected eigenvalues or eigenvectors
GV   |  compute generalized eigenvalues and/or generalized eigenvectors
GS   |  compute generalized eigenval., Schur form, and/or Schur vectors
SVD  |  compute the SVD and/or singular vectors

The driver routines provided in LAPACK are indicated by the following
table:
                                               | HE  | HP  | HB  |
     | GE  | GB  | GT  | PO  | PP  | PB  | PT  | SY  | SP  | SB  | ST  |
     -------------------------------------------------------------------
SV   |  x  |  x  |  x  |  x  |  x  |  x  |  x  |  x  |  x  |     |     |
SVX  |  x  |  x  |  x  |  x  |  x  |  x  |  x  |  x  |  x  |     |     |
LS   |  x  |     |     |     |     |     |     |     |     |     |     |
LSX  |  x  |     |     |     |     |     |     |     |     |     |     |
LSS  |  x  |     |     |     |     |     |     |     |     |     |     |
EV   |  x  |     |     |     |     |     |     |  x  |  x  |  x  |  x  |
EVX  |  x  |     |     |     |     |     |     |  x  |  x  |  x  |  x  |
ES   |  x  |     |     |     |     |     |     |     |     |     |     |
ESX  |  x  |     |     |     |     |     |     |     |     |     |     |
GV   |     |     |     |     |     |     |     |  x  |  x  |     |     |
GS   |     |     |     |     |     |     |     |     |     |     |     |
SVD  |  x  |     |     |     |     |     |     |     |     |     |     |

Bibliography:
============
<1>  E. Anderson, Z. Bai, C. Bischof, J. Demmel, J. Dongarra,
     J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney,
     S. Ostrouchov, and D. Sorensen,
     LAPACK Users' Guide, SIAM, Philadelphia, PA, 1992.
<2>  E. Anderson and J. Dongarra,
     LAPACK Working Note 16: Results from the Initial Release of LAPACK,
     University of Tennessee, CS-89-89, November 1989.
<3>  C. Bischof, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum,
     S. Hammarling, and D. Sorensen,
     LAPACK Working Note 5:  Provisional Contents,
     Argonne National Laboratory, ANL-88-38, September 1988.
<4>  Z. Bai, J. Demmel, and A. McKenney,
     LAPACK Working Note 13: On the Conditioning of the Nonsymmetric
     Eigenvalue Problem:  Theory and Software,
     University of Tennessee, CS-89-86, October 1989.
<5>  J. Dongarra, J. Du Croz, I. Duff, and S. Hammarling,
     "A Set of Level 3 Basic Linear Algebra Subprograms",
     ACM Trans. Math. Soft., 16, 1:1-17, March 1990
<6>  J. Dongarra, J. Du Croz, I. Duff, and S. Hammarling,
     "A Set of Level 3 Basic Linear Algebra Subprograms:
     Model Implementation and Test Programs",
     ACM Trans. Math. Soft., 16, 1:18-28, March 1990
<7>  J. Dongarra, J. Du Croz, S. Hammarling, and R. Hanson,
     "An Extended Set of Fortran Basic Linear Algebra Subprograms",
     ACM Trans. Math. Soft., 14, 1:1-17, March 1988.
<8>  J. Dongarra, J. Du Croz, S. Hammarling, and R. Hanson,
     "An Extended Set of Fortran Basic Linear Algebra Subprograms:
     Model Implementation and Test Programs",
     ACM Trans. Math. Soft., 14, 1:18-32, March 1988.
<9>  C. L. Lawson, R. J. Hanson, D. R. Kincaid, and F. T. Krogh,
     "Basic Linear Algebra Subprograms for Fortran Usage",
     ACM Trans. Math. Soft., 5, 3:308-323, September 1979.