{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T05:55:43Z","timestamp":1774590943919,"version":"3.50.1"},"reference-count":48,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2013,11,1]],"date-time":"2013-11-01T00:00:00Z","timestamp":1383264000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>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 106 in less than 3 minutes on a 16-core machine.<\/jats:p>","DOI":"10.3390\/a6040702","type":"journal-article","created":{"date-parts":[[2013,11,1]],"date-time":"2013-11-01T12:41:02Z","timestamp":1383309662000},"page":"702-725","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":23,"title":["New Parallel Sparse Direct Solvers for Multicore Architectures"],"prefix":"10.3390","volume":"6","author":[{"given":"Jonathan","family":"Hogg","sequence":"first","affiliation":[{"name":"Scientific Computing Department, STFC Rutherford Appleton Laboratory, Harwell Oxford, OX11 0QX, UK"}]},{"given":"Jennifer","family":"Scott","sequence":"additional","affiliation":[{"name":"Scientific Computing Department, STFC Rutherford Appleton Laboratory, Harwell Oxford, OX11 0QX, UK"}]}],"member":"1968","published-online":{"date-parts":[[2013,11,1]]},"reference":[{"key":"ref_1","unstructured":"HSL A collection of Fortran codes for large-scale scientific computation, 2013. Available online: http:\/\/www.hsl.rl.ac.uk\/."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Reid, J., and Scott, J. (2009). An out-of-core sparse Cholesky solver. ACM Trans. Math. Softw., 36.","DOI":"10.1145\/1499096.1499098"},{"key":"ref_3","unstructured":"Hogg, J., and Scott, J. (2010). An Indefinite Sparse Direct Solver for Large Problems on Multicore Machines, Rutherford Appleton Laboratory. Technical Report RAL-TR-2010-011."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"3627","DOI":"10.1137\/090757216","article-title":"Design of a multicore sparse Cholesky factorization using DAGs","volume":"32","author":"Hogg","year":"2010","journal-title":"SIAM J. Sci. Comput."},{"key":"ref_5","unstructured":"Hogg, J., and Scott, J. (2011). HSL_MA97: A Bit-Compatible Multifrontal Code for Sparse Symmetric Systems, Rutherford Appleton Laboratory. Technical Report RAL-TR-2011-024."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Davis, T. (2006). Direct Methods for Sparse Linear Systems, SIAM.","DOI":"10.1137\/1.9780898718881"},{"key":"ref_7","unstructured":"Duff, I., Erisman, A., and Reid, J. (1989). Direct Methods for Sparse Matrices, Oxford University Press."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Gould, N., Hu, Y., and Scott, J. (2007). A numerical evaluation of sparse direct symmetric solvers for the solution of large sparse, symmetric linear systems of equations. ACM Trans. Math. Softw., 33.","DOI":"10.1145\/1236463.1236465"},{"key":"ref_9","unstructured":"Golub, G., and van Loan, C. (1996). Matrix Computations, The Johns Hopkins University Press. [3rd ed.]."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1801","DOI":"10.1109\/PROC.1967.6011","article-title":"Direct solutions of sparse network equations by optimally ordered triangular factorization","volume":"55","author":"Tinney","year":"1967","journal-title":"Proc. IEEE"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"886","DOI":"10.1137\/S0895479894278952","article-title":"An approximate minimum degree ordering algorithm","volume":"17","author":"Amestoy","year":"1996","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1145\/1024074.1024081","article-title":"Algorithm 837: AMD, an approximate minimum degree ordering algorithm","volume":"30","author":"Amestoy","year":"2004","journal-title":"ACM Trans. Math. Softw."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1145\/214392.214398","article-title":"Modification of the minimum-degree algorithm by multiple elimination","volume":"11","author":"Liu","year":"1985","journal-title":"ACM Trans. Math. Softw."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1137\/0710032","article-title":"Nested dissection of a regular finite-element mesh","volume":"10","author":"George","year":"1973","journal-title":"SIAM J. Numer. Anal."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1145\/1024074.1024077","article-title":"A numerical evaluation of HSL packages for the direct solution of large sparse, symmetric linear systems of equations","volume":"30","author":"Gould","year":"2004","journal-title":"ACM Trans. Math. Softw."},{"key":"ref_16","unstructured":"Karypis, G., and Kumar, V. METIS: A software package for partitioning unstructured graphs, partitioning meshes and computing fill-reducing orderings of sparse matrices\u2014Version 4.0, 1998. Available online: http:\/\/www-users.cs.umn.edu\/karypis\/metis\/."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1137\/S1064827595287997","article-title":"A fast and high quality multilevel scheme for partitioning irregular graphs","volume":"20","author":"Karypis","year":"1999","journal-title":"SIAM J. Sci. Comput."},{"key":"ref_18","unstructured":"Pellegrini, F. Available online: http:\/\/www.labri.fr\/perso\/pelegrin\/scotch\/."},{"key":"ref_19","unstructured":"Boman, E., Devine, K., Fisk, L.A., Heaphy, R., Hendrickson, B., Vaughan, C., Catalyurek, U., Bozdag, D., Mitchell, W., and Teresco, J. (2007). Zoltan 3.0: Parallel Partitioning, Load-balancing, and Data Management Services; User\u2019s Guide, Available online: http:\/\/www.cs.sandia.gov\/Zoltan\/ug html\/ug.html."},{"key":"ref_20","unstructured":"Duff, I., and Scott, J. (2005). Towards an Automatic Ordering for a Symmetric Sparse Direct Solver, Rutherford Appleton Laboratory. Technical Report RAL-TR-2006-001."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1137\/0611010","article-title":"The role of elimination trees in sparse factorization","volume":"11","author":"Liu","year":"1990","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/77626.79170","article-title":"A set of level 3 basic linear algebra subprograms","volume":"16","author":"Dongarra","year":"1990","journal-title":"ACM Trans. Math. Softw."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1145\/76909.76910","article-title":"The influence of relaxed supernode partitions on the multifrontal method","volume":"15","author":"Ashcraft","year":"1989","journal-title":"ACM Trans. Math. Softw."},{"key":"ref_24","unstructured":"Hogg, J., and Scott, J. (2010). A Modern Analyse Phase for Sparse Tree-Based Direct Methods, Rutherford Appleton Laboratory. Technical Report RAL-TR-2010-031."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1145\/356044.356047","article-title":"The multifrontal solution of indefinite sparse symmetric linear systems","volume":"9","author":"Duff","year":"1983","journal-title":"ACM Trans. Math. Softw."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1137\/1034004","article-title":"The multifrontal method for sparse matrix solution: Theory and practice","volume":"34","author":"Liu","year":"1992","journal-title":"SIAM Rev."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1137\/S0895479896296921","article-title":"Accurate symmetric indefinite linear equation solvers","volume":"20","author":"Ashcraft","year":"1999","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1090\/S0025-5718-1977-0428694-0","article-title":"Some stable methods for calculating inertia and solving symmetric linear systems","volume":"31","author":"Bunch","year":"1977","journal-title":"Math. Comput."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1093\/imanum\/11.2.181","article-title":"Factorization of sparse symmetric indefinite matrices","volume":"11","author":"Duff","year":"1991","journal-title":"IMA J. Numer. Anal."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Hogg, J., and Scott, J. (2014). Pivoting strategies for tough sparse indefinite systems. ACM Trans. Math. Softw., 40, to be published.","DOI":"10.1145\/2513109.2513113"},{"key":"ref_31","unstructured":"Hogg, J., and Scott, J. (2013). Compressed Threshold Pivoting for Sparse Symmetric Indefinite Systems, Rutherford Appleton Laboratory. Technical Report RAL-P-2013-007."},{"key":"ref_32","unstructured":"Hogg, J., and Scott, J. (2008). The Effects of Scalings on the Performance of a Sparse Symmetric Indefinite Solver, Rutherford Appleton Laboratory. Technical Report RAL-TR-2008-007."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"1431","DOI":"10.1137\/120884262","article-title":"Optimal weighted matchings for rank-deficient sparse matrices","volume":"34","author":"Hogg","year":"2013","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"ref_34","unstructured":"Hogg, J., and Scott, J. (2012). Achieving Bit Compatibility in Sparse Direct Solvers, Rutherford Appleton Laboratory. Technical Report RAL-P-2012-005."},{"key":"ref_35","unstructured":"Buttari, A., Dongarra, J., Kurzak, J., Langou, J., Luszczek, P., and Tomov, S. (2006, January 18\u201321). The Impact of Multicore on Math Software. Proceedings of Workshop on State-of-the-Art in Scientific and Parallel Computing (PARA\u201906), Ume\u00e5, Sweden."},{"key":"ref_36","unstructured":"Buttari, A., Langou, J., Kurzak, J., and Dongarra, J. (2007). A Class of Parallel Tiled Linear Algebra Algorithms for Multicore Architectures, ICL, University of Tennessee. Technical Report UT-CS-07-600; Also LAPACK Working Note 191."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Anderson, E., Bai, Z., Bischof, C., Blackford, S., Demmel, J., Dongarra, J., Du Croz, J., Greenbaum, A., Hammarling, S., and McKenney, A. (1999). LAPACK Users\u2019 Guide, Society for Industrial and Applied Mathematics. [3rd ed.].","DOI":"10.1137\/1.9780898719604"},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Reid, J., and Scott, J. (2011). Partial Factorization of a Dense Symmetric Indefinite Matrix. ACM Trans. Math. Softw., 38.","DOI":"10.1145\/2049673.2049674"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1499096.1499098","article-title":"Algorithm 891: A Fortran virtual memory system","volume":"36","author":"Reid","year":"2009","journal-title":"ACM Trans. Math. Softw."},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Davis, T., and Hu, Y. (2011). The University of Florida sparse matrix collection. ACM Trans. Math. Softw., 38.","DOI":"10.1145\/2049662.2049663"},{"key":"ref_41","unstructured":"Ruiz, D., and U\u00e7ar, B. (2011). A Symmetry Preserving Algorithm of Matrix Scaling, INRIA. Technical Report RR-7552."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1145\/992200.992202","article-title":"MA57\u2014a new code for the solution of sparse symmetric definite and indefinite systems","volume":"30","author":"Duff","year":"2004","journal-title":"ACM Trans. Math. Softw."},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Hogg, J., and Scott, J. (2010). A fast and robust mixed precision solver for the solution of sparse symmetric linear systems. ACM Trans. Math. Softw., 37.","DOI":"10.1145\/1731022.1731027"},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"475","DOI":"10.1016\/j.future.2003.07.011","article-title":"Solving unsymmetric sparse systems of linear equations with PARDISO","volume":"20","author":"Schenk","year":"2004","journal-title":"J. Future Generation Comput. Syst."},{"key":"ref_45","first-page":"158","article-title":"On fast factorization pivoting methods for symmetric indefinite systems","volume":"23","author":"Schenk","year":"2006","journal-title":"Electron. Trans. Numer. Anal."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1137\/S0895479899358194","article-title":"A fully asynchronous multifrontal solver using distributed dynamic scheduling","volume":"23","author":"Amestoy","year":"2001","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1016\/S0167-8191(01)00141-7","article-title":"PaStiX: A high-performance parallel direct solver for sparse symmetric definite systems","volume":"28","author":"Ramet","year":"2002","journal-title":"Parallel Comput."},{"key":"ref_48","unstructured":"Gupta, A., Joshi, M., and Kumar, V. Available online: http:\/\/www.cs.umn.edu\/\u223cagupta\/doc\/wssmp-paper.ps."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/6\/4\/702\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T21:50:19Z","timestamp":1760219419000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/6\/4\/702"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,11,1]]},"references-count":48,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2013,12]]}},"alternative-id":["a6040702"],"URL":"https:\/\/doi.org\/10.3390\/a6040702","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,11,1]]}}}