{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T20:45:28Z","timestamp":1777581928479,"version":"3.51.4"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2024,12,11]],"date-time":"2024-12-11T00:00:00Z","timestamp":1733875200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Science Foundation Office of Advanced Cyberinfrastructure","award":["2004541"],"award-info":[{"award-number":["2004541"]}]},{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"crossref","award":["DE-AC05-00OR22725"],"award-info":[{"award-number":["DE-AC05-00OR22725"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Air Force Artificial Intelligence Accelerator","award":["FA8750-19-2-1000"],"award-info":[{"award-number":["FA8750-19-2-1000"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2024,12,31]]},"abstract":"<jats:p>Parker and L\u00ea introduced random butterfly transforms (RBTs) as a preprocessing technique to replace pivoting in dense LU factorization. Unfortunately, their FFT-like recursive structure restricts the dimensions of the matrix. Furthermore, on multinode systems, efficient management of the communication overheads restricts the matrix\u2019s distribution even more. To remove these limitations, we have generalized the RBT to arbitrary matrix sizes by truncating the dimensions of each layer in the transform. We expanded Parker\u2019s theoretical analysis to generalized RBT, specifically that in exact arithmetic, Gaussian elimination with no pivoting will succeed with probability 1 after transforming a matrix with full-depth RBTs. Furthermore, we experimentally show that these generalized transforms improve performance over Parker\u2019s formulation by up to 62% while retaining the ability to replace pivoting. This generalized RBT is available in the SLATE numerical software library.<\/jats:p>","DOI":"10.1145\/3699714","type":"journal-article","created":{"date-parts":[[2024,10,8]],"date-time":"2024-10-08T15:38:53Z","timestamp":1728401933000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Generalizing Random Butterfly Transforms to Arbitrary Matrix Sizes"],"prefix":"10.1145","volume":"50","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9404-3121","authenticated-orcid":false,"given":"Neil","family":"Lindquist","sequence":"first","affiliation":[{"name":"The University of Tennessee, Knoxville, TN, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0089-6965","authenticated-orcid":false,"given":"Piotr","family":"Luszczek","sequence":"additional","affiliation":[{"name":"MIT Lincoln Laboratory and The University of Tennessee, Lexington, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3247-1782","authenticated-orcid":false,"given":"Jack","family":"Dongarra","sequence":"additional","affiliation":[{"name":"The University of Tennessee, Knoxville, TN, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,12,11]]},"reference":[{"key":"e_1_3_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132597"},{"key":"e_1_3_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR42600.2020.01204"},{"key":"e_1_3_2_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/23M1549079"},{"key":"e_1_3_2_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2013.12.003"},{"key":"e_1_3_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2427023.2427025"},{"key":"e_1_3_2_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-32149-3_9"},{"key":"e_1_3_2_8_1","doi-asserted-by":"publisher","DOI":"10.15439\/2015F177"},{"key":"e_1_3_2_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-27308-2_15"},{"key":"e_1_3_2_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-17353-5_12"},{"key":"e_1_3_2_11_1","first-page":"6126","volume-title":"9th International Workshop on State-of-the-Art in Scientific and Parallel Computing (PARA \u201908)","author":"Baboulin Marc","year":"2008","unstructured":"Marc Baboulin, Stanimire Tomov, and Jack Dongarra. 2008. Some Issues in Dense Linear Algebra for Multicore and Special Purpose Architectures. In 9th International Workshop on State-of-the-Art in Scientific and Parallel Computing (PARA \u201908), Vol. 6126\u20136127, 1\u201312. Springer-Verlag, Trondheim, Norway."},{"key":"e_1_3_2_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31464-3_14"},{"key":"e_1_3_2_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1122918"},{"key":"e_1_3_2_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1140819"},{"key":"e_1_3_2_15_1","first-page":"1517","volume-title":"the 36th International Conference on Machine Learning","author":"Dao Tri","year":"2019","unstructured":"Tri Dao, Albert Gu, Matthew Eichhorn, Atri Rudra, and Christopher Re. 2019. Learning Fast Algorithms for Linear Transforms Using Butterfly Factorizations. In the 36th International Conference on Machine Learning. PMLR, Long Beach, CA, 1517\u20131527."},{"key":"e_1_3_2_16_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.3306"},{"key":"e_1_3_2_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCSE.2017.48"},{"key":"e_1_3_2_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO56248.2022.00050"},{"key":"e_1_3_2_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2015.06.007"},{"key":"e_1_3_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3295500.3356223"},{"key":"e_1_3_2_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/0909042"},{"key":"e_1_3_2_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2022.102897"},{"key":"e_1_3_2_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/100788926"},{"key":"e_1_3_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/SYNASC.2016.069"},{"key":"e_1_3_2_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.1998.10030"},{"key":"e_1_3_2_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ScalAH56622.2022.00010"},{"key":"e_1_3_2_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ScalA51936.2020.00010"},{"key":"e_1_3_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3577193.3593731"},{"key":"e_1_3_2_29_1","volume-title":"A Survey of Matrix Theory and Matrix Inequalities","author":"Marcus Marvin","year":"1992","unstructured":"Marvin Marcus and Henryk Minc. 1992. A Survey of Matrix Theory and Matrix Inequalities, Vol. 14. Dover Publications, Inc, New York, NY."},{"key":"e_1_3_2_30_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492920000021"},{"key":"e_1_3_2_31_1","doi-asserted-by":"publisher","unstructured":"Riley Murray James Demmel Michael W. Mahoney N. Benjamin Erichson Maksim Melnichenko Osman Asif Malik Laura Grigori Piotr Luszczek Micha\u0142 Derezi\u0144ski Miles E. Lopes Tianyu Liang Hengrui Luo and Jack Dongarra. 2023. Randomized Numerical Linear Algebra: A Perspective on the Field with an Eye to Software. Retrieved from 10.48550\/arXiv.2302.11474","DOI":"10.48550\/arXiv.2302.11474"},{"key":"e_1_3_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536446"},{"key":"e_1_3_2_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2015.04.021"},{"key":"e_1_3_2_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2011.02.052"},{"key":"e_1_3_2_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2017.04.007"},{"key":"e_1_3_2_36_1","first-page":"20","volume-title":"Random Butterfly Transformations with Applications in Computational Linear Algebra","author":"Parker D. Stott","year":"1995","unstructured":"D. Stott Parker. 1995a. Random Butterfly Transformations with Applications in Computational Linear Algebra. Technical Report CSD-950023. Computer Science Department, UCLA, Los Angeles, CA, 20 pages."},{"key":"e_1_3_2_37_1","first-page":"20","volume-title":"A Randomizing Butterfly Transformation Useful in Block Matrix Computations","author":"Parker D. Stott","year":"1995","unstructured":"D. Stott Parker. 1995b. A Randomizing Butterfly Transformation Useful in Block Matrix Computations. Technical Report CSD-950024. Computer Science Department, UCLA, Los Angeles, CA, 20 pages."},{"key":"e_1_3_2_38_1","first-page":"14","volume-title":"How to Eliminate Pivoting from Gaussian Elimination \u2014 By Randomizing Instead","author":"Parker D. Stott","year":"1995","unstructured":"D. Stott Parker and Dinh L\u00ea. 1995. How to Eliminate Pivoting from Gaussian Elimination \u2014 By Randomizing Instead. Technical Report CSD-950022. Computer Science Department, UCLA, Los Angeles, CA, 14 pages."},{"key":"e_1_3_2_39_1","volume-title":"The Randomizing FFT: An Alternative to Pivoting in Gaussian Elimination","author":"Parker D. Stott","year":"1995","unstructured":"D. Stott Parker and Brad Pierce. 1995. The Randomizing FFT: An Alternative to Pivoting in Gaussian Elimination. Technical Report CSD-950037. University of California, Los Angeles, CA."},{"key":"e_1_3_2_40_1","volume-title":"Numerical, Spectral, and Group Properties of Random Butterfly Matrices","author":"Peca-Medlin John","year":"2021","unstructured":"John Peca-Medlin. 2021. Numerical, Spectral, and Group Properties of Random Butterfly Matrices. Ph.D. Dissertation. UC Irvine."},{"key":"e_1_3_2_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/22M148762X"},{"key":"e_1_3_2_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(86)90255-7"},{"key":"e_1_3_2_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2022.102900"},{"key":"e_1_3_2_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2009.12.005"},{"key":"e_1_3_2_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aml.2019.03.024"},{"key":"e_1_3_2_46_1","volume-title":"The Algebraic Eigenvalue Problem","author":"Wilkinson James H.","year":"1965","unstructured":"James H. Wilkinson. 1965. The Algebraic Eigenvalue Problem. Oxford University Press, London, UK."},{"key":"e_1_3_2_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2007.12.002"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3699714","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3699714","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3699714","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:09:53Z","timestamp":1750295393000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3699714"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,11]]},"references-count":46,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,12,31]]}},"alternative-id":["10.1145\/3699714"],"URL":"https:\/\/doi.org\/10.1145\/3699714","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"value":"0098-3500","type":"print"},{"value":"1557-7295","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,12,11]]},"assertion":[{"value":"2023-12-14","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-09-25","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-12-11","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}