High-Performance Computer Algebra: A Hecke Algebra Case Study

MAIER, Patrick, LIVESEY, Daria, LOIDL, Hans-Wolfgang and TRINDER, Phil (2014). High-Performance Computer Algebra: A Hecke Algebra Case Study. In: Euro-Par 2014 Parallel Processing. Springer, 415-426.

EuroPar2014-accepted_version.pdf - Accepted Version
All rights reserved.

Download (345kB) | Preview
Official URL: https://doi.org/10.1007/978-3-319-09873-9_35
Link to published version:: https://doi.org/10.1007/978-3-319-09873-9_35


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.

Item Type: Book Section
Departments - Does NOT include content added after October 2018: Faculty of Science, Technology and Arts > Department of Computing
Identification Number: https://doi.org/10.1007/978-3-319-09873-9_35
Page Range: 415-426
Depositing User: Patrick Maier
Date Deposited: 28 Feb 2018 13:30
Last Modified: 18 Mar 2021 15:30
URI: https://shura.shu.ac.uk/id/eprint/18618

Actions (login required)

View Item View Item


Downloads per month over past year

View more statistics