With the advent of processors with multiple layers of cache and/or multiple processing cores it has become necessary to re-examine how matrices should be stored in memory. The investigators study how hierarchical data structures facilitate performance and reduce the programming effort when developing linear algebra libraries. Of particular interest is the impact on future multi-core processors, especially when the number of cores becomes large.
The project pursues the theory and practice of algorithms for linear algebra operations, and their implementations, when the matrices and/or vectors are stored recursively by blocks (hierarchical matrices). The goal is to formalize abstractions for such data structures, to develop Application Programming Interfaces (APIs) that allow the practical development of entire dense and sparse linear algebra libraries specialized for these new data structures, and to develop a theory for optimal performance of blocked algorithms for sequential and parallel architectures, including multi-core architectures.