Optimal order multilevel preconditioners for regularized ill-posed problems

Authors:
Andrei Draganescu and Todd F. Dupont

Journal:
Math. Comp. **77** (2008), 2001-2038

MSC (2000):
Primary 65M32, 65M55; Secondary 65M60

DOI:
https://doi.org/10.1090/S0025-5718-08-02100-5

Published electronically:
February 25, 2008

MathSciNet review:
2429872

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: 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 . As a consequence, the number of preconditioned conjugate gradient iterations needed for solving the system will **decrease** when increasing the number of levels, with the possibility of performing only one fine-level residual computation if 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 . 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.

**1.**Volkan Akçelik, George Biros, Andrei Drăgănescu, 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.**2.**Randolph E. Bank and Todd Dupont,*An optimal order process for solving finite element equations*, Math. Comp.**36**(1981), no. 153, 35-51. MR**82b:65113****3.**James H. Bramble,*Multigrid methods*, Pitman Research Notes in Mathematics Series, vol. 294, Longman Scientific & Technical, Harlow, 1993. MR**1247694 (95b:65002)****4.**James H. Bramble and Joseph E. Pasciak,*New estimates for multilevel algorithms including the -cycle*, Math. Comp.**60**(1993), no. 202, 447-471. MR**1176705 (94a:65064)****5.**James H. Bramble, Joseph E. Pasciak, and Panayot S. Vassilevski,*Computational scales of Sobolev norms with application to preconditioning*, Math. Comp.**69**(2000), no. 230, 463-480. MR**1651742 (2000k:65088)****6.**James H. Bramble, Joseph E. Pasciak, and Jinchao Xu,*Parallel multilevel preconditioners*, Math. Comp.**55**(1990), no. 191, 1-22. MR**1023042 (90k:65170)****7.**Susanne C. Brenner and L. Ridgway Scott,*The mathematical theory of finite element methods*, second ed., Texts in Applied Mathematics, vol. 15, Springer-Verlag, New York, 2002. MR**2003a:65103****8.**William L. Briggs, Van Emden Henson, and Steve F. McCormick,*A multigrid tutorial*, second ed., Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2000. MR**2001h:65002****9.**Henri Cartan,*Calcul différentiel*, Hermann, Paris, 1967. MR**36:6243****10.**E. G. D'Jakanov,*On an iterative method for the solution of a system of finite difference equations*, Dokl. Akad. Nauk. SSSR**138**(1961), 522-525.**11.**Andrei Drăgănescu,*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.**12.**-,*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.**13.**Andrei Drăgănescu and Todd F. Dupont,*A multigrid algorithm for backwards reaction-diffusion equations*, in preparation.**14.**Todd Dupont,*A factorization procedure for the solution of elliptic difference equations*, SIAM J. Numer. Anal.**5**(1968), 753-782. MR**0246528 (39:7832)****15.**Heinz W. Engl,*Necessary and sufficient conditions for convergence of regularization methods for solving linear operator equations of the first kind*, Numer. Funct. Anal. Optim.**3**(1981), no. 2, 201-222. MR**627122 (82j:47018)****16.**Heinz W. Engl, Martin Hanke, and Andreas Neubauer,*Regularization of inverse problems*, Mathematics and its Applications, vol. 375, Kluwer Academic Publishers Group, Dordrecht, 1996. MR**97k:65145****17.**James E. Gunn,*The solution of elliptic difference equations by semi-explicit iterative techniques*, J. Soc. Indust. Appl. Math. Ser. B Numer. Anal.**2**(1965), 24-45. MR**0179962 (31:4199)****18.**Karl E. Gustafson and Duggirala K. M. Rao,*Numerical range*, Universitext, Springer-Verlag, New York, 1997, The field of values of linear operators and matrices. MR**98b:47008****19.**Wolfgang Hackbusch,*Multigrid methods and applications*, Springer Series in Computational Mathematics, vol. 4, Springer-Verlag, Berlin, 1985. MR**814495 (87e:65082)****20.**Martin Hanke and Curtis R. Vogel,*Two-level preconditioners for regularized inverse problems. I. Theory*, Numer. Math.**83**(1999), no. 3, 385-402. MR**2001h:65069****21.**Thorsten Hohage,*Regularization of exponentially ill-posed problems*, Numer. Funct. Anal. Optim.**21**(2000), no. 3-4, 439-464. MR**1769885 (2001e:65095)****22.**Barbara Kaltenbacher,*On the regularizing properties of a full multigrid method for ill-posed problems*, Inverse Problems**17**(2001), no. 4, 767-788. MR**1861481 (2002h:65094)****23.**-,*V-cycle convergence of some multigrid methods for ill-posed problems*, Math. Comp.**72**(2003), no. 244, 1711-1730 (electronic). MR**1986801 (2004d:65069)****24.**Barbara Kaltenbacher and Josef Schicho,*A multi-grid method with a priori and a posteriori level choice for the regularization of nonlinear ill-posed problems*, Numer. Math.**93**(2002), no. 1, 77-107. MR**1938323 (2003h:65076)****25.**J. Thomas King,*Multilevel algorithms for ill-posed problems*, Numer. Math.**61**(1992), no. 3, 311-334. MR**1151773 (92k:65090)****26.**Mitchell Luskin and Rolf Rannacher,*On the smoothing property of the Galerkin method for parabolic equations*, SIAM J. Numer. Anal.**19**(1982), no. 1, 93-113. MR**83c:65245****27.**-,*On the smoothing property of the Crank-Nicolson scheme*, Applicable Anal.**14**(1982/83), no. 2, 117-135. MR**83m:65072****28.**Rolf Rannacher,*Finite element solution of diffusion problems with irregular data*, Numer. Math.**43**(1984), no. 2, 309-327. MR**85c:65145****29.**Teresa Regińska,*Regularization of discrete ill-posed problems*, BIT**44**(2004), no. 1, 119-133. MR**2057365 (2005h:65092)****30.**Andreas Rieder,*A wavelet multilevel method for ill-posed problems stabilized by Tikhonov regularization*, Numer. Math.**75**(1997), no. 4, 501-522. MR**97k:65299****31.**Vidar Thomée,*Galerkin finite element methods for parabolic problems*, Springer Series in Computational Mathematics, vol. 25, Springer-Verlag, Berlin, 1997. MR**98m:65007****32.**Curtis R. Vogel,*Computational methods for inverse problems*, Frontiers in Applied Mathematics, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2002. MR**2003i:65004**

Retrieve articles in *Mathematics of Computation*
with MSC (2000):
65M32,
65M55,
65M60

Retrieve articles in all journals with MSC (2000): 65M32, 65M55, 65M60

Additional Information

**Andrei Draganescu**

Affiliation:
Sandia National Laboratories, Albuquerque, New Mexico 87125

Address at time of publication:
Department of Mathematics and Statistics, University of Maryland, Baltimore County, Baltimore, Maryland 21250

Email:
draga@math.umbc.edu

**Todd F. Dupont**

Affiliation:
Department of Computer Science, University of Chicago, Chicago, Illinois 60637

Email:
t-dupont@uchicago.edu

DOI:
https://doi.org/10.1090/S0025-5718-08-02100-5

Keywords:
Multilevel methods,
inverse problems,
parabolic equations

Received by editor(s):
July 5, 2006

Received by editor(s) in revised form:
September 12, 2007

Published electronically:
February 25, 2008

Additional Notes:
The work of the authors was supported by the ASCI Flash Center at the University of Chicago under DOE contract B532820, and by the MRSEC Program of the National Science Foundation under award DMR-0213745.

Article copyright:
© Copyright 2008
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication.