ePubs

The open archive for STFC research publications

Full Record Details

Persistent URL http://purl.org/net/epubs/work/11539865
Record Status Checked
Record Id 11539865
Title On the efficient scaling of sparse symmetric matrices using an auction algorithm
Contributors
Abstract The well-known HSL software package MC64 is a powerful tool for scaling sparse matrices prior to the application of direct and iterative methods to solve linear systems Ax = b. It computes a scaling by using the Hungarian algorithm to solve the maximum weight maximum cardinality matching problem. However, with the parallelization of the factorization and solve phases of direct solvers, the serial Hungarian algorithm can represent an unacceptably large proportion of the total solution time for such solvers. Recently, auction algorithms and approximation algorithms have been suggested as alternatives for achieving near-optimal solutions for the maximum weight maximum cardinality matching problem. In this paper, the efficacy of auction and approximation algorithms as replacements for the Hungarian algorithm is assessed in the context of sparse symmetric direct solvers when used on problems arising from a range of practical applications. High cardinality sub-optimal matchings are shown to be as effective as optimal matchings for the purposes of scaling. However, a higher degree of optimality is required to effectively use matching-based ordering techniques. The auction algorithm is demonstrated to be capable of finding such matchings significantly faster than the Hungarian algorithm, but the 1/2-approximation matching fails to consistently achieve a sufficient cardinality.
Organisation STFC , SCI-COMP , SCI-COMP-CM
Keywords
Funding Information
Related Research Object(s):
Licence Information:
Language English (EN)
Type Details URI(s) Local file(s) Year
Report RAL Preprints RAL-P-2014-002. STFC, 2014. RAL-P-2014-002.pdf 2014