{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,26]],"date-time":"2026-08-26T02:38:23Z","timestamp":1787711903343,"version":"build-2784847793"},"reference-count":42,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>The rapid emergence of multicore machines has led to the need to design new algorithms that are efficient on these architectures. Here, we consider the solution of sparse symmetric positive-definite linear systems by Cholesky factorization. We were motivated by the successful division of the computation in the dense case into tasks on blocks and use of a task manager to exploit all the parallelism that is available between these tasks, whose dependencies may be represented by a directed acyclic graph (DAG). Our sparse algorithm is built on the assembly tree and subdivides the work at each node into tasks on blocks of the Cholesky factor. The dependencies between these tasks may again be represented by a DAG. To limit memory requirements, blocks are updated directly rather than through generated-element matrices. Our algorithm is implemented within a new efficient and portable solver HSL_MA87. It is written in Fortran 95 plus OpenMP and is available as part of the software library HSL. Using problems arising from a range of applications, we present experimental results that support our design choices and demonstrate that HSL_MA87 obtains good serial and parallel times on our 8-core test machines. Comparisons are made with existing modern solvers and show that HSL_MA87 performs well, particularly in the case of very large problems.<\/jats:p>","DOI":"10.1137\/090757216","type":"journal-article","created":{"date-parts":[[2010,12,21]],"date-time":"2010-12-21T18:23:09Z","timestamp":1292955789000},"page":"3627-3649","source":"Crossref","is-referenced-by-count":58,"title":["Design of a Multicore Sparse Cholesky Factorization Using DAGs"],"prefix":"10.1137","volume":"32","author":[{"given":"J. D.","family":"Hogg","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"J. K.","family":"Reid","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"J. A.","family":"Scott","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2010,12,21]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-6596\/180\/1\/012037"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479899358194"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1145\/1067967.1067969"},{"key":"R4","unstructured":"C. Augonnet, S. Thibault, and R. Namyst,\n                      StarPU: A Runtime System for Scheduling Tasks Over Accelerator-based Multicore Machines\n                      , Technical report Inria-00467677, Inria, Paris, 2010."},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1145\/1326548.1326550"},{"key":"R6","unstructured":"L. S. Blackford, J. Choi, A. Cleary, E. D'Azevedo, J. Demmel, I. Dhillon, J. Dongarra, S. Hammarling, G. Henry, A. Petitet, K. Stanley, D. Walker, and R. C. Whaley,\n                      ScaLAPACK Users' Guide\n                      , SIAM, Philadelphia, 1999."},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1996.0107"},{"key":"R8","unstructured":"A. Buttari, J. Dongarra, J. Kurzak, J. Langou, P. Luszczek, and S. Tomov,\n                      The impact of multicore on math software\n                      , in Proceedings of Workshop on State-of-the-art in Scientific and Parallel Computing (PARA06), 2006."},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2008.10.002"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1145\/1391989.1391995"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1145\/992200.992206"},{"key":"R12","unstructured":"T. A. Davis and Y. Hu,\n                      The University of Florida Sparse Matrix Collection\n                      , ACM TOMS, to appear."},{"key":"R13","unstructured":"T. A. Davis,\n                      Algorithm 8xx, SuiteSparseQR: A multifrontal multithreaded sparse QR factorization package\n                      , ACM Trans. Math. Software, submitted."},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479897317685"},{"key":"R15","unstructured":"I. S. Duff, A. M. Erisman, and J. K. Reid,\n                      Direct Methods for Sparse Matrices\n                      , Oxford University Press, London, 1986."},{"key":"R16","unstructured":"I. S. Duff, N. I. M. Gould, M. Lescrenier, and J. K. Reid,\n                      The Multifrontal Method in a Parallel Environment\n                      , Technical report CSS 211, Harwell Laboratory, Oxfordshire, UK, 1987."},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1145\/356044.356047"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(86)90019-0"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1145\/992200.992202"},{"key":"R20","unstructured":"M. Faverge and P. Ramet,\n                      Dynamic scheduling for sparse direct solver on NUMA architectures\n                      , in Proceedings of PARA'2008, NTNU, Trondheim, Norway, 2008."},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1007\/BF01407861"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1007\/BF01407878"},{"key":"R23","unstructured":"A. Gupta, M. Joshi, and V. Kumar,\n                      WSMP: A High-performance Serial and Parallel Sparse Linear Solver\n                      , Technical report RC 22038 (98932), IBM T.J. Watson Research Center, Yorktown Heights, NY, 2001; also available online from http:\/\/www.cs.umn.edu\/ \u02dcagupta\/doc\/wssmp-paper.ps."},{"key":"R24","unstructured":"A. Gupta,\n                      WSMP: Watson Sparse Matrix Package (Part\n                      I:\n                      Direct Solution of Symmetric Sparse Systems)\n                      , Technical report RC 21886, IBM T. J. Watson Research Center, Yorktown Heights, NY, 2000; also available online from http:\/\/www.cs.umn.edu\/ \u02dcagupta\/wsmp."},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1137\/1033099"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"P. H\u00e9non, P. Ramet, and J. Roman,\n                      PaStiX: A parallel sparse direct solver based on a static scheduling for mixed 1D\/2D block distributions\n                      , in Workshops IPDPS, Lecture Notes in Comput. Sci. 15, Springer-Verlag, New York, 2000, pp. 519\u2013525.","DOI":"10.1007\/3-540-45591-4_70"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(01)00141-7"},{"key":"R28","unstructured":"J. D. Hogg,\n                      A DAG-based Parallel Cholesky Factorization for Multicore Systems\n                      , Technical report RAL-TR-2008-029, Rutherford Appleton Laboratory, Chilton, Oxfordshire, UK, 2008."},{"key":"R29","unstructured":"HSL,\n                      A Collection of Fortran Codes for Large-scale Scientific Computation\n                      , http:\/\/www.hsl.rl.ac.uk\/."},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2003.07.007"},{"key":"R31","unstructured":"P. Kambadur, A. Gupta, A. Ghoting, H. Avron, and A. Lumsdaine,\n                      Modern task parallelism for modern high performance computing\n                      , in Proceedings of the SC09 (International Conference for High Performance Computing, Networking, Storage and Analysis), 2009, ACM, New York, http:\/\/www.coin-or.org\/projects\/PFunc.xml."},{"key":"R32","unstructured":"G. Karypis and V. Kumar,\n                      METIS\u2014Family of Multilevel Partitioning Algorithms\n                      , http:\/\/glaros.dtc.umn.edu\/gkhome\/views\/metis."},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1145\/1089014.1089017"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1088\/1742-6596\/125\/1\/012079"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1137\/0914048"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1096-9128(200002\/03)12:2\/3<69::AID-CPE472>3.0.CO;2-W"},{"key":"R38","doi-asserted-by":"crossref","unstructured":"F. Pellegrini and J. Roman,\n                      Sparse matrix ordering with SCOTCH\n                      , in Proceedings of HPCN'97, Vienna, Austria, Lecture Notes in Comput. Sci. 1225, Springer-Verlag, New York, 1997, pp. 370\u2013378.","DOI":"10.1007\/BFb0031609"},{"key":"R39","doi-asserted-by":"crossref","unstructured":"J. M. Perez, R. M. Badia, and J. Labarta,\n                      A dependency-aware task-based programming environment for multi-core architectures\n                      , in Proceedings of the IEEE International Conference on Cluster Computing, 2008, pp. 142\u2013151.","DOI":"10.1109\/CLUSTR.2008.4663765"},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1145\/1499096.1499098"},{"key":"R41","unstructured":"J. Reinders,\n                      Intel threading building blocks: Outfitting C++ for Multi-core Processor Parallelism\n                      , O'Reilly Media, Sebastopol, CA, 2007."},{"key":"R42","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2003.07.011"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/090757216","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:36:09Z","timestamp":1787330169000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/090757216"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":42,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/090757216"],"URL":"https:\/\/doi.org\/10.1137\/090757216","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}