{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T14:42:09Z","timestamp":1791297729572,"version":"4.1.0"},"reference-count":24,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Matrix Anal. Appl."],"published-print":{"date-parts":[[1999,1]]},"abstract":"<jats:p>Greedy algorithms for ordering sparse matrices for Cholesky factorization can be based on different metrics. Minimum degree, a popular and effective greedy ordering scheme, minimizes the number of nonzero entries in the rank-1 update (degree) at each step of the factorization. Alternatively, minimum deficiency minimizes the number of nonzero entries introduced (deficiency) at each step of the factorization. In this paper we develop two new heuristics: modified minimum deficiency (MMDF) and modified multiple minimum degree (MMMD). The former uses a metric similar to deficiency while the latter uses a degree-like metric. Our experiments reveal that on the average, MMDF orderings result in 21% fewer operations to factor than minimum degree; MMMD orderings result in 15% fewer operations to factor than minimum degree. MMMD requires on the average 7--13% more time than minimum degree, while MMDF requires on the average 33--34% more time than minimum degree.<\/jats:p>","DOI":"10.1137\/s0895479897319313","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"902-914","source":"Crossref","is-referenced-by-count":32,"title":["Performance of Greedy Ordering Heuristics for Sparse Cholesky Factorization"],"prefix":"10.1137","volume":"20","author":[{"given":"Esmond G.","family":"Ng","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Padma","family":"Raghavan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,8,1]]},"reference":[{"key":"R1","unstructured":"A. Aho, D\u017e. Hopkroft, D\u017e. Ul\u2019man, Postroenie i analiz vychislitelnykh algoritmov, \u201cMir\u201d, 1979, 536\u20130, Translated by A. O. Slisenko; Edited by Ju. V. Matijasevi\u010d80g:68036"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479894278952"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/0916081"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479896299081"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/0611005"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"E. Cuthill,\n                      Several strategies for reducing bandwidth of matrices\n                      , in Sparse Matrices and Their Applications, D. J. Rose and R. A. Willoughby, eds., Plenum Press, New York, 1972, pp. 157\u2013166.","DOI":"10.1007\/978-1-4615-8675-3_14"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"E. Cuthill and J. McKee,\n                      Reducing the bandwidth of sparse symmetric matrices\n                      , in Proceedings 24th ACM National Conference, August 1969, ACM, New York, pp. 157\u2013172.","DOI":"10.1145\/800195.805928"},{"key":"R8","volume-title":"Direct methods for sparse matrices","author":"Duff I.","year":"1989"},{"key":"R9","unstructured":"A. George,\n                      Computer Implementation of the Finite Element Method\n                      , Ph.D. thesis, Dept. of Computer Science, Stanford University, Stanford, CA, 1971."},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1137\/0715069"},{"key":"R11","unstructured":"Alan George, Joseph Liu, A quotient graph model for symmetric factorization, SIAM, Philadelphia, Pa., 1979, 154\u201317581i:68094"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1145\/355900.355906"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/0717024"},{"key":"R14","volume-title":"Computer solution of large sparse positive definite systems","author":"George Alan","year":"1981"},{"key":"R15","unstructured":"A. Gupta,\n                      Fast and Effective Algorithms for Graph Partitioning and Sparse Matrix Ordering\n                      , Technical report RC\u201020496, IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NY, 1996."},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827596300656"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1145\/214392.214398"},{"key":"R18","doi-asserted-by":"crossref","first-page":"902","DOI":"10.1137\/S0895479897319313","volume":"20","author":"Ng Esmond","year":"1999","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1137\/1003021"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"D. Rose,\n                      A graph\u2010theoretic study of the numerical solution of sparse positive definite systems of linear equations\n                      , in Graph Theory and Computing, R. C. Read, ed., Academic Press, New York, 1972, pp. 183\u2013217.","DOI":"10.1016\/B978-1-4832-3187-7.50018-0"},{"key":"R21","unstructured":"E. Rothberg,\n                      Ordering Sparse Matrices Using Approximate Minimum Local Fill\n                      , manuscript, 1996."},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479896302692"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1109\/PROC.1967.6011"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1137\/0602010"}],"container-title":["SIAM Journal on Matrix Analysis and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0895479897319313","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:33:39Z","timestamp":1787326419000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0895479897319313"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999,1]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1999,1]]}},"alternative-id":["10.1137\/S0895479897319313"],"URL":"https:\/\/doi.org\/10.1137\/s0895479897319313","relation":{},"ISSN":["0895-4798","1095-7162"],"issn-type":[{"value":"0895-4798","type":"print"},{"value":"1095-7162","type":"electronic"}],"subject":[],"published":{"date-parts":[[1999,1]]}}}