- idrs.m
Version of August 2010.
This is the bi-ortho variant of IDR(s) (with enhancements) that
is described in [4] (see below).

The most important changes with respect to version of December 2008 are:

- Preconditioner can be passed in decomposed form;
- Matrix-vector multiplication and preconditioning operations can be defined by functions;
- Residual smoothing (optional);
- Residual replacements to achieve accuracy close to machine precision (optional).

- test_idrs.tgz. A testset of 11 examples, also includes idrs.m. This manual describes idrs.m and the accompanying testset.
- example_idrs.m (needs idrs.m).

This MATLAB script defines a 3D discretised convection-diffusion-reaction problem on the unit cube. The parameters can be changed via a user interface to create a different test problem. The problem is solved with IDR(1), IDR(2), IDR(4), IDR(8), and with the built-in MATLAB routines for (full) GMRES and Bi-CGSTAB. The picture below shows the convergence of the methods for the default parameters, which specify a highly non-symmetric and indefinite problem consisting of about 60,000 equations.

- IDR(s) is described in: Peter Sonneveld and Martin B. van Gijzen, IDR(s): a family of simple and fast algorithms for solving large nonsymmetric linear systems. SIAM J. Sci. Comput. Vol. 31, No. 2, pp. 1035-1062, 2008 (copyright SIAM)
- The original IDR(s) report is: Peter Sonneveld and Martin B. van Gijzen, IDR(s): a family of simple and fast algorithms for solving large nonsymmetric linear systems. Delft University of Technology, Reports of the Department of Applied Mathematical Analysis, Report 07-07
- The relation of IDR(s) with Bi-CGSTAB, and how to derive
generalisations of Bi-CGSTAB using IDR-ideas can be found in: Gerard L.G. Sleijpen, Peter Sonneveld and
Martin B. van Gijzen, Bi-CGSTAB as an induced dimension
reduction method, Applied
Numerical Mathematics. Vol 60, pp.
- A very stable and efficient IDR(s) variant (implemented in the MATLAB code idrs.m given above) is described in: 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, Vol. 38, No. 1, pp. 5:1-5:19, 2011 (copyright ACM)
- The combination of IDR(s) with BiCGstab(ℓ) is described in: Gerard L.G. Sleijpen and Martin B. van
Gijzen, Exploiting BiCGstab(ℓ) strategies to induce dimension
reduction. SIAM J. Sci.
Comput. Vol. 32, No. 5, pp. 2687-2709, 2010 (copyright
SIAM)

- A version of IDR(s) that is tuned for parallel and grid
computing is described in: T.P. Collignon and M.B. van Gijzen, Minimizing
synchronization in IDR(
*s*). Numerical Linear Algebra with Applications, Vol. 18, No. 5, pp. 805–825, 2011 (Copyright John Wiley & Sons, Ltd.) - New!
Flexible and multi-shift IDR variants are described in: 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. Delft University of Technology, Reports of the
Department of Applied Mathematical Analysis, Report 11-06,
2011.

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

January 2010: IDR(s) (the biortho variant described in [4]) has been 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" which was part of the SIAM conference on Applied Linear Algebra LA09.

Photo of the participants (from
left to right): Kuniyoshi Abe, Martin Gutknecht, Jens-Peter Zemke,
me, Seiji Fujino, Peter Sonneveld, Man-Chung Yeung, Gerard
Sleijpen.

June 3, 2009: DCSE symposium "IDR and block Lanczos solvers for large nonsymmetric systems", with as speakers Martin Gutknecht, me, Man-Chung Yeung, Seiji Fujino, Peter Sonneveld, and Jens-Peter Zemke.

March 17, 2008: Mini symposium at the 9th IMACS conference. Participants: Peter Sonneveld, me, Gerard Sleijpen, Seiji Fujino, and Y. Onoue.

Extract from the "IMACS NEWS March 2008" (complete pdf version):

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 ﬁeld of Krylov subspace methods and of their theoretical support.

March 12, 2007: First presentation about IDR(s) (TU Delft, numerical analysis group seminar).

Peter Sonneveld and me in my office, finalising the talk |
The first slide of the presentation |

It exploits the flexibility of the code, subdomain deflation (J. Frank and C. Vuik, "On the construction of deflation-based preconditioners", SIAM J. Sci. Comp. 23 (2001) pp. 442-462) is implemented without the need to modify idrs.m.

A detailed description of the ocean circulation example can be found in:

M. B. van Gijzen, C. B.
Vreugdenhil, and H. Oksuzoglu,

The Finite Element Discretization for Stream-Function Problems on Multiply Connected Domains,

*J. Comp. Phys., *140, 1998, pp. 30-46. (copyright
Academic Press).

You are free to use this example for academic purposes. Please put a reference to the above
mentioned paper if you use the ocean test problem in a publication.The Finite Element Discretization for Stream-Function Problems on Multiply Connected Domains,

The file idrs_ocean_example.tgz contains all the matlab and data files needed to run the test problem. You can uncompress and unzip this file by entering the command tar xzf idrs_ocean_example.tgz. This creates a directory IDRS_OCEAN_EXAMPLE. In this directory you will find data-file in Matrix-Market format, and the matlab code to run the test problem.

The data files have the following names and meanings:

- stommel?.mtx: the system matrices. "?" can be either 1, 2, 3, or 4 and refers to the grid spacing in degrees.
- stommel?_b.mtx: the right-hand-side vectors. Each file contains 12 vectors, for each month one.
- stommel?_P.mtx: map from system degrees-of-freedom to earth degrees-of-freedom. Needed to make a picture of the solution.
- bathymetry.mtx: depth information. Needed to make a picture of the solution.

- ocean.m: running this program opens a gui that allows you to choose the grid and set the solver parameters. It solves the systems for the 12 right-hand-sides and gives the resulting ocean circulation patterns in the form of a movie.
- idrs.m.
- mv.m: file to perform deflated matrix-vector products.
- subdomain-deflation.m: set-up subdomain deflation vectors.
- mmread.m: Matrix-Market routine to read the data files.