×

New parallel sparse direct solvers for multicore architectures. (English) Zbl 1461.65063

Summary: At the heart of many computations in science and engineering lies the need to efficiently and accurately solve large sparse linear systems of equations. Direct methods are frequently the method of choice because of their robustness, accuracy and potential for use as black-box solvers. In the last few years, there have been many new developments, and a number of new modern parallel general-purpose sparse solvers have been written for inclusion within the HSL mathematical software library. In this paper, we introduce and briefly review these solvers for symmetric sparse systems. We describe the algorithms used, highlight key features (including bit-compatibility and out-of-core working) and then, using problems arising from a range of practical applications, we illustrate and compare their performances. We demonstrate that modern direct solvers are able to accurately solve systems of order \(10^6\) in less than 3 minutes on a 16-core machine.

MSC:

65F50 Computational methods for sparse matrices
65Y05 Parallel numerical computation
65F05 Direct numerical methods for linear systems and matrix inversion
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A collection of Fortran codes for large-scale scientific computation, 2013; ; .
[2] Reid, J.; Scott, J.; An out-of-core sparse Cholesky solver; ACM Trans. Math. Softw.: 2009; Volume 36 . · Zbl 1364.65071
[3] Hogg, J.; Scott, J.; ; An Indefinite Sparse Direct Solver for Large Problems on Multicore Machines: Didcot, UK 2010; .
[4] Hogg, J.; Reid, J.; Scott, J.; Design of a multicore sparse Cholesky factorization using DAGs; SIAM J. Sci. Comput.: 2010; Volume 32 ,3627-3649. · Zbl 1221.65088
[5] Hogg, J.; Scott, J.; ; HSL_MA97: A Bit-Compatible Multifrontal Code for Sparse Symmetric Systems: Didcot, UK 2011; .
[6] Davis, T.; ; Direct Methods for Sparse Linear Systems: Philadelphia, PA, USA 2006; . · Zbl 1119.65021
[7] Duff, I.; Erisman, A.; Reid, J.; ; Direct Methods for Sparse Matrices: Oxford, UK 1989; . · Zbl 0666.65024
[8] Gould, N.; Hu, Y.; Scott, J.; A numerical evaluation of sparse direct symmetric solvers for the solution of large sparse, symmetric linear systems of equations; ACM Trans. Math. Softw.: 2007; Volume 33 . · Zbl 1365.65129
[9] Golub, G.; van Loan, C.; ; Matrix Computations: Baltimore, MD, USA 1996; . · Zbl 0865.65009
[10] Tinney, W.; Walker, J.; Direct solutions of sparse network equations by optimally ordered triangular factorization; Proc. IEEE: 1967; Volume 55 ,1801-1809.
[11] Amestoy, P.; Davis, T.; Duff, I.; An approximate minimum degree ordering algorithm; SIAM J. Matrix Anal. Appl.: 1996; Volume 17 ,886-905. · Zbl 0861.65021
[12] Amestoy, P.; Davis, T.; Duff, I.; Algorithm 837: AMD, an approximate minimum degree ordering algorithm; ACM Trans. Math. Softw.: 2004; Volume 30 ,381-388. · Zbl 1070.65534
[13] Liu, J.; Modification of the minimum-degree algorithm by multiple elimination; ACM Trans. Math. Softw.: 1985; Volume 11 ,141-153. · Zbl 0568.65015
[14] George, A.; Nested dissection of a regular finite-element mesh; SIAM J. Numer. Anal.: 1973; Volume 10 ,345-363. · Zbl 0259.65087
[15] Gould, N.; Scott, J.; A numerical evaluation of HSL packages for the direct solution of large sparse, symmetric linear systems of equations; ACM Trans. Math. Softw.: 2004; Volume 30 ,300-325. · Zbl 1073.65022
[16] Karypis, G.; Kumar, V.; METIS: A software package for partitioning unstructured graphs, partitioning meshes and computing fill-reducing orderings of sparse matrices—Version 4.0, 1998; ; .
[17] Karypis, G.; Kumar, V.; A fast and high quality multilevel scheme for partitioning irregular graphs; SIAM J. Sci. Comput.: 1999; Volume 20 ,359-392. · Zbl 0915.68129
[18] Pellegrini, F.; ; SCOTCH 5.1 User’s Guide: Frace 2008; .
[19] Boman, E.; Devine, K.; Fisk, L.A.; Heaphy, R.; Hendrickson, B.; Vaughan, C.; Catalyurek, U.; Bozdag, D.; Mitchell, W.; Teresco, J.; ; Zoltan 3.0: Parallel Partitioning, Load-balancing, and Data Management Services; User’s Guide: Albuquerque, NM, USA 2007; .
[20] Duff, I.; Scott, J.; ; Towards an Automatic Ordering for a Symmetric Sparse Direct Solver: Didcot, UK 2005; .
[21] Liu, J.; The role of elimination trees in sparse factorization; SIAM J. Matrix Anal. Appl.: 1990; Volume 11 ,134-172. · Zbl 0697.65013
[22] Dongarra, J.; Croz, J.D.; Hammarling, S.; Duff, I.S.; A set of level 3 basic linear algebra subprograms; ACM Trans. Math. Softw.: 1990; Volume 16 ,1-17. · Zbl 0900.65115
[23] Ashcraft, C.; Grimes, R.G.; The influence of relaxed supernode partitions on the multifrontal method; ACM Trans. Math. Softw.: 1989; Volume 15 ,291-309. · Zbl 0900.65061
[24] Hogg, J.; Scott, J.; ; A Modern Analyse Phase for Sparse Tree-Based Direct Methods: Didcot, UK 2010; .
[25] Duff, I.; Reid, J.; The multifrontal solution of indefinite sparse symmetric linear systems; ACM Trans. Math. Softw.: 1983; Volume 9 ,302-325. · Zbl 0515.65022
[26] Liu, J.; The multifrontal method for sparse matrix solution: Theory and practice; SIAM Rev.: 1992; Volume 34 ,82-109. · Zbl 0919.65019
[27] Ashcraft, C.; Grimes, R.G.; Lewis, J.G.; Accurate symmetric indefinite linear equation solvers; SIAM J. Matrix Anal. Appl.: 1999; Volume 20 ,513-561. · Zbl 0923.65010
[28] Bunch, J.R.; Kaufman, L.; Some stable methods for calculating inertia and solving symmetric linear systems; Math. Comput.: 1977; Volume 31 ,163-179. · Zbl 0355.65023
[29] Duff, I.S.; Gould, N.I.M.; Reid, J.K.; Scott, J.A.; Turner, K.; Factorization of sparse symmetric indefinite matrices; IMA J. Numer. Anal.: 1991; Volume 11 ,181-204. · Zbl 0739.65018
[30] Hogg, J.; Scott, J.; Pivoting strategies for tough sparse indefinite systems; ACM Trans. Math. Softw.: 2014; Volume 40 . · Zbl 1295.65054
[31] Hogg, J.; Scott, J.; ; Compressed Threshold Pivoting for Sparse Symmetric Indefinite Systems: Didcot, UK 2013; . · Zbl 1301.65020
[32] Hogg, J.; Scott, J.; ; The Effects of Scalings on the Performance of a Sparse Symmetric Indefinite Solver: Didcot, UK 2008; .
[33] Hogg, J.; Scott, J.; Optimal weighted matchings for rank-deficient sparse matrices; SIAM J. Matrix Anal. Appl.: 2013; Volume 34 ,1431-1447. · Zbl 1287.05116
[34] Hogg, J.; Scott, J.; ; Achieving Bit Compatibility in Sparse Direct Solvers: Didcot, UK 2012; .
[35] Buttari, A.; Dongarra, J.; Kurzak, J.; Langou, J.; Luszczek, P.; Tomov, S.; The Impact of Multicore on Math Software; Proceedings of Workshop on State-of-the-Art in Scientific and Parallel Computing (PARA’06): ; . · Zbl 1197.65240
[36] Buttari, A.; Langou, J.; Kurzak, J.; Dongarra, J.; ; A Class of Parallel Tiled Linear Algebra Algorithms for Multicore Architectures: Knoxville, TN, USA 2007; .
[37] Anderson, E.; Bai, Z.; Bischof, C.; Blackford, S.; Demmel, J.; Dongarra, J.; Du Croz, J.; Greenbaum, A.; Hammarling, S.; McKenney, A.; ; LAPACK Users’ Guide: Philadelphia, PA, USA 1999; . · Zbl 0934.65030
[38] Reid, J.; Scott, J.; Partial Factorization of a Dense Symmetric Indefinite Matrix; ACM Trans. Math. Softw.: 2011; Volume 38 . · Zbl 1365.65073
[39] Reid, J.; Scott, J.; Algorithm 891: A Fortran virtual memory system; ACM Trans. Math. Softw.: 2009; Volume 36 ,1-12.
[40] Davis, T.; Hu, Y.; The University of Florida sparse matrix collection; ACM Trans. Math. Softw.: 2011; Volume 38 . · Zbl 1365.65123
[41] Ruiz, D.; Uçar, B.; ; A Symmetry Preserving Algorithm of Matrix Scaling: Paris, France 2011; . · Zbl 1329.65089
[42] Duff, I.S.; MA57—a new code for the solution of sparse symmetric definite and indefinite systems; ACM Trans. Math. Softw.: 2004; Volume 30 ,118-154. · Zbl 1070.65525
[43] Hogg, J.; Scott, J.; A fast and robust mixed precision solver for the solution of sparse symmetric linear systems; ACM Trans. Math. Softw.: 2010; Volume 37 . · Zbl 1364.65070
[44] Schenk, O.; Gärtner, K.; Solving unsymmetric sparse systems of linear equations with PARDISO; J. Future Generation Comput. Syst.: 2004; Volume 20 ,475-487. · Zbl 1062.65035
[45] Schenk, O.; Gärtner, K.; On fast factorization pivoting methods for symmetric indefinite systems; Electron. Trans. Numer. Anal.: 2006; Volume 23 ,158-179. · Zbl 1112.65022
[46] Amestoy, P.; Duff, I.; L’Excellent, J.Y.; Koster, J.; A fully asynchronous multifrontal solver using distributed dynamic scheduling; SIAM J. Matrix Anal. Appl.: 2001; Volume 23 ,15-41. · Zbl 0992.65018
[47] Hénon, P.; Ramet, P.; Roman, J.; PaStiX: A high-performance parallel direct solver for sparse symmetric definite systems; Parallel Comput.: 2002; Volume 28 ,301-321. · Zbl 0984.68208
[48] Gupta, A.; Joshi, M.; Kumar, V.; ; WSMP: A High-Performance Serial and Parallel Sparse Linear Solver: 2001; .
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.