Research reports

Years: 2024 2023 2022 2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996 1995 1994 1993 1992 1991

By how much can residual minimization accelerate the convergence of orthogonal residual methods?

by M. H. Gutknecht and M. Rozloznik

(Report number 2000-09)

Abstract
We capitalize upon the known relationship between pairs of orthogonal and minimal residual methods (or, biorthogonal and quasi-minimal residual methods) in order to estimate how much smaller the residuals or quasi-residuals of the minimizing methods can be compared to the those of the corresponding Galerkin or Petrov-Galerkin method. Examples of such pairs are the conjugate gradient (CG) and the conjugate residual (CR) methods, the full orthogonalization method (FOM) and the generalized minimal residual (\GMRES) method, the CGNE and CGNR versions of applying CG to the normal equations, as well as the biconjugate gradient (\BICG) and the quasi-minimal residual (QMR) methods. Also the pairs consisting of the (bi)conjugate gradient squared (CGS) and the transpose-free QMR (TFQMR) methods can be added to this list if the residuals at half-steps are included, and further examples can be created easily. The analysis is more generally applicable to the minimal residual (MR) and quasi-minimal residual (QMR) smoothing processes, which are known to provide the transition from the results of the first method of such a pair to those of the second one. By an interpretation of these smoothing processes in coordinate space we deepen the understanding of some of the underlying relationships and introduce a unifying framework for minimal residual and quasi-minimal residual smoothing. This framework includes the general notion of QMR-type methods.

Keywords: system of linear algebraic equations, iterative method, Krylov space method, conjugate gradient method, biconjugate gradient method, CG, CGNE, CGNR, CGS, FOM, \GMRES, QMR, TFQMR, residual smoothing, MR smoothing, QMR smoothing

@Techreport{GR00_268,
  author = {M. H. Gutknecht and M. Rozloznik},
  title = {By how much can residual minimization accelerate the convergence of orthogonal residual methods?},
  institution = {Seminar for Applied Mathematics, ETH Z{\"u}rich},
  number = {2000-09},
  address = {Switzerland},
  url = {https://www.sam.math.ethz.ch/sam_reports/reports_final/reports2000/2000-09.pdf },
  year = {2000}
}

Disclaimer
© Copyright for documents on this server remains with the authors. Copies of these documents made by electronic or mechanical means including information storage and retrieval systems, may only be employed for personal use. The administrators respectfully request that authors inform them when any paper is published to avoid copyright infringement. Note that unauthorised copying of copyright material is illegal and may lead to prosecution. Neither the administrators nor the Seminar for Applied Mathematics (SAM) accept any liability in this respect. The most recent version of a SAM report may differ in formatting and style from published journal version. Do reference the published version if possible (see SAM Publications).