ePubs
The open archive for STFC research publications
Home
About ePubs
Content Policies
News
Help
Privacy/Cookies
Suggest an Enhancement
Contact ePubs
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
Contributors
O Kaya
,
E Kayaaslan
,
B Ucar
,
IS Duff (STFC Rutherford Appleton Lab.)
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
Showing record 1 of 1
Recent Additions
Browse Organisations
Browse Journals/Series
Login to add & manage publications and access information for OA publishing
Username:
Password:
Useful Links
Chadwick & RAL Libraries
SHERPA FACT
SHERPA RoMEO
SHERPA JULIET
Journal Checker Tool
Google Scholar