{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T14:43:49Z","timestamp":1787496229923,"version":"build-2736575974"},"reference-count":110,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM Rev."],"published-print":{"date-parts":[[1991,9]]},"abstract":"<jats:p>This paper surveys recent progress in the development of parallel algorithms for solving sparse linear systems on computer architectures having multiple processors. Attention is focused on direct methods for solving sparse symmetric positive definite systems, specifically by Cholesky factorization. Recent progress on parallel algorithms is surveyed for all phases of the solution process, including ordering, symbolic factorization, numeric factorization, and triangular solution.<\/jats:p>","DOI":"10.1137\/1033099","type":"journal-article","created":{"date-parts":[[2005,3,7]],"date-time":"2005-03-07T02:21:47Z","timestamp":1110162107000},"page":"420-460","source":"Crossref","is-referenced-by-count":154,"title":["Parallel Algorithms for Sparse Linear Systems"],"prefix":"10.1137","volume":"33","author":[{"given":"Michael T.","family":"Heath","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Esmond","family":"Ng","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Barry W.","family":"Peyton","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,18]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(89)90029-X"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"G. Alaghband, H. Jordan,  Multiprocessor sparse  L\/U decomposition with controlled fill-in, Tech. Report, 85-48, ICASE, NASA Langley Research Center, Hampton, VA,  1985","DOI":"10.21236\/ADA211570"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1177\/109434208900300303"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1142\/S0129053389000056"},{"key":"R5","unstructured":"C. Ashcraft,  A vector implementation of the multifrontal method for large sparse, symmetric positive definite linear systems, Tech. Report, ETA-TR-51, Engineering Technology Applications Division, Boeing Computer Services, Seattle, WA,  1987"},{"key":"R6","unstructured":"C. Ashcraft,  1990, Personal communication"},{"key":"R7","unstructured":"C. Ashcraft, Ph.D. Thesis,  The aggregate model for the factorization of symmetric positive definite matrices, Dept. of Computer Science, Yale University, New Haven, CT,  1990"},{"key":"R8","unstructured":"C. Ashcraft, S. Eisenstat, J. Liu, B. Peyton, A. Sherman,  A compute-ahead implementation of the fan-in sparse distributed factorization scheme, Tech. Report, ORNL\/TM-11496, Oak Ridge National Laboratory, Oak Ridge, TN,  1990"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"C. Ashcraft, S. Eisenstat, J. Liu, A. Sherman,  A comparison of three column-based distributed sparse factorization schemes, Tech. Report, YALEU\/DCS\/RR-810, Dept. of Computer Science,Yale University, New Haven, CT,  1990","DOI":"10.21236\/ADA228143"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1137\/0911033"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1177\/109434208700100403"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1177\/109434208700100304"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/0611005"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1109\/52.28127"},{"key":"R15","unstructured":"I. Cavers, Masters Thesis,  Tiebreaking the minimum degree algorithm for ordering sparse symmetric positive definite matrices, Master's thesis, Dept. of Computer Science, University of British Columbia, Vancouver, B.C.,  1987"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1137\/0611031"},{"key":"R17","unstructured":"E. Chu, A. George, J. W.H. Liu, E. G.Y. Ng,  User's guide for SPARSPAK-A: Waterloo sparse linear equations package, Tech. Report, CS-84-36, University of Waterloo, Waterloo, Ontario,  1984"},{"key":"R18","unstructured":"J. Conroy,  Parallel direct solution of sparse linear systems of equations, Tech. Report, TR 1714, Dept. of Computer Science, University of Maryland, College Park, MD,  1986"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(87)90006-8"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1137\/0611028"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1137\/1026003"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(86)90019-0"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1016\/0377-0427(89)90368-3"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1137\/0713056"},{"key":"R25","volume-title":"Direct Methods for Sparse Matrices","author":"Duff I.","year":"1987"},{"key":"R26","series-title":"Oxford Sci. Publ.","first-page":"93","volume-title":"Reliable numerical computation","author":"Duff I.","year":"1990"},{"key":"R27","unstructured":"I. Duff, J. Reid,  MA27 - a set of Fortran subroutines for solving sparse symmetric sets of linear equations, Tech. Report, AERE R 10533, Harwell,  1982"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1145\/356044.356047"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1002\/nme.1620180804"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1137\/0909038"},{"key":"R31","doi-asserted-by":"crossref","unstructured":"C. Fiduccia, R. Mattheyses,  A linear-time heuristic for improving network partitions,  Proceedings of the 19th Design Automation Conference,  1982,  175\u2013181","DOI":"10.1109\/DAC.1982.1585498"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.21136\/CMJ.1973.101168"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.21136\/CMJ.1975.101357"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1137\/1032002"},{"key":"R35","unstructured":"F. Gao, B. Parlett,  Communication cost of sparse Cholesky factorization on a hypercube, Tech. Report, PAM-436, Center for Pure and Applied Mathematics, University of California, Berkeley, CA,  1988"},{"key":"R36","first-page":"656","volume-title":"Hypercube Multiprocessors 1987","author":"Geist G.","year":"1987"},{"key":"R37","unstructured":"G. Geist, M. Heath,  Parallel Cholesky factorization on a hypercube multiprocessor, Tech. Report, ORNL-6211, Oak Ridge National Laboratory, Oak Ridge, TN,  1985"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1007\/BF01407861"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1137\/0710032"},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(86)90167-9"},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1007\/BF01407878"},{"key":"R42","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(87)90009-3"},{"key":"R43","doi-asserted-by":"publisher","DOI":"10.1137\/0909021"},{"key":"R44","doi-asserted-by":"publisher","DOI":"10.1016\/0377-0427(89)90364-6"},{"key":"R45","doi-asserted-by":"publisher","DOI":"10.1137\/0715069"},{"key":"R46","doi-asserted-by":"publisher","DOI":"10.1137\/0209044"},{"key":"R47","volume-title":"Computer solution of large sparse positive definite systems","author":"George A.","year":"1981"},{"key":"R48","doi-asserted-by":"publisher","DOI":"10.1137\/1031001"},{"key":"R49","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(89)90101-4"},{"key":"R50","doi-asserted-by":"publisher","DOI":"10.1137\/0715006"},{"key":"R51","doi-asserted-by":"publisher","DOI":"10.1007\/BF02023054"},{"key":"R52","unstructured":"J. Gilbert,  An efficient parallel sparse partial pivoting algorithm, Tech. Report, CMI No. 88\/45052-1, Centre for Computer Science, Dept. of Science and Technology, Chr. Michelsen Institute, Bergen, Norway,  1988"},{"key":"R53","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(90)90104-H"},{"key":"R54","doi-asserted-by":"publisher","DOI":"10.1137\/0913067"},{"key":"R55","doi-asserted-by":"publisher","DOI":"10.1007\/BF01388998"},{"key":"R56","unstructured":"A. Greenbaum,  Solving sparse triangular linear systems using fortran with extensions on the NYU Ultracomputer prototype, Tech. Report, 99, NYU Ultracomputer Note, New York University, New York,  1986, April"},{"key":"R57","unstructured":"M. Heath,  Visual animation of parallel algorithms for matrix computations,  Proc. Fifth Distributed Memory Computing Conf., Charleston, SC,  1990"},{"key":"R58","doi-asserted-by":"publisher","DOI":"10.1137\/0909037"},{"key":"R59","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(86)90168-0"},{"key":"R60","doi-asserted-by":"publisher","DOI":"10.1137\/0710033"},{"key":"R61","doi-asserted-by":"publisher","DOI":"10.1002\/nme.1620020104"},{"key":"R62","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1982.1675979"},{"key":"R63","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1970.tb01770.x"},{"key":"R64","doi-asserted-by":"publisher","DOI":"10.1145\/355841.355847"},{"key":"R65","first-page":"27","volume-title":"Parallel Processing for Scientific Computing","author":"Leiserson C.","year":"1989"},{"key":"R66","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(89)90016-1"},{"key":"R67","doi-asserted-by":"publisher","DOI":"10.1137\/0910070"},{"key":"R68","doi-asserted-by":"publisher","DOI":"10.1137\/0716027"},{"key":"R69","doi-asserted-by":"publisher","DOI":"10.1137\/0136016"},{"key":"R70","doi-asserted-by":"publisher","DOI":"10.1145\/214392.214398"},{"key":"R71","doi-asserted-by":"publisher","DOI":"10.1145\/6497.6499"},{"key":"R72","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(86)90014-1"},{"key":"R73","doi-asserted-by":"publisher","DOI":"10.1137\/0909029"},{"key":"R74","doi-asserted-by":"publisher","DOI":"10.1145\/66888.66890"},{"key":"R75","doi-asserted-by":"publisher","DOI":"10.1137\/0910069"},{"key":"R76","doi-asserted-by":"publisher","DOI":"10.1145\/76909.76911"},{"key":"R77","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(89)90064-1"},{"key":"R78","unstructured":"J. W.H. Liu,  The multifrontal method for sparse matrix solution: theory and practice, Tech. Report, CS-90-04, Dept. of Computer Science, York University, North York, Ontario,  1990"},{"key":"R79","doi-asserted-by":"publisher","DOI":"10.1137\/0611010"},{"key":"R80","doi-asserted-by":"publisher","DOI":"10.1137\/0402011"},{"key":"R81","unstructured":"J. W.H. Liu, E. G.Y. Ng,  A supernodal symbolic Cholesky factorization on a local-memory multiprocessor,  1990, in preparation"},{"key":"R82","unstructured":"R. Lucas, Ph.D. Thesis,  Solving planar systems of equations on distributed-memory multiprocessors, Dept. of Electrical Engineering, Stanford University, Stanford, CA,  1987"},{"key":"R83","unstructured":"R. Lucas,  1990, Personal communication"},{"key":"R84","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.1987.1270339"},{"key":"R85","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(88)90082-8"},{"key":"R86","unstructured":"V. Naik, M. Patrick,  Data traffic reduction schemes for sparse Cholesky factorization, Tech. Report, ICASE Report no. 88-14, ICASE, NASA Langley Research Center, Hampton, VA,  1988"},{"key":"R87","doi-asserted-by":"crossref","unstructured":"V. Naik, M. Patrick,  Data traffic reduction schemes for Cholesky factorization on asynchronous multiprocessor systems, Tech. Report ICASE Report, 89-40, ICASE, NASA Langley Research Center, Hampton, VA,  1989","DOI":"10.1145\/318789.318820"},{"key":"R88","doi-asserted-by":"publisher","DOI":"10.1137\/0914048"},{"key":"R89","volume-title":"Introduction to parallel and vector solution of linear systems","author":"Ortega J.","year":"1989"},{"key":"R90","unstructured":"J. Ortega, R. Voigt, C. Romine,  A bibliography on parallel and vector numerical algorithms, Tech. Report, ORNL\/TM-10998, Oak Ridge National Laboratory, Oak Ridge, TN,  1989"},{"key":"R91","doi-asserted-by":"publisher","DOI":"10.1137\/1003021"},{"key":"R92","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(84)90446-0"},{"key":"R93","unstructured":"A. Pothen,  The complexity of optimal elimination trees, Tech. Report, Dept. of Computer Science, The Pennsylvania State University, University Park, PA,  1988"},{"key":"R94","doi-asserted-by":"publisher","DOI":"10.1145\/98267.98287"},{"key":"R95","doi-asserted-by":"publisher","DOI":"10.1137\/0611030"},{"key":"R96","unstructured":"P. Raghavan, A. Pothen,  Parallel orthogonal factorization,  SIAM Symposium on Sparse Matrices, Gleneden Beach, OR, Society for Industrial and Applied Mathematics, Philadelphia, PA,  1989"},{"key":"R97","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(70)90282-9"},{"key":"R98","doi-asserted-by":"publisher","DOI":"10.1016\/B978-1-4832-3187-7.50018-0"},{"key":"R99","doi-asserted-by":"publisher","DOI":"10.1137\/0205021"},{"key":"R100","doi-asserted-by":"crossref","unstructured":"E. Rothberg, A. Gupta,  Fast sparse matrix factorization on modern workstations, Tech. Report, STAN-CS-89-1286, Stanford University, Stanford, CA,  1989","DOI":"10.21236\/ADA326885"},{"key":"R101","unstructured":"P. Sadayappan, V. Visvanathan,  Distributed sparse factorization of circuit matrices via recursive  E-tree partitioning,  SIAM Symposium on Sparse Matrices, Gleneden Beach, OR, Society for Industrial and Applied Mathematics, Philadelphia, PA,  1989"},{"key":"R102","doi-asserted-by":"publisher","DOI":"10.1137\/0911008"},{"key":"R103","doi-asserted-by":"publisher","DOI":"10.1145\/356004.356006"},{"key":"R104","unstructured":"A. Sherman, Ph.D. Thesis,  On the efficient solution of sparse systems of linear and nonlinear equations, Yale University, New Haven, CT,  1975"},{"key":"R105","first-page":"8","volume-title":"New computing environments: parallel, vector and systolic (Stanford, Calif., 1984)","author":"Worley P.","year":"1986"},{"key":"R106","unstructured":"C. Yang, P. Vu,  A vector\/parallel implementation of the multifrontal method for sparse symmetric definite linear systems on the Cray Y-MP, Tech. Report, CRAY Research,  1990"},{"key":"R107","doi-asserted-by":"publisher","DOI":"10.1137\/0602010"},{"key":"R108","unstructured":"E. Zmijewski, Ph.D. Thesis,  Sparse Cholesky Factorization on a Multiprocessor, Dept. of Computer Science, Cornell University, Ithaca, NY,  1987, August"},{"key":"R109","unstructured":"E. Zmijewski,  Limiting communication in parallel sparse Cholesky factorization, Tech. Report, TRCS89-18, Dept. of Computer Science, University of California, Santa Barbara, CA,  1989"},{"key":"R110","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(88)90039-7"}],"container-title":["SIAM Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/1033099","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,20]],"date-time":"2026-08-20T14:16:31Z","timestamp":1787235391000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/1033099"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,9]]},"references-count":110,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1991,9]]}},"alternative-id":["10.1137\/1033099"],"URL":"https:\/\/doi.org\/10.1137\/1033099","relation":{},"ISSN":["0036-1445","1095-7200"],"issn-type":[{"value":"0036-1445","type":"print"},{"value":"1095-7200","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,9]]}}}