SparseLU, A Novel Algorithm and Math Library for Sparse LU Factorization

Pedro Valero-Lara; Cameron Greenwalt; Jeffrey S. Vetter

doi:10.1109/IA356718.2022.00010

SparseLU, A Novel Algorithm and Math Library for Sparse LU Factorization

Pedro Valero-Lara, Cameron Greenwalt, Jeffrey S. Vetter

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

4 Scopus citations

Abstract

Decomposing sparse matrices into lower and upper triangular matrices (sparse LU factorization) is a key operation in many computational scientific applications. We developed SparseLU, a sparse linear algebra library that implements a new algorithm for LU factorization on general sparse matrices. The new algorithm divides the input matrix into tiles to which OpenMP tasks are created for factorization computation, where only tiles that contain nonzero elements are computed. For comparative performance analysis, we used the reference library SuperLU. Testing was performed on synthetically generated matrices which replicate the conditions of the real-world matrices. SparseLU is able to reach a mean speedup of 29× compared to SuperLU.

Original language	English
Title of host publication	Proceedings of IA3 2022
Subtitle of host publication	Workshop on Irregular Applications: Architectures and Algorithms, Held in conjunction with SC 2022: The International Conference for High Performance Computing, Networking, Storage and Analysis
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	25-31
Number of pages	7
ISBN (Electronic)	9781665475068
DOIs	https://doi.org/10.1109/IA356718.2022.00010
State	Published - 2022
Event	2022 Workshop on Irregular Applications: Architectures and Algorithms, IA3 2022 - Dallas, United States Duration: Nov 13 2022 → Nov 18 2022

Publication series

Name	Proceedings of IA3 2022: Workshop on Irregular Applications: Architectures and Algorithms, Held in conjunction with SC 2022: The International Conference for High Performance Computing, Networking, Storage and Analysis

Conference

Conference	2022 Workshop on Irregular Applications: Architectures and Algorithms, IA3 2022
Country/Territory	United States
City	Dallas
Period	11/13/22 → 11/18/22

Funding

Notice: This manuscript has been authored by UT-Battelle, LLC under Contract No. DE-AC05-00OR22725 with the U.S. Department of Energy. The publisher, by accepting the article for publication, acknowledges that the U.S. Government retains a non-exclusive, paid up, irrevocable, worldwide license to publish or reproduce the published form of the manuscript, or allow others to do so, for U.S. Government purposes. The DOE will provide public access to these results in accordance with the DOE Public Access Plan (http://energy.gov/downloads/doe-public-access-plan). ACKNOWLEDGMENTS Notice: This manuscript has been authored by UT-Battelle, LLC under Contract No. DE-AC05-00OR22725 with the U.S. Department of Energy. The publisher, by accepting the article for publication, acknowledges that the U.S. Government retains a non-exclusive, paid up, irrevocable, world-wide license to publish or reproduce the published form of the manuscript, or allow others to do so, for U.S. Government purposes. The DOE will provide public access to these results in accordance with the DOE Public Access Plan (http://energy.gov/downloads/doe-public-access-plan).

Keywords

LU factorization
OpenMP
Sparse Linear Algebra

Access to Document

10.1109/IA356718.2022.00010

Cite this

Valero-Lara, P., Greenwalt, C., & Vetter, J. S. (2022). SparseLU, A Novel Algorithm and Math Library for Sparse LU Factorization. In Proceedings of IA3 2022: Workshop on Irregular Applications: Architectures and Algorithms, Held in conjunction with SC 2022: The International Conference for High Performance Computing, Networking, Storage and Analysis (pp. 25-31). (Proceedings of IA3 2022: Workshop on Irregular Applications: Architectures and Algorithms, Held in conjunction with SC 2022: The International Conference for High Performance Computing, Networking, Storage and Analysis). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/IA356718.2022.00010

Valero-Lara, Pedro ; Greenwalt, Cameron ; Vetter, Jeffrey S. / SparseLU, A Novel Algorithm and Math Library for Sparse LU Factorization. Proceedings of IA3 2022: Workshop on Irregular Applications: Architectures and Algorithms, Held in conjunction with SC 2022: The International Conference for High Performance Computing, Networking, Storage and Analysis. Institute of Electrical and Electronics Engineers Inc., 2022. pp. 25-31 (Proceedings of IA3 2022: Workshop on Irregular Applications: Architectures and Algorithms, Held in conjunction with SC 2022: The International Conference for High Performance Computing, Networking, Storage and Analysis).

@inproceedings{f5699b19cf384477b4e55bd4ec70722b,

title = "SparseLU, A Novel Algorithm and Math Library for Sparse LU Factorization",

abstract = "Decomposing sparse matrices into lower and upper triangular matrices (sparse LU factorization) is a key operation in many computational scientific applications. We developed SparseLU, a sparse linear algebra library that implements a new algorithm for LU factorization on general sparse matrices. The new algorithm divides the input matrix into tiles to which OpenMP tasks are created for factorization computation, where only tiles that contain nonzero elements are computed. For comparative performance analysis, we used the reference library SuperLU. Testing was performed on synthetically generated matrices which replicate the conditions of the real-world matrices. SparseLU is able to reach a mean speedup of 29× compared to SuperLU.",

keywords = "LU factorization, OpenMP, Sparse Linear Algebra",

author = "Pedro Valero-Lara and Cameron Greenwalt and Vetter, {Jeffrey S.}",

note = "Publisher Copyright: {\textcopyright} 2022 IEEE.; 2022 Workshop on Irregular Applications: Architectures and Algorithms, IA3 2022 ; Conference date: 13-11-2022 Through 18-11-2022",

year = "2022",

doi = "10.1109/IA356718.2022.00010",

language = "English",

series = "Proceedings of IA3 2022: Workshop on Irregular Applications: Architectures and Algorithms, Held in conjunction with SC 2022: The International Conference for High Performance Computing, Networking, Storage and Analysis",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "25--31",

booktitle = "Proceedings of IA3 2022",

}

Valero-Lara, P, Greenwalt, C & Vetter, JS 2022, SparseLU, A Novel Algorithm and Math Library for Sparse LU Factorization. in Proceedings of IA3 2022: Workshop on Irregular Applications: Architectures and Algorithms, Held in conjunction with SC 2022: The International Conference for High Performance Computing, Networking, Storage and Analysis. Proceedings of IA3 2022: Workshop on Irregular Applications: Architectures and Algorithms, Held in conjunction with SC 2022: The International Conference for High Performance Computing, Networking, Storage and Analysis, Institute of Electrical and Electronics Engineers Inc., pp. 25-31, 2022 Workshop on Irregular Applications: Architectures and Algorithms, IA3 2022, Dallas, United States, 11/13/22. https://doi.org/10.1109/IA356718.2022.00010

SparseLU, A Novel Algorithm and Math Library for Sparse LU Factorization. / Valero-Lara, Pedro; Greenwalt, Cameron; Vetter, Jeffrey S.
Proceedings of IA3 2022: Workshop on Irregular Applications: Architectures and Algorithms, Held in conjunction with SC 2022: The International Conference for High Performance Computing, Networking, Storage and Analysis. Institute of Electrical and Electronics Engineers Inc., 2022. p. 25-31 (Proceedings of IA3 2022: Workshop on Irregular Applications: Architectures and Algorithms, Held in conjunction with SC 2022: The International Conference for High Performance Computing, Networking, Storage and Analysis).

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

TY - GEN

T1 - SparseLU, A Novel Algorithm and Math Library for Sparse LU Factorization

AU - Valero-Lara, Pedro

AU - Greenwalt, Cameron

AU - Vetter, Jeffrey S.

PY - 2022

Y1 - 2022

N2 - Decomposing sparse matrices into lower and upper triangular matrices (sparse LU factorization) is a key operation in many computational scientific applications. We developed SparseLU, a sparse linear algebra library that implements a new algorithm for LU factorization on general sparse matrices. The new algorithm divides the input matrix into tiles to which OpenMP tasks are created for factorization computation, where only tiles that contain nonzero elements are computed. For comparative performance analysis, we used the reference library SuperLU. Testing was performed on synthetically generated matrices which replicate the conditions of the real-world matrices. SparseLU is able to reach a mean speedup of 29× compared to SuperLU.

AB - Decomposing sparse matrices into lower and upper triangular matrices (sparse LU factorization) is a key operation in many computational scientific applications. We developed SparseLU, a sparse linear algebra library that implements a new algorithm for LU factorization on general sparse matrices. The new algorithm divides the input matrix into tiles to which OpenMP tasks are created for factorization computation, where only tiles that contain nonzero elements are computed. For comparative performance analysis, we used the reference library SuperLU. Testing was performed on synthetically generated matrices which replicate the conditions of the real-world matrices. SparseLU is able to reach a mean speedup of 29× compared to SuperLU.

KW - LU factorization

KW - OpenMP

KW - Sparse Linear Algebra

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

U2 - 10.1109/IA356718.2022.00010

DO - 10.1109/IA356718.2022.00010

M3 - Conference contribution

AN - SCOPUS:85148087274

T3 - Proceedings of IA3 2022: Workshop on Irregular Applications: Architectures and Algorithms, Held in conjunction with SC 2022: The International Conference for High Performance Computing, Networking, Storage and Analysis

SP - 25

EP - 31

BT - Proceedings of IA3 2022

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2022 Workshop on Irregular Applications: Architectures and Algorithms, IA3 2022

Y2 - 13 November 2022 through 18 November 2022

ER -

Valero-Lara P, Greenwalt C, Vetter JS. SparseLU, A Novel Algorithm and Math Library for Sparse LU Factorization. In Proceedings of IA3 2022: Workshop on Irregular Applications: Architectures and Algorithms, Held in conjunction with SC 2022: The International Conference for High Performance Computing, Networking, Storage and Analysis. Institute of Electrical and Electronics Engineers Inc. 2022. p. 25-31. (Proceedings of IA3 2022: Workshop on Irregular Applications: Architectures and Algorithms, Held in conjunction with SC 2022: The International Conference for High Performance Computing, Networking, Storage and Analysis). doi: 10.1109/IA356718.2022.00010

SparseLU, A Novel Algorithm and Math Library for Sparse LU Factorization

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this