{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:20:08Z","timestamp":1787322008585,"version":"build-2736575974"},"reference-count":18,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Matrix Anal. Appl."],"published-print":{"date-parts":[[1996,4]]},"abstract":"<jats:p>In $QR$ factorization of an $m \\times n$ matrix $A\\, ( m \\geq n )$, the orthogonal factor Q is often stored implicitly as an $m \\times n$ lower trapezoidal matrix W, known as the Householder matrix. When the sparsity of A is to be exploited, the factorization is often preceded by a symbolic factorization step, which computes a data structure in which the nonzero entries of W and R are computed and stored. This is achieved by computing an upper bound on the nonzero structure of these factors, based solely on the nonzero structure of A. In this paper we use a well-known upper bound on the nonzero structure of W to obtain an upper bound on the nonzero structure of Q.<\/jats:p>\n                  <jats:p>Let U be the matrix consisting of the first n columns of Q. One interesting feature of the new bound is that the bound on W\u2019s structure is identical to the lower trapezoidal part of the bound on U\u2019s structure. We show that if A is strong Hall and has no zero entry on its main diagonal, then the bounds on the nonzero structures of W and U are the smallest possible based solely on the nonzero structure of A. We then use this result to obtain corresponding smallest upper bounds in the case where A is weak Hall, is in block upper triangular form, and has no zero entry on its main diagonal. Finally, we show that one can always reorder a weak Hall matrix into block upper triangular form so that there is no increase in the fill incurred by the $QR$ factorization.<\/jats:p>","DOI":"10.1137\/s0895479892230973","type":"journal-article","created":{"date-parts":[[2005,2,27]],"date-time":"2005-02-27T07:15:07Z","timestamp":1109488507000},"page":"443-459","source":"Crossref","is-referenced-by-count":5,"title":["Some Results on Structure Prediction in Sparse $QR$ Factorization"],"prefix":"10.1137","volume":"17","author":[{"given":"Esmond G.","family":"Ng","sequence":"first","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":[[2012,2,17]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1145\/5925.5932"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611971811"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1145\/355958.355968"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1145\/355958.355963"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1145\/355780.355790"},{"key":"R6","unstructured":"A. George, F. Gustavson,  A new proof on permuting to block triangular form, Tech. report, RC 8238, IBM T. J. Watson Research Center, Yorktown Heights, NY,  1980"},{"key":"R7","volume-title":"Computer solution of large sparse positive definite systems","author":"George Alan","year":"1981"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/0909008"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1137\/0908072"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(97)80024-9"},{"key":"R11","volume-title":"Matrix computations","author":"Golub G.","year":"1983"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-10.37.26"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/0614046"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1145\/6497.6499"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1137\/0611010"},{"key":"R16","volume-title":"Matching theory","author":"Lovasz L.","year":"1986"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(93)90121-4"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1145\/98267.98287"}],"container-title":["SIAM Journal on Matrix Analysis and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0895479892230973","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:17:04Z","timestamp":1787318224000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0895479892230973"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,4]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1996,4]]}},"alternative-id":["10.1137\/S0895479892230973"],"URL":"https:\/\/doi.org\/10.1137\/s0895479892230973","relation":{},"ISSN":["0895-4798","1095-7162"],"issn-type":[{"value":"0895-4798","type":"print"},{"value":"1095-7162","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,4]]}}}