What iterative method can effectively solve a linear system with this kind of spectrum

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?

• 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)? – Christian Clason Jun 3 '15 at 13:43
• Also, take a look at page.math.tu-berlin.de/~liesen/Publicat/LiTiGAMM.pdf – Christian Clason Jun 3 '15 at 13:44
• 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. – Daniel Shapero Jun 3 '15 at 14:58
• @ChristianClason in general case the matrix is not normal. It has a certain block structure and is sparse. Thank you for the reference! – faleichik Jun 3 '15 at 18:45
• 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. – Daniel Shapero Jun 3 '15 at 19:55

• 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),".");  – wim Jun 5 '15 at 5:54
• @wim: You are right; I was assuming without good reason that $A$ was normal. – Arnold Neumaier Jun 5 '15 at 9:52