{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:29:12Z","timestamp":1750220952544,"version":"3.41.0"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,8,8]],"date-time":"2019-08-08T00:00:00Z","timestamp":1565222400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Ministry of Economy and Competitiveness of Spain and ERDF","award":["TIN2016-75845-P"],"award-info":[{"award-number":["TIN2016-75845-P"]}]},{"DOI":"10.13039\/501100008530","name":"ERDF","doi-asserted-by":"crossref","award":["ED7431G\/01"],"award-info":[{"award-number":["ED7431G\/01"]}],"id":[{"id":"10.13039\/501100008530","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Government of Galicia and ERDF funds from the EU"},{"name":"Consolidation Programme of Competitive Reference Groups","award":["ED431C 2017\/04"],"award-info":[{"award-number":["ED431C 2017\/04"]}]},{"name":"Ministry of Education of Spain","award":["FPU14\/02801"],"award-info":[{"award-number":["FPU14\/02801"]}]},{"DOI":"10.13039\/501100010801","name":"Xunta de Galicia","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100010801","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2019,9,30]]},"abstract":"<jats:p>\n            Solving tridiagonal linear-equation systems is a fundamental computing kernel in a wide range of scientific and engineering applications, and its computation can be modeled with parallel algorithms. These parallel solvers are typically designed to compute problems whose data fit in a common shared-memory space where all the cores taking part in the computation have access. However, when the problem size is large, data cannot be entirely stored in the common shared-memory space, and a high number of high-latency communications are performed. One alternative is to partition the problem among different memory spaces. At this point, conventional parallel algorithms do not facilitate the partition of computation in independent tiles, since each reduction depends on equations that may be in different tiles. This article proposes an algorithm based on a tree reduction, called\n            <jats:italic>the Tree Partitioning Reduction<\/jats:italic>\n            (TPR) method, which partitions the problem into independent slices that can be partially computed in parallel within different common shared-memory spaces. The TPR method can be implemented for any parallel and distributed programming paradigm. Furthermore, in this work, TPR is efficiently implemented for CUDA GPUs to solve large size problems, providing highly competitive performance results with respect to existing packages, being, on average, 22.03\u00d7 faster than CUSPARSE.\n          <\/jats:p>","DOI":"10.1145\/3328731","type":"journal-article","created":{"date-parts":[[2019,8,8]],"date-time":"2019-08-08T12:30:31Z","timestamp":1565267431000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Tree Partitioning Reduction"],"prefix":"10.1145","volume":"45","author":[{"given":"Adri\u00e1n P.","family":"Di\u00e9guez","sequence":"first","affiliation":[{"name":"University of A Coru\u00f1a, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Margarita","family":"Amor","sequence":"additional","affiliation":[{"name":"University of A Coru\u00f1a, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ram\u00f3n","family":"Doallo","sequence":"additional","affiliation":[{"name":"University of A Coru\u00f1a, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,8,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2011.92"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1964179.1964185"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2012.03.003"},{"volume-title":"Numerical Computation with GPUs","author":"Chang Li-Wen","key":"e_1_2_1_4_1","unstructured":"Li-Wen Chang and Wen-mei Hwu. 2014. A guide for implementing tridiagonal solvers on GPUs . In Numerical Computation with GPUs , V. Kindratenko (Ed.). Springer , Berlin , 29--44. Li-Wen Chang and Wen-mei Hwu. 2014. A guide for implementing tridiagonal solvers on GPUs. In Numerical Computation with GPUs, V. Kindratenko (Ed.). Springer, Berlin, 29--44."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/HiPC.2015.17"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2017.2723879"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2011.41"},{"key":"e_1_2_1_9_1","unstructured":"R. W. Hockney and C. R. Jesshope. 1988. Parallel Computers 2: Architecture Programming and Algorithms. Taylor 8 Francis.   R. W. Hockney and C. R. Jesshope. 1988. Parallel Computers 2: Architecture Programming and Algorithms. Taylor 8 Francis."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/321250.321259"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11075-016-0251-3"},{"key":"e_1_2_1_12_1","unstructured":"D. B. Kirk and W. W. Hwu. 2012. Programming Massively Parallel Processors: A Hands-on Approach (2nd ed.). Morgan Kaufmann.   D. B. Kirk and W. W. Hwu. 2012. Programming Massively Parallel Processors: A Hands-on Approach (2nd ed.). Morgan Kaufmann."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/2388996.2389033"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10766-014-0323-8"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2015.2450718"},{"key":"e_1_2_1_16_1","unstructured":"NVIDIA-Corporation. 2012. CUDA CUSPARSE Library.  NVIDIA-Corporation. 2012. CUDA CUSPARSE Library."},{"key":"e_1_2_1_17_1","volume-title":"CUDPP: CUDA Data Parallel Primitives Library.","author":"NVIDIA-Corporation","year":"2014","unstructured":"NVIDIA-Corporation . 2014 . CUDPP: CUDA Data Parallel Primitives Library. Retrieved from http:\/\/cudpp.github.io\/. NVIDIA-Corporation. 2014. CUDPP: CUDA Data Parallel Primitives Library. Retrieved from http:\/\/cudpp.github.io\/."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/322047.322054"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/321738.321741"},{"key":"e_1_2_1_21_1","volume-title":"Elliptic problems in linear difference equations over a network. Watson Sci. Comput. Lab. Rep","author":"Thomas L. H.","year":"1949","unstructured":"L. H. Thomas . 1949. Elliptic problems in linear difference equations over a network. Watson Sci. Comput. Lab. Rep ., Columbia University ( 1949 ). L. H. Thomas. 1949. Elliptic problems in linear difference equations over a network. Watson Sci. Comput. Lab. Rep., Columbia University (1949)."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2015.03.008"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/SPDP.1991.218237"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1693453.1693472"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11227-014-1299-2"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3328731","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3328731","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:01Z","timestamp":1750204441000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3328731"}},"subtitle":["A New Parallel Partition Method for Solving Tridiagonal Systems"],"short-title":[],"issued":{"date-parts":[[2019,8,8]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,9,30]]}},"alternative-id":["10.1145\/3328731"],"URL":"https:\/\/doi.org\/10.1145\/3328731","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"type":"print","value":"0098-3500"},{"type":"electronic","value":"1557-7295"}],"subject":[],"published":{"date-parts":[[2019,8,8]]},"assertion":[{"value":"2018-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-08-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}