{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:14:53Z","timestamp":1787328893823,"version":"3.56.0"},"reference-count":68,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"name":"Carver Mead New Horizons Fund"},{"name":"DOE, Office of Science, Office of Advanced Scientific Computing Research, Department of Energy Computational Science Graduate Fellowship","award":["DE-SC0021110"],"award-info":[{"award-number":["DE-SC0021110"]}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-2103317"],"award-info":[{"award-number":["DMS-2103317"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-2410045"],"award-info":[{"award-number":["DMS-2410045"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-2103317"],"award-info":[{"award-number":["DMS-2103317"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["FRG 1952777"],"award-info":[{"award-number":["FRG 1952777"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2025,6,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>A direct solver is introduced for solving overdetermined linear systems involving nonuniform discrete Fourier transform matrices. Such matrices can be transformed into a Cauchy-like form that has hierarchical low rank structure. The rank structure of this matrix is explained, and it is shown that the ranks of the relevant submatrices grow only logarithmically with the number of columns of the matrix. A fast rank-structured hierarchical approximation method based on this analysis is developed, along with a hierarchical least-squares solver for these and related systems. This result is a direct method for inverting nonuniform discrete transforms with a complexity that is usually nearly linear with respect to the degrees of freedom in the problem. This solver is benchmarked against various iterative and direct solvers in the setting of inverting the one-dimensional type-II (or forward) transform, for a range of condition numbers and problem sizes (up to [Formula: see text] by [Formula: see text]). These experiments demonstrate that this method is especially useful for large problems with multiple right-hand sides.<\/jats:p>","DOI":"10.1137\/24m1656694","type":"journal-article","created":{"date-parts":[[2025,5,6]],"date-time":"2025-05-06T03:11:16Z","timestamp":1746501076000},"page":"A1702-A1732","source":"Crossref","is-referenced-by-count":2,"title":["Superfast Direct Inversion of the Nonuniform Discrete Fourier Transform via Hierarchically Semiseparable Least Squares"],"prefix":"10.1137","volume":"47","author":[{"given":"Heather","family":"Wilber","sequence":"first","affiliation":[{"name":"Department of Applied Mathematics, University of Washington, Seattle, WA 98105 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0712-8296","authenticated-orcid":true,"given":"Ethan N.","family":"Epperly","sequence":"additional","affiliation":[{"name":"Division of Computing and Mathematical Sciences, California Institute of Technology, Pasadena, CA 91125 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alex H.","family":"Barnett","sequence":"additional","affiliation":[{"name":"Center for Computational Mathematics, Flatiron Institute, New York, NY 10010 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2025,5,6]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1137\/130943431"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1137\/16M1107760"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1023\/A:1016694031362"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-1229-5_7"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1137\/18M120885X"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2020.08.034"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479898336021"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1137\/16M1096426"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.cam.2009.08.108"},{"key":"ref10","first-page":"161","volume-title":"Exploiting Hidden Structure in Matrix Computations: Algorithms and Applications, Cetraro, Italy 2015","author":"Benzi M.","year":"2016"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2024.04.003"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718850"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479803436652"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1137\/040617200"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1137\/030602678"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1109\/78.678470"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1137\/0149053"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1137\/0914081"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1006\/acha.1995.1007"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1007\/s002110050101"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2005.853152"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1995-1312096-X"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.3934\/ammc.2023005"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1137\/S003614450343200X"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.2140\/camcos.2006.1.121"},{"key":"ref26","unstructured":"S. G\u00fcttel, Y. Nakatsukasa, M. Webb, and A. B. Riley, A Sherman\u2013Morrison\u2013Woodbury Approach to Solving Least Squares Problems with Low-Rank Updates, preprint, arXiv:2406.15120, 2024."},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47324-5"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4228-4_5"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1137\/120902677"},{"key":"ref30","unstructured":"S. Inati, J.Y. Lee, L. Fleysher, R. Fleysher, and L. Greengard, Iterative reconstruction of magnetic resonance images from non-uniform samples in k-space, manuscript."},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1137\/0732009"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1137\/1037082"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1145\/1555386.1555388"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2019.03.028"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.3389\/fams.2023.1155484"},{"key":"ref36","unstructured":"P. Koev, Matrices with Displacement Structure\u2013a Survey, (1999), https:\/\/citeseerx.ist.psu.edu\/document?repid=rep1&type=pdf&doi=78414668f0645906d6fb10da68a5ba3c9bfc84d2."},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1007\/s11075-020-00974-x"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1137\/060665075"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1007\/BF03549487"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1016\/0041-5553(77)90036-2"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479801384937"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1007\/s10958-013-1177-0"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1137\/100786617"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976045"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1016\/j.camwa.2005.03.011"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1137\/19M1288048"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718324"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0129-8"},{"key":"ref49","doi-asserted-by":"publisher","DOI":"10.1137\/0103003"},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827502400984"},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1145\/2930660"},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.1137\/17M1134822"},{"key":"ref53","doi-asserted-by":"crossref","unstructured":"Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd ed. SIAM, Philadelphia, 2003.","DOI":"10.1137\/1.9780898718003"},{"key":"ref54","doi-asserted-by":"publisher","DOI":"10.1190\/1.1444033"},{"key":"ref55","doi-asserted-by":"publisher","DOI":"10.1007\/BF02733426"},{"key":"ref56","doi-asserted-by":"publisher","DOI":"10.1086\/113252"},{"key":"ref57","unstructured":"The MathWorks, Inc., nufft: Nonuniform Fast Fourier Transform Function, MATLAB Version R2024a, https:\/\/www.mathworks.com\/help\/matlab\/ref\/double.nufft.html."},{"key":"ref58","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2018.02.025"},{"key":"ref59","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719574"},{"key":"ref60","doi-asserted-by":"publisher","DOI":"10.1007\/s10915-010-9364-3"},{"key":"ref61","unstructured":"H. D. Wilber, Computing Numerically with Rational Functions, Ph.D. thesis, Cornell University, Ithaca, NY, 2021."},{"key":"ref62","doi-asserted-by":"publisher","DOI":"10.1137\/16M1061965"},{"key":"ref63","doi-asserted-by":"publisher","DOI":"10.1137\/120895755"},{"key":"ref64","unstructured":"J. Xia, A Hierarchically Semiseparable (HSS) Package, https:\/\/www.math.purdue.edu\/\u223cxiaj\/packages.html (2010)."},{"key":"ref65","doi-asserted-by":"publisher","DOI":"10.1137\/110831982"},{"key":"ref66","doi-asserted-by":"publisher","DOI":"10.1007\/s10543-023-00965-z"},{"key":"ref67","first-page":"1","volume":"30","author":"Zolotarev E.","year":"1877","journal-title":"Zap. Imp. Akad. Nauk. St. Petersburg"},{"key":"ref68","doi-asserted-by":"publisher","DOI":"10.1190\/1.2399442"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/24M1656694","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:06:59Z","timestamp":1787324819000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/24M1656694"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,6]]},"references-count":68,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,6,30]]}},"alternative-id":["10.1137\/24M1656694"],"URL":"https:\/\/doi.org\/10.1137\/24m1656694","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,5,6]]}}}