Introduction to the Induced Dimension Reduction Method IDR(S)
(2026) In Bachelor's Theses in Mathematical Sciences NUMK11 20261Mathematics (Faculty of Sciences)
Centre for Mathematical Sciences
- Abstract
- Finding the solution to a large, nonsymmetric system of linear equations is a challenging problem in mathematics that often requires a lot of computational power.
In this thesis, we provide a basis for understanding the Induced Dimension Reduction theorem. We introduce the IDR(s) theorem and the algorithm derived from it, which is a short recurrence method that addresses these challenges in an efficient way. This is a Krylov subspace method, which calculates the residuals in the nested subspaces of decreasing dimension. IDR(s) is an iterative method that computes the true solution in exact arithmetic in at most N+N/s matrix-vector products, where N is the size of the linear system and s is the dimension relative to N. Lastly, we show the... (More) - Finding the solution to a large, nonsymmetric system of linear equations is a challenging problem in mathematics that often requires a lot of computational power.
In this thesis, we provide a basis for understanding the Induced Dimension Reduction theorem. We introduce the IDR(s) theorem and the algorithm derived from it, which is a short recurrence method that addresses these challenges in an efficient way. This is a Krylov subspace method, which calculates the residuals in the nested subspaces of decreasing dimension. IDR(s) is an iterative method that computes the true solution in exact arithmetic in at most N+N/s matrix-vector products, where N is the size of the linear system and s is the dimension relative to N. Lastly, we show the performance of the algorithm through some numerical examples. First, we validate our implementation against the academic example of a convection-diffusion problem from the literature. Then, we apply the same principle to two randomly chosen linear systems and finally demonstrate the real-world application to a weather model simulating a Gaussian bubble. Our results illustrate the convergence behavior and efficiency of IDR(s) compared to other well-known iterative methods. (Less) - Popular Abstract
- Many modern simulation problems rely on solving a linear system of equations of the form Ax=b, where A is of size N by N. When talking about weather models or flow problems, these systems are very large, with N often greater than 100 000. Finding an exact solution for systems of this size is impossible within a reasonable timeframe, because direct computation requires more memory and computing power than today's computers have. To overcome this, iterative methods were developed that can acquire an approximate solution to the system.
The most common type of method used for such problems are Krylov subspace methods. (However, these methods are limited by the properties of the matrix A.) As shown by Faber and Manteuffel, it is impossible... (More) - Many modern simulation problems rely on solving a linear system of equations of the form Ax=b, where A is of size N by N. When talking about weather models or flow problems, these systems are very large, with N often greater than 100 000. Finding an exact solution for systems of this size is impossible within a reasonable timeframe, because direct computation requires more memory and computing power than today's computers have. To overcome this, iterative methods were developed that can acquire an approximate solution to the system.
The most common type of method used for such problems are Krylov subspace methods. (However, these methods are limited by the properties of the matrix A.) As shown by Faber and Manteuffel, it is impossible to create a method that works for a general A, which is both memory efficient and optimal. Here, memory efficient means that the method uses short recurrences, storing only the most recent iterations rather than all of them. Optimal means that it finds the best possible mathematical approximation to the solution at every step. This limitation forces a compromise, which is why different approaches have been developed. Most of these are generalizations of the conjugate gradient method. The most prevalent being GMRES, which aims to minimize the distance to the solution. However, in the process, it needs to store large amounts of information, which leads to more computations and memory needs. An alternative is the Bi-CG method, which does not require that much memory but is more computationally expensive.
This leads us to the goal of finding a method, which is reliable and also efficient, additionally it works for nonsymmetric systems of equations. The induced dimension reduction method, or IDR(s), is based on an algorithm created by Sonneveld in 1980 and it is memory efficient, because it uses short recurrences just as Bi-CG, but also reliable, because it is able to compute the exact solution in at most 2N steps.
IDR(s) works based on the idea that in order to find the solution, we do not need to save all the information about where we have searched for it, but we can create a "map", in which we systematically search certain areas and "forget" about them if the solution is not in that specific area. In other words, we are forcing each area that we search in, to shrink into a smaller dimension at each step.
In this thesis, we will explain the IDR(s) theorem and algorithm and present some examples of how it can be applied, whilst discussing the efficiency of the method. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/student-papers/record/9243453
- author
- Bosáková, Orsolya LU
- supervisor
- organization
- course
- NUMK11 20261
- year
- 2026
- type
- M2 - Bachelor Degree
- subject
- keywords
- Iterative method, Krylov subspace method, IDR, Large linear systems
- publication/series
- Bachelor's Theses in Mathematical Sciences
- report number
- LUNFNA-4070-2026
- ISSN
- 1654-6229
- other publication id
- 2026:K10
- language
- English
- id
- 9243453
- date added to LUP
- 2026-09-14 16:32:10
- date last changed
- 2026-09-14 16:32:10
@misc{9243453,
abstract = {{Finding the solution to a large, nonsymmetric system of linear equations is a challenging problem in mathematics that often requires a lot of computational power.
In this thesis, we provide a basis for understanding the Induced Dimension Reduction theorem. We introduce the IDR(s) theorem and the algorithm derived from it, which is a short recurrence method that addresses these challenges in an efficient way. This is a Krylov subspace method, which calculates the residuals in the nested subspaces of decreasing dimension. IDR(s) is an iterative method that computes the true solution in exact arithmetic in at most N+N/s matrix-vector products, where N is the size of the linear system and s is the dimension relative to N. Lastly, we show the performance of the algorithm through some numerical examples. First, we validate our implementation against the academic example of a convection-diffusion problem from the literature. Then, we apply the same principle to two randomly chosen linear systems and finally demonstrate the real-world application to a weather model simulating a Gaussian bubble. Our results illustrate the convergence behavior and efficiency of IDR(s) compared to other well-known iterative methods.}},
author = {{Bosáková, Orsolya}},
issn = {{1654-6229}},
language = {{eng}},
note = {{Student Paper}},
series = {{Bachelor's Theses in Mathematical Sciences}},
title = {{Introduction to the Induced Dimension Reduction Method IDR(S)}},
year = {{2026}},
}