LAWRA LINEAR ALGEBRA WITH RECURSIVE ALGORITHMS * Jerzy Wasniewski 1 , Bjarne S. Andersen 1 , Fred Gustavson 2 , Alexander Karaivanov 1 , Minka Marinova 1 , Plarnen Yalamov 3 Abstract Recursion leads to automatic variable blocking for dense linear algebra
algorithms. The recursion transforms LAPACK level-2 algorithms into lev-
els codes. For this and other reasons recursion usually speeds up the algo-
rithms.
Recursion provides a new, easy and very successful way of program-
ming numerical linear algebra, algorithms. Several algorithms for matrix
factorization have been implemented and tested. Some of these algorithms
are already candidates for the LAPACK library.
Recursion has also been successfully applied to the BLAS (Basic Lin-
ear Algebra Subprograms). The ATLAS system (Automatically Tuned Lin-
ear Algebra Software) uses a recursive coding of the BLAS.
The Cholesky factorization algorithm for positive definite matrices, LU factorization for general matrices, and LDL T factorization for symmetric
indefinite matrices using recursion are formulated in this paper. Perform-
ance graphs of our packed Cholesky and LDL T algorithms are presented
here.
*
This research was partially supported by the UNI•C collaboration with the IBM
T.J. Watson Research Center at. Yorktown Heights. The second and fifth authors
was also supported by the Danish Natural Science Research Council through a
grant for the EPOS project (Efficient Parallel Algorithms for Optimization and
Simulation).
1
Danish Computing Center for Research and Education (UNI•C), Technical
University of Denmark, Building 304, DK-2800 Lyngby, Denmark, email:
jerzy.wasniewski@uni-c.dk.
2
IBM T.J. Watson Research Center, P.P. Box 218, Yorktown Heights, NY 10598,
USA.
3
Center of Applied Mathematics and Informatics, University of Rousse, 7017
Rousse, Bulgaria.
