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. On this page you can find reports and papers
that describe IDR(s),
MATLAB code for IDR(s),
and examples of how to use the code.
Version of August 2010.
This is the bi-ortho variant of IDR(s) (with enhancements) that
is described in  (see below).
The most important changes with respect to version of December
- 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
- 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.
Reports and papers:
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
- The original IDR(s) report is: Peter
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. 1100-1114, 2010 (copyright
- 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
- 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
5, pp. 805–825, 2011 (Copyright John Wiley & Sons,
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,
November 2011: IDR(s) has been included in the Collected Algorithms of
as Algorithm 913.
July 8, 2010: Invited talk about IDR(s) at the ICCAM 2010 conference in
January 2010: IDR(s) (the biortho variant
described in ) 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
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
June 3, 2009: DCSE symposium
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
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
An ocean circulation problem:
The example illustrates how to use
subdomain deflation in combination with idrs.m.
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
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 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:
The following matlab-files are provided:
- 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
- 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.
- 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.