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

Recursive Blocked Algorithms and Hybrid Data Structures for Dense Matrix Library Software

Bo Kågström
Department of Computing Science and HPC2N
Umeå University
SE-901 87 Umeå, Sweden
email: bokg@cs.umu.se

Abstract:

Matrix computations are both fundamental and ubiquitous in computational science and its vast application areas. Along with the development of more advanced computer systems with complex memory hierarchies, there is a continuing demand for new algorithms and library software that efficiently utilize and adapt to new architecture features. In this presentation, we review some of the recent advances made by applying the paradigm of recursion to dense matrix computations on today's memory tiered computer systems (see Elmroth, Gustavson, Jonsson and Kågström, SIAM Review, Vol. 46, No. 1, 2004, pp. 3-45).

Recursion allows for efficient utilization of a memory hierarchy and generalizes existing fixed blocking by introducing automatic variable blocking that has the potential of matching every level of a deep memory hierarchy. Novel recursive blocked algorithms offer new ways to compute factorizations such as Cholesky and QR and to solve matrix equations. In fact, the whole gamut of existing dense linear algebra factorization is beginning to be re-examined in view of the recursive paradigm. Use of recursion has led to using new hybrid data structures and optimized superscalar kernels. The results we survey include new algorithms and library software implementations for level 3 kernels, matrix factorizations, the solution of general systems of linear equations and several common Sylvester-type matrix equations. The software implementations we survey are robust and show impressive performance on today's high performance computing systems.

We end by discussing some open problems and ongoing work on using recursion for solving periodic matrix equations, leading to recursive blocked algorithms for 3-dimensional data structures (matrices). The third dimension is the periodicity index of the matrices.

Home page