• FrontPage

Objective

The objective of the FLAME project is to transform the development of dense linear algebra libraries from an art reserved for experts to a science that can be understood by novice and expert alike. Rather than being only a library, the project encompasses a new notation for expressing algorithms, a methodology for systematic derivation of algorithms, Application Program Interfaces (APIs) for representing the algorithms in code, and tools for mechanical derivation, implementation and analysis of algorithms and implementations.

The Library: libflame

Many visitors of this wiki will be primarily interested in the high-performance dense linear algebra library that has resulted from the FLAME project. Information on how to download and use this library can be found HERE.

Notation

The key insight that enables the FLAME methodology is a new, more stylized notation for expressing loop-based linear algebra algorithms. This notation closely resembles how algorithms are naturally illustrated with pictures.

Related publications

• Paolo Bientinesi, Enrique S. Quintana-Ortí, and Robert van de Geijn. "Representing Linear Algebra Algorithms in Code: The FLAME APIs," TOMS, 31(1):27-59, March 2005.
• Robert A. van de Geijn and Enrique S. Quintana-Ortí. The Science of Programming Matrix Computations. www.lulu.com. 2008.

Derivation

The FLAME project promotes the systematic derivation of loop-based algorithms hand-in-hand with the proof of their correctness. Key is the ability to identify the loop-invariant: the state to be maintained before and after each loop iteration, which then prescribes the loop-guard, the initialization before the loop, how to progress through the operand(s), and the updates. To derive the shown algorithm for LU factorization one fills in the below "worksheet". In the grey-shaded areas predicates appear that ensure the correctness of the algorithm.

Related publications

• John A. Gunnels, Fred G. Gustavson, Greg M. Henry, and Robert A. van de Geijn, "FLAME: Formal Linear Algebra Methods Environment," TOMS, 27(4):422-455, December 2001.
• Paolo Bientinesi, John A. Gunnels, Margaret E. Myers, Enrique S. Quintana-Ortí, and Robert van de Geijn, "The Science of Deriving Dense Linear Algebra Algorithms," TOMS, 31(1):1-26, March 2005.
• Robert A. van de Geijn and Enrique S. Quintana-Ortí. The Science of Programming Matrix Computations. www.lulu.com. 2008.

function [ A_out ] = LU_blk_var1( A, nb_alg )

  [ ATL, ATR, ...
    ABL, ABR ] = FLA_Part_2x2( A, ...
                               0, 0, 'FLA_TL');

  while ( size( ATL, 1 ) < size( A, 1 ) )

    b = min( size( ABR, 1 ), nb_alg );

    [ A00, A01, A02, ...
      A10, A11, A12, ...
      A20, A21, A22 ] = ...
      FLA_Repart_2x2_to_3x3( ATL, ATR, ...
                             ABL, ABR, b, b, 'FLA_BR');

    %----------------------------------------------%

    A01 = trilu( A00 ) \ A01;
    A10 = A10 / triu( A00 );
    A11 = A11 - A10 * A01;
    A11 = LU_unb_var1( A11 );

    %----------------------------------------------%

    [ ATL, ATR, ...
      ABL, ABR ] = ...
      FLA_Cont_with_3x3_to_2x2( A00, A01, A02, ...
                                A10, A11, A12, ...
                                A20, A21, A22, ...
                                'FLA_TL');
  end

  A_out = [ ATL, ATR
            ABL, ABR ];
  return 

APIs

A number of APIs have been defined fo representing the algorithms in different languages. These include

• SuperMatrix

  Runtime system for scheduling tasks with submatrices to threads

Related publications

• Paolo Bientinesi, Enrique S. Quintana-Ortí, and Robert van de Geijn. "Representing Linear Algebra Algorithms in Code: The FLAME APIs," TOMS, 31(1):27-59, March 2005.
• Tze Meng Low, Kent Milfeld, Robert van de Geijn, and Field Van Zee. "Parallelizing FLAME Code with OpenMP Task Queues," FLAME Working Note #15. The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-2004-50.
• John A. Gunnels, Daniel S. Katz, Enrique S. Quintana-Ortí, and Robert van de Geijn. "Fault-Tolerant High-Performance Matrix-Matrix Multiplication: Theory and Practice," The International Conference for Dependable Systems and Networks (DSN-2001), pp. 47-56, July 2-4, 2001.
• Robert A. van de Geijn and Enrique S. Quintana-Ortí. The Science of Programming Matrix Computations. www.lulu.com. 2008.

Downloads

Libraries and materials can be downloaded for those interested in trying the approach and resulting libraries.

• libflame

• Other FLAME related tools and libraries

Publications and Reference Materials

We maintain a number of documents and web pages.

• All FLAME related publications.

• Robert A. van de Geijn and Enrique S. Quintana-Orti. The Science of Programming Matrix Computations. www.lulu.com, 2008.

• Field G. Van Zee. libflame: The Complete Reference. www.lulu.com, 2009.

  • PDF (Updated frequently).

• FLAME/C online reference materials

  • An incomplete list of routines.

  • A listing of all routines that are part of the libFLAME library has been automatically compiled with Doxygen.

Information for Developers

libflame and related projects are maintained in a repository managed with subversion.

• Information on how to use the FLAME repository.

Contact us

Please e-mail us at flame@cs.utexas.edu , field@cs.utexas.edu , or rvdg@cs.utexas.edu