{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:31:27Z","timestamp":1787319087026,"version":"build-2736575974"},"reference-count":12,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Matrix Anal. Appl."],"published-print":{"date-parts":[[1993,7]]},"abstract":"<jats:p>Given only the zero\u2013nonzero pattern of an $m \\times n$ matrix A of full column rank, which entries of Q and which entries of R in its $QR$ factorization must be zero, and which entries may be nonzero? A complete answer to this question is given, which involves an interesting interplay between combinatorial structure and the algebra implicit in orthogonality. To this end some new sparse structural concepts are introduced, and an algorithm to determine the structure of Q is given. The structure of R then follows immediately from that of Q and A. The computable zero\/nonzero structures for the matrices Q and R are proven to be tight, and the conditions on the pattern for A are the weakest possible (namely, that it allows matrices A with full column rank). This complements existing work that focussed upon R and then only under an additional combinatorial assumption (the strong Hall property).<\/jats:p>","DOI":"10.1137\/0614046","type":"journal-article","created":{"date-parts":[[2005,2,27]],"date-time":"2005-02-27T07:14:21Z","timestamp":1109488461000},"page":"655-669","source":"Crossref","is-referenced-by-count":13,"title":["Sparsity Analysis of the $QR$ Factorization"],"prefix":"10.1137","volume":"14","author":[{"given":"Donovan R.","family":"Hare","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Charles R.","family":"Johnson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"D. D.","family":"Olesky","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"P.","family":"van den Driessche","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,17]]},"reference":[{"key":"RCEG","doi-asserted-by":"publisher","DOI":"10.1145\/5925.5932"},{"key":"RD","doi-asserted-by":"publisher","DOI":"10.1145\/355958.355963"},{"key":"RGE","unstructured":"W. M. Gentleman,  G. A. Watson,  Row elimination for solving sparse linear systems and least squares problems,  Proc.1975 Dundee Conference on Numerical Analysis, Lecture Notes in Math., Vol. 506, Springer-Verlag, New York,  1976,  122\u2013133 0334.65032"},{"key":"RGH","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(80)90159-7"},{"key":"RGLN","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(84)90022-3"},{"key":"RGN","doi-asserted-by":"publisher","DOI":"10.1137\/0908072"},{"key":"RGI","unstructured":"J. R. Gilbert,  An Efficient Parallel Sparse Partial Pivoting Algorithm, Report, 88\/45052-1, Chr. Michelsen Institute Department of Science and Technology, Bergen, Norway,  1988"},{"key":"RGI","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511810817"},{"key":"RJOD","doi-asserted-by":"publisher","DOI":"10.1137\/0610007"},{"key":"RLP","volume-title":"Matching theory","author":"Lov\u00e1sz L.","year":"1986"},{"key":"RRND","volume-title":"Combinatorial algorithms: theory and practice","author":"Reingold Edward M.","year":"1977"},{"key":"RS","doi-asserted-by":"publisher","DOI":"10.1137\/0714030"}],"container-title":["SIAM Journal on Matrix Analysis and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0614046","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T12:45:05Z","timestamp":1787316305000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0614046"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,7]]},"references-count":12,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1993,7]]}},"alternative-id":["10.1137\/0614046"],"URL":"https:\/\/doi.org\/10.1137\/0614046","relation":{},"ISSN":["0895-4798","1095-7162"],"issn-type":[{"value":"0895-4798","type":"print"},{"value":"1095-7162","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,7]]}}}