Using Additive Modifications in LU Factorization Instead of Pivoting

Neil Lindquist, Piotr Luszczek, Jack Dongarra

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

3 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 languageEnglish
Title of host publicationACM ICS 2023 - Proceedings of the International Conference on Supercomputing
PublisherAssociation for Computing Machinery
Pages14-24
Number of pages11
ISBN (Electronic)9798400700569
DOIs
StatePublished - Jun 21 2023
Externally publishedYes
Event37th ACM International Conference on Supercomputing, ICS 2023 - Orlando, United States
Duration: Jun 21 2023Jun 23 2023

Publication series

NameProceedings of the International Conference on Supercomputing

Conference

Conference37th ACM International Conference on Supercomputing, ICS 2023
Country/TerritoryUnited States
CityOrlando
Period06/21/2306/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.

FundersFunder number
U.S. Department of EnergyDE-AC05-00OR22725
Office of Advanced Cyberinfrastructure2004541
Office of Science
National Nuclear Security Administration

    Keywords

    • LU factorization
    • communication avoidance
    • linear algebra

    Fingerprint

    Dive into the research topics of 'Using Additive Modifications in LU Factorization Instead of Pivoting'. Together they form a unique fingerprint.

    Cite this