{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,8]],"date-time":"2026-10-08T17:23:40Z","timestamp":1791480220984,"version":"4.3.4"},"reference-count":35,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","funder":[{"name":"DOE ASCR","award":["DE-SC0023171"],"award-info":[{"award-number":["DE-SC0023171"]}]},{"name":"DOE ASCR","award":["DE-SC0021239"],"award-info":[{"award-number":["DE-SC0021239"]}]},{"name":"DOD MURI","award":["FA9550-21-1-0084"],"award-info":[{"award-number":["FA9550-21-1-0084"]}]},{"name":"Texas Advanced Computing Center (TACC) at UT Austin"},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DGE 2137420"],"award-info":[{"award-number":["DGE 2137420"]}],"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,10,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>We present an efficient and scalable algorithm for performing matrix-vector multiplications (matvecs) for block Toeplitz matrices. Such matrices, which are shift-invariant with respect to their blocks, arise in the context of solving inverse problems governed by autonomous systems, and time-invariant systems in particular. In this article, we consider inverse problems that infer unknown parameters from observational data of a linear time-invariant dynamical system given in the form of partial differential equations (PDEs). Matrix-free Newton-conjugate-gradient methods are often the gold standard for solving these inverse problems, but they require numerous actions of the Hessian on a vector. Matrix-free adjoint-based Hessian matvecs require solution of a pair of linearized forward\/adjoint PDE solves per Hessian action, which may be prohibitive for large-scale inverse problems. Time invariance of the forward PDE problem leads to a block Toeplitz structure of the discretized parameter-to-observable (p2o) map defining the mapping from inputs (parameters) to outputs (observables) of the PDEs. This block Toeplitz structure enables us to exploit two key properties: (1) compact storage of the p2o map and its adjoint, and (2) efficient fast Fourier transform\u2013based Hessian matvecs. The proposed algorithm is mapped onto large multi-GPU clusters and achieves more than 80% of peak bandwidth on NVIDIA A100 GPUs. Excellent weak scaling is shown for up to 48 A100 GPUs. For the targeted problems, the implementation executes Hessian matvecs within fractions of a second, which is orders of magnitude faster than can be achieved by conventional matrix-free Hessian matvecs via forward\/adjoint PDE solves.<\/jats:p>\n                  <jats:p>Reproducibility of computational results. This paper has been awarded the \u201cSIAM Reproducibility Badge: Code and data available\u201d as a recognition that the authors have followed reproducibility principles valued by SISC and the scientific computing community. Code and data that allow readers to reproduce the results in this paper are available at https:\/\/github.com\/s769\/FFTMatvec and in the supplementary materials ( FFTMatvec-main.zip [1.05MB]). [Formula: see text]<\/jats:p>","DOI":"10.1137\/24m1683172","type":"journal-article","created":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T07:25:03Z","timestamp":1759994703000},"page":"B1201-B1226","source":"Crossref","is-referenced-by-count":3,"title":["Fast and Scalable FFT-Based GPU-Accelerated Algorithms for Block-Triangular Toeplitz Matrices with Application to Linear Inverse Problems Governed by Autonomous Dynamical Systems"],"prefix":"10.1137","volume":"47","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8622-1063","authenticated-orcid":true,"given":"Sreeram","family":"Venkat","sequence":"first","affiliation":[{"name":"Oden Institute, The University of Texas at Austin, Austin, TX 78712 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5502-9367","authenticated-orcid":true,"given":"Milinda","family":"Fernando","sequence":"additional","affiliation":[{"name":"Oden Institute, The University of Texas at Austin, Austin, TX 78712 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2177-8519","authenticated-orcid":true,"given":"Stefan","family":"Henneking","sequence":"additional","affiliation":[{"name":"Oden Institute, The University of Texas at Austin, Austin, TX 78712 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7742-2509","authenticated-orcid":true,"given":"Omar","family":"Ghattas","sequence":"additional","affiliation":[{"name":"Oden Institute, The University of Texas at Austin, Austin, TX 78712 USA."},{"name":"Walker Department of Mechanical Engineering, The University of Texas at Austin, Austin, TX 78712 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2025,10,9]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1137\/23M1584745"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1137\/18M1189324"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1137\/16M1084365"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1137\/19M1270367"},{"key":"ref5","volume-title":"Estimation Techniques for Distributed Parameter Systems","author":"Banks H. T.","year":"2012"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1002\/mop.1348"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-32875-6"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2011.03.006"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-009-1740-8"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(95)00649-4"},{"key":"ref11","volume-title":"Linear Time-Invariant Dynamical Systems","author":"Gavin H. P.","year":"2018"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492921000064"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1561\/0100000006"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1016\/j.aml.2019.05.013"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2012.95"},{"key":"ref16","doi-asserted-by":"crossref","unstructured":"S. Henneking, S. Venkat, V. Dobrev, J. Camier, T. Kolev, M. Fernando, A.A. Gabriel, and O. Ghattas, Real-time Bayesian inference at extreme scale: A digital twin for tsunami early warning applied to the Cascadia subduction zone, in Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, to appear, 2025, https:\/\/doi.org\/10.48550\/arXiv.2504.16344.","DOI":"10.1145\/3712285.3771787"},{"key":"ref17","doi-asserted-by":"crossref","unstructured":"S. Henneking, S. Venkat, and O. Ghattas, Goal-Oriented Real-Time Bayesian Inference for Linear Autonomous Dynamical Systems with Application to Digital Twins for Tsunami Early Warning, preprint, 2025, https:\/\/doi.org\/10.48550\/arXiv.2501.14911.","DOI":"10.1016\/j.jcp.2026.114682"},{"key":"ref18","series-title":"Appl. Math. Sci. 127","volume-title":"Inverse Problems for Partial Differential Equations","author":"Isakov V.","year":"2006"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1007\/s10766-015-0366-5"},{"key":"ref20","series-title":"Appl. Math. Sci. 160","volume-title":"Statistical and Computational Inverse Problems","author":"Kaipio J.","year":"2006"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1137\/110844830"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-8474-6"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1090\/surv\/176"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1016\/0885-064X(86)90007-5"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1007\/s10596-015-9472-0"},{"key":"ref26","first-page":"261","author":"Luo Y.","year":"2021","journal-title":"Proceedings of the 13th International Conference on Communication Software and Networks"},{"key":"ref27","doi-asserted-by":"crossref","unstructured":"R. Nammour, Approximate Multi-parameter Inverse Scattering Using Pseudodifferential Scaling, Ph.D. thesis, Rice University, 2011, https:\/\/hdl.handle.net\/1911\/102180.","DOI":"10.1190\/1.3627757"},{"key":"ref28","unstructured":"S. D. Relton, P. Valero-Lara, and M. Zounon, A Comparison of Potential Interfaces for Batched BLAS Computations, Technical report, Manchester Institute for Mathematical Sciences, University of Manchester, 2016."},{"key":"ref29","volume":"18","author":"Ruetsch G.","year":"2009","journal-title":"NVIDIA CUDA SDK, Application Note"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492910000061"},{"key":"ref31","volume-title":"SIAM","author":"Tarantola A.","year":"2005"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1145\/3428447"},{"key":"ref33","volume-title":"SIAM","author":"Vogel C. R.","year":"2002"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1109\/TASSP.1983.1164208"},{"key":"ref35","first-page":"1929","volume":"3","author":"Yagle A. E.","year":"2001","journal-title":"Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/24M1683172","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:48:06Z","timestamp":1787330886000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/24M1683172"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,9]]},"references-count":35,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,10,31]]}},"alternative-id":["10.1137\/24M1683172"],"URL":"https:\/\/doi.org\/10.1137\/24m1683172","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,9]]}}}