{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:49:46Z","timestamp":1750308586292,"version":"3.41.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,1,2]],"date-time":"2017-01-02T00:00:00Z","timestamp":1483315200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004410","name":"Scientific and Technological Research Council of Turkey","doi-asserted-by":"crossref","award":["BIDEB-2211"],"award-info":[{"award-number":["BIDEB-2211"]}],"id":[{"id":"10.13039\/501100004410","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Turkish Academy of Sciences Distinguished Young Scientist","award":["M.M\/TUBA-GEBIP\/2012-19"],"award-info":[{"award-number":["M.M\/TUBA-GEBIP\/2012-19"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2017,12,31]]},"abstract":"<jats:p>Underdetermined systems of equations in which the minimum norm solution needs to be computed arise in many applications, such as geophysics, signal processing, and biomedical engineering. In this article, we introduce a new parallel algorithm for obtaining the minimum 2-norm solution of an underdetermined system of equations. The proposed algorithm is based on the Balance scheme, which was originally developed for the parallel solution of banded linear systems. The proposed scheme assumes a generalized banded form where the coefficient matrix has column overlapped block structure in which the blocks could be dense or sparse. In this article, we implement the more general sparse case. The blocks can be handled independently by any existing sequential or parallel QR factorization library. A smaller reduced system is formed and solved before obtaining the minimum norm solution of the original system in parallel. We experimentally compare and confirm the error bound of the proposed method against the QR factorization based techniques by using true single-precision arithmetic. We implement the proposed algorithm by using the message passing paradigm. We demonstrate numerical effectiveness as well as parallel scalability of the proposed algorithm on both shared and distributed memory architectures for solving various types of problems.<\/jats:p>","DOI":"10.1145\/3004280","type":"journal-article","created":{"date-parts":[[2017,1,3]],"date-time":"2017-01-03T13:18:41Z","timestamp":1483449521000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Parallel Minimum Norm Solution of Sparse Block Diagonal Column Overlapped Underdetermined Systems"],"prefix":"10.1145","volume":"43","author":[{"given":"F. Sukru","family":"Torun","sequence":"first","affiliation":[{"name":"Bilkent University, Ankara, Turkey"}]},{"given":"Murat","family":"Manguoglu","sequence":"additional","affiliation":[{"name":"Middle East Technical University, Ankara, Turkey"}]},{"given":"Cevdet","family":"Aykanat","sequence":"additional","affiliation":[{"name":"Bilkent University, Ankara, Turkey"}]}],"member":"320","published-online":{"date-parts":[[2017,1,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1099-1506(199607\/08)3:4%3C275::AID-NLA83%3E3.0.CO;2-7"},{"volume-title":"Proceedings of the 9th SIAM Conference on Parallel Processing for Scientific Computing. SIAM.","author":"Ashcraft Cleve","key":"e_1_2_1_2_1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611971484"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719642"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Ronald F. Boisvert Roldan Pozo Karin A. Remington Richard F. Barrett and Jack Dongarra. 1996. Matrix market: A web resource for test matrix collections. In Quality of Numerical Software. 125--137.  Ronald F. Boisvert Roldan Pozo Karin A. Remington Richard F. Barrett and Jack Dongarra. 1996. Matrix market: A web resource for test matrix collections. In Quality of Numerical Software. 125--137.","DOI":"10.1007\/978-1-5041-2940-4_9"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/0917020"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/060657704"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/110846427"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2005.849172"},{"key":"e_1_2_1_10_1","unstructured":"Timothy A. Davis. 2009. Users guide for SuiteSparseQR a multifrontal multithreaded sparse QR factorization package. http:\/\/faculty.cse.tamu.edu\/davis\/suitesparse.html.  Timothy A. Davis. 2009. Users guide for SuiteSparseQR a multifrontal multithreaded sparse QR factorization package. http:\/\/faculty.cse.tamu.edu\/davis\/suitesparse.html."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049670"},{"key":"e_1_2_1_12_1","unstructured":"Timothy A. Davis. 2013. SuiteSparse packages released 4.2.1. http:\/\/faculty.cse.tamu.edu\/davis\/suitesparse.html.  Timothy A. Davis. 2013. SuiteSparse packages released 4.2.1. http:\/\/faculty.cse.tamu.edu\/davis\/suitesparse.html."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049670"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11075-008-9218-3"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/0614001"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01583795"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02594780"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/1026001"},{"key":"e_1_2_1_19_1","unstructured":"Leibniz Supercomputing Centre GCS Supercomputer. 2012. SuperMUC Petascale System. Retrieved from www.lrz.de.  Leibniz Supercomputing Centre GCS Supercomputer. 2012. SuperMUC Petascale System. Retrieved from www.lrz.de."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(73)90047-5"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1002\/nla.241"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(96)00024-5"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/114697.116805"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718027"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0045-7949(75)90027-9"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01589349"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.procs.2013.05.222"},{"volume-title":"Metis: Unstructured Graph Partitioning and Sparse Matrix Ordering System, Version 4.0","year":"2009","author":"Karypis George","key":"e_1_2_1_30_1"},{"key":"e_1_2_1_31_1","unstructured":"Charles L. Lawson and Richard J. Hanson. 1987. Solving Least Squares Problems (Classics in Applied Mathematics). Society for Industrial Mathematics.  Charles L. Lawson and Richard J. Hanson. 1987. Solving Least Squares Problems (Classics in Applied Mathematics). Society for Industrial Mathematics."},{"key":"e_1_2_1_32_1","unstructured":"MATLAB. 2015. version 8.6.0 (R2015b). The MathWorks Inc. Natick Massachusetts.  MATLAB. 2015. version 8.6.0 (R2015b). The MathWorks Inc. Natick Massachusetts."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/10.387200"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1364\/AO.17.000660"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(97)00178-1"},{"key":"e_1_2_1_36_1","unstructured":"James Reinders. 2007. Intel Threading Building Blocks: Outfitting C++ for Multi-core Processor Parallelism. O\u2019Reilly Media Inc.  James Reinders. 2007. Intel Threading Building Blocks: Outfitting C++ for Multi-core Processor Parallelism. O\u2019Reilly Media Inc."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(01)00140-5"},{"key":"e_1_2_1_38_1","unstructured":"Michael A. Saunders. 1972. Large-scale linear programming using the cholesky factorization. (1972).  Michael A. Saunders. 1972. Large-scale linear programming using the cholesky factorization. (1972)."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511997570"},{"key":"e_1_2_1_40_1","first-page":"13","article-title":"Parallel finite element computations in fluid mechanics","volume":"195","author":"Tezduyar Tayfun E.","year":"2006","journal-title":"Computer Methods in Applied Mechanics and Engineering"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/10.142641"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0076-6895(02)80037-3"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3004280","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3004280","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:05:12Z","timestamp":1750273512000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3004280"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1,2]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,12,31]]}},"alternative-id":["10.1145\/3004280"],"URL":"https:\/\/doi.org\/10.1145\/3004280","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"type":"print","value":"0098-3500"},{"type":"electronic","value":"1557-7295"}],"subject":[],"published":{"date-parts":[[2017,1,2]]},"assertion":[{"value":"2015-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-01-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}