# Convergence of gmres from IterativeSolvers in minimal examples

**URL:** <https://discourse.julialang.org/t/convergence-of-gmres-from-iterativesolvers-in-minimal-examples/115852>\
**Category:** Numerics\
**Tags:** linearalgebra, iterative-solvers, linearsolve\
**Created:** [June 19, 2024, 11:14am UTC](https://discourse.julialang.org/t/convergence-of-gmres-from-iterativesolvers-in-minimal-examples/115852 "2024-06-19T11:14:49Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![Pablo\_Marchant](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pablo_marchant/32/32828_2.png) [@Pablo\_Marchant](https://discourse.julialang.org/u/Pablo_Marchant)\
**Post date:** [June 19, 2024, 11:14am UTC](https://discourse.julialang.org/t/convergence-of-gmres-from-iterativesolvers-in-minimal-examples/115852/1 "2024-06-19T11:14:50Z")

</div>

Hi all,

I’m trying to see if I can apply gmres in a domain specific problem I have, where I need to solve a system `Ax=b` where A is a non-symmetric square block tridiagonal matrix. I have not managed to get this to work, and in the process have realized that I can’t get the `gmres` function from `IterativeSolvers` to work on some simple examples either.

Below is one such example. I define a tridiagonal matrix with only ones in the diagonals, and setup a linear system with an initial guess close to the solution:

```julia
using IterativeSolvers
using LinearAlgebra
n = 100
A = Tridiagonal(ones(n-1), ones(n), ones(n-1))
x = rand(n)
b = A*x .+rand(n)/100000
res = gmres!(copy(x), A, b, restart=n, log=true, initially_zero=false, verbose=true)

```

This always takes `n` iterations to complete, which is why I set the restart to n, otherwise it does not converge. The residuals pretty much stagnate until the very last iteration.

I would have expected `gmres` to perform much better in such a simple example, but I don’t know if I’m just missing some basics about what to expect about `gmres` and iterative solvers in general.

---

<div class="post-metadata">

**Author:** ![Domenico\_Lahaye](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/domenico_lahaye/32/203728_2.png) [@Domenico\_Lahaye](https://discourse.julialang.org/u/Domenico_Lahaye)\
**Post date:** [June 19, 2024, 5:45pm UTC](https://discourse.julialang.org/t/convergence-of-gmres-from-iterativesolvers-in-minimal-examples/115852/2 "2024-06-19T17:45:49Z")

</div>

GMRES is known to require # iterations = problem size in these one-dimensional problems. See e.g. papers by A. Greenbaum. Idea is that this number of iterations is required top propagate information from left to right on the mesh, network or graph. Please use preconditioning (or deflation) to accelerate convergence.

---

<div class="post-metadata">

**Author:** ![Pablo\_Marchant](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pablo_marchant/32/32828_2.png) [@Pablo\_Marchant](https://discourse.julialang.org/u/Pablo_Marchant)\
**Post date:** [June 21, 2024, 6:51am UTC](https://discourse.julialang.org/t/convergence-of-gmres-from-iterativesolvers-in-minimal-examples/115852/3 "2024-06-21T06:51:15Z")

</div>

Thanks for the info Domenico. I’m pretty new to the concept of iterative solvers, so definitely need to study a bit more the basics. Do you know if the Greenbaum book on iterative methods is a good resource for that?

[https://epubs.siam.org/doi/10.1137/1.9781611970937](https://epubs.siam.org/doi/10.1137/1.9781611970937)

---

<div class="post-metadata">

**Author:** ![amontoison](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/amontoison/32/218741_2.png) [@amontoison](https://discourse.julialang.org/u/amontoison)\
**Post date:** [June 22, 2024, 5:03am UTC](https://discourse.julialang.org/t/convergence-of-gmres-from-iterativesolvers-in-minimal-examples/115852/4 "2024-06-22T05:03:25Z")

</div>

The book of Greenbaum is a good reference.  
I also suggest the book of.Youssef Saad:  
[https://epubs.siam.org/doi/book/10.1137/1.9780898718003](https://epubs.siam.org/doi/book/10.1137/1.9780898718003)

For your problem, you probably need a specialized preconditioner.  
However, you can try a few generic ones.

I documented preconditioners in Krylov.jl and added some examples:

> **[Preconditioners · Krylov.jl](https://jso.dev/Krylov.jl/dev/preconditioners/)**
>
> Documentation for Krylov.jl.

It could help to understand why we need them and you can easily check if it improves the convergence rate on your problem.

---

<div class="post-metadata">

**Author:** ![Domenico\_Lahaye](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/domenico_lahaye/32/203728_2.png) [@Domenico\_Lahaye](https://discourse.julialang.org/u/Domenico_Lahaye)\
**Post date:** [June 23, 2024, 9:35am UTC](https://discourse.julialang.org/t/convergence-of-gmres-from-iterativesolvers-in-minimal-examples/115852/5 "2024-06-23T09:35:54Z")

</div>

Book by Saad is indeed a good reference. See [IterMethBook\_2ndEd.pdf](https://www-users.cse.umn.edu/~saad/IterMethBook_2ndEd.pdf).

Book by Anne Greenbaum gives other perspectives. Book by Henk van der Vorst gives other angles on the same.

Out of the box incomplete ILU or Cholesky preconditioner should largely suffices to break the curse of # iterations = problem size.

Good luck.

---

<div class="post-metadata">

**Author:** ![ctkelley](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ctkelley/32/10684_2.png) [@ctkelley](https://discourse.julialang.org/u/ctkelley)\
**Post date:** [June 23, 2024, 2:13pm UTC](https://discourse.julialang.org/t/convergence-of-gmres-from-iterativesolvers-in-minimal-examples/115852/6 "2024-06-23T14:13:10Z")

</div>

You might look at chapters 1, 2, and 3 of

[https://epubs.siam.org/doi/book/10.1137/1.9781611970944](https://epubs.siam.org/doi/book/10.1137/1.9781611970944)

(Shameless plug)

---

<div class="post-metadata">

**Author:** ![Pablo\_Marchant](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pablo_marchant/32/32828_2.png) [@Pablo\_Marchant](https://discourse.julialang.org/u/Pablo_Marchant)\
**Post date:** [June 23, 2024, 2:24pm UTC](https://discourse.julialang.org/t/convergence-of-gmres-from-iterativesolvers-in-minimal-examples/115852/7 "2024-06-23T14:24:46Z")

</div>

Thanks for all the feedback!

It will take me a while to dig into all this, as I do need to study a bit more the fundamentals of these methods. So perhaps I’ll be jumping with more questions on iterative solvers in a couple of months.

---

<div class="post-metadata">

**Author:** ![John\_Gibson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/john_gibson/32/5321_2.png) [@John\_Gibson](https://discourse.julialang.org/u/John_Gibson)\
**Post date:** [June 23, 2024, 2:55pm UTC](https://discourse.julialang.org/t/convergence-of-gmres-from-iterativesolvers-in-minimal-examples/115852/8 "2024-06-23T14:55:07Z")

</div>

Try GMRES on a matrix with a few large and many small eigenvalues and observe the convergence of the residual ||Ax-b||/||b||. If you care about finding an x that solves Ax=b approximately, then that’s the measure, and for such systems that measure will converge quickly. If you care about finding an \hat{x} that is good approximation to the true solution x, then look at convergence of \| \hat{x} - x\|/\|x\|.