Workshops Archive

Performance-Portable Symbolic Factorization through Common Graph Operations

Workshop: IA^3 2025 — 15th Workshop on Irregular Applications: Architectures and Algorithms

Authors: Oguz Selvitopi, Xiaoye S. Li, and Aydin Buluc (Lawrence Berkeley National Laboratory (LBNL))

Abstract: In lower-upper (LU) factorization in the form A=LU, symbolic factorization is a pre-processing stage performed to discover the sparsity structure of the factors. A is usually not equal to L+U due to fill-ins (the nonzeros that do not appear in A but element of L or U) introduced in factorization. Symbolic factorization can be performed with A's pattern by utilizing the corresponding graph. In this work, we assess the viability of utilizing GraphBLAS for symbolic factorization. GraphBLAS defines a standard way to express operations on graphs in the language of linear algebra. We express edge-based and path-based symbolic factorization using graph operations and investigate utilization of masks and elimination trees. Our goal is to obtain a performant symbolic factorization, which can be used in a portable manner on any hardware GraphBLAS standard is realized. We demonstrate our approach with various sparse matrices on multi-core and many-core architectures.

Back to IA^3 2025 — 15th Workshop on Irregular Applications: Architectures and Algorithms Archive Listing Back to Full Workshop Archive Listing