Martin van Gijzen - IDR(s)

IDR(\(s\)) - State-of-the-Art Nonsymmetric Solver



The Induced Dimension Reduction method, IDR(\(s\)), is a robust and efficient short-recurrence Krylov subspace method for solving large nonsymmetric systems of linear equations.

IDR(\(s\)) compared to  BI-CGSTAB/BiCGStab(\(\ell\)): Note:
Available here:

Software


Timeline

2016: IDR(\(s\)) included in the MAGMA (Matrix Algebra on GPU and Multicore Architectures) library by the Innovative Computing Laboratory (ICL) at the University of Tennessee.

November 2011: IDR(\(s\)) included in the Collected Algorithms of the ACM as Algorithm 913.

July 8, 2010: Invited talk on IDR(\(s\)) at the ICCAM 2010 conference in Leuven, Belgium.

January 2010: IDR(\(s\)) (the biortho variant from [4], below) included in IFISS 3.0, an open source Incompressible Flow & Iterative Solver Software by Howard Elman, David Silvester and Alison Ramage.

October 27, 2009: Mini symposium Induced Dimension Reduction (IDR) Methods: a Family of Efficient Krylov Solvers, held during the SIAM conference on Applied Linear Algebra LA09.



Minisymposium participants (from left to right): Kuniyoshi Abe, Martin Gutknecht, Jens-Peter Zemke, Martin van Gijzen, Seiji Fujino, Peter Sonneveld, Man-Chung Yeung, Gerard Sleijpen.


June 3, 2009: DCSE Symposium IDR and Block Lanczos Solvers for Large Nonsymmetric Systems. Speakers: Martin Gutknecht, Martin van Gijzen, Man-Chung Yeung, Seiji Fujino, Peter Sonneveld, and Jens-Peter Zemke.

March 17, 2008: Minisymposium 1 held during the 9th IMACS conference. Speakers: Peter Sonneveld, Martin van Gijzen, Gerard Sleijpen, Seiji Fujino, and Y. Onoue.

From IMACS NEWS March 2008:
Although this 9th edition was a little bit rainy, it has been more than enlightened by the contributions of more than 90 attendants representing more than 20 countries and a.o. by a remarqued come back of the IDR method of our friends from The Netherlands, which might bring a true breakthrough in the field of Krylov subspace methods and of their theoretical support.

March 12, 2007: Introducing IDR(\(s\))! TU Delft, Numerical Analysis Group Seminar.

Preparing the presentation in Martin's office
First slide of the presentation

Publications

  1. IDR(\(s\))'s seminal article:
    Peter Sonneveld and Martin B. van Gijzen. IDR(\(s\)): A Family of Simple and Fast Algorithms for Solving Large Nonsymmetric Systems of Linear Equations. SIAM Journal on Scientific Computing, 31(2):1035-1062, 2008. © 2008 SIAM

  2. The original IDR(\(s\)) report:
    Peter Sonneveld and Martin B. van Gijzen. IDR(\(s\)): A Family of Simple and Fast Algorithms for Solving Large Nonsymmetric Linear Systems. Technical Report 07-07, Delft Institute of Applied Mathematics, Delft University of Technology, Delft, The Netherlands, 19 March 2007.

  3. The relationship between IDR(\(s\)) and Bi-CGSTAB as well as the derivation of Bi-CGSTAB generalizations using IDR ideas:
    Gerard L.G. Sleijpen, Peter Sonneveld, and Martin B. van Gijzen. Bi-CGSTAB as an Induced Dimension Reduction Method. Applied Numerical Mathematics with Applications, 60:1100-1114, 2010. © 2010 Elsevier

  4. A very stable and efficient IDR(\(s\)) variant (implemented in idrs.m):
    Martin B. van Gijzen and Peter Sonneveld. Algorithm 913: An Elegant IDR(s) Variant that Efficiently Exploits Bi-orthogonality Properties. ACM Transactions on Mathematical Software, 38(1), article 5, 19 pages, 2011. © 2011 ACM

  5. The combination of IDR(\(s\)) and BiCGstab(\(\ell\)):
    Gerard L.G. Sleijpen and Martin B. van Gijzen. Exploiting BiCGstab(\(\ell\)) Strategies to Induce Dimension Reduction. SIAM Journal on Scientific Computing, 32(5):2687-2709, 2010. © 2010 SIAM

  6. IDR(\(s\)) for parallel and grid computing:
    Tijmen P. Collignon and Martin B. van Gijzen. Minimizing Synchronization in IDR(\(s\)). Numerical Linear Algebra with Applications, 18(5):805-825, 2011. © 2011 John Wiley & Sons, Ltd.


  7. Flexible and multi-shift IDR(\(s\)) variants:
    Martin B. van Gijzen, Gerard L.G. Sleijpen, and Jens-Peter M. Zemke. Flexible and Multi-Shift Induced Dimension Reduction Algorithms for Solving Large Sparse Linear Systems. Numerical Linear Algebra with Applications, 22(1):1-25, 2015.

  8. IDR(\(s\)) for matrix equations:
    R. Astudillo and M.B. van Gijzen. Induced Dimension Reduction Method for Solving Linear Matrix Equations. Procedia Computer Science, 80:222-232, 2016.

  9. An IDR(\(s\)) algorithm for computing eigenpairs:
    Reinaldo Astudillo and Martin B. van Gijzen. A Restarted Induced Dimension Reduction Method to Approximate Eigenpairs of Large Unsymmetric Matrices. Journal of Computational and Applied Mathematics, 296:24-35, 2016.

  10. R. Astudillo and M.B. van Gijzen. Induced Dimension Reduction Method to Solve the Quadratic Eigenvalue Problem. Lecture Notes in Computer Science, 10187:203-211, 2017.

  11. R. Astudillo, J.M. de Gier, and M.B. van Gijzen. Accelerating the Induced Dimension Reduction Method Using Spectral Information. Journal of Computational and Applied Mathematics, 345:33-47, 2019.