{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,21]],"date-time":"2026-10-21T16:16:42Z","timestamp":1792599402016,"version":"4.5.0"},"reference-count":58,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550-17-1-0190"],"award-info":[{"award-number":["FA9550-17-1-0190"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006132","name":"Office of Science","doi-asserted-by":"publisher","award":["DE-AC02-06CH11357"],"award-info":[{"award-number":["DE-AC02-06CH11357"]}],"id":[{"id":"10.13039\/100006132","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000146","name":"Division of Chemical, Bioengineering, Environmental, and Transport Systems","doi-asserted-by":"publisher","award":["1508713"],"award-info":[{"award-number":["1508713"]}],"id":[{"id":"10.13039\/100000146","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["ACI-1550593"],"award-info":[{"award-number":["ACI-1550593"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"publisher","award":["DE-SC0010518"],"award-info":[{"award-number":["DE-SC0010518"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"publisher","award":["DE-SC0009286"],"award-info":[{"award-number":["DE-SC0009286"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"publisher","award":["DE-SC0019393"],"award-info":[{"award-number":["DE-SC0019393"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"publisher","award":["DE-SC0018147"],"award-info":[{"award-number":["DE-SC0018147"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2019,1]]},"abstract":"<jats:p>We present an adaptive grid matrix-free operator approximation scheme based on a \u201cproduct-convolution\u201d interpolation of convolution operators. This scheme is appropriate for operators that are locally translation-invariant, even if these operators are high rank or full rank. Such operators arise in Schur complement methods for solving partial differential equations (PDEs), as Hessians in PDE-constrained optimization and inverse problems, as integral operators, as covariance operators, and as Dirichlet-to-Neumann maps. Constructing the approximation requires computing the impulse responses of the operator to point sources centered on nodes in an adaptively refined grid of sample points. A randomized a posteriori error estimator drives the adaptivity. Once constructed, the approximation can be efficiently applied to vectors using the fast Fourier transform. The approximation can be efficiently converted to hierarchical matrix ($H$-matrix) format, then inverted or factorized using scalable $H$-matrix arithmetic. The quality of the approximation degrades gracefully as fewer sample points are used, allowing cheap lower quality approximations to be used as preconditioners. This yields an automated method to construct preconditioners for locally translation-invariant Schur complements. We directly address issues related to boundaries and prove that our scheme eliminates boundary artifacts. We test the scheme on a spatially varying blurring kernel, on the nonlocal component of an interface Schur complement for the Poisson operator, and on the data misfit Hessian for an advection dominated advection-diffusion inverse problem. Numerical results show that the scheme outperforms existing methods.<\/jats:p>","DOI":"10.1137\/18m1189324","type":"journal-article","created":{"date-parts":[[2019,7,23]],"date-time":"2019-07-23T12:03:32Z","timestamp":1563883412000},"page":"A2296-A2328","source":"Crossref","is-referenced-by-count":11,"title":["Scalable Matrix-Free Adaptive Product-Convolution Approximation for Locally Translation-Invariant Operators"],"prefix":"10.1137","volume":"41","author":[{"given":"Nick","family":"Alger","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vishwas","family":"Rao","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aaron","family":"Myers","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tan","family":"Bui-Thanh","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Omar","family":"Ghattas","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2019,7,23]]},"reference":[{"key":"atypb1","first-page":"72","volume-title":"The Restoration of HST Images and Spectra-II","author":"Adorf H.-M.","year":"1994"},{"key":"atypb2","volume-title":"Proceedings of Supercomputing (SC2005)","author":"Ak\u00e7elik V.","year":"2005"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718133.ch16"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1137\/16M1084365"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1145\/1944345.1944349"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0207(19970228)40:4<727::AID-NME86>3.0.CO;2-N"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1981-0595040-2"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1364\/OE.14.001767"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1007\/PL00005410"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1137\/14095563X"},{"key":"atypb11","volume-title":"Appl. Comput. Harmon. Anal.","author":"Bigot J.","year":"2017"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1002\/nme.4562"},{"key":"atypb13","volume-title":"European Mathematical Society","author":"B\u00f6rm S.","year":"2010"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1007\/s00211-005-0618-1"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1137\/0720066"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/0045-7825(82)90071-8"},{"key":"atypb17","volume-title":"SC12: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, IEEE","author":"Bui-Thanh T.","year":"2012"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1137\/12089586X"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.3934\/ipi.2015.9.767"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.3934\/ipi.2015.9.749"},{"key":"atypb21","first-page":"364","volume-title":"Proc. SPIE 4116","author":"Calvetti D.","year":"2000"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144594276474"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2019.01.047"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1137\/030602678"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1137\/110825972"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1088\/0266-5611\/30\/11\/114015"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1007\/s11263-015-0817-x"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1007\/s10851-017-0714-8"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1364\/JOSAA.13.000464"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1137\/090780717"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1364\/JOSAA.22.000504"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1051\/0004-6361\/201219739"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2005.12.003"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(96)00301-1"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1007\/s006070050015"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47324-5"},{"key":"atypb37","first-page":"9","volume-title":"Lectures on Applied Mathematics: Proceedings of the Symposium Organized by the Sonderforschungsbereich 438 on the Occasion of Karl-Heinz Hoffmann's 60th Birthday","author":"Hackbusch W.","year":"1999"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1137\/090771806"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2010.5540158"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2010.2063426"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2015.04.047"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827599361047"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1016\/S0045-7825(96)01207-8"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2011.02.033"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1561\/2200000035"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-5280-1"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1137\/S106482759528507X"},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.1109\/TUFFC.2007.278"},{"key":"atypb49","volume-title":"PyAMG: Algebraic Multigrid Solvers in Python Release 4.0, https:\/\/github.com\/pyamg\/pyamg","author":"Olson L. N.","year":"2018"},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.1137\/130934805"},{"key":"atypb51","doi-asserted-by":"publisher","DOI":"10.1364\/JOSAA.21.001593"},{"key":"atypb52","doi-asserted-by":"publisher","DOI":"10.1088\/0004-637X\/743\/1\/68"},{"key":"atypb53","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827597328996"},{"key":"atypb54","doi-asserted-by":"publisher","DOI":"10.1137\/140977308"},{"key":"atypb55","doi-asserted-by":"publisher","DOI":"10.1109\/TASSP.1978.1163073"},{"key":"atypb56","doi-asserted-by":"publisher","DOI":"10.1109\/83.128039"},{"key":"atypb57","doi-asserted-by":"publisher","DOI":"10.1007\/s006070070031"},{"key":"atypb58","doi-asserted-by":"publisher","DOI":"10.1190\/geo2015-0641.1"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/18M1189324","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:17:33Z","timestamp":1787325453000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/18M1189324"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1]]},"references-count":58,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,1]]}},"alternative-id":["10.1137\/18M1189324"],"URL":"https:\/\/doi.org\/10.1137\/18m1189324","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1]]}}}