{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,17]],"date-time":"2026-09-17T12:55:34Z","timestamp":1789649734213,"version":"4.0.0"},"reference-count":29,"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":[[1994,10]]},"abstract":"<jats:p>Let an undirected graph G be given, along with a specified depth-first spanning tree T. Almost-linear-time algorithms are given to solve the following two problems. First, for every vertex v, compute the number of descendants w of v for which some descendant of w is adjacent (in G) to v. Second, for every vertex v, compute the number of ancestors of v that are adjacent (in $G $) to at least one descendant of v.<\/jats:p>\n                  <jats:p>These problems arise in Cholesky and $QR$ factorizations of sparse matrices. The authors\u2019 algorithms can be used to determine the number of nonzero entries in each row and column of the triangular factor of a matrix from the zero\/nonzero structure of the matrix. Such a prediction makes storage allocation for sparse matrix factorizations more efficient. The authors\u2019 algorithms run in time linear in the size of the input times a slowly growing inverse of Ackermann\u2019s function. The best previously known algorithms for these problems ran in time linear in the sum of the nonzero counts, which is usually much larger. Experimental results are given demonstrating the practical efficiency of the new algorithms.<\/jats:p>","DOI":"10.1137\/s0895479892236921","type":"journal-article","created":{"date-parts":[[2005,2,27]],"date-time":"2005-02-27T07:14:24Z","timestamp":1109488464000},"page":"1075-1091","source":"Crossref","is-referenced-by-count":33,"title":["An Efficient Algorithm to Compute Row and Column Counts for Sparse Cholesky Factorization"],"prefix":"10.1137","volume":"15","author":[{"given":"John R.","family":"Gilbert","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Esmond G.","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,17]]},"reference":[{"key":"R1","unstructured":"C. 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":"R2","doi-asserted-by":"publisher","DOI":"10.1145\/76909.76910"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1009"},{"key":"R4","unstructured":"E. C. H. 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":"R5","unstructured":"T. Coleman, Y. Li,  On the Convergence of Reflective Newton Methods for Large-Scale Nonlinear Minimization Subject to Bounds, Tech. Report, 92-1314, Cornell University Computer Science Department, Ithaca, NY,  1992"},{"key":"R6","unstructured":"T. Coleman, Y. Li,  A Reflective Newton Method for Minimizing a Quadratic Function Subject to Bounds on the Variables, Tech. Report, 92-1315, Cornell University Computer Science Department, Ithaca, NY,  1992"},{"key":"R7","volume-title":"Direct Methods for Sparse Matrices","author":"Duff I. S.","year":"1987"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1145\/62038.62043"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1002\/nme.1620180804"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90014-5"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(74)90094-X"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(80)90159-7"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1007\/BF01407878"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1137\/0909021"},{"key":"R15","volume-title":"Computer solution of large sparse positive definite systems","author":"George A.","year":"1981"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1137\/1033099"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1137\/0910070"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1145\/6497.6499"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1137\/0611010"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1137\/0614019"},{"key":"R21","unstructured":"A. Pothen,  Simplicial Cliques, Shortest Elimination Trees, and Supernodes in Sparse Cholesky Factorization, Tech. Report, CS-88-13, Department of Computer Science, The Pennsylvania State University, University Park, PA,  1988"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1016\/B978-1-4832-3187-7.50018-0"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1137\/0205021"},{"key":"R24","volume-title":"Algorithms","author":"Sedgewick Robert","year":"1983"},{"key":"R25","unstructured":"A. H. Sherman, Ph.D. Thesis,  On the efficient solution of sparse systems of linear and nonlinear equations, Yale University, New Haven, CT,  1975"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1145\/321879.321884"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1145\/322154.322161"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970265"}],"container-title":["SIAM Journal on Matrix Analysis and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0895479892236921","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T12:52:44Z","timestamp":1787316764000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0895479892236921"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,10]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1994,10]]}},"alternative-id":["10.1137\/S0895479892236921"],"URL":"https:\/\/doi.org\/10.1137\/s0895479892236921","relation":{},"ISSN":["0895-4798","1095-7162"],"issn-type":[{"value":"0895-4798","type":"print"},{"value":"1095-7162","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,10]]}}}