{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,21]],"date-time":"2026-09-21T13:45:53Z","timestamp":1789998353232,"version":"4.0.1"},"reference-count":35,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["HR0011-12-2-0016"],"award-info":[{"award-number":["HR0011-12-2-0016"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006132","name":"Office of Science","doi-asserted-by":"publisher","award":["DE-SC0008700"],"award-info":[{"award-number":["DE-SC0008700"]}],"id":[{"id":"10.13039\/100006132","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006132","name":"Office of Science","doi-asserted-by":"publisher","award":["DE-SC0010200"],"award-info":[{"award-number":["DE-SC0010200"]}],"id":[{"id":"10.13039\/100006132","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006132","name":"Office of Science","doi-asserted-by":"publisher","award":["AC02-05CH11231"],"award-info":[{"award-number":["AC02-05CH11231"]}],"id":[{"id":"10.13039\/100006132","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010661","name":"Horizon 2020 Framework Programme","doi-asserted-by":"publisher","award":["671633"],"award-info":[{"award-number":["671633"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>In this paper we present an algorithm for computing a low rank approximation of a sparse matrix based on a truncated LU factorization with column and row permutations. We present various approaches for determining the column and row permutations that show a trade-off between speed versus deterministic\/probabilistic accuracy. We show that if the permutations are chosen by using tournament pivoting based on QR factorization, then the obtained truncated LU factorization with column\/row tournament pivoting, LU_CRTP, satisfies bounds on the singular values which have similarities with the ones obtained by a communication avoiding rank revealing QR factorization. Experiments on challenging matrices show that LU_CRTP provides a good low rank approximation of the input matrix and it is less expensive than the rank revealing QR factorization in terms of computational and memory usage costs, while also minimizing the communication cost. We also compare the computational complexity of our algorithm with randomized algorithms and show that for sparse matrices and high enough but still modest accuracies, our approach is faster.<\/jats:p>","DOI":"10.1137\/16m1074527","type":"journal-article","created":{"date-parts":[[2018,3,15]],"date-time":"2018-03-15T16:07:51Z","timestamp":1521130071000},"page":"C181-C209","source":"Crossref","is-referenced-by-count":19,"title":["Low Rank Approximation of a Sparse Matrix Based on LU Factorization with Column and Row Tournament Pivoting"],"prefix":"10.1137","volume":"40","author":[{"given":"Laura","family":"Grigori","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sebastien","family":"Cayrols","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"James W.","family":"Demmel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,3,15]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719604"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/090769156"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1137\/0912002"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1007\/BF01436084"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479891223781"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488620"},{"key":"atypb7","volume-title":"Theory","author":"Cullum J. K.","year":"2002"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049670"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1145\/1024074.1024079"},{"key":"atypb10","first-page":"1","volume":"38","author":"Davis T. A.","year":"2011","journal-title":"ACM Trans. Math. Software"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1137\/13092157X"},{"key":"atypb12","volume-title":"Technical report","author":"Demmel J.","year":"2018"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1137\/080731992"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1002\/nla.1680020208"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1137\/0710032"},{"key":"atypb17","volume-title":"Computer Solution of Large Sparse Positive Definite Systems","author":"George A.","year":"1981"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1137\/0909008"},{"key":"atypb19","first-page":"262","author":"Gilbert J. R.","year":"1997","journal-title":"Linear Algebra Appl."},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1007\/BF01436075"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.56021\/9781421407944"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(96)00301-1"},{"key":"atypb23","volume-title":"Technical report 8910","author":"Grigori L.","year":"2016"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1137\/100788926"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1137\/0917055"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1137\/090771806"},{"key":"atypb28","first-page":"213","volume":"58","author":"Hong Y. P.","year":"1992","journal-title":"Math. Comp."},{"key":"atypb29","unstructured":"G. Karypis and V. Kumar,\n                      A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes and Computing Fill-Reducing Orderings of Sparse Matrices-Version\n                      4.0,http:\/\/glaros.dtc.umn.edu\/gkhome\/views\/metis, 1998."},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1137\/120863691"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1137\/0136016"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1561\/2200000035"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(02)00572-4"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(00)00120-8"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970739"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1007\/s002110050451"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827597319519"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/16M1074527","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:43:31Z","timestamp":1787334211000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16M1074527"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":35,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/16M1074527"],"URL":"https:\/\/doi.org\/10.1137\/16m1074527","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}