{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T11:11:44Z","timestamp":1777547504696,"version":"3.51.4"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2013,4,1]],"date-time":"2013-04-01T00:00:00Z","timestamp":1364774400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006112","name":"Microsoft Research","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006112","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2013,4]]},"abstract":"<jats:p>This article presents a new high-performance bidiagonal reduction (BRD) for homogeneous multicore architectures. This article is an extension of the high-performance tridiagonal reduction implemented by the same authors [Luszczek et al., IPDPS 2011] to the BRD case. The BRD is the first step toward computing the singular value decomposition of a matrix, which is one of the most important algorithms in numerical linear algebra due to its broad impact in computational science. The high performance of the BRD described in this article comes from the combination of four important features: (1) tile algorithms with tile data layout, which provide an efficient data representation in main memory; (2) a two-stage reduction approach that allows to cast most of the computation during the first stage (reduction to band form) into calls to Level 3 BLAS and reduces the memory traffic during the second stage (reduction from band to bidiagonal form) by using high-performance kernels optimized for cache reuse; (3) a data dependence translation layer that maps the general algorithm with column-major data layout into the tile data layout; and (4) a dynamic runtime system that efficiently schedules the newly implemented kernels across the processing units and ensures that the data dependencies are not violated. A detailed analysis is provided to understand the critical impact of the tile size on the total execution time, which also corresponds to the matrix bandwidth size after the reduction of the first stage. The performance results show a significant improvement over currently established alternatives. The new high-performance BRD achieves up to a 30-fold speedup on a 16-core Intel Xeon machine with a 12000\u00d7 12000 matrix size against the state-of-the-art open source and commercial numerical software packages, namely LAPACK, compiled with optimized and multithreaded BLAS from MKL as well as Intel MKL version 10.2.<\/jats:p>","DOI":"10.1145\/2450153.2450154","type":"journal-article","created":{"date-parts":[[2013,5,1]],"date-time":"2013-05-01T19:47:09Z","timestamp":1367437629000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["High-performance bidiagonal reduction using tile algorithms on homogeneous multicore architectures"],"prefix":"10.1145","volume":"39","author":[{"given":"Hatem","family":"Ltaief","sequence":"first","affiliation":[{"name":"KAUST Supercomputing Laboratory, Thuwal, Saudi Arabia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Piotr","family":"Luszczek","sequence":"additional","affiliation":[{"name":"University of Tennessee, Knoxville, TN"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jack","family":"Dongarra","sequence":"additional","affiliation":[{"name":"University of Tennessee, Oak Ridge National Laboratory, and University of Manchester, Knoxville, TN"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,5,3]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Agullo E. Dongarra J. Nath R. and Tomov S. 2010. Autotuned dense QR factorization for multicore architectures. Tech. rep. RR-7526 Institut National de Recherche en Informatique et en Automatique (INRIA). arXiv:1102.5328.  Agullo E. Dongarra J. Nath R. and Tomov S. 2010. Autotuned dense QR factorization for multicore architectures. Tech. rep. RR-7526 Institut National de Recherche en Informatique et en Automatique (INRIA). arXiv:1102.5328."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1654059.1654080"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Anderson E. Bai Z. Bischof C. Blackford S. L. Demmel J. W. Dongarra J. J. Croz J. D. Greenbaum A. Hammarling S. Mckenney A. and Sorensen D. C. 1999. LAPACK User's Guide 3rd Ed SIAM Philadelphia PA.   Anderson E. Bai Z. Bischof C. Blackford S. L. Demmel J. W. Dongarra J. J. Croz J. D. Greenbaum A. Hammarling S. Mckenney A. and Sorensen D. C. 1999. LAPACK User's Guide 3rd Ed SIAM Philadelphia PA.","DOI":"10.1137\/1.9780898719604"},{"key":"e_1_2_1_4_1","unstructured":"Anderson E. and Dongarra J. J. 1990. Evaluating block algorithm variants in LAPACK. In Parallel Processing for Scientific Computing J. Dongarra et al. Eds. SIAM Philadelphia PA. 3--8.   Anderson E. and Dongarra J. J. 1990. Evaluating block algorithm variants in LAPACK. In Parallel Processing for Scientific Computing J. Dongarra et al. Eds. SIAM Philadelphia PA. 3--8."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2004.09.019"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1882792.1882839"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/365723.365736"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Blackford L. S. Choi J. Cleary A. D'azevedo E. F. Demmel J. W. Dhillon I. S. Dongarra J. J. Hammarling S. Henry G. Petitet A. Stanley K. Walker D. W. and Whaley R. C. 1997. ScaLAPACK Users' Guide. SIAM Philadelphia PA.   Blackford L. S. Choi J. Cleary A. D'azevedo E. F. Demmel J. W. Dhillon I. S. Dongarra J. J. Hammarling S. Henry G. Petitet A. Stanley K. Walker D. W. and Whaley R. C. 1997. ScaLAPACK Users' Guide. SIAM Philadelphia PA.","DOI":"10.1137\/1.9780898719642"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2011.299"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/050636723"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Buttari A. Dongarra J. Kurzak J. Langou J. Luszczek P. and \n      Tomov S\n  . \n  2006\n  . The impact of multicore on math software. In Proceedings of the 8th International Workshop on Applied Parallel Computing. State of the Art in Scientific Computing (PARA). B. K\u00e5gstr\u00f6m et al. Eds. Lecture Notes in Computer Science vol. \n  4699\n  Springer Berlin 1--10.   Buttari A. Dongarra J. Kurzak J. Langou J. Luszczek P. and Tomov S. 2006. The impact of multicore on math software. In Proceedings of the 8th International Workshop on Applied Parallel Computing. State of the Art in Scientific Computing (PARA). B. K\u00e5gstr\u00f6m et al. Eds. Lecture Notes in Computer Science vol. 4699 Springer Berlin 1--10.","DOI":"10.1007\/978-3-540-75755-9_1"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.v20:13"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2008.10.002"},{"key":"e_1_2_1_14_1","first-page":"173","article-title":"The design and implementation of the ScaLAPACK LU, QR, and Cholesky factorization routines. Sci","volume":"5","author":"Choi J.","year":"1996","journal-title":"Program."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 5th SIAM Conference on Parallel Processing for Scientific Computing. SIAM","author":"Dackland K."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the SIAM Conference on Computational Science and Engineering (CSE03)","author":"D'Azevedo E."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/0728076"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/0911052"},{"key":"e_1_2_1_19_1","volume-title":"Parallel Linear Algebra Software for Multicore Architectures, Version 2.3","author":"Dongarra J."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002110050024"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02163027"},{"key":"e_1_2_1_22_1","volume-title":"Matrix Computation","author":"Golub G. H.","edition":"3"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(99)00041-1"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479892242232"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the IFIP WG 2.5 Working Conference on Software Architectures for Scientific Computing Applications. Kluwer Academic","author":"Gustavson F. G.","year":"2000"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.1829"},{"key":"e_1_2_1_27_1","volume-title":"Computer Architecture: A Quantitative Approach","author":"Hennessy J. L.","year":"2012","edition":"5"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1037\/h0071325"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02287921"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/320941.320947"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/S089547989120195X"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10543-008-0180-1"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2009.79"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2011.91"},{"key":"e_1_2_1_35_1","unstructured":"MKL. 2011. Intel Math Kernel Library (MKL). http:\/\/www.intel.com\/software\/products\/mkl\/. Version 10.2.  MKL. 2011. Intel Math Kernel Library (MKL). http:\/\/www.intel.com\/software\/products\/mkl\/. Version 10.2."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.1981.1102568"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the IEEE International Conference on Cluster Computing. IEEE","author":"Perez J."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(01)00569-9"},{"key":"e_1_2_1_39_1","unstructured":"SMPSs Team. 2008. SMP Superscalar (SMPSs) User's Manual. Version 2.3.  SMPSs Team. 2008. SMP Superscalar (SMPSs) User's Manual. Version 2.3."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/5992.814658"},{"key":"e_1_2_1_41_1","doi-asserted-by":"crossref","unstructured":"Trefethen L. N. and Bau D. 1997. Numerical Linear Algebra. SIAM Philadelphia PA.  Trefethen L. N. and Bau D. 1997. Numerical Linear Algebra. SIAM Philadelphia PA.","DOI":"10.1137\/1.9780898719574"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065895.1065898"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2450153.2450154","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2450153.2450154","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:18:49Z","timestamp":1750234729000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2450153.2450154"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,4]]},"references-count":42,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,4]]}},"alternative-id":["10.1145\/2450153.2450154"],"URL":"https:\/\/doi.org\/10.1145\/2450153.2450154","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"value":"0098-3500","type":"print"},{"value":"1557-7295","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,4]]},"assertion":[{"value":"2011-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-05-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}