High-performance computer algebra: A Hecke algebra case study

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

doi:10.1007/978-3-319-09873-9_35

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 proceeding › Conference 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 language	English
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publisher	Springer
Pages	415-426
Number of pages	12
Volume	8632 LNCS
ISBN (Print)	9783319098722
DOIs	https://doi.org/10.1007/978-3-319-09873-9_35
Publication status	Published - 1 Jan 2014
Event	20th International Conference on Parallel Processing 2014 - Porto, Portugal Duration: 25 Aug 2014 → 29 Aug 2014

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8632 LNCS
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Conference

Conference	20th International Conference on Parallel Processing 2014
Abbreviated title	Euro-Par 2014
Country/Territory	Portugal
City	Porto
Period	25/08/14 → 29/08/14

ASJC Scopus subject areas

Computer Science(all)
Theoretical Computer Science

Access to Document

10.1007/978-3-319-09873-9_35

Hans-Wolfgang Loidl
- h.w.loidlhw.acuk
- School of Mathematical & Computer Sciences - Associate Professor
- School of Mathematical & Computer Sciences, Computer Science - Associate Professor
Person: Academic (Research & Teaching)

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

Maier, Patrick ; Livesey, Daria ; Loidl, Hans Wolfgang et al. / High-performance computer algebra : A Hecke algebra case study. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 8632 LNCS Springer, 2014. pp. 415-426 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{46718ea174a24895a3736a6f25937113,

title = "High-performance computer algebra: A Hecke algebra case study",

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.",

author = "Patrick Maier and Daria Livesey and Loidl, {Hans Wolfgang} and Phil Trinder",

year = "2014",

month = jan,

day = "1",

doi = "10.1007/978-3-319-09873-9_35",

language = "English",

isbn = "9783319098722",

volume = "8632 LNCS",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "415--426",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

note = "20th International Conference on Parallel Processing 2014, Euro-Par 2014 ; Conference date: 25-08-2014 Through 29-08-2014",

}

Maier, P, Livesey, D, Loidl, HW & 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, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8632 LNCS, Springer, pp. 415-426, 20th International Conference on Parallel Processing 2014, Porto, Portugal, 25/08/14. https://doi.org/10.1007/978-3-319-09873-9_35

High-performance computer algebra : A Hecke algebra case study. / Maier, Patrick; Livesey, Daria; Loidl, Hans Wolfgang et al.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 8632 LNCS Springer, 2014. p. 415-426 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8632 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - High-performance computer algebra

T2 - 20th International Conference on Parallel Processing 2014

AU - Maier, Patrick

AU - Livesey, Daria

AU - Loidl, Hans Wolfgang

AU - Trinder, Phil

PY - 2014/1/1

Y1 - 2014/1/1

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-319-09873-9_35

DO - 10.1007/978-3-319-09873-9_35

M3 - Conference contribution

AN - SCOPUS:84906330202

SN - 9783319098722

VL - 8632 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 415

EP - 426

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

PB - Springer

Y2 - 25 August 2014 through 29 August 2014

ER -

Maier P, Livesey D, Loidl HW, Trinder P. 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. Springer. 2014. p. 415-426. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-09873-9_35

High-performance computer algebra: A Hecke algebra case study

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Fingerprint

Profiles

Hans-Wolfgang Loidl

Cite this