SC 740 Seminar Week 2
Topic: High Performance of Linear Systems (Comparisons of Gaussian Elimination Algorithms on a Cray Y-MP)
By Dr. Marcin Paprzycki
Summary: By Lee L. Emmanwori
1) Basic Idea:
a) The basic premise is the solution of a system of linear equations
ax = b
Where 'a' is an N X N real dense matrix. The basic method for solving the linear equations problem is a suitably modified version of the Gaussian elimination method with partial pivoting.
b) Basic Linear Algebra Subprograms (BLAS) designed using FORTRAN was used as a tool to investigate the performance of different versions of Gaussian elimination method on a single processor Cray Y-MP.
c) FORTRAN was the programming language used in the performance investigation of only three (column oriented) implementations out of the six possible versions of Gaussian elimination.
d) The three column oriented versions investigated were DOT, GAXPY, and SAXPY. The performance of unblocked (level 2 BLAS based) and blocked (level 3 BLAS based) versions of these algorithms were compared for efficiency for the Cray Y-MP.
2) Column Oriented Variants of Block LU Decomposition:
a) Since the considered variants of Gaussian elimination are column oriented, in each step of the process a block of columns will be decomposed, resulting in the calculation of block factors.
b) Each of the blocked versions of the Gaussian elimination utilizes three basic block matrix operations: block triangular solve, matrix-matrix product, and reduction of a block of columns.