{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,16]],"date-time":"2026-05-16T16:29:11Z","timestamp":1778948951012,"version":"3.51.4"},"reference-count":32,"publisher":"American Mathematical Society (AMS)","issue":"264","license":[{"start":{"date-parts":[[2009,2,25]],"date-time":"2009-02-25T00:00:00Z","timestamp":1235520000000},"content-version":"am","delay-in-days":366,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"

\n In this article we design and analyze multilevel preconditioners for linear systems arising from regularized inverse problems. Using a scale-independent distance function that measures spectral equivalence of operators, it is shown that these preconditioners approximate the inverse of the operator to optimal order with respect to the spatial discretization parameter\n \n \n \n h<\/mml:mi>\n h<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . As a consequence, the number of preconditioned conjugate gradient iterations needed for solving the system will\n decrease<\/bold>\n when increasing the number of levels, with the possibility of performing only one fine-level residual computation if\n \n \n \n h<\/mml:mi>\n h<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n is small enough. The results are based on the previously known two-level preconditioners of Rieder (1997) (see also Hanke and Vogel (1999)), and on applying Newton-like methods to the operator equation\n \n \n \n \n \n X<\/mml:mi>\n \n \n \u2212\n \n <\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n \n \u2212\n \n <\/mml:mo>\n A<\/mml:mi>\n =<\/mml:mo>\n 0<\/mml:mn>\n <\/mml:mrow>\n X^{-1} - A = 0<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . We require that the associated forward problem has certain smoothing properties; however, only natural stability and approximation properties are assumed for the discrete operators. The algorithm is applied to a reverse-time parabolic equation, that is, the problem of finding the initial value leading to a given final state. We also present some results on constructing restriction operators with preassigned approximating properties that are of independent interest.\n <\/p>","DOI":"10.1090\/s0025-5718-08-02100-5","type":"journal-article","created":{"date-parts":[[2008,7,25]],"date-time":"2008-07-25T12:55:42Z","timestamp":1216990542000},"page":"2001-2038","source":"Crossref","is-referenced-by-count":11,"title":["Optimal order multilevel preconditioners for regularized ill-posed problems"],"prefix":"10.1090","volume":"77","author":[{"given":"Andrei","family":"Dr\u0103g\u0103nescu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Todd","family":"Dupont","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2008,2,25]]},"reference":[{"key":"1","unstructured":"Volkan Ak\u00e7elik, George Biros, Andrei Dr\u0103g\u0103nescu, Omar Ghattas, Judith C. Hill, and Bart G. van Bloemen Waanders, Dynamic data driven inversion for terascale simulations: Real-time identification of airborne contaminants, Proceedings of SC2005 (Seattle, WA), IEEE\/ACM, November 2005."},{"issue":"153","key":"2","doi-asserted-by":"publisher","first-page":"35","DOI":"10.2307\/2007724","article-title":"An optimal order process for solving finite element equations","volume":"36","author":"Bank, Randolph E.","year":"1981","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"3","series-title":"Pitman Research Notes in Mathematics Series","isbn-type":"print","volume-title":"Multigrid methods","volume":"294","author":"Bramble, James H.","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/0582234352"},{"issue":"202","key":"4","doi-asserted-by":"publisher","first-page":"447","DOI":"10.2307\/2153097","article-title":"New estimates for multilevel algorithms including the \ud835\udc49-cycle","volume":"60","author":"Bramble, James H.","year":"1993","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"230","key":"5","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1090\/S0025-5718-99-01106-0","article-title":"Computational scales of Sobolev norms with application to preconditioning","volume":"69","author":"Bramble, James H.","year":"2000","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"191","key":"6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.2307\/2008789","article-title":"Parallel multilevel preconditioners","volume":"55","author":"Bramble, James H.","year":"1990","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"7","series-title":"Texts in Applied Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-3658-8","volume-title":"The mathematical theory of finite element methods","volume":"15","author":"Brenner, Susanne C.","year":"2002","ISBN":"https:\/\/id.crossref.org\/isbn\/0387954511","edition":"2"},{"key":"8","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719505","volume-title":"A multigrid tutorial","author":"Briggs, William L.","year":"2000","ISBN":"https:\/\/id.crossref.org\/isbn\/0898714621","edition":"2"},{"key":"9","volume-title":"Calcul diff\\'{e}rentiel","author":"Cartan, Henri","year":"1967"},{"key":"10","unstructured":"E. G. D\u2019Jakanov, On an iterative method for the solution of a system of finite difference equations, Dokl. Akad. Nauk. SSSR 138 (1961), 522\u2013525."},{"key":"11","unstructured":"Andrei Dr\u0103g\u0103nescu, A fast multigrid method for inverting linear parabolic problems, Tech. Report TR-2004-01, University of Chicago, Department of Computer Science, 2004, presented at the Eighth Copper Mountain Conference on Iterative Methods."},{"key":"12","unstructured":"\\bysame, Two investigations in numerical analysis: Monotonicity preserving finite element methods, and multigrid methods for inverse parabolic problems, Ph.D. thesis, University of Chicago, August 2004."},{"key":"13","unstructured":"Andrei Dr\u0103g\u0103nescu and Todd F. Dupont, A multigrid algorithm for backwards reaction-diffusion equations, in preparation."},{"key":"14","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1137\/0705058","article-title":"A factorization procedure for the solution of elliptic difference equations","volume":"5","author":"Dupont, Todd","year":"1968","journal-title":"SIAM J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0036-1429","issn-type":"print"},{"issue":"2","key":"15","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1080\/01630568108816087","article-title":"Necessary and sufficient conditions for convergence of regularization methods for solving linear operator equations of the first kind","volume":"3","author":"Engl, Heinz W.","year":"1981","journal-title":"Numer. Funct. Anal. Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/0163-0563","issn-type":"print"},{"key":"16","series-title":"Mathematics and its Applications","isbn-type":"print","doi-asserted-by":"crossref","DOI":"10.1007\/978-94-009-1740-8","volume-title":"Regularization of inverse problems","volume":"375","author":"Engl, Heinz W.","year":"1996","ISBN":"https:\/\/id.crossref.org\/isbn\/0792341570"},{"key":"17","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1137\/0702003","article-title":"The solution of elliptic difference equations by semi-explicit iterative techniques","volume":"2","author":"Gunn, James E.","year":"1965","journal-title":"J. Soc. Indust. Appl. Math. Ser. B Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0887-459X","issn-type":"print"},{"key":"18","series-title":"Universitext","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-8498-4","volume-title":"Numerical range","author":"Gustafson, Karl E.","year":"1997","ISBN":"https:\/\/id.crossref.org\/isbn\/038794835X"},{"key":"19","series-title":"Springer Series in Computational Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02427-0","volume-title":"Multigrid methods and applications","volume":"4","author":"Hackbusch, Wolfgang","year":"1985","ISBN":"https:\/\/id.crossref.org\/isbn\/3540127615"},{"issue":"3","key":"20","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/s002110050455","article-title":"Two-level preconditioners for regularized inverse problems. I. Theory","volume":"83","author":"Hanke, Martin","year":"1999","journal-title":"Numer. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0029-599X","issn-type":"print"},{"issue":"3-4","key":"21","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1080\/01630560008816965","article-title":"Regularization of exponentially ill-posed problems","volume":"21","author":"Hohage, Thorsten","year":"2000","journal-title":"Numer. Funct. Anal. Optim.","ISSN":"https:\/\/id.crossref.org\/issn\/0163-0563","issn-type":"print"},{"issue":"4","key":"22","doi-asserted-by":"publisher","first-page":"767","DOI":"10.1088\/0266-5611\/17\/4\/313","article-title":"On the regularizing properties of a full multigrid method for ill-posed problems","volume":"17","author":"Kaltenbacher, Barbara","year":"2001","journal-title":"Inverse Problems","ISSN":"https:\/\/id.crossref.org\/issn\/0266-5611","issn-type":"print"},{"issue":"244","key":"23","doi-asserted-by":"publisher","first-page":"1711","DOI":"10.1090\/S0025-5718-03-01533-3","article-title":"V-cycle convergence of some multigrid methods for ill-posed problems","volume":"72","author":"Kaltenbacher, Barbara","year":"2003","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"1","key":"24","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/s002110100375","article-title":"A multi-grid method with a priori and a posteriori level choice for the regularization of nonlinear ill-posed problems","volume":"93","author":"Kaltenbacher, Barbara","year":"2002","journal-title":"Numer. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0029-599X","issn-type":"print"},{"issue":"3","key":"25","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/BF01385512","article-title":"Multilevel algorithms for ill-posed problems","volume":"61","author":"King, J. Thomas","year":"1992","journal-title":"Numer. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0029-599X","issn-type":"print"},{"issue":"1","key":"26","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1137\/0719003","article-title":"On the smoothing property of the Galerkin method for parabolic equations","volume":"19","author":"Luskin, Mitchell","year":"1982","journal-title":"SIAM J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0036-1429","issn-type":"print"},{"issue":"2","key":"27","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1080\/00036818208839415","article-title":"On the smoothing property of the Crank-Nicolson scheme","volume":"14","author":"Luskin, Mitchell","year":"1982","journal-title":"Applicable Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0003-6811","issn-type":"print"},{"issue":"2","key":"28","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1007\/BF01390130","article-title":"Finite element solution of diffusion problems with irregular data","volume":"43","author":"Rannacher, Rolf","year":"1984","journal-title":"Numer. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0029-599X","issn-type":"print"},{"issue":"1","key":"29","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1023\/B:BITN.0000025090.68586.5e","article-title":"Regularization of discrete ill-posed problems","volume":"44","author":"Regi\u0144ska, Teresa","year":"2004","journal-title":"BIT","ISSN":"https:\/\/id.crossref.org\/issn\/0006-3835","issn-type":"print"},{"issue":"4","key":"30","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1007\/s002110050250","article-title":"A wavelet multilevel method for ill-posed problems stabilized by Tikhonov regularization","volume":"75","author":"Rieder, Andreas","year":"1997","journal-title":"Numer. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0029-599X","issn-type":"print"},{"key":"31","series-title":"Springer Series in Computational Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03359-3","volume-title":"Galerkin finite element methods for parabolic problems","volume":"25","author":"Thom\u00e9e, Vidar","year":"1997","ISBN":"https:\/\/id.crossref.org\/isbn\/3540632360"},{"key":"32","series-title":"Frontiers in Applied Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898717570","volume-title":"Computational methods for inverse problems","volume":"23","author":"Vogel, Curtis R.","year":"2002","ISBN":"https:\/\/id.crossref.org\/isbn\/0898715075"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2008-77-264\/S0025-5718-08-02100-5\/S0025-5718-08-02100-5.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2008-77-264\/S0025-5718-08-02100-5\/S0025-5718-08-02100-5.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T15:29:15Z","timestamp":1776785355000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2008-77-264\/S0025-5718-08-02100-5\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,2,25]]},"references-count":32,"journal-issue":{"issue":"264","published-print":{"date-parts":[[2008,10]]}},"alternative-id":["S0025-5718-08-02100-5"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-08-02100-5","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2008,2,25]]}}}