{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:29:22Z","timestamp":1787336962998,"version":"build-2736575974"},"reference-count":53,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","funder":[{"DOI":"10.13039\/501100001824","name":"Grantov\u00e2 Agentura Cesk\u00e9 Republiky","doi-asserted-by":"publisher","award":["17-04150J"],"award-info":[{"award-number":["17-04150J"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/M025179\/1"],"award-info":[{"award-number":["EP\/M025179\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2017,1]]},"abstract":"<jats:p>The efficient solution of large linear least-squares problems in which the system matrix $A$ contains rows with very different densities is challenging. Previous work has focused on direct methods for problems in which $A$ has a few relatively dense rows. These rows are initially ignored, a factorization of the sparse part is computed using a sparse direct solver, and then the solution is updated to take account of the omitted dense rows. In some practical applications the number of dense rows can be significant, and for very large problems, using a direct solver may not be feasible. We propose processing rows that are identified as dense separately within a conjugate gradient method using an incomplete factorization preconditioner combined with the factorization of a dense matrix of size equal to the number of dense rows. Numerical experiments on large-scale problems from real applications are used to illustrate the effectiveness of our approach. The results demonstrate that we can efficiently solve problems that could not be solved by a preconditioned conjugate gradient method without exploiting the dense rows.<\/jats:p>","DOI":"10.1137\/16m1108339","type":"journal-article","created":{"date-parts":[[2017,11,7]],"date-time":"2017-11-07T11:58:57Z","timestamp":1510055937000},"page":"A2422-A2437","source":"Crossref","is-referenced-by-count":13,"title":["Solving Mixed Sparse-Dense Linear Least-Squares Problems by Preconditioned Iterative Methods"],"prefix":"10.1137","volume":"39","author":[{"given":"Jennifer","family":"Scott","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Miroslav","family":"T\u016fma","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2017,11,7]]},"reference":[{"key":"atypb1","unstructured":"M. Adlers,\n                      Topics in Sparse Least Squares Problems\n                      , Technical Report, Department of Mathematics, Link\u00f6ping University, Link\u00f6ping, Sweden, 2000."},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1099-1506(200003)7:2<51::AID-NLA187>3.0.CO;2-O"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1007\/BF02510237"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1145\/232826.232937"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-842X.1976.tb00966.x"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/63.2.391"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1137\/070698725"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1137\/0905029"},{"key":"atypb9","volume-title":"Numerical Methods for Least Squares Problems","year":"1996"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(80)90158-5"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1137\/S089547989631202X"},{"key":"atypb12","first-page":"1","volume":"38","author":"Davis T. A.","year":"2011","journal-title":"ACM Trans. Math. Software"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-4106-9"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2004.12.008"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0545-6"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1137\/10079687X"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611971248"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(80)90159-7"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1137\/0905068"},{"key":"atypb20","unstructured":"A. George and E. Ng,\n                      SPARSPAK: Waterloo Sparse Matrix Package User's Guide for SPARSPAK-B\n                      , Research Report CS-84-37, Department of Computer Science, University of Waterloo, Waterloo, ON, Canada, 1984."},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1137\/0906028"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1137\/0908072"},{"key":"atypb23","doi-asserted-by":"crossref","unstructured":"P. E. Gill, W. Murray, D. B. Ponceleon, and M. A. Saunders,\n                      Solving Reduced KKT Systems in Barrier Methods for Linear and Quadratic Programming\n                      , Technical Report SOL 91-7, Department of Operations Research, Stanford University, Stanford, CA, 1991.","DOI":"10.21236\/ADA239191"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-003-0377-7"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-014-9687-3"},{"key":"atypb26","unstructured":"N. I. M. Gould and J. A. Scott,\n                      The State-of-the-Art of Preconditioners for Sparse Linear Least Squares Problems: The Complete Results\n                      , Technical Report RAL-TR-2015-009, Rutherford Appleton Laboratory, Didcot, Oxfordshire, England, 2015."},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1145\/3014057"},{"key":"atypb28","unstructured":"J. F. Grcar,\n                      Matrix Stretching for Linear Equations\n                      , Technical Report SAND90-8723, Sandia National Laboratories, Albuquerque, NM, 1990."},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177730946"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1137\/1031049"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1137\/0903014"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.6028\/jres.049.044"},{"key":"atypb33","unstructured":"HSL,\n                      A Collection of Fortran Codes for Large-Scale Scientific Computation\n                      ,http:\/\/www.hsl.rl.ac.uk, 2016."},{"key":"atypb34","unstructured":"T.M. Hwang, W.W. Lin, and D. Pierce,\n                      A Robust Method for Handling Dense Rows in a Sparse QR or RRQR Factorization\n                      , Technical Report ISSTECH-96-021, Boeing Information and Support Services, Plano, TX, 1996."},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1115\/1.3662552"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1137\/0802022"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1137\/0912062"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2004.08.019"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1137\/0712047"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1145\/355984.355989"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/13.3.309"},{"key":"atypb42","first-page":"92","volume-title":"Linear and Nonlinear Conjugate Gradient-Related Methods","author":"Saunders M. A.","year":"1996"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1007\/BF02042943"},{"key":"atypb44","volume-title":"Fundamentals of Adaptive Filtering","author":"Sayed A. H.","year":"2003"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1137\/130917582"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1145\/2617555"},{"key":"atypb47","unstructured":"J. A. Scott and M. T\u016fma,\n                      A Schur Complement Approach to Preconditioning Sparse Linear Least-Squares Problems with Some Dense Rows\n                      , Technical Report RAL-TR-2017-P-004, Rutherford Appleton Laboratory, Didcot, Oxfordshire, England, 2017."},{"key":"atypb48","unstructured":"C. Sun,\n                      Dealing with Dense Rows in the Solution of Sparse Linear Least Squares Problems\n                      , Research Report CTC95TR227, Advanced Computing Research Institute, Cornell Theory Center, Cornell University, Ithaca, NY, 1995."},{"key":"atypb49","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(97)00064-1"},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(91)90269-3"},{"key":"atypb51","volume-title":"The Stability of Out-Input Matrices","author":"Woodbury M. A.","year":"1949"},{"key":"atypb52","volume-title":"Inverting Modified Matrices","author":"Woodbury M. A.","year":"1950"},{"key":"atypb53","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492900002300"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/16M1108339","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:38:25Z","timestamp":1787333905000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16M1108339"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1]]},"references-count":53,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2017,1]]}},"alternative-id":["10.1137\/16M1108339"],"URL":"https:\/\/doi.org\/10.1137\/16m1108339","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,1]]}}}