begindocument PARA'04 State-of-the-Art
in Scientific Computing
June 20-23, 2004 (Home page)
Updated: 22 March 2004

Ideas for high performance linear algebra software

Fred G. Gustavson
IBM T.J. Watson Research Center
Yorktown Heights NY 10598
USA
email: gustav@watson.ibm.com

In this talk we present several ideas for the development of sequential and parallel dense linear algebra software. The algorithms of Linpack and Eispack and later LAPACK and ScaLAPACK have stood the test of time in terms of robustness and accuracy. This talk focuses on producing high performance versions of these algorithms. Our main results use the Algorithms and Architecture Approach. We briefly cover the following topics:

1. The Linear Transformation Approach as a general way to produce the traditional algorithms.

2. The underlying role of Matrix Multiplication.

3. The use of matrix partitioning to describe traditional algorithms.

4. The LAPACK and Level 3 BLAS approach has a basic flaw.

5. New Block-based Data Structures for Matrices removes the flaw.

6. Some of these Data Structures can be used to simplify LAPACK.

7. A plea for Compiler Theory to embrace Linear Algebra Theory.

Home page