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

Abstract: 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, extends H2 hierarchical matrix operations to distributed memory and GPUs.

computational engineering, finance, and sciencenumerical analysis

Audience: researchers in the topic

E-NLA - Online seminar series on numerical linear algebra

Series comments: E-NLA is an online seminar series dedicated to topics in Numerical Linear Algebra. Talks take place on Wednesdays at 4pm (Central European Time) via Zoom and are initially scheduled on a weekly basis.

To join the seminar, please complete the sign up form at the bottom of the webpage. Information about how to connect to the conference call will be circulated via email to all registered attendees.