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?

  • $\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$ Jun 3 '15 at 13:43
  • 3
    $\begingroup$ Also, take a look at page.math.tu-berlin.de/~liesen/Publicat/LiTiGAMM.pdf $\endgroup$ 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$ 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$ Jun 3 '15 at 19:55

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$ Jun 5 '15 at 9:52

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.