Conference Proceeding
Details
Citation
Maier P, Livesey D, Loidl H & Trinder P (2014) High-Performance Computer Algebra: A Hecke Algebra Case Study. In: Silva F, Dutra I & Costa Santos V (eds.) Euro-Par 2014 Parallel Processing. Lecture Notes on Computer Science, 8632. Euro-Par 2014 Parallel Processing: 20th International Conference, Porto, Portugal, 25.08.2014-29.08.2014. Cham, Switzerland: Springer, pp. 415-426. https://doi.org/10.1007/978-3-319-09873-9_35
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.
Keywords
parallel algorithm; computer algebra; symbolic computation; Laurent polynomial; reduce phase;
Journal
Lecture Notes in Computer Science; Euro-Par 2014 Parallel Processing
Status | Published |
---|---|
Funders | Engineering and Physical Sciences Research Council and Engineering and Physical Sciences Research Council |
Title of series | Lecture Notes on Computer Science |
Number in series | 8632 |
Publication date | 31/12/2014 |
URL | http://hdl.handle.net/1893/30035 |
Publisher | Springer |
Place of publication | Cham, Switzerland |
ISSN | 0302-9743 |
eISSN | 1611-3349 |
ISSN of series | 0302-9743 |
ISBN | 9783319098722 |
eISBN | 9783319098739 |
Conference | Euro-Par 2014 Parallel Processing: 20th International Conference |
Conference location | Porto, Portugal |
Dates | – |
People (1)
Lecturer, Computing Science