×

zbMATH — the first resource for mathematics

On the use of suboptimal matchings for scaling and ordering sparse symmetric matrices. (English) Zbl 1363.65039
The paper discusses preprocessing techniques for solving systems of linear equations with sparse symmetric matrices. In particular, the authors discuss reordering techniques based on bipartite graph matchings and related matrix scalings. While traditional techniques of this kind are based on the Hungarian algorithm, here the auction algorithm as well as approximation algorithms are discussed. The authors are interested most of all in their use for parallel direct sparse solvers. The paper contains a careful experimental study on the effectiveness of the considered reordering algorithms and scalings. They show that both the serial and parallel versions of the auction algorithm are more straightforward than the Hungarian algorithm-based strategies used in the HSL code MC64 and plan to include the new developed implementations in mathematical software libraries.

MSC:
65F05 Direct numerical methods for linear systems and matrix inversion
65F35 Numerical computation of matrix norms, conditioning, scaling
65Y05 Parallel numerical computation
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
65F50 Computational methods for sparse matrices
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Hogg JD Scott JA The effects of scalings on the performance of a sparse symmetric indefinite solver 2008
[2] Hogg, Pivoting strategies for tough sparse indefinite systems, ACM Transactions on Mathematical Software 40 pp 4:1– (2013) · Zbl 1295.65054 · doi:10.1145/2513109.2513113
[3] Duff, On algorithms for permuting large entries to the diagonal of a sparse matrix, SIAM Journal Matrix Analysis and Applications 22 (4) pp 973– (2001) · Zbl 0979.05087 · doi:10.1137/S0895479899358443
[4] Hogg, Optimal weighted matchings for rank-deficient sparse matrices, SIAM Journal Matrix Analysis and Applications 34 pp 1431– (2013) · Zbl 1287.05116 · doi:10.1137/120884262
[5] Kuhn, The Hungarian method for the assignment problem, Naval Research Logistics Quarterly 2 (1- 2) pp 83– (1955) · Zbl 0143.41905 · doi:10.1002/nav.3800020109
[6] Duff, Strategies for scaling and pivoting for sparse symmetric indefinite problems, SIAM Journal Matrix Analysis and Applications 27 pp 313– (2005) · Zbl 1092.65037 · doi:10.1137/04061043X
[7] Hagemann, Weighted matchings for preconditioning symmetric indefinite linear systems, SIAM Journal Scientific Computing 28 pp 403– (2006) · Zbl 1111.65042 · doi:10.1137/040615614
[8] Schenk, On fast factorization pivoting methods for symmetric indefinite systems, Electronic Transactions on Numerical Analysis 23 pp 158– (2006) · Zbl 1112.65022
[9] Schenk, Matching-based preprocessing algorithms to the solution of saddle-point problems in large-scale nonconvex interior-point optimization, Computer Optimization and Applications 36 pp 321– (2007) · Zbl 1146.90055 · doi:10.1007/s10589-006-9003-y
[10] Azad A Halappanavar M Rajamanickam S Boman EG Khan A Pothen A Multithreaded algorithms for maximum matching in bipartite graphs Shanghai, China 2012 860 872
[11] Deveci, Euro-Par 2013 Parallel Processing, Lecture Notes in Computer Science pp 850– (2013) · Zbl 06226448 · doi:10.1007/978-3-642-40047-6_84
[12] Halappanavar, Approximate weighted matching on emerging manycore and multithreaded architectures, International Journal of High Performance Computing Applications 26 (4) pp 413– (2012) · doi:10.1177/1094342012452893
[13] Sathe, An auction-based weighted matching implementation on massively parallel architectures, Parallel Computing 38 (12) pp 595– (2012) · doi:10.1016/j.parco.2012.09.001
[14] Bertsekas DP A distributed asynchronous relaxation algorithm for the assignment problem 24 Fort Lauderdale, Florida, USA 1985 1703 1704
[15] Bertsekas, Parallel synchronous and asynchronous implementations of the auction algorithm, Parallel Computing 17 (6- 7) pp 707– (1991) · Zbl 0737.68036 · doi:10.1016/S0167-8191(05)80062-6
[16] Buš, Towards auction algorithms for large dense assignment problems, Computer Optimization and Applications 43 (3) pp 411– (2009) · Zbl 1170.90463 · doi:10.1007/s10589-007-9146-5
[17] Riedy J Making static pivoting scalable and dependable 2010
[18] Mehlhorn, The LEDA Platform of Combinatorial and Geometric Computing (1999) · Zbl 0976.68156
[19] Avis, A survey of heuristics for the weighted matching problem, Networks 13 (4) pp 475– (1983) · Zbl 0532.90090 · doi:10.1002/net.3230130404
[20] Preis R Linear time 1 2 - approximation algorithm for maximum weighted matching in general graphs Trier, Germany 1999 259 269
[21] Hogg JD Scott JA On the efficient scaling of sparse symmetric matrices using an auction algorithm 2014
[22] Davis, The University of Florida sparse matrix collection, ACM Transactions on Mathematical Software 38 (1) pp 1:1– (2011) · Zbl 1365.65123 · doi:10.1145/2049662.2049663
[23] Hogg JD Scott JA HSL_MA97: a bit-compatible multifrontal code for sparse symmetric systems 2011
[24] Hogg, New parallel sparse direct solvers for multicore architectures, Algorithms 6 pp 702– (2013) · doi:10.3390/a6040702
[25] Pothen A Dobrian F Halappanavar M Matchbox, A Library of Graph Matching Algorithms http://www.cs.odu.edu/mhalappa/matching/ 2013
[26] Li, SuperLU_DIST: a scalable distributed-memory sparse direct solver or unsymmetric linear systems, ACM Transactions on Mathematical Software 29 (2) pp 110– (2003) · Zbl 1068.90591 · doi:10.1145/779359.779361
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.