{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:28:13Z","timestamp":1787336893051,"version":"build-2736575974"},"reference-count":42,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>We are interested in parallelizing the least angle regression (LARS) algorithm for fitting linear regression models to high-dimensional data. We consider two parallel and communication avoiding versions of the basic LARS algorithm. The two algorithms have different asymptotic costs and practical performance. One offers more speedup and the other produces more accurate output. The first is bLARS, a block version of the LARS algorithm, where we update $b$ columns at each iteration. Assuming that the data are row-partitioned, bLARS reduces the number of arithmetic operations, latency, and bandwidth by a factor of $b$. The second is tournament-bLARS (T-bLARS), a tournament version of LARS where processors compete by running several LARS computations in parallel to choose $b$ new columns to be added in the solution. Assuming that the data are column-partitioned, T-bLARS reduces latency by a factor of $b$. Similarly to LARS, our proposed methods generate a sequence of linear models. We present extensive numerical experiments that illustrate speedups up to 4x compared to LARS without any compromise in solution quality.<\/jats:p>","DOI":"10.1137\/19m1305720","type":"journal-article","created":{"date-parts":[[2021,3,15]],"date-time":"2021-03-15T11:38:38Z","timestamp":1615808318000},"page":"C154-C176","source":"Crossref","is-referenced-by-count":1,"title":["Parallel and Communication Avoiding Least Angle Regression"],"prefix":"10.1137","volume":"43","author":[{"given":"Swapnil","family":"Das","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"James","family":"Demmel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kimon","family":"Fountoulakis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Laura","family":"Grigori","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael W.","family":"Mahoney","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shenghao","family":"Yang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,3,15]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1997.1346"},{"key":"atypb2","unstructured":"G. Ballard,\n                      Avoiding Communication in Dense Linear Algebra\n                      , Ph.D. thesis, EECS Department, University of California, Berkeley, CA, 2013."},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492914000038"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.862083"},{"key":"atypb5","unstructured":"L. Cannon,\n                      A Cellular Computer to Implement the Kalman Filter Algorithm\n                      , Ph.D. thesis, Montana State University, Bozeman, MT, 1969."},{"key":"atypb6","unstructured":"E. Carson,\n                      Communication-Avoiding Krylov Subspace Methods in Theory and Practice\n                      , Ph.D. thesis, EECS Department, University of California, Berkeley, CA, 2015."},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1145\/1961189.1961199"},{"key":"atypb8","unstructured":"A. T. Chronopoulos,\n                      A Class of Parallel Iterative Methods Implemented on Multiprocessors\n                      , Ph.D. thesis, Department of Computer Science, University of Illinois, Urbana, IL, 1986."},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(89)90062-8"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/0377-0427(89)90045-9"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(96)00022-1"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1145\/155332.155333"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/j.advwatres.2011.04.013"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1137\/080731992"},{"key":"atypb15","unstructured":"J. Demmel, M. Hoemmen, M. Mohiyuddin, and K. Yelick,\n                      Avoiding Communication in Computing Krylov Subspaces\n                      , Technical Report UCB\/EECS-2007-123, EECS Department, University of California, Berkeley, CA, 2007."},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2018.00051"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1214\/009053604000000067"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1137\/130949993"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1214\/07-EJS004"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-21606-5"},{"key":"atypb21","unstructured":"M. Hoemmen,\n                      Communication-avoiding Krylov Subspace Methods\n                      , Ph.D. thesis, University of California, Berkeley, CA, 2010."},{"key":"atypb22","first-page":"3068","volume-title":"Proceedings of the 27th International Conference on Neural Information Processing Systems, NIPS'14, MIT Press","author":"Jaggi M.","year":"2014"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1016\/0377-0427(92)90085-C"},{"key":"atypb24","unstructured":"M. Mohiyuddin,\n                      Tuning Hardware and Software for Multiprocessors\n                      , Ph.D. thesis, EECS Department, University of California, Berkeley, CA, 2012."},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1145\/1654059.1654096"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-#"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1109\/ITA.2017.8023462"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1137\/100802001"},{"key":"atypb29","volume-title":"Proceedings of the Twenty-first International Conference on Machine Learning","author":"Ng A. Y.","year":"2004"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2003.1214317"},{"key":"atypb31","volume-title":"Morgan Kaufman","author":"Patterson D. A.","year":"2013"},{"key":"atypb32","volume-title":"Parallel Programming in C with MPI and OpenMP","author":"Quinn M. J.","year":"2004"},{"key":"atypb33","first-page":"693","volume-title":"Proceedings of the 24th International Conference on Neural Information Processing Systems","author":"Recht B.","year":"2011"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-012-0614-z"},{"key":"atypb35","first-page":"1","volume-title":"Proceedings of the International Conference on High Performance Computing for Computational Science - VECPAR 2010","author":"Shalf J.","year":"2010"},{"key":"atypb36","unstructured":"E. Solomonik,\n                      Provably Efficient Algorithms for Numerical Tensor Algebra\n                      , Ph.D. thesis, EECS Department, University of California, Berkeley, CA, 2014."},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1177\/1094342005051521"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1996.tb02080.x"},{"key":"atypb39","first-page":"44","volume-title":"Proceedings of the International Conference on Parallel Processing, ICPP'83","author":"Rosendale J. Van","year":"1983"},{"key":"atypb40","volume-title":"Applied Linear Regression","author":"Weisberg S.","year":"1980"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2014.119"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0892-3"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/19M1305720","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:35:22Z","timestamp":1787333722000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/19M1305720"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":42,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/19M1305720"],"URL":"https:\/\/doi.org\/10.1137\/19m1305720","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}