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

IDR explained

by M. H. Gutknecht

(Report number 2009-14)

Abstract
The Induced Dimension Reduction (IDR) method is a Krylov space method for solving linear systems that was developed by Peter Sonneveld around 1979. It was only noticed by few people, and mainly as the forerunner of Bi-CGSTAB, which was introduced a decade later. In 2007 Sonneveld and van Gijzen reconsidered IDR and generalized it to IDR(s), claiming that IDR(1) = IDR is equally fast but preferable to the closely related Bi-CGSTAB, and that IDR(s) with s>1 may be much faster than Bi-CGSTAB. It also turned out that when s >1, IDR(s) is related to ML(s)BiCGSTAB of Yeung and Chan, and that there is quite some flexibility in the IDR approach. This approach differs completely from traditional approaches to Krylov space methods, and therefore it requires an extra effort to get familiar with it and to understand the connections as well as the differences to better known Krylov space methods. This expository paper aims at providing some help in this and to make the method understandable even to non-experts. After presenting the history of IDR and related methods we summarize some of the basic facts on Krylov space methods. Then we present the original IDR(s) in detail and put it into perspective with other methods. Specifically, we analyze the differences between the IDR method published 1980, IDR(1) and Bi-CGSTAB. At the end, we discuss a recently proposed ingenious variant of IDR(s) whose residuals fulfill extra orthogonality conditions. There we dwell on details that have been left out in the publications of van Gijzen and Sonneveld.

Keywords: Krylov space method, iterative method, induced dimension reduction, IDR, CGS, Bi-CGSTAB, ML(k)BiCGSTAB, large nonsymmetric linear system

@Techreport{G09_401,
  author = {M. H. Gutknecht},
  title = {IDR explained},
  institution = {Seminar for Applied Mathematics, ETH Z{\"u}rich},
  number = {2009-14},
  address = {Switzerland},
  url = {https://www.sam.math.ethz.ch/sam_reports/reports_final/reports2009/2009-14.pdf },
  year = {2009}
}

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).