High-performance computer algebra: A Hecke algebra case study

Patrick Maier, Daria Livesey, Hans Wolfgang Loidl, Phil Trinder

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Citations (Scopus)

Abstract

We describe the first ever parallelisation of an algebraic computation at modern HPC scale. Our case study poses challenges typical of the domain: it is a multi-phase application with dynamic task creation and irregular parallelism over complex control and data structures. Our starting point is a sequential algorithm for finding invariant bilinear forms in the representation theory of Hecke algebras, implemented in the GAP computational group theory system. After optimising the sequential code we develop a parallel algorithm that exploits the new skeleton-based SGP2 framework to parallelise the three most computationally-intensive phases. To this end we develop a new domain-specific skeleton, parBufferTryReduce. We report good parallel performance both on a commodity cluster and on a national HPC, delivering speedups up to 548 over the optimised sequential implementation on 1024 cores.

Original languageEnglish
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer
Pages415-426
Number of pages12
Volume8632 LNCS
ISBN (Print)9783319098722
DOIs
Publication statusPublished - 1 Jan 2014
Event20th International Conference on Parallel Processing - Porto, United Kingdom
Duration: 25 Aug 201429 Aug 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8632 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Conference

Conference20th International Conference on Parallel Processing
Abbreviated titleEuro-Par 2014
CountryUnited Kingdom
CityPorto
Period25/08/1429/08/14

ASJC Scopus subject areas

  • Computer Science(all)
  • Theoretical Computer Science

Fingerprint Dive into the research topics of 'High-performance computer algebra: A Hecke algebra case study'. Together they form a unique fingerprint.

  • Profiles

    Cite this

    Maier, P., Livesey, D., Loidl, H. W., & Trinder, P. (2014). High-performance computer algebra: A Hecke algebra case study. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 8632 LNCS, pp. 415-426). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8632 LNCS). Springer. https://doi.org/10.1007/978-3-319-09873-9_35