Algorithm 913: An elegant IDR( s ) variant that efficiently exploits biorthogonality properties

• Published in: ACM transactions on mathematical software 2011-11, Vol.38 (1), p.1-19
• Main Authors: Van Gijzen, Martin B., Sonneveld, Peter
• Format: Article
• Language: English
• Subjects: Algorithms
• ISSN: 0098-3500; 1557-7295
• DOI: 10.1145/2049662.2049667

The IDR( s ) method that is proposed in Sonneveld and van Gijzen [2008] is a very efficient limited memory method for solving large nonsymmetric systems of linear equations. IDR( s ) is based on the induced dimension reduction theorem, that provides a way to construct subsequent residuals that lie in a sequence of shrinking subspaces. The IDR( s ) algorithm that is given in Sonneveld and van Gijzen [2008] is a direct translation of the theorem into an algorithm. This translation is not unique. This article derives a new IDR( s ) variant, that imposes (one-sided) biorthogonalization conditions on the iteration vectors. The resulting method has lower overhead in vector operations than the original IDR( s ) algorithms. In exact arithmetic, both algorithms give the same residual at every ( s + 1)-st step, but the intermediate residuals and also the numerical properties differ. We show through numerical experiments that the new variant is more stable and more accurate than the original IDR( s ) algorithm, and that it outperforms other state-of-the-art techniques for realistic test problems.