Iterative sparse triangular solves for preconditioning

Hartwig Anzt; Edmond Chow; Jack Dongarra

doi:10.1007/978-3-662-48096-0_50

Iterative sparse triangular solves for preconditioning

Hartwig Anzt, Edmond Chow, Jack Dongarra

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

59 Scopus citations

Abstract

Sparse triangular solvers are typically parallelized using level-scheduling techniques, but parallel efficiency is poor on high-throughput architectures like GPUs. We propose using an iterative approach for solving sparse triangular systems when an approximation is suitable. This approach will not work for all problems, but can be successful for sparse triangular matrices arising from incomplete factorizations, where an approximate solution is acceptable. We demonstrate the performance gains that this approach can have on GPUs in the context of solving sparse linear systems with a preconditioned Krylov subspace method. We also illustrate the effect of using asynchronous iterations.

Original language	English
Title of host publication	Euro-Par 2015
Subtitle of host publication	Parallel Processing - 21st International Conference on Parallel and Distributed Computing, Proceedings
Editors	Jesper Larsson Traff, Sascha Hunold, Francesco Versaci
Publisher	Springer Verlag
Pages	650-661
Number of pages	12
ISBN (Print)	9783662480953
DOIs	https://doi.org/10.1007/978-3-662-48096-0_50
State	Published - 2015
Externally published	Yes
Event	21st International Conference on Parallel and Distributed Computing, Euro-Par 2015 - Vienna, Austria Duration: Aug 24 2015 → Aug 28 2015

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9233
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	21st International Conference on Parallel and Distributed Computing, Euro-Par 2015
Country/Territory	Austria
City	Vienna
Period	08/24/15 → 08/28/15

Funding

This material is based upon work supported by the U.S. Department of Energy Office of Science, Office of Advanced Scientific Computing Research, Applied Mathematics program under Award Numbers DE-SC-0012538 and DE-SC-0010042. Support from NVIDIA is also gratefully acknowledged.

Funders	Funder number
Office of Science
U.S. Department of Energy
U.S. Department of Energy
Advanced Scientific Computing Research	DE-SC-0010042, DE-SC-0012538

Access to Document

10.1007/978-3-662-48096-0_50

Cite this

Anzt, H., Chow, E., & Dongarra, J. (2015). Iterative sparse triangular solves for preconditioning. In J. L. Traff, S. Hunold, & F. Versaci (Eds.), Euro-Par 2015: Parallel Processing - 21st International Conference on Parallel and Distributed Computing, Proceedings (pp. 650-661). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9233). Springer Verlag. https://doi.org/10.1007/978-3-662-48096-0_50

Anzt, Hartwig ; Chow, Edmond ; Dongarra, Jack. / Iterative sparse triangular solves for preconditioning. Euro-Par 2015: Parallel Processing - 21st International Conference on Parallel and Distributed Computing, Proceedings. editor / Jesper Larsson Traff ; Sascha Hunold ; Francesco Versaci. Springer Verlag, 2015. pp. 650-661 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{5c582e2c81924483911f3af29355097b,

title = "Iterative sparse triangular solves for preconditioning",

abstract = "Sparse triangular solvers are typically parallelized using level-scheduling techniques, but parallel efficiency is poor on high-throughput architectures like GPUs. We propose using an iterative approach for solving sparse triangular systems when an approximation is suitable. This approach will not work for all problems, but can be successful for sparse triangular matrices arising from incomplete factorizations, where an approximate solution is acceptable. We demonstrate the performance gains that this approach can have on GPUs in the context of solving sparse linear systems with a preconditioned Krylov subspace method. We also illustrate the effect of using asynchronous iterations.",

author = "Hartwig Anzt and Edmond Chow and Jack Dongarra",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2015.; 21st International Conference on Parallel and Distributed Computing, Euro-Par 2015 ; Conference date: 24-08-2015 Through 28-08-2015",

year = "2015",

doi = "10.1007/978-3-662-48096-0_50",

language = "English",

isbn = "9783662480953",

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

publisher = "Springer Verlag",

pages = "650--661",

editor = "Traff, {Jesper Larsson} and Sascha Hunold and Francesco Versaci",

booktitle = "Euro-Par 2015",

}

Anzt, H, Chow, E & Dongarra, J 2015, Iterative sparse triangular solves for preconditioning. in JL Traff, S Hunold & F Versaci (eds), Euro-Par 2015: Parallel Processing - 21st International Conference on Parallel and Distributed Computing, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9233, Springer Verlag, pp. 650-661, 21st International Conference on Parallel and Distributed Computing, Euro-Par 2015, Vienna, Austria, 08/24/15. https://doi.org/10.1007/978-3-662-48096-0_50

Iterative sparse triangular solves for preconditioning. / Anzt, Hartwig; Chow, Edmond; Dongarra, Jack.
Euro-Par 2015: Parallel Processing - 21st International Conference on Parallel and Distributed Computing, Proceedings. ed. / Jesper Larsson Traff; Sascha Hunold; Francesco Versaci. Springer Verlag, 2015. p. 650-661 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9233).

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

TY - GEN

T1 - Iterative sparse triangular solves for preconditioning

AU - Anzt, Hartwig

AU - Chow, Edmond

AU - Dongarra, Jack

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 2015.

PY - 2015

Y1 - 2015

N2 - Sparse triangular solvers are typically parallelized using level-scheduling techniques, but parallel efficiency is poor on high-throughput architectures like GPUs. We propose using an iterative approach for solving sparse triangular systems when an approximation is suitable. This approach will not work for all problems, but can be successful for sparse triangular matrices arising from incomplete factorizations, where an approximate solution is acceptable. We demonstrate the performance gains that this approach can have on GPUs in the context of solving sparse linear systems with a preconditioned Krylov subspace method. We also illustrate the effect of using asynchronous iterations.

AB - Sparse triangular solvers are typically parallelized using level-scheduling techniques, but parallel efficiency is poor on high-throughput architectures like GPUs. We propose using an iterative approach for solving sparse triangular systems when an approximation is suitable. This approach will not work for all problems, but can be successful for sparse triangular matrices arising from incomplete factorizations, where an approximate solution is acceptable. We demonstrate the performance gains that this approach can have on GPUs in the context of solving sparse linear systems with a preconditioned Krylov subspace method. We also illustrate the effect of using asynchronous iterations.

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

U2 - 10.1007/978-3-662-48096-0_50

DO - 10.1007/978-3-662-48096-0_50

M3 - Conference contribution

AN - SCOPUS:84944104636

SN - 9783662480953

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

SP - 650

EP - 661

BT - Euro-Par 2015

A2 - Traff, Jesper Larsson

A2 - Hunold, Sascha

A2 - Versaci, Francesco

PB - Springer Verlag

T2 - 21st International Conference on Parallel and Distributed Computing, Euro-Par 2015

Y2 - 24 August 2015 through 28 August 2015

ER -

Anzt H, Chow E, Dongarra J. Iterative sparse triangular solves for preconditioning. In Traff JL, Hunold S, Versaci F, editors, Euro-Par 2015: Parallel Processing - 21st International Conference on Parallel and Distributed Computing, Proceedings. Springer Verlag. 2015. p. 650-661. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-662-48096-0_50

Iterative sparse triangular solves for preconditioning

Abstract

Publication series

Conference

Funding

Access to Document

Other files and links

Fingerprint

Cite this