Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 

 

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 Free Access

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 $ 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 [Enhancements On Off] (What's this?)


Similar Articles

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.