I have a linear system with matrix which eigenvalues are uniformly distributed on the unit circle like this:
Is it possible to solve this kind of system effectively by iterative method, maybe with some preconditioner?
$\begingroup$
$\endgroup$
-
$\begingroup$ I think MINRES will do this, although I only know of a similar results for a real spectrum. Do you know more about the matrix (in particular, is it normal)? $\endgroup$ – Christian Clason Jun 3 '15 at 13:43
-
3$\begingroup$ Also, take a look at page.math.tu-berlin.de/~liesen/Publicat/LiTiGAMM.pdf $\endgroup$ – Christian Clason Jun 3 '15 at 13:44
-
4$\begingroup$ This paper is also a good reference. In particular, applying the conjugate gradient method to the normal equations ($A^*Ax = A^*b$), while inadvisable for matrices with large condition number, might work in your case because the singular values look pretty close to 1. $\endgroup$ – Daniel Shapero Jun 3 '15 at 14:58
-
$\begingroup$ @ChristianClason in general case the matrix is not normal. It has a certain block structure and is sparse. Thank you for the reference! $\endgroup$ – faleichik Jun 3 '15 at 18:45
-
2$\begingroup$ If the matrix is highly non-normal then my suggestion of CGNE is wrong, but that paper ought to be a good start. The library PETSc has pretty much every Krylov subspace solver under the sun, so you can try them all and see which one works best. There's also a Python interface for it, which makes things much more convenient. $\endgroup$ – Daniel Shapero Jun 3 '15 at 19:55
$\begingroup$
$\endgroup$
The matrix is very well-conditioned, hence GMRES(k) should work fine without preconditioner.
-
1$\begingroup$ Although the matrix is well-conditioned, this does not necessarily imply that GMRES converges well. Octave (Matlab) example: ` n=100;A=eye(n);p=[n, 1:n-1];A=A(:,p);condition_number=cond(A),b=eye(n,1)+rand(n,1)*1e-6;[x, flag, relres, iter, resvec] = gmres (A,b);close all;semilogy(resvec);figure;plot(eig(A),"."); ` $\endgroup$ – wim Jun 5 '15 at 5:54
-
2$\begingroup$ @wim: You are right; I was assuming without good reason that $A$ was normal. $\endgroup$ – Arnold Neumaier Jun 5 '15 at 9:52
