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.
Reviewer: Miroslav Tůma (Praha)
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 |
Keywords:
sparse linear solver; symmetric indefinite systems; parallel computation; approximation algorithm; auction algorithm; matching; sparse symmetric matrix; scaling; reordering; numerical examples; Hungarian algorithmReferences:
| [1] | HoggJD, ScottJA. The effects of scalings on the performance of a sparse symmetric indefinite solver.Technical Report RAL‐TR‐2008‐007, Rutherford Appleton Laboratory, 2008. |
| [2] | HoggJD, ScottJA. Pivoting strategies for tough sparse indefinite systems. ACM Transactions on Mathematical Software2013; 40:4:1-4:19. · Zbl 1295.65054 |
| [3] | DuffIS, KosterJ. On algorithms for permuting large entries to the diagonal of a sparse matrix. SIAM Journal Matrix Analysis and Applications2001; 22(4):973-996. · Zbl 0979.05087 |
| [4] | HoggJD, ScottJA. Optimal weighted matchings for rank‐deficient sparse matrices. SIAM Journal Matrix Analysis and Applications2013; 34:1431-1447. · Zbl 1287.05116 |
| [5] | KuhnHW. The Hungarian method for the assignment problem. Naval Research Logistics Quarterly1955; 2(1- 2):83-97. · Zbl 0143.41905 |
| [6] | DuffIS, PraletS. Strategies for scaling and pivoting for sparse symmetric indefinite problems. SIAM Journal Matrix Analysis and Applications2005; 27:313-340. · Zbl 1092.65037 |
| [7] | HagemannM, SchenkO. Weighted matchings for preconditioning symmetric indefinite linear systems. SIAM Journal Scientific Computing2006; 28:403-420. · Zbl 1111.65042 |
| [8] | SchenkO, GärtnerK. On fast factorization pivoting methods for symmetric indefinite systems. Electronic Transactions on Numerical Analysis2006; 23:158-179. · Zbl 1112.65022 |
| [9] | SchenkO, WächterA, HagemannM. Matching‐based preprocessing algorithms to the solution of saddle‐point problems in large‐scale nonconvex interior‐point optimization. Computer Optimization and Applications2007; 36:321-341. · Zbl 1146.90055 |
| [10] | AzadA, HalappanavarM, RajamanickamS, BomanEG, KhanA, PothenA. Multithreaded algorithms for maximum matching in bipartite graphs. International Parallel and Distributed Processing Symposium, IEEE Computer Society, Shanghai, China, 2012; 860-872. |
| [11] | DeveciM, KayaK, UçarB, ÇatalyürekUV, GPU accelerated maximum cardinality matching algorithms for bipartite graphs. In Euro‐Par 2013 Parallel Processing, Lecture Notes in Computer Science, vol. 8097, WolfF (ed.), MohrB (ed.), MeyD (ed.). Springer, Aachen, Germany2013; 850-861. |
| [12] | HalappanavarM, FeoJ, VillaO, TumeoA, PothenA. Approximate weighted matching on emerging manycore and multithreaded architectures. International Journal of High Performance Computing Applications2012; 26(4):413-430. |
| [13] | SatheM, SchenkO, BurkhartH. An auction‐based weighted matching implementation on massively parallel architectures. Parallel Computing2012; 38(12):595-614. |
| [14] | BertsekasDP. A distributed asynchronous relaxation algorithm for the assignment problem. 24th IEEE Conference on Decision and Control, 24, IEEE, Fort Lauderdale, Florida, USA, 1985; 1703-1704. |
| [15] | BertsekasDP, CastañonDA. Parallel synchronous and asynchronous implementations of the auction algorithm. Parallel Computing1991; 17(6- 7):707-732. · Zbl 0737.68036 |
| [16] | BušL, TvrdíkP. Towards auction algorithms for large dense assignment problems. Computer Optimization and Applications2009; 43(3):411-436. · Zbl 1170.90463 |
| [17] | RiedyJ. Making static pivoting scalable and dependable. Ph.D. Thesis, EECS Department, University of California, Berkeley. UCB/EECS‐2010‐172, 2010. |
| [18] | MehlhornK, NäherSt. The LEDA Platform of Combinatorial and Geometric Computing. Cambridge University Press, Cambridge, UK, 1999. · Zbl 0976.68156 |
| [19] | AvisD. A survey of heuristics for the weighted matching problem. Networks1983; 13(4):475-493. · Zbl 0532.90090 |
| [20] | PreisR. Linear time \(\frac{ 1}{ 2} \) ‐ approximation algorithm for maximum weighted matching in general graphs. 16th Symposium on Theoretical Aspects of Computer Science (STACS), Trier, Germany, 1999; 259-269. · Zbl 0927.05075 |
| [21] | HoggJD, ScottJA. On the efficient scaling of sparse symmetric matrices using an auction algorithm. RAL‐P‐2014‐002, Rutherford Appleton Laboratory, 2014. |
| [22] | DavisTA, HuY. The University of Florida sparse matrix collection. ACM Transactions on Mathematical Software2011; 38(1):1:1-1:25. · Zbl 1365.65123 |
| [23] | HoggJD, ScottJA. HSL_MA97: a bit‐compatible multifrontal code for sparse symmetric systems. RAL‐TR‐2011‐024, Rutherford Appleton Laboratory, 2011. |
| [24] | HoggJD, ScottJA. New parallel sparse direct solvers for multicore architectures. Algorithms2013; 6:702-725. Special issue: Algorithms for Multi Core Parallel Computation. · Zbl 1461.65063 |
| [25] | PothenA, DobrianF, HalappanavarM. Matchbox, A Library of Graph Matching Algorithms. (Available from: http://www.cs.odu.edu/mhalappa/matching/), Development version, June 2013. |
| [26] | LiXS, DemmelJW. SuperLU_DIST: a scalable distributed‐memory sparse direct solver or unsymmetric linear systems. ACM Transactions on Mathematical Software2003; 29(2):110-140. · Zbl 1068.90591 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
