{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T06:21:32Z","timestamp":1772518892107,"version":"3.50.1"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2004,9,1]],"date-time":"2004-09-01T00:00:00Z","timestamp":1093996800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2004,9]]},"abstract":"<jats:p>\n            Sparse Gaussian elimination with partial pivoting computes the factorization\n            <jats:bold>PAQ<\/jats:bold>\n            =\n            <jats:bold>LU<\/jats:bold>\n            of a sparse matrix\n            <jats:bold>A<\/jats:bold>\n            , where the row ordering\n            <jats:bold>P<\/jats:bold>\n            is selected during factorization using standard partial pivoting with row interchanges. The goal is to select a column preordering,\n            <jats:bold>Q<\/jats:bold>\n            , based solely on the nonzero pattern of\n            <jats:bold>A<\/jats:bold>\n            , that limits the worst-case number of nonzeros in the factorization. The fill-in also depends on\n            <jats:bold>P<\/jats:bold>\n            , but\n            <jats:bold>Q<\/jats:bold>\n            is selected to reduce an upper bound on the fill-in for any subsequent choice of\n            <jats:bold>P<\/jats:bold>\n            . The choice of\n            <jats:bold>Q<\/jats:bold>\n            can have a dramatic impact on the number of nonzeros in\n            <jats:bold>L<\/jats:bold>\n            and\n            <jats:bold>U<\/jats:bold>\n            . One scheme for determining a good column ordering for\n            <jats:bold>A<\/jats:bold>\n            is to compute a symmetric ordering that reduces fill-in in the Cholesky factorization of\n            <jats:bold>\n              A\n              <jats:sup>T<\/jats:sup>\n              A\n            <\/jats:bold>\n            . A conventional minimum degree ordering algorithm would require the sparsity structure of\n            <jats:bold>\n              A\n              <jats:sup>T<\/jats:sup>\n              A\n            <\/jats:bold>\n            to be computed, which can be expensive both in terms of space and time since\n            <jats:bold>\n              A\n              <jats:sup>T<\/jats:sup>\n              A\n            <\/jats:bold>\n            may be much denser than\n            <jats:bold>A<\/jats:bold>\n            . An alternative is to compute\n            <jats:bold>Q<\/jats:bold>\n            directly from the sparsity structure of\n            <jats:bold>A<\/jats:bold>\n            ; this strategy is used by MATLAB's COLMMD preordering algorithm. A new ordering algorithm, COLAMD, is presented. It is based on the same strategy but uses a better ordering heuristic. COLAMD is faster and computes better orderings, with fewer nonzeros in the factors of the matrix.\n          <\/jats:p>","DOI":"10.1145\/1024074.1024079","type":"journal-article","created":{"date-parts":[[2004,10,7]],"date-time":"2004-10-07T17:38:56Z","timestamp":1097170736000},"page":"353-376","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":151,"title":["A column approximate minimum degree ordering algorithm"],"prefix":"10.1145","volume":"30","author":[{"given":"Timothy A.","family":"Davis","sequence":"first","affiliation":[{"name":"University of Florida, Gainesville, FL"}]},{"given":"John R.","family":"Gilbert","sequence":"additional","affiliation":[{"name":"University of California, Santa Barbara, CA"}]},{"given":"Stefan I.","family":"Larimore","sequence":"additional","affiliation":[{"name":"Microsoft, Inc., Redmond, WA"}]},{"given":"Esmond G.","family":"Ng","sequence":"additional","affiliation":[{"name":"Lawrence Berkeley National Laboratory, Berkeley, CA"}]}],"member":"320","published-online":{"date-parts":[[2004,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479894278952"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1024074.1024081"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/0916081"},{"key":"e_1_2_1_4_1","unstructured":"Bai Z. Day D. Demmel J. and Dongarra J. 1996. Test matrix collection (non-Hermitian eigenvalue problems) Release 1. Tech. rep. University of Kentucky. September. Available at ftp:\/\/ftp.ms.uky.edu\/pub\/misc\/bai\/Collection.  Bai Z. Day D. Demmel J. and Dongarra J. 1996. Test matrix collection (non-Hermitian eigenvalue problems) Release 1. Tech. rep. University of Kentucky. September. Available at ftp:\/\/ftp.ms.uky.edu\/pub\/misc\/bai\/Collection."},{"key":"e_1_2_1_5_1","article-title":"Solving multistage stochastic programs using tree dissection","author":"Berger A. J.","year":"1995","unstructured":"Berger , A. J. , Mulvey , J. M. , Rothberg , E. , and Vanderbei , R. J. 1995 . Solving multistage stochastic programs using tree dissection . Tech. Rep. SOR-95-07, Dept. of Civil Eng. and Operations Research, Princeton Univ., Princeton, NJ. June. Berger, A. J., Mulvey, J. M., Rothberg, E., and Vanderbei, R. J. 1995. Solving multistage stochastic programs using tree dissection. Tech. Rep. SOR-95-07, Dept. of Civil Eng. and Operations Research, Princeton Univ., Princeton, NJ. June.","journal-title":"Tech. Rep. SOR-95-07, Dept. of Civil Eng. and Operations Research, Princeton Univ., Princeton, NJ. June."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.38.2.240"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/5925.5932"},{"key":"e_1_2_1_8_1","unstructured":"Davis T. A. 2000. Univ. of Florida sparse matrix collection. http:\/\/www.cise.ufl.edu\/research\/ sparse.  Davis T. A. 2000. Univ. of Florida sparse matrix collection. http:\/\/www.cise.ufl.edu\/research\/ sparse."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479894246905"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/305658.287640"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1024074.1024080"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479895291765"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/77626.79170"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/22899.22904"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/355958.355963"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/62038.62043"},{"key":"e_1_2_1_17_1","volume-title":"Tech. Rep. RAL-92-086, Rutherford Appleton Laboratory, Didcot, Oxon, England. Dec.","author":"Duff I. S.","year":"1992","unstructured":"Duff , I. S. , Grimes , R. G. , and Lewis , J. G . 1992 . Users' guide for the Harwell-Boeing sparse matrix collection (Release 1). Tech. Rep. RAL-92-086, Rutherford Appleton Laboratory, Didcot, Oxon, England. Dec. Duff, I. S., Grimes, R. G., and Lewis, J. G. 1992. Users' guide for the Harwell-Boeing sparse matrix collection (Release 1). Tech. Rep. RAL-92-086, Rutherford Appleton Laboratory, Didcot, Oxon, England. Dec."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/356044.356047"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the IEEE Custom Integrated Circuits Conference (Santa Clara, Calif.). IEEE Computer Society Press, Los Alamitos Calif.","author":"Feldmann P.","unstructured":"Feldmann , P. , Melville , R. , and Long , D . 1996. Efficient frequency domain analysis of large nonlinear analog circuits . In Proceedings of the IEEE Custom Integrated Circuits Conference (Santa Clara, Calif.). IEEE Computer Society Press, Los Alamitos Calif. Feldmann, P., Melville, R., and Long, D. 1996. Efficient frequency domain analysis of large nonlinear analog circuits. In Proceedings of the IEEE Custom Integrated Circuits Conference (Santa Clara, Calif.). IEEE Computer Society Press, Los Alamitos Calif."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/0209044"},{"key":"e_1_2_1_21_1","unstructured":"George A. and Liu J. W. H. 1981. Computer Solution of Large Sparse Positive Definite Systems. Prentice-Hall Englewood Cliffs N.J.   George A. and Liu J. W. H. 1981. Computer Solution of Large Sparse Positive Definite Systems. Prentice-Hall Englewood Cliffs N.J."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/0715006"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/0906028"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/0908072"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/0613024"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Gilbert J. R. and Ng E. G. 1993. Predicting structure in nonsymmetric sparse matrix factorizations. In Graph Theory and Sparse Matrix Computation A. George J. R. Gilbert and J. W. H. Liu Eds. Volume 56 of the IMA Volumes in Mathematics and Its Applications. Springer-Verlag New York 107--139.  Gilbert J. R. and Ng E. G. 1993. Predicting structure in nonsymmetric sparse matrix factorizations. In Graph Theory and Sparse Matrix Computation A. George J. R. Gilbert and J. W. H. Liu Eds. Volume 56 of the IMA Volumes in Mathematics and Its Applications. Springer-Verlag New York 107--139.","DOI":"10.1007\/978-1-4613-8369-7_6"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479892236921"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/0909058"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/355791.355796"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/0614046"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Heggernes P. and Matstoms P. 1994. Finding good column orderings for sparse QR factorization. Tech. rep. Dept. of Informatics Univ. of Bergen Bergen Norway.  Heggernes P. and Matstoms P. 1994. Finding good column orderings for sparse QR factorization. Tech. rep. Dept. of Informatics Univ. of Bergen Bergen Norway.","DOI":"10.1145\/174603.174408"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579150"},{"key":"e_1_2_1_33_1","volume-title":"Approximate deficiency for ordering the columns of a matrix. Tech. rep","author":"Kern J. L.","unstructured":"Kern , J. L. 1999. Approximate deficiency for ordering the columns of a matrix. Tech. rep ., Univ. of Florida , Gainesville, Fla . (Senior thesis, see http:\/\/www.cise.ufl.edu\/colamd\/kern.ps.) Kern, J. L. 1999. Approximate deficiency for ordering the columns of a matrix. Tech. rep., Univ. of Florida, Gainesville, Fla. (Senior thesis, see http:\/\/www.cise.ufl.edu\/colamd\/kern.ps.)"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/214392.214398"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/103147.103159"},{"key":"e_1_2_1_37_1","first-page":"255","article-title":"The elimination form of the inverse and its application to linear programming. Manage","volume":"3","author":"Markowitz H. M.","year":"1957","unstructured":"Markowitz , H. M. 1957 . The elimination form of the inverse and its application to linear programming. Manage . Sci. 3 , 255 -- 269 . Markowitz, H. M. 1957. The elimination form of the inverse and its application to linear programming. Manage. Sci. 3, 255--269.","journal-title":"Sci."},{"key":"e_1_2_1_38_1","unstructured":"Miller J. J. H. and Wang S. 1991. An exponentially fitted finite element method for a stationary convection-diffusion problem. In Computational Methods for Boundary and Interior Layers in Several Dimensions J. J. H. Miller Ed. Boole Press Dublin 120--137.  Miller J. J. H. and Wang S. 1991. An exponentially fitted finite element method for a stationary convection-diffusion problem. In Computational Methods for Boundary and Interior Layers in Several Dimensions J. J. H. Miller Ed. Boole Press Dublin 120--137."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479897319313"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.43.5.781"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479896302692"},{"key":"e_1_2_1_43_1","volume-title":"Primal-dual interior-point methods","author":"Wright S. J.","unstructured":"Wright , S. J. 1996. Primal-dual interior-point methods . SIAM Publications , Philadelphia, Pa . Wright, S. J. 1996. Primal-dual interior-point methods. SIAM Publications, Philadelphia, Pa."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/0602010"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/147877.148039"},{"key":"e_1_2_1_46_1","doi-asserted-by":"crossref","unstructured":"Zitney S. E. Mallya J. Davis T. A. and Stadtherr M. A. 1996. Multifrontal vs. frontal techniques for chemical process simulation on supercomputers. Comput. Chem. Eng. 20 6\/7 641--646.  Zitney S. E. Mallya J. Davis T. A. and Stadtherr M. A. 1996. Multifrontal vs. frontal techniques for chemical process simulation on supercomputers. Comput. Chem. Eng. 20 6\/7 641--646.","DOI":"10.1016\/0098-1354(95)00198-0"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1024074.1024079","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1024074.1024079","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:23:53Z","timestamp":1750267433000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1024074.1024079"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,9]]},"references-count":44,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2004,9]]}},"alternative-id":["10.1145\/1024074.1024079"],"URL":"https:\/\/doi.org\/10.1145\/1024074.1024079","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"value":"0098-3500","type":"print"},{"value":"1557-7295","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,9]]},"assertion":[{"value":"2004-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}