Optimal order multilevel preconditioners for regularized ill-posed problems

Drăgănescu, Andrei; Dupont, Todd

doi:10.1090/S0025-5718-08-02100-5

Optimal order multilevel preconditioners for regularized ill-posed problems
HTML articles powered by AMS MathViewer

by Andrei Drăgănescu and Todd F. Dupont PDF

Math. Comp. 77 (2008), 2001-2038 Request permission

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 $h$. 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 $h$ 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 $X^{-1} - A = 0$. 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.

References

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.
Randolph E. Bank and Todd Dupont, An optimal order process for solving finite element equations, Math. Comp. 36 (1981), no. 153, 35–51. MR 595040, DOI 10.1090/S0025-5718-1981-0595040-2
James H. Bramble, Multigrid methods, Pitman Research Notes in Mathematics Series, vol. 294, Longman Scientific & Technical, Harlow; copublished in the United States with John Wiley & Sons, Inc., New York, 1993. MR 1247694
James H. Bramble and Joseph E. Pasciak, New estimates for multilevel algorithms including the $V$-cycle, Math. Comp. 60 (1993), no. 202, 447–471. MR 1176705, DOI 10.1090/S0025-5718-1993-1176705-9
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, DOI 10.1090/S0025-5718-99-01106-0
James H. Bramble, Joseph E. Pasciak, and Jinchao Xu, Parallel multilevel preconditioners, Math. Comp. 55 (1990), no. 191, 1–22. MR 1023042, DOI 10.1090/S0025-5718-1990-1023042-6
Susanne C. Brenner and L. Ridgway Scott, The mathematical theory of finite element methods, 2nd ed., Texts in Applied Mathematics, vol. 15, Springer-Verlag, New York, 2002. MR 1894376, DOI 10.1007/978-1-4757-3658-8
William L. Briggs, Van Emden Henson, and Steve F. McCormick, A multigrid tutorial, 2nd ed., Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2000. MR 1774296, DOI 10.1137/1.9780898719505
Henri Cartan, Calcul différentiel, Hermann, Paris, 1967 (French). MR 0223194
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.
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.
—, 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.
Andrei Drăgănescu and Todd F. Dupont, A multigrid algorithm for backwards reaction-diffusion equations, in preparation.
Todd Dupont, A factorization procedure for the solution of elliptic difference equations, SIAM J. Numer. Anal. 5 (1968), 753–782. MR 246528, DOI 10.1137/0705058
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, DOI 10.1080/01630568108816087
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 1408680
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 179962
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 1417493, DOI 10.1007/978-1-4613-8498-4
Wolfgang Hackbusch, Multigrid methods and applications, Springer Series in Computational Mathematics, vol. 4, Springer-Verlag, Berlin, 1985. MR 814495, DOI 10.1007/978-3-662-02427-0
Martin Hanke and Curtis R. Vogel, Two-level preconditioners for regularized inverse problems. I. Theory, Numer. Math. 83 (1999), no. 3, 385–402. MR 1715577, DOI 10.1007/s002110050455
Thorsten Hohage, Regularization of exponentially ill-posed problems, Numer. Funct. Anal. Optim. 21 (2000), no. 3-4, 439–464. MR 1769885, DOI 10.1080/01630560008816965
Barbara Kaltenbacher, On the regularizing properties of a full multigrid method for ill-posed problems, Inverse Problems 17 (2001), no. 4, 767–788. Special issue to celebrate Pierre Sabatier’s 65th birthday (Montpellier, 2000). MR 1861481, DOI 10.1088/0266-5611/17/4/313
Barbara Kaltenbacher, V-cycle convergence of some multigrid methods for ill-posed problems, Math. Comp. 72 (2003), no. 244, 1711–1730. MR 1986801, DOI 10.1090/S0025-5718-03-01533-3
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, DOI 10.1007/s002110100375
J. Thomas King, Multilevel algorithms for ill-posed problems, Numer. Math. 61 (1992), no. 3, 311–334. MR 1151773, DOI 10.1007/BF01385512
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 646596, DOI 10.1137/0719003
Mitchell Luskin and Rolf Rannacher, On the smoothing property of the Crank-Nicolson scheme, Applicable Anal. 14 (1982/83), no. 2, 117–135. MR 678498, DOI 10.1080/00036818208839415
Rolf Rannacher, Finite element solution of diffusion problems with irregular data, Numer. Math. 43 (1984), no. 2, 309–327. MR 736087, DOI 10.1007/BF01390130
Teresa Regińska, Regularization of discrete ill-posed problems, BIT 44 (2004), no. 1, 119–133. MR 2057365, DOI 10.1023/B:BITN.0000025090.68586.5e
Andreas Rieder, A wavelet multilevel method for ill-posed problems stabilized by Tikhonov regularization, Numer. Math. 75 (1997), no. 4, 501–522. MR 1431213, DOI 10.1007/s002110050250
Vidar Thomée, Galerkin finite element methods for parabolic problems, Springer Series in Computational Mathematics, vol. 25, Springer-Verlag, Berlin, 1997. MR 1479170, DOI 10.1007/978-3-662-03359-3
Curtis R. Vogel, Computational methods for inverse problems, Frontiers in Applied Mathematics, vol. 23, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2002. With a foreword by H. T. Banks. MR 1928831, DOI 10.1137/1.9780898717570