Data-sparse Algorithms for Large-scale Applications on Emerging Architectures

A traditional goal of algorithmic optimality, squeezing out operations, has been superseded because of evolution in architecture. Algorithms must now squeeze memory, data transfers, and synchronizations, while extra operations on locally cached data cost relatively little time or energy. Hierarchically low-rank matrices realize a rarely achieved combination of optimal storage complexity and high-computational intensity in approximating a wide class of formally dense operators that arise in exascale applications. They may be regarded as algebraic generalizations of the fast multipole method. Methods based on hierarchical tree-based data structures and their simpler cousins, tile low-rank matrices, are well suited for early exascale architectures, which are provisioned for high processing power relative to memory capacity and memory bandwidth. These data-sparse algorithms are ushering in a renaissance of numerical linear algebra. We describe modules of a software toolkit, Hierarchical Computations on Manycore Architectures (HiCMA), that illustrate these features on several applications. Early modules of this open-source project are distributed in software libraries of major vendors. A recent addition, H2Opus, from the KAUST PhD thesis of Wajih Boukaram, extends H2 hierarchical matrix operations to distributed memory and GPUs.

Brief Biography

David Keyes directs the Extreme Computing Research Center at the King Abdullah University of Science and Technology (KAUST), where he was the founding Dean of the Division of Mathematical and Computer Sciences and Engineering in 2009 and currently serves in the Office of the President as Senior Associate for strategic priorities and institutional partnerships. 

He works at the interface between parallel computing and partial differential equations and statistics, with a current focus on scalable algorithms exploiting data sparsity. 

Before joining KAUST he led multi-institutional scalable solver software projects in the SciDAC and ASCI programs of the US DOE, ran university collaboration programs at US Department of Energy and NASA academic collaboration institutes, and taught at Columbia, Old Dominion, and Yale Universities. 

He is a Fellow of SIAM, AMS, and AAAS, and has been awarded the ACM Gordon Bell Prize, the IEEE Sidney Fernbach Award, and the SIAM Prize for Distinguished Service to the Profession. 

He earned a BSE in Aerospace and Mechanical Sciences from Princeton in 1978 and a Ph.D. in Applied Mathematics from Harvard in 1984.