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:
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.
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.
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
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
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:
It could help to understand why we need them and you can easily check if it improves the convergence rate on your problem.
1 Like
Book by Saad is indeed a good reference. See 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.
1 Like
You might look at chapters 1, 2, and 3 of
https://epubs.siam.org/doi/book/10.1137/1.9781611970944
(Shameless plug)
2 Likes
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.
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\|.