{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,20]],"date-time":"2026-09-20T22:48:56Z","timestamp":1789944536699,"version":"4.0.1"},"reference-count":32,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. and Stat. Comput."],"published-print":{"date-parts":[[1991,1]]},"abstract":"<jats:p>This paper presents a new version of the Householder algorithm with column pivoting for computing a QR factorization that identifies rank and range space of a given matrix. The standard pivoting technique is not well suited for parallel computation, since it requires synchronization at every step in order to choose the next pivot column. In contrast, a restricted pivoting scheme that restricts the choice of pivot columns and avoids this synchronization constraint is employed. Incremental condition estimation is used to assess the effect that the addition of a candidate pivot column would have on the condition number of the matrix being generated. This safeguard ensures that this local strategy selects pivot columns that make sense in the global context of the computation. The resulting algorithm is well suited for implementation on a parallel machine, in particular, a MIMD machine with distributed memory. Simulations demonstrate that the numerical behavior of the restricted pivoting strategy is comparable to the traditional global pivoting strategy. Implementation results of the QR factorization algorithm without pivoting and with local and traditional pivoting on the Intel iPSC\/1 and iPSC\/2 hypercubes show that our scheme about halves the extra time required for pivoting.<\/jats:p>","DOI":"10.1137\/0912002","type":"journal-article","created":{"date-parts":[[2005,3,1]],"date-time":"2005-03-01T03:37:13Z","timestamp":1109648233000},"page":"36-57","source":"Crossref","is-referenced-by-count":29,"title":["A Parallel QR Factorization Algorithm with Controlled Local Pivoting"],"prefix":"10.1137","volume":"12","author":[{"given":"Christian H.","family":"Bischof","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"R. Arlauskas, G.  Fox, iPSC\/2 system: a second generation hypercube, The Third Conference on Hypercube Concurrent Computers and Applications, ACM Press, New York, 1988, 38\u201342","DOI":"10.1145\/62297.62303"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"M. Berry, K. Gallivan, W. Harrod, W. Jalby, S.S. Lo, U. Meier, B. Philippe, A. Sameh, W.  H\u00e4ndler, Parallel algorithms on the Cedar system, Proc. CONPAR 86, Springer-Verlag, New York, 1986, 25\u201339","DOI":"10.1007\/3-540-16811-7_150"},{"key":"R3","first-page":"3","volume-title":"Parallel processing for scientific computing (Los Angeles, CA, 1987)","author":"Bischof C. H.","year":"1989"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1137\/0611021"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/0908009"},{"key":"R6","volume-title":"Difference Methods\u2014Solutions of Equations in Rn","author":"Bj\u00f6rck A.","year":"1989"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1007\/BF01436084"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(87)90103-0"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-12914-6"},{"key":"R10","unstructured":"T. F. Coleman, G. Li, Solving systems of nonlinear equations on a message-passing multiprocessor, Tech. Report, CS-87-887, Department of Computer Science, Cornell University, Ithaca, NY, 1987, November"},{"key":"R11","unstructured":"T. F. Coleman, P. Plassman, The solution of nonlinear least-squares problems on a message-passing multiprocessor, Tech. Report, CS-TR-88-923, Department of Computer Science, Cornell University, Ithaca, NY, 1988, June"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(86)90004-9"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611971811"},{"key":"R14","first-page":"178","volume-title":"Hypercube Multiprocessors","author":"Dunigan T. H.","year":"1987"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1137\/0909038"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(86)90115-1"},{"key":"R17","unstructured":"K. Gallivan, W. Jalby, U. Meier, A. Sameh, The impact of hierarchical memory systems on linear algebra algorithm design, Tech. Report, 625, Center for Supercomputing Research and Development, University of Illinois at Urbana-Champaign, 1987, September"},{"key":"R18","unstructured":"G. A. Geist, M. T. Heath, Parallel Cholesky factorization on a hypercube multiprocessor, Tech. Report, ORNL-6190, Engineering Physics and Mathematics Division, Oak Ridge National Laboratory, Oak Ridge, TN, 1985"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"G. H. Golub, V. Klema, G. W. Stewart, Rank degeneracy and least squares problems, Tech. Report, TR-456, Department of Computer Science, University of Maryland, 1976","DOI":"10.3386\/w0165"},{"key":"R20","volume-title":"Matrix computations","author":"Golub Gene H.","year":"1983"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1137\/0909037"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(86)90169-2"},{"key":"R23","volume-title":"Solving least squares problems","author":"Lawson Charles L.","year":"1974"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1137\/0910025"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1137\/0909032"},{"key":"R26","volume-title":"Hypercube Multiprocessors 1986","author":"Moler C.","year":"1986"},{"key":"R27","volume-title":"PRO-MATLAB User's Guide","author":"Moler C.","year":"1987"},{"key":"R28","first-page":"587","volume-title":"Hypercube multiprocessors 1987 (Knoxville, TN, 1986)","author":"Pothen Alex","year":"1987"},{"key":"R29","unstructured":"Y. Saad, M. H. Schultz, Topological properties of hypercubes, Tech. Report, YALEU\/DCS\/RR-389, Department of Computer Science, Yale University, New Haven, CT, 1985"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-6357-6_12"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1137\/0910005"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1137\/0717034"}],"container-title":["SIAM Journal on Scientific and Statistical Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0912002","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,20]],"date-time":"2026-08-20T13:02:58Z","timestamp":1787230978000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0912002"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,1]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1991,1]]}},"alternative-id":["10.1137\/0912002"],"URL":"https:\/\/doi.org\/10.1137\/0912002","relation":{},"ISSN":["0196-5204","2168-3417"],"issn-type":[{"value":"0196-5204","type":"print"},{"value":"2168-3417","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,1]]}}}