Hybrid multi-elimination ILU preconditioners on GPUs

Dimitar Lukarski; Hartwig Anzt; Stanimire Tomov; Jack Dongarra

doi:10.1109/IPDPSW.2014.7

Hybrid multi-elimination ILU preconditioners on GPUs

Dimitar Lukarski, Hartwig Anzt, Stanimire Tomov, Jack Dongarra

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

4 Scopus citations

Abstract

Iterative solvers for sparse linear systems often benefit from using preconditioners. While there exist implementations for many iterative methods that leverage the computing power of accelerators, porting the latest developments in preconditioners to accelerators has been challenging. In this paper we develop a selfadaptive multi-elimination preconditioner for graphics processing units (GPUs). The preconditioner is based on a multi-level incomplete LU factorization and uses a direct dense solver for the bottom-level system. For test matrices from the University of Florida matrix collection, we investigate the influence of handling the triangular solvers in the distinct iteration steps in either single or double precision arithmetic. Integrated into a Conjugate Gradient method, we show that our multi-elimination algorithm is highly competitive against popular preconditioners, including multi-colored symmetric Gauss-Seidel relaxation preconditioners, and (multi-colored symmetric) ILU for numerous problems.

Original language	English
Title of host publication	Proceedings - IEEE 28th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2014
Publisher	IEEE Computer Society
Pages	7-16
Number of pages	10
ISBN (Electronic)	9780769552088
DOIs	https://doi.org/10.1109/IPDPSW.2014.7
State	Published - Nov 27 2014
Externally published	Yes
Event	28th IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2014 - Phoenix, United States Duration: May 19 2014 → May 23 2014

Publication series

Name	Proceedings - IEEE 28th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2014

Conference

Conference	28th IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2014
Country/Territory	United States
City	Phoenix
Period	05/19/14 → 05/23/14

Keywords

GPUs
Hybrid Solver
Incomplete LU Factorization
Mixed Precision
Multi-Elimination
Self-Adaptive Preconditioning

Access to Document

10.1109/IPDPSW.2014.7

Cite this

Lukarski, D., Anzt, H., Tomov, S., & Dongarra, J. (2014). Hybrid multi-elimination ILU preconditioners on GPUs. In Proceedings - IEEE 28th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2014 (pp. 7-16). Article 6969366 (Proceedings - IEEE 28th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2014). IEEE Computer Society. https://doi.org/10.1109/IPDPSW.2014.7

Lukarski, Dimitar ; Anzt, Hartwig ; Tomov, Stanimire et al. / Hybrid multi-elimination ILU preconditioners on GPUs. Proceedings - IEEE 28th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2014. IEEE Computer Society, 2014. pp. 7-16 (Proceedings - IEEE 28th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2014).

@inproceedings{64887653f7a8472582138ddd61e5115a,

title = "Hybrid multi-elimination ILU preconditioners on GPUs",

abstract = "Iterative solvers for sparse linear systems often benefit from using preconditioners. While there exist implementations for many iterative methods that leverage the computing power of accelerators, porting the latest developments in preconditioners to accelerators has been challenging. In this paper we develop a selfadaptive multi-elimination preconditioner for graphics processing units (GPUs). The preconditioner is based on a multi-level incomplete LU factorization and uses a direct dense solver for the bottom-level system. For test matrices from the University of Florida matrix collection, we investigate the influence of handling the triangular solvers in the distinct iteration steps in either single or double precision arithmetic. Integrated into a Conjugate Gradient method, we show that our multi-elimination algorithm is highly competitive against popular preconditioners, including multi-colored symmetric Gauss-Seidel relaxation preconditioners, and (multi-colored symmetric) ILU for numerous problems.",

keywords = "GPUs, Hybrid Solver, Incomplete LU Factorization, Mixed Precision, Multi-Elimination, Self-Adaptive Preconditioning",

author = "Dimitar Lukarski and Hartwig Anzt and Stanimire Tomov and Jack Dongarra",

note = "Publisher Copyright: {\textcopyright} 2014 IEEE.; 28th IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2014 ; Conference date: 19-05-2014 Through 23-05-2014",

year = "2014",

month = nov,

day = "27",

doi = "10.1109/IPDPSW.2014.7",

language = "English",

series = "Proceedings - IEEE 28th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2014",

publisher = "IEEE Computer Society",

pages = "7--16",

booktitle = "Proceedings - IEEE 28th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2014",

}

Lukarski, D, Anzt, H, Tomov, S & Dongarra, J 2014, Hybrid multi-elimination ILU preconditioners on GPUs. in Proceedings - IEEE 28th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2014., 6969366, Proceedings - IEEE 28th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2014, IEEE Computer Society, pp. 7-16, 28th IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2014, Phoenix, United States, 05/19/14. https://doi.org/10.1109/IPDPSW.2014.7

Hybrid multi-elimination ILU preconditioners on GPUs. / Lukarski, Dimitar; Anzt, Hartwig; Tomov, Stanimire et al.
Proceedings - IEEE 28th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2014. IEEE Computer Society, 2014. p. 7-16 6969366 (Proceedings - IEEE 28th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2014).

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

TY - GEN

T1 - Hybrid multi-elimination ILU preconditioners on GPUs

AU - Lukarski, Dimitar

AU - Anzt, Hartwig

AU - Tomov, Stanimire

AU - Dongarra, Jack

PY - 2014/11/27

Y1 - 2014/11/27

N2 - Iterative solvers for sparse linear systems often benefit from using preconditioners. While there exist implementations for many iterative methods that leverage the computing power of accelerators, porting the latest developments in preconditioners to accelerators has been challenging. In this paper we develop a selfadaptive multi-elimination preconditioner for graphics processing units (GPUs). The preconditioner is based on a multi-level incomplete LU factorization and uses a direct dense solver for the bottom-level system. For test matrices from the University of Florida matrix collection, we investigate the influence of handling the triangular solvers in the distinct iteration steps in either single or double precision arithmetic. Integrated into a Conjugate Gradient method, we show that our multi-elimination algorithm is highly competitive against popular preconditioners, including multi-colored symmetric Gauss-Seidel relaxation preconditioners, and (multi-colored symmetric) ILU for numerous problems.

AB - Iterative solvers for sparse linear systems often benefit from using preconditioners. While there exist implementations for many iterative methods that leverage the computing power of accelerators, porting the latest developments in preconditioners to accelerators has been challenging. In this paper we develop a selfadaptive multi-elimination preconditioner for graphics processing units (GPUs). The preconditioner is based on a multi-level incomplete LU factorization and uses a direct dense solver for the bottom-level system. For test matrices from the University of Florida matrix collection, we investigate the influence of handling the triangular solvers in the distinct iteration steps in either single or double precision arithmetic. Integrated into a Conjugate Gradient method, we show that our multi-elimination algorithm is highly competitive against popular preconditioners, including multi-colored symmetric Gauss-Seidel relaxation preconditioners, and (multi-colored symmetric) ILU for numerous problems.

KW - GPUs

KW - Hybrid Solver

KW - Incomplete LU Factorization

KW - Mixed Precision

KW - Multi-Elimination

KW - Self-Adaptive Preconditioning

UR - http://www.scopus.com/inward/record.url?scp=84918835419&partnerID=8YFLogxK

U2 - 10.1109/IPDPSW.2014.7

DO - 10.1109/IPDPSW.2014.7

M3 - Conference contribution

AN - SCOPUS:84918835419

T3 - Proceedings - IEEE 28th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2014

SP - 7

EP - 16

BT - Proceedings - IEEE 28th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2014

PB - IEEE Computer Society

T2 - 28th IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2014

Y2 - 19 May 2014 through 23 May 2014

ER -

Lukarski D, Anzt H, Tomov S, Dongarra J. Hybrid multi-elimination ILU preconditioners on GPUs. In Proceedings - IEEE 28th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2014. IEEE Computer Society. 2014. p. 7-16. 6969366. (Proceedings - IEEE 28th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2014). doi: 10.1109/IPDPSW.2014.7

Hybrid multi-elimination ILU preconditioners on GPUs

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this