{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T07:40:08Z","timestamp":1787384408761,"version":"build-2736575974"},"reference-count":32,"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":[[2006,1]]},"abstract":"<jats:p>Consider an incomplete Cholesky factorization of a sparse symmetric positive definite matrix. It is common practice to start with a symmetric permutation of the rows and columns of the matrix using an ordering to reduce fill in the complete Cholesky factor. Such an approach has two drawbacks. First, such an ordering is designed to reduce fill or operation counts in the complete Cholesky factor, and thus does not necessarily address the issue of controlling fill or operation counts during incomplete factorization. Second, because the ordering is determined in advance of the incomplete factorization, it is not easy to accommodate alternative pivoting sequences, for example, using numeric measures to promote stability, while taking into account their impact on fill and operation counts. In this paper, we consider an alternative approach that interleaves ordering with numeric computation in an incomplete Cholesky factorization. Such an interleaved scheme controls fill and operation counts. It also allows the incorporation of some limited, pivot selection strategies for stability. We demonstrate through experiments that our interleaved minimum-degree approach leads to fewer failures during incomplete factorization and improved convergence when the incomplete factor is used as a preconditioner for the conjugate gradient method. We conjecture that the improvements in the quality of preconditioning arise from the ability of our method to generate better approximations to the complete factor.<\/jats:p>","DOI":"10.1137\/040618357","type":"journal-article","created":{"date-parts":[[2006,3,24]],"date-time":"2006-03-24T21:00:17Z","timestamp":1143234017000},"page":"1069-1088","source":"Crossref","is-referenced-by-count":11,"title":["Effective Preconditioning through Ordering Interleaved with Incomplete Factorization"],"prefix":"10.1137","volume":"27","author":[{"given":"Ingyu","family":"Lee","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Padma","family":"Raghavan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Esmond G.","family":"Ng","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,31]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479894278952"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479896299081"},{"key":"R3","unstructured":"O. Axelsson, N. Munksgaard, Analysis of incomplete factorizations with fixed storage allocation, Topics in Comput. Math., Vol. 1, Gordon & Breach, New York, 1983, 219\u201324185g:65052"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"P. Concus, G. Golub, and D. O\u2019leary,\n                      A generalized conjugate gradient method for the numerical solution of elliptic partial differential equations\n                      , in Sparse Matrix Computations, J. R. Bunch and D. J. Rose, eds., Academic Press, New York, 1976, pp. 309\u2013332.","DOI":"10.1016\/B978-0-12-141050-6.50023-4"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/0613057"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/BF02074880"},{"key":"R7","unstructured":"E. D\u2019Azevedo, P. Forsyth, and W. Tang,\n                      On the Availability of Minimum Discarded Fill Ordering Codes\n                      , Personal communication, 2004."},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1007\/BF01932738"},{"key":"R9","volume-title":"Direct methods for sparse matrices","author":"Duff I.","year":"1986"},{"key":"R10","unstructured":"J. Liu, E. Chu, A. George, and E. Ng,\n                      SPARSEPAK: Waterloo Sparse Matrix Package User\u2019s Guide for SPARSEPAK\n                      , Tech. Report CS\u201084\u201036, Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada, 1984."},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/1031001"},{"key":"R12","volume-title":"Computer solution of large sparse positive definite systems","author":"George Alan","year":"1981"},{"key":"R13","unstructured":"Numerical Algorithms Group,\n                      The NAG C Library Manual, Mark\n                      7, Oxford, UK, 2002."},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.6028\/jres.049.044"},{"key":"R15","unstructured":"M. T. Jones and P. E. Plassmann,\n                      Blocksolve95 Users Manual: Scalable Library Software for the Parallel Solution of Sparse Linear Systems\n                      , Tech. Report ANL\u201095\/48, Argonne National Laboratory, Argonne, IL, 1995."},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827597327334"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1137\/0716027"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1145\/214392.214398"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1980-0559197-0"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.3.3.255"},{"key":"R21","first-page":"148","volume":"31","author":"Meijerink J. A.","year":"1977","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1145\/355887.355893"},{"key":"R23","unstructured":"E. Ng, B. Peyton, and P. Raghavan,\n                      A blocked incomplete cholesky preconditioner for hierarchical\u2010memory computers\n                      , in Iterative Methods in Scientific Computation IV, D. R. Kincaid and A. C. Elster, eds., IMACS Ser. Comput. Appl. Math. 5, International Association for Mathematics and Computers in Simulation, Rutgers University, New Brunswick, NJ, 1999, pp. 211\u2013221."},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479897319313"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1137\/1003021"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"D. J. 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":"R27","doi-asserted-by":"publisher","DOI":"10.1137\/0205021"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479896302692"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1002\/nla.1680010405"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1023\/A:1021908421589"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1109\/PROC.1967.6011"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1137\/0719024"}],"container-title":["SIAM Journal on Matrix Analysis and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/040618357","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:33:21Z","timestamp":1787333601000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/040618357"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,1]]},"references-count":32,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2006,1]]}},"alternative-id":["10.1137\/040618357"],"URL":"https:\/\/doi.org\/10.1137\/040618357","relation":{},"ISSN":["0895-4798","1095-7162"],"issn-type":[{"value":"0895-4798","type":"print"},{"value":"1095-7162","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,1]]}}}