2
$\begingroup$

Recently, I have been studied my lessons about gmres iteration, probably the most popular iteration method for general large sparse linear system of equations Ax=b. And the convergence is obtained under the condition of which the matrix A is diagonalizable, but in real applications, this is seldom the case where such a good diagonalizable matrix A. So, is there any other convergence results for GMRES iteration? or in other words, when we choose a preconditioner M for solving $$M^{-1}Ax=M^{-1}b,$$ which aspects should we consider to guarantee the better convergence for this preconditioned GMRES? Because $M^{-1}A$ can not be diagonalizable in general case, is it enough to cluster the spectral distributions of the $M^{-1}A$? What aspects of the preconditioned matrix $M^{-1}A$ should we discuss?

A strange example is as follows: $$ A=\left(\begin{array}{cccccc}{1} & {c_{1}} & {} & {} & {} & {} \\ {0} & {1} & {c_{2}} & {} & {} & {} \\ {} & {} & {\ddots} & {\ddots} & {} & {} \\ {} & {} & {} & {1} & {c_{n-2}} & {} \\ {} & {} & {} & {} & {1} & {c_{n-1}} \\ {} & {} & {} & {} & {} & {1}\end{array}\right)\in\mathbb{R}^{n\times n},$$ with $c_i\neq 0$, we set $b=A*[1, 1,...,1]^T$ to solve this system $Ax=b$ using matlab command gmres. And we compare this result with matlab A\b, but gmres fails (my CPU memory is 8GB), A\b instead succeed. I just cannot understand why this happened, because we often say that for large sparse matrix, direct method can be beaten by iterative method. Can you give me some suggestions about gmres convergence and some explanations about the above example Ax=b, because all the eigenvalues of matrix A is unit, theoretically, gmres will converges very fast. Thanks very much.

Below is my simple test matlab code

%   just a simple test
clc;clear;
rng(0)% fix the random number
n=1e+5;
c = rand(n,1);% c_i
A = spdiags([ones(n,1)  c],[0 1],n,n);
b = A*ones(n,1);
%   mdirect method
A\b;
%   iterative method
x=gmres(A,b,[],[],n);

$\endgroup$
  • 1
    $\begingroup$ Well for the direct method the LU factorisation of this matrix is fairly easy to work out ... Maybe MATLAB can detect this and take advantage to reduce the problem to at worst O(N**2) - and better if it can take advantage of the sparsity in the triangular matrix. Basically his is an extremely easy matrix for classical direct methods, an O(N) solution method is extremely easy to write. $\endgroup$ – Ian Bush Nov 4 at 8:52
  • $\begingroup$ Thanks Professor. When we use a preconditioner, in general, if we can cluster the eigenvalues then, a better convergence can be obtained, right? It seems that in general case, only eigenvalues can be discussed about a preconditioner for $M^{-1}A$. Thanks professor. $\endgroup$ – Zhen-Wei Sun Nov 4 at 9:19
  • $\begingroup$ Firstly I am a mere Doctor. Secondly iterative methods are not my area at all, so I'll leave the GMRES side to somebody who really knows what they are saying. $\endgroup$ – Ian Bush Nov 4 at 9:52
6
$\begingroup$

Unfortunately, convergence of GMRES does not have a clear dependence on the distribution of eigenvalues.

It was proved by Greenbaum, Ptak and Strakos in 1996 that you can construct examples with an arbitrary spectrum and an arbitrary convergence history: that is, give me any $n$ nonzero complex numbers, and any decreasing sequence $\|r_k\|$, and I can construct a matrix $A$ with that spectrum and a vector $b$ so that gmres(A, b) achieves those residual norms at each step. Essentially everything you heard about the relationship between spectrum and GMRES convergence can fail spectacularly.

Some more references here http://www.cs.cas.cz/duintjertebbens/Talks/Liblice12.pdf .

$\endgroup$
  • 2
    $\begingroup$ I think it's worth pointing out that if a matrix is normal then GMRES does have a clear dependence on the distribution of its eigenvalues. Furthermore, mild departure from normality is often still acceptable for understanding GMRES behavior based on eigenvalues - but ultimately it will fail. $\endgroup$ – Reid.Atcheson Nov 4 at 21:50
  • $\begingroup$ @Reid.Atcheson True, good point. $\endgroup$ – Federico Poloni Nov 4 at 22:06
5
$\begingroup$

Estimates for GMRES convergence based on eigenvalue distribution often implicitly assume that the matrix is normal. Sometimes the convergence rate is still provable in an asymptotic sense in the non-normal case, but if the matrix is severely non-normal then the "pre-asymptotic" behavior will make such convergence rates never reachable in practice.

Your matrix is not normal, and its non-normality gets worse as the size grows.

$\endgroup$
2
$\begingroup$

Well, I can only propose a potential cause for why GMRES method fails for the problem you showed. I don't have enough reputation so I can't comment.

Since GMRES is using Anorldi Process to generate a set of orthogonal vectors in the Krylov subspace, if the matrix itself is very large, that means the Q and H matrix produced could be very large. So if you are solving a very large problem, you need to use the limited-GMRES (or limited-memory GMRES, can't recall the name exactly). But the key point is that the solver will reset the orthogonal matrix and restart the entire process to handle the memory limitation. This is probably the reason why your GMRES failed. Check if there is a limited option in the MatLab command.

A\b works straight away since this is a very sparse and bi-diagonal system, which is simply perfect for backward elimination.

Hope this helps. Cheers!

$\endgroup$
  • $\begingroup$ Thanks Mr Sen, you mean the restarted GMRES, which is used to handle the memory problem. many thanks. $\endgroup$ – Zhen-Wei Sun Nov 8 at 0:45
  • $\begingroup$ @Zhen-WeiSun, sorry for the wrong terminology. That is the one I was referring too. Hope that would help. $\endgroup$ – Sen Nov 8 at 2:02
  • $\begingroup$ That's ok, I get it. hope to communicate with you often ;-). $\endgroup$ – Zhen-Wei Sun Nov 8 at 2:22
  • $\begingroup$ No problem. Cheers🍺 $\endgroup$ – Sen Nov 8 at 5:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.