Robert van de Geijn : March 7, 2005

A few challenging problems in computational sciences.

Abstract

For the past few years, the Formal Linear Algebra Methods Environment (FLAME) project at UT-Austin has pursued a new methodology for developing dense linear algebra libraries. Algorithms, implementations, and (performance and numerical stability) analyses are systematically derived using formal derivation techniques starting only with a mathematical specification of an operation. For performance reasons, the algorithms inherently must be loop-based. The key insight has been how to systematically derive loop-invariants from the mathematical specification of the operation. Given a loop-invariant, the loop that computes the operation is then completely prescribed. Different loop-invariants yield different algorithmic variants for computing the operation.

The results have been encouraging. The approach applies to a broad class of operations, including all operations supported by the Basic Linear Algebra Subprograms (BLAS) and most operations supported by LAPACK. For these operations the FLAME methodology systematically derives families of algorithms that are proven correct as part of the derivation. The introduction of Application Programming Interfaces (APIs) for MATLAB's M-script language, the C and Fortran programming languages, and PLAPACK allows the resulting algorithms to be expressed in code in a way that closely resembles the algorithms themselves so that the correctness of the algorithm implies the correctness of the implementation. An experienced user can derive, implement and test high-performance algorithms in a matter of minutes. A prototype mechanical system, automated using Mathematica, has been developed that partially automates the approach. We describe the project, the theoretical foundation that supports the approach, the automated system, and the libraries that are being developed.

This work is a collaboration with many researchers, including Paolo Bientinesi (UT-Austin), Tze Meng Low (UT-Austin), Field Van Zee (UT-Austin), and Enrique Quintana-Orti (Univ. Jaume I).

We recommend that the interested attendee read the following papers prior to the talk:

• Paolo Bientinesi, John A. Gunnels, Margaret E. Myers, Enrique Quintana-Orti, and Robert van de Geijn. "The Science of Deriving Dense Linear Algebra Algorithms." ACM Transactions on Mathematical Software, March 2005.
• Paolo Bientinesi, Enrique Quintana-Orti, and Robert van de Geijn. "Representing Linear Algebra Algorithms in Code: The FLAME APIs." ACM Transactions on Mathematical Software, March 2005.

both of which are available at http://www.cs.utexas.edu/users/flame/pubs.html.

Further information regarding this project can be found at http://www.cs.utexas.edu/users/flame where a more complete list of collaborators can also be found.