Cache-aware matrix polynomials

Dominik Huber, Martin Schreiber, Dai Yang, Martin Schulz

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Scopus citations

Abstract

Efficient solvers for partial differential equations are among the most important areas of algorithmic research in high-performance computing. In this paper we present a new optimization for solving linear autonomous partial differential equations. Our approach is based on polynomial approximations for exponential time integration, which involves the computation of matrix polynomial terms () in every time step. This operation is very memory intensive and requires targeted optimizations. In our approach, we exploit the cache-hierarchy of modern computer architectures using a temporal cache blocking approach over the matrix polynomial terms. We develop two single-core implementations realizing cache blocking over several sparse matrix-vector multiplications of the polynomial approximation and compare it to a reference method that performs the computation in the traditional iterative way. We evaluate our approach on three different hardware platforms and for a wide range of different matrices and demonstrate that our approach achieves time savings of up to 50% for a large number of matrices. This is especially the case on platforms with large caches, significantly increasing the performance to solve linear autonomous differential equations.

Original languageEnglish
Title of host publicationComputational Science – ICCS 2020 - 20th International Conference, Proceedings
EditorsValeria V. Krzhizhanovskaya, Gábor Závodszky, Michael H. Lees, Peter M.A. Sloot, Peter M.A. Sloot, Peter M.A. Sloot, Jack J. Dongarra, Sérgio Brissos, João Teixeira
PublisherSpringer Science and Business Media Deutschland GmbH
Pages132-146
Number of pages15
ISBN (Print)9783030503703
DOIs
StatePublished - 2020
Event20th International Conference on Computational Science, ICCS 2020 - Amsterdam, Netherlands
Duration: 3 Jun 20205 Jun 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12137 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference20th International Conference on Computational Science, ICCS 2020
Country/TerritoryNetherlands
CityAmsterdam
Period3/06/205/06/20

Keywords

  • Cache-blocking in time dimension
  • Higher-order time integration
  • Matrix exponentiation

Fingerprint

Dive into the research topics of 'Cache-aware matrix polynomials'. Together they form a unique fingerprint.

Cite this