The open archive for STFC research publications

Full Record Details

Persistent URL http://purl.org/net/epubs/work/12136109
Record Status Checked
Record Id 12136109
Title Fill-in reduction in sparse matrix factorizations using hypergraphs
Abstract We discuss partitioning methods using hypergraphs to produce fill-reducing orderings of sparse matrices for Cholesky, LU and QR factorizations. For the Cholesky factorization, we investigate a recent result on pattern-wise decomposition of sparse matrices, generalize the result, and develop algorithmic tools to obtain more effective ordering methods. The generalized results help us to develop fill-reducing orderings for LU factorization in a similar way to those for Cholesky factorization, without symmetrizing the given matrix A as jAj + jAT j or jAT jjAj. For the QR factorization, we adopt a recently proposed technique to use hypergraph models in a fairly standard manner. The method again does not form the possibly much denser matrix jAT jjAj. We also discuss alternatives for LU and QR factorization where the symmetrized matrix can be used. We provide comparisons with the most common alternatives in all three cases.
Organisation STFC , SCI-COMP , SCI-COMP-CM
Keywords hypergraph partitioning; sparse matrices; direct methods; , fill-reducing orderings; Cholesky factorization; LU factorization; QR factorization;
Funding Information
Related Research Object(s):
Licence Information:
Language English (EN)
Type Details URI(s) Local file(s) Year
Preprint RAL Preprints, Numer Linear Algebr 2014. RAL-P-2014-004.pdf 2014