Using Additive Modifications in LU Factorization Instead of Pivoting

Neil Lindquist; Piotr Luszczek; Jack Dongarra

doi:10.1145/3577193.3593731

Using Additive Modifications in LU Factorization Instead of Pivoting

Neil Lindquist, Piotr Luszczek, Jack Dongarra

Computer Science and Mathematics Div

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

5 Scopus citations

Abstract

Direct solvers for dense systems of linear equations commonly use partial pivoting to ensure numerical stability. However, pivoting can introduce significant performance overheads, such as synchronization and data movement, particularly on distributed systems. To improve the performance of these solvers, we present an alternative to pivoting in which numerical stability is obtained through additive updates. We implemented this approach using SLATE, a GPU-accelerated numerical linear algebra library, and evaluated it on the Summit supercomputer. Our approach provides better performance (up to 5-fold speedup) than Gaussian elimination with partial pivoting for comparable accuracy on most of the tested matrices. It also provides better accuracy (up to 15 more digits) than Gaussian elimination with no pivoting for comparable performance.

Original language	English
Title of host publication	ACM ICS 2023 - Proceedings of the International Conference on Supercomputing
Publisher	Association for Computing Machinery
Pages	14-24
Number of pages	11
ISBN (Electronic)	9798400700569
DOIs	https://doi.org/10.1145/3577193.3593731
State	Published - Jun 21 2023
Event	37th ACM International Conference on Supercomputing, ICS 2023 - Orlando, United States Duration: Jun 21 2023 → Jun 23 2023

Publication series

Name	Proceedings of the International Conference on Supercomputing

Conference

Conference	37th ACM International Conference on Supercomputing, ICS 2023
Country/Territory	United States
City	Orlando
Period	06/21/23 → 06/23/23

Funding

This material is based upon work supported by the National Science Foundation Office of Advanced Cyberinfrastructure under Grant No. 2004541. This research was also supported by the Exascale Computing Project, a collaborative effort of the U.S. Department of Energy Office of Science and the National Nuclear Security Administration. Additionally, this research used resources of the Oak Ridge Leadership Computing Facility at the Oak Ridge National Laboratory, which is supported by the Office of Science of the U.S. Department of Energy under Contract No. DE-AC05-00OR22725.

Keywords

LU factorization
communication avoidance
linear algebra

Access to Document

10.1145/3577193.3593731

Cite this

@inproceedings{50ecb56a96b746089aa3ceb8e2190746,

title = "Using Additive Modifications in LU Factorization Instead of Pivoting",

abstract = "Direct solvers for dense systems of linear equations commonly use partial pivoting to ensure numerical stability. However, pivoting can introduce significant performance overheads, such as synchronization and data movement, particularly on distributed systems. To improve the performance of these solvers, we present an alternative to pivoting in which numerical stability is obtained through additive updates. We implemented this approach using SLATE, a GPU-accelerated numerical linear algebra library, and evaluated it on the Summit supercomputer. Our approach provides better performance (up to 5-fold speedup) than Gaussian elimination with partial pivoting for comparable accuracy on most of the tested matrices. It also provides better accuracy (up to 15 more digits) than Gaussian elimination with no pivoting for comparable performance.",

keywords = "LU factorization, communication avoidance, linear algebra",

author = "Neil Lindquist and Piotr Luszczek and Jack Dongarra",

note = "Publisher Copyright: {\textcopyright} 2023 ACM.; 37th ACM International Conference on Supercomputing, ICS 2023 ; Conference date: 21-06-2023 Through 23-06-2023",

year = "2023",

month = jun,

day = "21",

doi = "10.1145/3577193.3593731",

language = "English",

series = "Proceedings of the International Conference on Supercomputing",

publisher = "Association for Computing Machinery",

pages = "14--24",

booktitle = "ACM ICS 2023 - Proceedings of the International Conference on Supercomputing",

}

Lindquist, N, Luszczek, P & Dongarra, J 2023, Using Additive Modifications in LU Factorization Instead of Pivoting. in ACM ICS 2023 - Proceedings of the International Conference on Supercomputing. Proceedings of the International Conference on Supercomputing, Association for Computing Machinery, pp. 14-24, 37th ACM International Conference on Supercomputing, ICS 2023, Orlando, United States, 06/21/23. https://doi.org/10.1145/3577193.3593731

Using Additive Modifications in LU Factorization Instead of Pivoting. / Lindquist, Neil; Luszczek, Piotr; Dongarra, Jack.
ACM ICS 2023 - Proceedings of the International Conference on Supercomputing. Association for Computing Machinery, 2023. p. 14-24 (Proceedings of the International Conference on Supercomputing).

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

TY - GEN

T1 - Using Additive Modifications in LU Factorization Instead of Pivoting

AU - Lindquist, Neil

AU - Luszczek, Piotr

AU - Dongarra, Jack

PY - 2023/6/21

Y1 - 2023/6/21

N2 - Direct solvers for dense systems of linear equations commonly use partial pivoting to ensure numerical stability. However, pivoting can introduce significant performance overheads, such as synchronization and data movement, particularly on distributed systems. To improve the performance of these solvers, we present an alternative to pivoting in which numerical stability is obtained through additive updates. We implemented this approach using SLATE, a GPU-accelerated numerical linear algebra library, and evaluated it on the Summit supercomputer. Our approach provides better performance (up to 5-fold speedup) than Gaussian elimination with partial pivoting for comparable accuracy on most of the tested matrices. It also provides better accuracy (up to 15 more digits) than Gaussian elimination with no pivoting for comparable performance.

AB - Direct solvers for dense systems of linear equations commonly use partial pivoting to ensure numerical stability. However, pivoting can introduce significant performance overheads, such as synchronization and data movement, particularly on distributed systems. To improve the performance of these solvers, we present an alternative to pivoting in which numerical stability is obtained through additive updates. We implemented this approach using SLATE, a GPU-accelerated numerical linear algebra library, and evaluated it on the Summit supercomputer. Our approach provides better performance (up to 5-fold speedup) than Gaussian elimination with partial pivoting for comparable accuracy on most of the tested matrices. It also provides better accuracy (up to 15 more digits) than Gaussian elimination with no pivoting for comparable performance.

KW - LU factorization

KW - communication avoidance

KW - linear algebra

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

U2 - 10.1145/3577193.3593731

DO - 10.1145/3577193.3593731

M3 - Conference contribution

AN - SCOPUS:85168416544

T3 - Proceedings of the International Conference on Supercomputing

SP - 14

EP - 24

BT - ACM ICS 2023 - Proceedings of the International Conference on Supercomputing

PB - Association for Computing Machinery

T2 - 37th ACM International Conference on Supercomputing, ICS 2023

Y2 - 21 June 2023 through 23 June 2023

ER -

Using Additive Modifications in LU Factorization Instead of Pivoting

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this