10

I have a linear system with matrix which eigenvalues are uniformly distributed on the unit circle like this:

enter image description here

Is it possible to solve this kind of system effectively by iterative method, maybe with some preconditioner?

faleichik
  • 1,832
  • 13
  • 23
  • 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 03 '15 at 13:43
  • 3
    Also, take a look at http://page.math.tu-berlin.de/~liesen/Publicat/LiTiGAMM.pdf – Christian Clason Jun 03 '15 at 13:44
  • 4
    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 03 '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 03 '15 at 18:45
  • @DanielShapero the paper is awesome, thank you! – faleichik Jun 03 '15 at 18:45
  • 2
    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 03 '15 at 19:55

1 Answers1

1

The matrix is very well-conditioned, hence GMRES(k) should work fine without preconditioner.

Arnold Neumaier
  • 11,318
  • 20
  • 47
  • 1
    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 05 '15 at 05:54
  • 2
    @wim: You are right; I was assuming without good reason that $A$ was normal. – Arnold Neumaier Jun 05 '15 at 09:52